C++::基于minimax算法设计的三子棋游戏

基础的c语言三子棋相信很多人都做过了,碰巧今年电赛有个三子棋,就试试这个算法

三子棋的规则很简单：在一个3x3的格子板上，两名玩家轮流放置自己的棋子（通常是X和O）。第一个玩家成功在横向、纵向或对角线上连成一条由自己棋子组成的线（即三子连线）即为胜者。如果所有格子都被填满而没有人连成三子线，则游戏平局

而游戏的对弈模型是基本的零和博弈模型,minimax算法就是为了零和博弈而生的.

Minimax算法是一种用于零和博弈的决策算法，主要用于找到最佳策略。它通过递归地模拟所有可能的游戏状态来确定每个玩家的最佳行动。算法的核心是：

1. 最大化：当前玩家（最大化者）试图使得其最终收益最大化,在这里指电脑.
2. 最小化：对手（最小化者）试图使得当前玩家的收益最小化,在这里指玩家.

在每一步，算法评估所有可能的后续状态，选择能够在最终回合中达到最佳结果的行动。

一、游戏逻辑设计

1、头文件定义(board.h)

首先定义一个对象用于存储棋盘和调用方法。

#include <iostream>
#include <string>

using namespace std;


#define _computer_  'O'     //电脑棋子
#define _player_    'X'     //玩家棋子
#define _continue_  'C'     //继续游戏
#define _pease_    'P'      //平局
#define _empty_    ' '      //空棋子
#define ROW 3               //棋盘水平长度
#define COL 3               //棋盘垂直长度


//棋盘对象
class Board
{
    //定义棋盘为 ROW X COL 大小
    char board[ROW][COL];

    public:

    //初始化棋盘
    void InitBoard();

    //玩家移动
    bool Player_move(int x,int y);

    //打印棋盘
    void displayBoard();
    
    //电脑移动
    void Computer_move();

    //判断棋盘是否已经满了
    bool is_full();

    //minimax评分函数
    int evaluate();
    
    //minimax算法逻辑
    int minimax(int depth,bool is_maxing);

    //判断胜利方
    char is_win();
};

//菜单
void menu();

*ps:为什么要把所有函数放在一个对象内，因为对象内可以直接调用board属性，省去传参

2、游戏逻辑设计(board.cpp)

（1）菜单、棋盘初始化、棋盘打印

//菜单
void menu()
{
    cout<<"***************************"<<endl;
    cout<<"***************************"<<endl;
    cout<<"******* 三子棋小游戏 *******"<<endl;
    cout<<"*******   1.play   *******"<<endl;
    cout<<"*******   0.exit   *******"<<endl;
    cout<<"***************************"<<endl;
    cout<<"***************************"<<endl;
}

//初始化棋盘
void Board::InitBoard()
{
    //遍历每个格子,将其置为 _empty_
    for(int i=0;i<ROW;i++)
    {
        for(int j=0;j<COL;j++)
        {
            this->board[i][j] = _empty_;
        }
    }
}


//打印棋盘
void Board::displayBoard() 
{
    //为了好看,加了点框
    string top = "┌";       //顶部三框
    string mid = "├";       //中间三框
    string bottom = "└";    //底部三框

    //添加中间隔层
    for(int i = 0; i < COL - 1; ++i) {
        top += "────┬";
        mid += "────┼";

        bottom += "────┴";
    }
    
    //尾部修缮
    top += "────┐";
    mid += "────┤";
    bottom += "────┘";
    cout << top << '\n';

    //遍历
    for(int i = 0; i < ROW; ++i) {
        if(i > 0)
            cout << mid << '\n';

        //每行的第一个隔层
        cout << "│  ";
        for(int j = 0; j < COL; ++j) {
            //将board中的数据插入隔层前
            cout << this->board[i][j] << " │  ";
        }
        //删除多余空格
        cout << "\b\b\b│\n"; 
    }
    //打印底下隔层
    cout << bottom << '\n';

}

（2）玩家下棋

//玩家下棋          获取外部输入的x,y下标
bool Board::Player_move(int  x,int y)
{
    //判断当前选定的棋盘位置是否为 _empty_
    if(board[x][y] == _empty_)
    {
        //如果是空的将 _player_ 置换 board 对应位置的 _empty_
        board[x][y] = _player_;
        //下棋成功标签
        return true;    
    }
    else
    {
        cout<<"当前位置已有棋子,请重新选择"<<endl;
        system("pause");
        //下棋失败标签
        return false;
    }

}

（3）电脑下棋

重要的来了，minimax算法的评分函数是判断当前棋盘的状态，给定评断分数，是minimax的结束条件

