C++::基于minimax算法设计的三子棋游戏
基础的c语言三子棋相信很多人都做过了,碰巧今年电赛有个三子棋,就试试这个算法
三子棋的规则很简单：在一个3x3的格子板上，两名玩家轮流放置自己的棋子（通常是X和O）。第一个玩家成功在横向、纵向或对角线上连成一条由自己棋子组成的线（即三子连线）即为胜者。如果所有格子都被填满而没有人连成三子线，则游戏平局
而游戏的对弈模型是基本的零和博弈模型,minimax算法就是为了零和博弈而生的.
Minimax算法是一种用于零和博弈的决策算法，主要用于找到最佳策略。它通过递归地模拟所有可能的游戏状态来确定每个玩家的最佳行动。算法的核心是：
- 最大化：当前玩家（最大化者）试图使得其最终收益最大化,在这里指电脑.
- 最小化：对手（最小化者）试图使得当前玩家的收益最小化,在这里指玩家.
在每一步，算法评估所有可能的后续状态，选择能够在最终回合中达到最佳结果的行动。
一、游戏逻辑设计
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,-1pair<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
优化算法后的程序为
可以看到，电脑已经完全实现了三子棋的功能