使用QT creator实现一个五子棋AI包括GUI实现（8K字超详细）

五子棋AI实现 五子棋游戏介绍 五子棋的定义

五子棋是全国智力运动会竞技项目之一，是具有完整信息的、确定性的、轮流行动的、两个游戏者的零和游戏。因此，五子棋是一个博弈问题。

五子棋的玩法

五子棋有两种玩法：

玩法一：双方分别使用黑白两色的棋子，下在棋盘直线与横线的交叉点上，先形成五子连线者获胜。

玩法二：自己形成五子连线就替换对方任意一枚棋子。被替换的棋子可以和对方交换棋子。最后以先出完所有棋子的一方为胜。

本次实验的玩法是第一种。

五子棋的具体规则

对局双方各执一色棋子，棋盘一共15行15列，225个下棋点。

空棋盘开局。

黑先、白后，交替下子，每次只能下一子。

棋子下在棋盘的空白点上，棋子下定后，不得向其它点移动，不得从棋盘上拿掉或拿起另落别处。

黑方的第一枚棋子必须下在天元点上，即中心交叉点

轮流下子是双方的权利，但允许任何一方放弃下子权（即：PASS权）。

五子棋博弈算法的具体实现 算法定义：

由于是零和游戏的博弈问题，因此针对此问题的经典算法为min-max算法以及针对其的alpha-beta剪枝优化算法。

min-max算法：

设游戏的两个游戏者为MAX和MIN。MAX先下棋，然后两人轮流出招，对于每一步当前的棋盘局面，使用一个评估函数 \(score(x)\) 来评价MAX距离游戏胜利的远近。MAX越容易获得胜利，\(score(x)\)的值就越大。

算法思想：

对于MAX来说，他的每一步棋都要使得当前棋盘局面的评估函数最大，即\(max(score(board[r][l]))\)，\(r\),\(l\) 表示MAX下的棋子的位置。

而相反，对于MIN来说，他的每一步棋都要使得当前棋盘局面的评估函数最小，即\(min(score(board[r][l]))\)，\(r\),\(l\) 表示MIN下的棋子的位置。

因此，使用深度有限搜索的方法，即限制问题搜索的深度为\(depth\)(\(depth\)表示MAX和MIN从目前棋盘轮流下子的次数)，一旦搜索深度到达\(depth\)就计算预测棋盘的得分，然后往上回溯，搜索树以及搜索过程如图所示：

图引自：《人工智能》(一)：min-max算法 - 简书 (jianshu.com)

该树的深度为5层，但是\(depth\)为4。

\(depth = 3\)为MIN层，MIN选择所有预测局面中的得分最小的情况作为自己这一步下棋的位置，而\(depth = 2\)的MAX层在\(depth=3\)的MIN层的基础上形成的局面中选择得分最大的位置来作为自己这一步下棋的位置（就是MAX考虑下棋时，遍历225个下棋的点位，选择局面得分最高的点下棋）。以此类推，最后找到能够使\(depth=0\)的MAX下一步得分最高的点。

Min-Max的核心就是假设双方每一步都是相对于评估函数的最优解的情况下来选择下一步该走的位置。

算法伪代码：

cpp代码： void chess_board::min_max_search(QTextBrowser *detail_info) { score_next = max_sear(0,detail_info); } int chess_board::max_sear(int deep,QTextBrowser *detail_info) { if(deep==depth) return cal_score(first_me); int v = -0x3f3f3f3f; int old_a = 0; for(int l=0;l<board_col;l++) for(int r=0;r<board_row;r++) { if(board[r][l]==\'0\')//如果当前位置是空子的话 { set_temp_chess(r,l,true); v = max(v,min_sear(deep+1, detail_info)); if(deep==0&&v!=old_a)//如果是在最表层且有更新，则选择这一步 { char tip_out[1005] = {0}; sprintf(tip_out,"update max:\n l = %d, r = %d \nv = %d\n",l,r,v); detail_info->textCursor().insertText(tip_out); next.set_rl(r,l); old_a = v; } clear_temp_chess(r,l);//注意要回溯 } } return v; } int chess_board::min_sear(int deep,QTextBrowser *detail_info) { if(deep==depth) return cal_score(first_me); int v = 0x3f3f3f3f; for(int l=0;l<board_col;l++) for(int r=0;r<board_row;r++) { if(board[r][l]==\'0\')//如果当前位置是空子的话 { set_temp_chess(r,l,false); v = min(v,max_sear(deep+1, detail_info)); clear_temp_chess(r,l);//注意要回溯 } } return v; } 实现细节：

由于只有一个棋盘，因此要注意dfs回溯的时候要清除临时下的棋子。

MAX根节点，也就是最高层，每次更新\(v\)的时候记录下落子的位置，搜索完后对应的位置就是人工智能要落子的位置。

算法缺点：

太慢了。