evaluate评分函数实现

//评分函数
int Board::evaluate()
 {

    //判断每行、每列状态
    for(int i=0;i< ROW;i++)
    {
        if(board[i][0] == board[i][1] && board[i][1]== board[i][2] && board[i][0] != _empty_)
            {
                return (board[i][0] == _computer_)? 1 : -1;
            }
        if(board[0][i] == board[1][i] && board[1][i] == board[2][i] && board[0][i] != _empty_)
            {
                return (board[0][i] == _computer_)? 1 : -1;
            }
    }
    //判断斜线
    if(board[0][0] == board[1][1] && board[1][1] == board[2][2] && board[0][0] != _empty_)
            return (board[0][0] == _computer_)? 1 : -1;
    if(board[2][0] == board[1][1] && board[1][1] == board[0][2] && board[2][0]!= _empty_)
            return (board[2][0] == _computer_)? 1 : -1;
    //没有胜利条件
    return 0;
 }

注意，因为是作为在三子棋递归中的结束条件，所以只需要判断每行、每列、斜线是否连成一条线

，如果连成一条线的是MAX者的棋子，则返回的是 1 ，反之返回 -1，如果没有连成线，则返回 0 

Minimax算法实现

int Board::minimax(int depth,bool is_maxing)
{
    //评估棋盘状态 接收一个返回值(-1,1,0) 表示游戏结果
    int score = evaluate();

    //若结果为 1 或 -1 表示游戏结束 ,则退出递归
    if(score == 1 || score == -1)
        return score;
    //若判断棋盘为满的, 表示游戏平局,退出递归
    if(is_full())
        return 0;
    
    //如果当前是电脑回合,则最大化玩家
    if(is_maxing)
    {
        //设置 最佳值 初始化为最小值
        double best_score = INT_MIN;
        //遍历棋盘上每一个为 _empty_ 的位置
        for(int i=0;i<ROW;i++)
        {
            for(int j=0;j<COL;j++)
            {
                //若当前棋盘位置为 _empty_
                if(board[i][j] == _empty_)
                {
                    //假设电脑在当前位置下棋
                    board[i][j] = _computer_;
                    //获取当前棋盘分数,递归minimax函数,并将下一回合切换到对手回合
                    score = minimax(depth+1,false);
                    //复位棋局
                    board[i][j] = _empty_;
                    //获取当前回合的最大值
                    best_score = max(best_score,(double)score);
                }
            }
        }
        //返回最佳值
        return best_score;
    }
    else
    {
        //若当前回合是玩家,则最小化玩家

        //设置 最佳值 初始化为最大值
        double best_score = INT_MAX;

        //遍历棋盘上每一个为 _empty_ 的位置
        for(int i=0;i<ROW;i++)
        {
            for(int j=0;j<COL;j++)
            {
                //若当前位置为 _empty_
                if(board[i][j] == _empty_)
                {
                    //则假设玩家在当前位置下棋
                    board[i][j] = _player_;
                    //获取当前分数,递归minimax函数 并切换到电脑回合 
                    score = minimax(depth+1,true);
                    //复位当前棋局
                    board[i][j] = _empty_;
                    //获取当前回合的最小值
                    best_score = min(best_score,(double)score);
                }
            }
        }
        //返回最佳值
        return best_score;

    }

}

详细算法逻辑见：【从minimax到alpha-beta剪枝算法(上)：minimax算法原理介绍】

Computer_move电脑下棋实现

//电脑下棋
void Board::Computer_move()
{
    //电脑回合,最大化玩家
    double best_val = INT_MIN;

    //设置初始最佳下棋位置为 -1,-1
    pair<int, int> best_move(-1, -1);
    //遍历当前棋盘上为 _empty_ 的位置
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            //若当前位置为 _empty_
            if (board[i][j] == _empty_) {
                //执行minimax决策
                board[i][j] = _computer_;
                int move_val = minimax(0, false);

                board[i][j] = _empty_;

                // cout<<"move_val:>"<<move_val<<"\tbest_val:>"<<best_val<<"\t<x,y>:"<<i<<" "<<j<<endl;
                //若当前值大于最佳值
                if (move_val > best_val) {
                    //则将最佳下棋位置替换为当前的位置
                    best_move = std::make_pair(i, j);
                    //更新最佳值
                    best_val = move_val;
                }
            }
        }
    }
    //将棋盘对应最佳下棋位置替换为 _computer_
    this->board[best_move.first][best_move.second] = _computer_;
}

(4)判断胜利、判断平局

判断平局

bool Board::is_full()
{
    for(int i=0;i<ROW;i++)
    {
        for(int j=0;j<COL;j++)
        {
            if(board[i][j] == _empty_)
                return false;
        }
    }
    return true;
}

判断胜利

char Board::is_win()
{
    for(int i=0;i< ROW;i++)
    {
        if(this->board[i][0] == this->board[i][1] && this->board[i][1] == this->board[i][2] &&this->board[i][0]!= _empty_)
            {return this->board[i][0];}
        if(this->board[0][i] == this->board[1][i] && this->board[1][i] == this->board[2][i] &&this->board[0][i] != _empty_)
            {return this->board[0][i];}
    }
    //判断斜线
    if(this->board[0][0] == this->board[1][1] && this->board[1][1] == this->board[2][2] && this->board[0][0]!= _empty_)
            {return this->board[0][0];}
    if(this->board[2][0] == this->board[1][1] && this->board[1][1] == this->board[0][2] &&this->board[2][0]!= _empty_)
            {return this->board[2][0];}
    if(is_full())
        return _pease_;
    return _continue_;

}

3、主函数设计(main.cpp)

#include "board.h"


void game()
{
    //清屏
    system("cls");
    //定义棋盘对象
    Board b;

    //初始化棋盘
    b.InitBoard();

    //游戏状态
    char ret;
    while (true)
    {
        //展示棋盘
        system("cls");
        b.displayBoard();

        //玩家下棋
        int x,y;
        cout<<"请输入要下的位置<row col>:";
        cin>>x>>y;
        if(!b.Player_move(x,y))
            continue;
            
        //胜利判断
        ret = b.is_win();
        if(ret != _continue_)
            break;
        
        //电脑下棋
        b.Computer_move();

        //胜利判断
        ret = b.is_win();
        if(ret != _continue_)
            break;
        

    }

    //展示最后棋盘状态
    b.displayBoard();
    if(ret == _player_)
    cout<<"玩家胜利"<<endl;
    if(ret == _computer_)
    cout<<"电脑胜利"<<endl;
    if(ret == _pease_)
    cout<<"平局"<<endl;

    system("pause");
    system("cls");

}

int main()
{
    //菜单选择
    int input;
    
    while (true)
    {
        menu();
        cout<<"请选择:>";
        cin>>input;
        switch (input)
        {
        case 1:
            game();
            break;
        case 0:
        cout<<"游戏结束"<<endl;
        system("pause");
            return 0;
            break;
        default:
            cout<<"输入错误"<<endl;
            system("pause");
            system("cls");
            break;
        }
    }
    


    system("pause");
}

二、游戏展示

可以看到，程序完美运行。

但是有个问题，在我下第三个棋子（2，2）后，明明电脑已经连成两个棋子可以直接胜利，

却选择堵住（1，2）点位，这是因为递归中循环是从上往下依次遍历模拟下棋，然后在返回的值中从上往下选择，当找到（1，2）这个点位时，刚好是返回值是1，所以电脑选择在这一步下棋而不是在（2，1）处下棋

解决这个问题的办法就是使用α-β剪枝，当判断当前值已经最大时，直接break，而不是继续遍历

优化minimax算法实现

int Board::minimax(int depth, bool is_maxing, int alpha, int beta)
{
    double score = evaluate();

    if(score == 1 || score == -1)
        return score;
    if(is_full())
        return 0;

    if(is_maxing)
    {
        double best_score = INT_MIN;
        for(int i = 0; i < ROW; i++)
        {
            for(int j = 0; j < COL; j++)
            {
                if(board[i][j] == _empty_)
                {
                    board[i][j] = _computer_;
                    score = minimax(depth + 1, false, alpha, beta);
                    board[i][j] = _empty_;
                    best_score = max(best_score, score);
                    //更新α值
                    alpha = max((double)alpha, best_score);
                    //减去β枝
                    if(beta <= alpha)
                        break; // Beta cutoff
                }
            }
        }
        return best_score;
    }
    else
    {
        double best_score = INT_MAX;
        for(int i = 0; i < ROW; i++)
        {
            for(int j = 0; j < COL; j++)
            {
                if(board[i][j] == _empty_)
                {
                    board[i][j] = _player_;
                    score = minimax(depth + 1, true, alpha, beta);
                    board[i][j] = _empty_;
                    best_score = min(best_score, score);
                    //更新β值
                    beta = min((double)beta, best_score);
                    //减去α枝
                    if(beta <= alpha)
                        break; // Alpha cutoff
                }
            }
        }
        return best_score;
    }
}

设置初始的α值为INT_MAX，设置初始β值为INT_MIN

优化算法后的程序为

可以看到，电脑已经完全实现了三子棋的功能