基于博弈树的五子棋 AI 算法及其 C++ 实现
- 摘要
- 一 五子棋的游戏规则
- 二 五子棋对弈的算法描述
-
- 2.1 博弈树搜索算法
- 2.2 α ─ β 剪枝
- 2.3 估价函数
- 三 五子棋对弈的算法实现
-
- 3.1 Node类
-
- 3.1.1 成员变量
- 3.1.2 成员函数
- 3.2 GameTree类
-
- 3.2.1 成员变量
- 3.2.2 成员函数
- 四 五子棋对弈过程
-
- 4.1 人机对弈过程
- 4.2 机机对弈过程
- 五 感悟
- 附录一 程序使用的简单说明
- 附录二 完整的C++代码
- 参考文献
摘要
五子棋是一个风靡全国的棋类游戏，本文研究五子棋的博弈树算法，并编程实现该算法。本文介绍了博弈树的极大极小搜索算法和α-β剪枝优化技术，并提出了自己的估价函数。本文采用C++编程，并用类封装代码，方便外部调用。本文展示了一个人机对弈过程的实例和一个机机对弈过程的实例，实践证明该算法已经具有较高的业余级水平，但对复杂局面的判断还不理想。本文最后给出了作者的感悟。
关键词：五子棋 博弈树 α-β剪枝 估价函数
一 五子棋的游戏规则
五子棋（Five In A Row，FIR）是全国智力运动会竞技项目之一，是一种两人对弈的纯策略型棋类游戏。五子棋不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性，在各大游戏平台都有应用，主要流行于东亚以及欧洲的一些国家。著名的五子棋手有中国的吴侃、吴镝、戴晓涵、祁观、曹冬和日本的中村茂等。1
标准的五子棋盘由横纵各15条等距离、垂直交叉的平行线构成。在棋盘上，横纵线交叉形成的225个交叉点为对弈时的落子点。
五子棋的游戏规则是，双方棋手分别使用黑白两色的棋子，下在棋盘竖线与横线的交叉点上，先形成“五子连线”者获胜。
五子棋还有一种游戏规则是，自己连成五枚棋子就吃掉对方最近的一枚棋子，被吃的棋子还给对方继续使用。最后以先出完所有棋子的一方为胜利者。被对方吃掉棋子的那一格自己不能再放棋子，但对方可以放。但是吃子不能吃对方已经连成五子的其中一枚棋子，除非对方全部棋子都连成了五子。
图1展示了五子棋中全部四种“五子连线”的形态，分别是横向五子连线、竖向五子连线和两种对角线五子连线。
图1 五子棋“五子连线”的四种形态
我们将五子棋的游戏流程叙述如下：
（1）开局前，双方确定执子颜色；
（2）空棋盘开局；
（3）黑子先手；
（4）黑白交替下子，每次下一子，只能下在空白的交叉点处；
（5）下子后不能悔棋，也不能移动任何棋子；
（6）某方达成“五子连线”，则该方获胜，游戏结束；
（7）棋盘上没有落子点，且双方均没有“五子连线”，则平局，游戏结束；
二 五子棋对弈的算法描述
五子棋是一个双方对弈的游戏，我们称执黑子的一方为“黑方”，执白子的一方为“白方”。对于当前棋局，我们的目的是找到一个最佳的落子点，使得我方的胜算最大。这也是本算法的目的，确定下一步的落子点，使得我方胜算最大。为了判断到底落子何处才能使胜算最大，我们需要往后多推算几步，包括推算我方落子和对方落子，模拟出可能出现的棋局，从这些棋局中选出胜算最大的那个棋局，进而确定下一步的最佳落子点。
本算法始终认为计算机是黑方，如果计算机是白方，我们可以反转棋盘上所有的黑白棋子，这样计算机就变成了黑方。本算法的输入是一个棋局，输出的是下一步的落子点坐标。
2.1 博弈树搜索算法
可以看出，该推算过程本质上就是一个搜索算法。具体来说，对于当前棋局，我方有许多种落子方法，对于我方的每种落子方法，对方又有许多种落子方法，而对于对方的每种落子方法，我方又有许多种落子方法……这样，往后多推算几步，有利于看清当前棋局中的最佳落子点和潜在威胁。
图2 五子棋的搜索树
如图2所示，在当前棋局1，有两颗白子，现在是黑方回合。黑方可以落子形成棋局2，也可以落子形成棋局3。如果黑方落子形成棋局2，则白方可以落子形成棋局4和棋局5，如果黑方落子形成棋局3，则白方可以落子形成棋局6和棋局7。
黑白双方都会选择对自己最有利的落子点，站在黑方的角度，黑方下一步会使黑方的胜算最大，而白方的下一步会使黑方的胜算最小。该过程反映在搜索树中是这样的，若当前节点是黑方回合，则找一个对黑方最佳的落子点，若当前节点是白方回合，则找一个对黑方最差的落子点。
最佳落子点和最差落子点是一个很模糊的说法，我们需要量化最佳落子点和最差落子点，即对每种落子方法打分。具体来说，我们需要建立一套评分机制，该评分机制需要满足：对于任一棋局，该棋局对黑方越有利则分数越高，该棋局对黑方越不利则分数越低。对于某一棋局，黑白双方可能需要再下几十甚至上百步才能使游戏结束，这意味着搜索树的深度会达到几十甚至上百层。例如，每种棋局考虑10种落子方法，推算50步，则搜索树是一棵50层的十叉数，搜索量是巨大的。所以，我们的评分机制不仅要对已经结束的棋局进行打分，还要能估算未结束棋局的分数。我们把这个评分机制称为“估价函数”。
至此，算法的主题思想已叙述完毕。下面，我们结合一个实例将算法的主要步骤叙述一遍。
图3 五子棋的博弈树搜索
如图3所示是一棵搜索树，每一个节点就是一个棋局。当前处于0号节点，当前深度是0，当前是黑方回合。我们的搜索树向后推算三步，一共得到8种可能的棋局（7～14号节点），使用估价函数对这8个节点进行估计，将得到的分数用红色字体写在节点下方。节点3是黑方回合，黑方会选择对自己最有利的走法，此时黑方会走到节点8，同理，节点4的黑方会走到节点9，节点5的黑方会走到节点11，节点6的黑方会走到节点14。节点1的白方，会选择对自己最有利的走法，该走法使得黑方得分最低，所以节点1的白方会走到节点3，同理，节点2的白方会走到节点5。节点0的黑方会选择对自己最有利的走法，黑方会走到节点1。因此，处于当前棋局的黑方，会落子形成节点1的棋局，该落子点就是当前的最佳落子点。
0、3、4、5、6号节点是黑方节点，这些节点会选择下一层中估值最大的那个节点，因此我们称这些节点为“MAX节点”。而1、2、7、8、9、10、11、12、13、14号节点是白方节点，这些节点会选择下一层中估值最小的那个节点，因此我们称这些节点为“MIN节点”。每一层要么全是MAX节点，要么全是MIN节点，即MAX节点和MIN节点隔层交替出现。
MAX节点寻找极大值，MIN节点寻找极小值，所以该搜索算法称为“极大极小搜索”算法，该搜索树称为“极大极小搜索树”，亦称为“博弈树”。
2.2 α ─ β 剪枝
在上述博弈树搜索的过程中，我们把深度范围内的全部节点都访问了一遍。这导致算法的搜索量特别大，算法效率低下。事实上，遍历全部节点是没有必要的，我们可以对博弈树搜索算法进行剪枝优化。
我们分别考虑当前节点是MAX节点和MIN节点的情况，约定函数f(node)表示节点node的估值得分，有
◆ 当前节点是MAX节点：当前节点记为M，节点M有一个MIN子节点，记为m1，且f(m1)=α，则必有f(M)≥α。这是因为节点M是MAX节点，会选择所有子节点中估值最大的那个节点，所以MAX节点不会选择估值比α还小的子节点，而只会选择估值比α还大的子节点，所以得到f(M)≥α，该值称为“MAX节点的α值”，α值刻画了MAX节点的下界；
◆ 当前节点是MIN节点：当前节点记为m，节点m有一个MAX子节点，记为M1，且f(M1)=β,则必有f(m)≤β，这是因为节点m是MIN节点，会选择所有子节点中估值最小的那个节点，所以MIN节点不会选择估值比β还大的子节点，而只会选择估值比β还小的子节点，所以得到f(m)≤β，该值称为“MIN节点的β值”，β值刻画了MIN节点的上界；
我们通过一个实例来具体介绍上述思想是如何进行剪枝优化的。我们还是以图3中的博弈树为例，采用深度优先搜索（DFS）算法遍历，假设最大搜索深度为3。搜索过程叙述如下：
◆ 从节点0开始，遍历过程：0→1→3→7，如图4所示。节点7达到最大深度，用估价函数得到f(7)=-5。对于MAX节点3，必有f(3)≥-5，接着往上推，对于MIN节点1，必有f(1)≤-5，最后，对于MAX节点0，必有f(0)≥-5；
图4 五子棋博弈树的α-β剪枝过程（1）
◆ 从节点3继续，遍历过程：3→8，如图5所示。节点8达到最大深度，用估价函数得到f(8)=5。更新节点3得到f(3)≥5，更新节点1得到f(1)≤5，更新节点0得到f(0)≥5；
图5 五子棋博弈树的α-β剪枝过程（2）
◆ 从节点1继续，遍历过程：1→4→9，如图6所示。节点9达到最大深度，用估价函数得到f(9)=10。更新节点4得到f(4)≥10。此时，f(3)≥5，f(4)≥10，MIN节点1会选择有更小估值的节点3，而不会选择有更大估值的节点4。所以，节点4的任何子节点都不需要再继续搜索下去了，即节点10被剪枝掉了；
图6 五子棋博弈树的α-β剪枝过程（3）
◆ 从节点0继续，遍历过程：0→2→5→11，如图7所示。节点11达到最大深度，用估价函数得到f(11)=-4。更新节点5得到f(5)≥-4，更新节点2得到f(2)≤-4。此时，f(1)≤5，f(2)≤-4，MAX节点0会选择有更大估值的节点1，而不会选择有更小估值的节点2。所以，节点2的任何子节点都不需要再继续搜索下去了，即节点2被剪枝掉了。从图中可以看出，6、12、13、14号节点都是节点2的子节点，这四个节点都被剪枝掉了；
图7 五子棋博弈树的α-β剪枝过程（4）
◆ 至此，搜索过程全部结束，前往节点1是最优选择；
下面我们叙述一般情况的α-β剪枝规则：
α剪枝：当前节点是MIN节点，其β值小于等于其父节点的α值，则可以将以当前节点为根节点的子树剪枝，该剪枝称为“α剪枝”；
β剪枝：当前节点是MAX节点，其α值大于等于其父节点的β值，则可以将以当前节点为根节点的子树剪枝，该剪枝称为“β剪枝”；
根据上述对α-β剪枝规则的定义2，我们知道，在博弈树搜索过程中，第一次剪枝属于β剪枝，第二次剪枝属于α剪枝，已在图7中标注。
2.3 估价函数
从上文的叙述中可以看出，估价函数的好坏直接影响了决策树的搜索过程和路径判断，所以估价函数的定义至关重要。在同一个应用场景中，不同学者定义的估价函数往往都不一样，这也就导致决策树的效率和正确率都有很大偏差。
张明亮等学者在《五子棋机器博弈系统评估函数的设计》一文中指出，“因五子棋先手优势大，评估函数分为先手和后手两类：先手时加重己方非关键棋型分值，相当于加重进攻招法的分值；后手则加重对手棋型分值，相当于加重计算机防守招法的分值，道理是利用局势的发展趋势稍作引导，实验效果很好，明显加快后手棋的搜索，表明起到了优化博弈树的作用。”3而学者董红安使用的估价函数非常简单，考虑的是每个“五元组”中棋子的状态。2学者刘瑞使用的估价函数也是考虑每个“五元组”，但设计的规则要略复杂一些。4
本文参考前人对于估价函数的设计工作，提出了自己的估价函数。
首先，我们给出“五元组”的定义。五元组指棋盘上连续的五个位置，包括横向、纵向、主对角线方向、副对角线方向，一共4个方向。图8展示了这4种五元组的形态，其中红色方框表示一个竖向五元组，黄色方框表示一个横向五元组，蓝色方框表示一个主对角线方向五元组，绿色方框表示一个副对角线方向五元组。
图8 四种“五元组”的形态
对于棋盘上每一个落子点，我们规定使用‘B’表示该点是黑子(Black)，‘W’表示该点是白子(White)，‘0’表示该点为空，‘*’表示该点可能为任何三种状态（黑子点、白子点、空点）。这样，我们可以表示出每个五元组内部的落子情况。方向先从上到下，再从左到右。我们用该符号表示图8中的4个五元组，结果如表1所示。
表1 图8中五元组的符号表示
| 方框颜色 | 符号表示 |
|---|---|
| 红色方框 | B000W |
| 黄色方框 | B0W0W |
| 蓝色方框 | B0WBW |
| 绿色方框 | BBBWW |
对于每个五元组，我们定义评分规则如下：
（1）同时含有黑子和白子，得0分；
（2）含有1个黑子和4个空点，得+1分；
（3）含有2个黑子和3个空点，得+10分；
（4）含有3个黑子和2个空点，得+100分；
（5）含有4个黑子和1个空点，得+10000分；
（6）含有5个黑子，得+1000000分；
（7）含有1个白子和4个空点，得-1分；
（8）含有2个白子和3个空点，得-10分；
（9）形如“0WWW0”，得-2000分；
（10）含有3个白子和2个空点，得-1000分；
（11）含有4个白子和1个空点，得-100000分；
（12）含有5个白子，得-10000000分；
该评分规则的使用法则是：从上到下匹配，返回第一条匹配规则的分值。例如，五元组“0WWW0”符合第9条和第10条规则，但是优先匹配第9条规则，所以返回分值-2000。
我们设计该评分规则的想法是：
◆ 若某个五元组同时含有黑子和白子，则任何一方都无法形成“五子连线”而获胜，该五元组无意义，所以第1条为0分；
◆ 我们偏向保守规则，即防守优先于进攻，所以“仅含3个黑子五元组的分值(100)”＜“仅含3个白子五元组的分值(1000)”＜“仅含4个黑子五元组的分值(10000)”＜“仅含4个白子五元组的分值(100000)”＜“含5个黑子五元组的分值(1000000)”＜“含5个白子五元组的分值(10000000)”，分值是按等级依次递增的，且下一等级的分值为上一等级分值的10倍；
◆ 在第9条中，我们单独列出了形如“0WWW0”的五元组。因为在实际测试过程中，我们发现如果棋局出现“00WWW00”的局面，由于搜索顺序的原因，黑方会这样落子，形成“B0WWW00”的局面，这显然是不合理的，因为白方下一步可以形成“B0WWWW0”的局面，从而赢得比赛，所以我们给“0WWW0”相对于同一等级更高的分值；
我们的已经定义了针对单个五元组的评分规则，我们定义当前棋局的总得分为全部五元组得分的总和。形式化地，设W是棋局上全部的五元组集合，w是单个五元组，score(S)表示单个五元组的得分，设总得分为S，则
S=∑w∈Wscore(w)S=\sum_{w \in W}score(w) S=w∈W∑score(w)
三 五子棋对弈的算法实现
上一章中，我们叙述了五子棋对弈的算法思想，本章我们叙述其编程实现。我们采用C++语言编写程序，代码遵循C++17标准。
数据结构主要是两个类，一个Node类表示一个节点，一个GameTree类表示一棵博弈树。显然，一个GameTree类中含有多个Node类。全部的变量和函数都封装在GameTree类中，方便外部调用。并且GameTree类提供了cmd命令行窗口的可视化对弈功能，可进行人机对弈。
下面，我们将详细介绍Node类和GameTree类。
3.1 Node类
Node类记录了一个节点的所有信息，包括深度、估值得分、落点位置、棋局信息、父节点信息、子节点信息，并提供了判断当前节点是否为MAX节点的函数、当前棋局的估价函数、判断胜负的函数等。
3.1.1 成员变量
Node类的成员变量定义如表2所示。
表2 Node类的成员变量
| 变量名 | 变量类型 | 变量说明 |
|---|---|---|
| value | int32_t | 若当前节点是叶节点，记录的是估值得分； 若当前节点是MAX节点，记录的是α值； 若当前节点是MIN节点，记录的是β值； |
| depth | uint32_t | 记录当前节点的深度，根节点深度为0 |
| cntX | uint8_t | 记录当前棋局最后一步落子点的x轴坐标 |
| cntY | uint8_t | 记录当前棋局最后一步落子点的y轴坐标 |
| father | Node* | 记录当前节点的父节点，是一个指针 |
| children | set<Node*> | 记录当前节点的子节点，使用STL的set容器，set中每一个指针都指向一个子节点 |
| board | uint8_t[15][15] | 记录当前棋局，‘B’(66)表示黑子，‘W’(87)表示白子，‘0’(48)表示空位 |
3.1.2 成员函数
本节介绍Node类的成员函数。对于核心成员函数，我们将详细介绍，并给出实现的伪代码，对于非核心成员函数，我们只简要说明其用途。
◆ is_max_node() : bool
判断当前节点是否为MAX节点，若是则返回真值，若不是则返回假值。
◆ evaluate()
估价函数，是Node类的核心函数。该函数会调用上面三个函数。该函数的伪代码如下所示，其中evaluate_black(s)函数返回该五元组的黑方得分，evaluate_white(s)函数返回该五元组的白方得分。
void evaluate() {value = 0;for i,j = (0,0) to (14,14) {if (j + 4 < 15) {s = 以(i,j)开头的横向五元组;value += evaluate_black(s) – evaluate_white(s);}if (i + 4 < 15) {s = 以(i,j)开头的竖向五元组;value += evaluate_black(s) – evaluate_white(s);}if (i + 4 < 15 and j + 4 < 15) {s = 以(i,j)开头的主对角线方向五元组;value += evaluate_black(s) – evaluate_white(s);}if (i + 4 < 15 and j - 4 >= 0) {s = 以(i,j)开头的副对角线方向五元组;value += evaluate_black(s) – evaluate_white(s);}}
}
◆ board_identify() : uint8_t
判断当前棋局是否已经分出胜负，若黑方获胜返回66，若白方获胜返回87，若还未分出胜负返回0。该函数的伪代码如下：
void board_identify() {for i,j = (0,0) to (14,14) {if (j + 4 < 15) {s = 以(i,j)开头的横向五元组; //这里会调用convert函数,下同if (s == “BBBBB”) return ‘B’; //黑方获胜if (s == “WWWWW”) return ‘W’; //白方获胜}if (i + 4 < 15) {s = 以(i,j)开头的竖向五元组;if (s == “BBBBB”) return ‘B’; //黑方获胜if (s == “WWWWW”) return ‘W’; //白方获胜}if (i + 4 < 15 and j + 4 < 15) {s = 以(i,j)开头的主对角线方向五元组;if (s == “BBBBB”) return ‘B’; //黑方获胜if (s == “WWWWW”) return ‘W’; //白方获胜}if (i + 4 < 15 and j - 4 >= 0) {s = 以(i,j)开头的副对角线方向五元组;if (s == “BBBBB”) return ‘B’; //黑方获胜if (s == “WWWWW”) return ‘W’; //白方获胜}}return 0;
}
3.2 GameTree类
GameTree类记录了一棵博弈树的所有信息，包括搜索半径、最大深度、根节点指针、最佳节点指针、open表、closed表，并提供了博弈控制函数、节点扩展函数、α-β更新函数、α-β剪枝判断函数等。此外，GameTree类还提供了cmd命令行窗口的可视化功能。
GameTree类的成员变量中，只保存了一个指向根节点的指针，所有节点间的关系均使用指针来刻画。
3.2.1 成员变量
Node类的成员变量定义如表3所示。
表3 GameTree的成员变量
| 变量名 | 变量类型 | 变量说明 |
|---|---|---|
| expandRadius | uint8_t | 搜索半径，从当前节点向四周扩展的距离，扩展区域是一个正方形 |
| maxDepth | uint32_t | 最大深度 |
| nodeRoot | Node* | 一个指向根节点的指针 |
| nodeNext | Node* | 一个指向最佳节点的指针 |
| openTable | deque<Node*> | 一个双向队列，存放待扩展节点的指针 |
| closedTable | deque<Node*> | 一个双向队列，存放已扩展节点的指针 |
3.2.2 成员函数
本节介绍GameTree类的成员函数。对于核心成员函数，我们将详细介绍，并给出实现的伪代码，对于非核心成员函数，我们只简要说明其用途。此外，实现可视化功能的成员函数将在下一章中说明。
◆ set_next_pos()
在完成博弈树的搜索过程后，该函数负责寻找下一步的最佳落子点，即寻找根节点的最佳子节点。该函数的伪代码如下：
void set_next_pos() {nodeNext = nodeRoot的第一个子节点;for (n in nodeRoot的所有子节点)if (n的值 > nodeNext的值) nodeNext = n;
}
◆ game()
博弈控制函数，是GameTree类最核心的函数。该函数控制整个博弈搜索过程，伪代码如下：
void game() {调用nodeRoot->board_identify()判断棋局是否已经分出胜负，若是则直接退出将nodeRoot节点加入openTable的末端while (openTable非空) {取出openTable中首元素node将node从openTable移除，移入closedTable的末端if (is_alpha_beta_cut(node->father)) continue; //α-β剪枝if (node还未达到最大深度) {扩展node节点if (node存在子节点) continue;}node->evaluate(); //调用估价函数update_value_from_node(node); //更新所有父节点的α-β值}set_next_pos(); //寻找最佳节点
}
◆ expand_children_nodes(Node *node) : uint8_t
扩展node节点，生成node节点的所有子节点，该函数的伪代码如下：
uint8_t expand_children_nodes(Node *node) {调用get_search_nodes(node)获取待扩展点集合，存入变量maskfor (x,y) in mask {新建节点n，节点n的属性根据其父节点node生成在节点node的子节点中加入节点n将节点n加入openTable的前端}return mask.size();
}
◆ get_search_nodes(Node *node) : vector<pair<uint8_t,uint8_t>>
返回当前棋局的待扩展点坐标集合，返回一个vector容器，容器中每个元素都是一个pair，代表一个点的坐标。如图9所示的棋局中，所有黄点是当前棋局的待扩展点，一共32个点。
图9 四种“五元组”的形态
该函数的伪代码如下：
vector<pair<uint8_t, uint8_t>> get_search_nodes(Node *node) {如果是空棋局，返回{(7,7)}，即黑方开局始终落子在棋盘中点bool newBoard[15][15];for i,j = (0,0) to (14,14) {if (点(i,j)已有落子) continue;for x,y = (i-radius,j-radius) to (i+radius,j+radius)if (点(x,y)是空点) newBoard[x][y] = true;}vector<pair<uint8_t, uint8_t>> mask;for i,j = (0,0) to (14,14) {if (newBoard[i][j]) 将点(i,j)加入mask中}return mask;
}
◆ is_alpha_beta_cut(Node *node) : bool
判断节点node是否能α-β剪枝，该函数的伪代码如下：
bool is_alpha_beta_cut(Node *node) {if (node是空节点或根节点) return false;if (node是MAX节点 and node的值 > 其父节点的值) return true;if (node是MIN节点 and node的值 < 其父节点的值) return true;return is_alpha_beta_cut(node->father); //判断其父节点是否能剪枝
}
◆ update_value_from_node(Node *node)
在某个叶节点完成估价后，该函数负责更新其所有父节点的α值或β值。该函数的伪代码如下：
void update_value_from_node(Node *node) {if (node是空节点) return;if (node是叶节点) {update_value_from_node(node->father);return;}if (node是MAX节点) {cntValue = node所有子节点中的最大估值;if (cntValue > node的值) {更新node的值为cntValue;update_value_from_node(node->father);}}if (node是MAX节点) {cntValue = node所有子节点中的最小估值;if (cntValue < node的值) {更新node的值为cntValue;update_value_from_node(node->father);}}
}
四 五子棋对弈过程
GameTree类提供了cmd命令行窗口的可视化功能，主要由3个成员函数实现。下面简要说明一下这三个成员函数。
◆ show_next_pos()
该函数在cmd窗口中打印下一步落子点坐标。
◆ show_board()
该函数在cmd窗口中打印当前棋局。
◆ get_next_pos() : pair<uint8_t, uint8_t>
该函数返回下一步落子点坐标，两个返回值分别表示x轴坐标和y轴坐标。
如图10所示，计算机执黑子先手开局。我们先后调用show_next_pos()函数和show_board()函数打印最后落子点坐标和当前棋局。可以看出，黑方开局选择下在棋盘中央，坐标是(7,7)。
图10 可视化对弈界面
4.1 人机对弈过程
我们配置最大深度为9，扩展半径为2，计算机执黑子先手开局，我方执白子。开局前三步的落子情况如图11所示。在图11左中，是计算机下的第一步，第一步坐标是(7,7)。在图11右中，在cmd窗口中输入我方落子点的坐标，这里我们输入“7 6”并回车，表示第二步坐标是(7,6)，随后计算机下出第三步，第三步坐标是(8,7)。同时，在cmd窗口中会绘制此时的棋局。这样，我们在cmd窗口中方便地进行人机对弈。
图11 人机对弈过程（1）
图12左展示了九步时的棋局，可以看出，计算机控制的黑方已经率先构造了一个四子威胁，马上就要形成“五子连线”了，该威胁已在图中用红色方框标出。此时，我方没有选择，下一步只能落在(8,4)处，以消解这个威胁。
图12右展示了十三步时的棋局，可以看出，计算机控制的黑方又构造了一个斜向的四子威胁，已在图中用红色方框标出。此时，我们只能下载(11,3)处来堵住黑子。
图12 人机对弈过程（2）
图13左展示的棋局中，我方选择下在(6,6)处，此时，我方的白子形成两个“三连”形态，已在图中用红点标出我方落子点，并用两条红线标出两个“三连”的位置。事实上，此时我方已经获胜了。
图13右中，我方落子在(6,9)处，形成“五子连线”。至此，我方获胜，本局比赛结束。已在图中用红色方框标出这五颗白子。在cmd窗口中，打印了最终棋局，并输出“White Win ！”的文字。
图13 人机对弈过程（3）
4.2 机机对弈过程
我们配置最大深度为8，扩展半径为2，黑白双方均为计算机。下面简单展示机机对弈的过程。
如图14左所示，是开局第八步时的棋局，此时白方已经对黑方形成了一个四子威胁，在图中用红色方框标出。黑方不得不下在(5,8)的位置上，以化解该危机。庆幸的是，黑方成功识别出了该危机，并正确地在(5,8)处落子了，此时的棋局如图14右所示。
图14 机机对弈过程（1）
如图15左所示，在第二十四步时，白方落子在(6,5)处。此时，黑方发现白方还差一子就能形成“五连”，所以黑方不得不在第二十五步时，落子在(7,5)处，以阻止白方形成“五连”而获胜。
图15 机机对弈过程（2）
然而，黑方没有意识到白方有一个潜在的巨大威胁。如图16左所示，在第二十六步时，白方落子在(7,4)处，形成了两个“三连”，其实此时白方已经获胜。如图16右所示，最终，在第三十步时，白方落子在(6,3)处，形成了“五子连线”而获胜，比赛结束。
图16 机机对弈过程（3）
五 感悟
这是自己第一次学习博弈树算法，之前一直有听说博弈树的模型，但一直没有机会去认真研究博弈树，更别说把博弈树的算法原理给讲清楚了。通过这次的课堂学习、算法编程和论文撰写，可以说，自己已经完全弄明白了博弈树的模型，包括博弈树的极大极小搜索算法、α-β剪枝优化技术、估价函数。
自己花了大概两天时间编程C++程序代码，写代码并调试程序。运行程序后，发现程序可以和自己对弈的那一刻，心情实在是太激动了！但也发现算法存在一点小问题，比如出现“00WWW00”的局面时，算法无法正确地进行阻拦操作。研究后发现，这是由于估价函数设计不当造成的后果。自己也是参考了数篇论文中对五子棋估价函数的定义，并结合自己的理解，才提出了自己的估价函数。并且自己设计的估价函数也并不是一次就成功的，前前后后修改了将近快十次才最终敲定。自己也深深体会到了估价函数的重要性，估价函数的好坏，会直接影响算法的好坏，所以寻找一个好的估价函数至关重要。
最终程序的智能化程度已经很高了，如果不使用高级的技巧，程序已经能下赢自己了。但该模型还存在许多缺陷，比如算法是完全固定的，没有任何随机化因素，这也就意味着有很大概率会出现重复的棋局。再比如在寻找下一步落子点的时候，由于是顺序搜索，所以会优先选择左上角的坐标，这里也是可以优化的一个地方。
寻找估价函数需要参考前人的科研成果，并加入自己的创新性思想。而创新能力正是研究生科研所必须的能力，也是提出新算法或优化现有算法所必须具备的技能。
附录一 程序使用的简单说明
程序代码的详细说明在第三章“五子棋对弈的算法实现”中。本附录只简要说明程序的使用方法。
程序只有一个文件，全部C++代码都在该文件中，代码遵循C++17标准，请注意兼容性。代码结构说明如下：
#include<...>
using namespace std;class GameTree {...}; //博弈树算法的实现代码封装在该类中void machine_human_play() //人机对弈控制函数
void machine_machine_play() //机机对弈控制函数int main() {machine_human_play(); //人机对弈machine_machine_play(); //机机对弈return 0;
}
代码使用非常简单，如要“人机对弈”，只要在main函数中注释掉机机对弈的调用即可，即
int main() {machine_human_play();//machine_machine_play();return 0;
}
同理，如要观看“机机对弈”，只要在main函数中注释掉人机对弈的调用即可，即
int main() {//machine_human_play();machine_machine_play();return 0;
}
图17展示了人机对弈的cmd界面，图18展示了机机对弈的cmd界面。
图17 人机对弈的cmd界面
图18 机机对弈的cmd界面
附录二 完整的C++代码
#include<iostream>
#include<string>
#include<memory.h>
#include<set>
#include<deque>
#include<vector>using namespace std;class GameTree {
private:class Node {public:int32_t value;uint32_t depth;Node *father;set<Node *> children;uint8_t cntX, cntY;uint8_t board[15][15]{};Node() {father = nullptr;children.clear();value = INT32_MIN;depth = cntX = cntY = 0;memset(board, 0, sizeof(board));}Node(Node *node, uint8_t opeX, uint8_t opeY) {depth = node->depth + 1;value = is_max_node() ? INT32_MIN : INT32_MAX;father = node;children.clear();cntX = opeX;cntY = opeY;memcpy(board, node->board, sizeof(board));board[cntX][cntY] = (depth & 1u) ? 'B' : 'W';}bool is_max_node() {return (depth & 1u) ^ 1u;}static int32_t evaluate_black(string &s) {string patterns[31] = {"B0000", "0B000", "00B00", "000B0", "0000B","BB000", "0BB00", "00BB0", "000BB", "B0B00", "0B0B0", "00B0B", "B00B0", "0B00B", "B000B","BBB00", "0BBB0", "00BBB", "BB0B0", "0BB0B", "B0BB0", "0B0BB", "BB00B", "B00BB", "B0B0B","BBBB0", "BBB0B", "BB0BB", "B0BBB", "0BBBB", "BBBBB",};int32_t scores[31] = {1, 1, 1, 1, 1,10, 10, 10, 10, 10, 10, 10, 10, 10, 10,100, 100, 100, 100, 100, 100, 100, 100, 100, 100,10000, 10000, 10000, 10000, 10000, 1000000,};for (uint8_t i = 0; i < 31; i++)if (s == patterns[i]) return scores[i];return 0;}static int32_t evaluate_white(string &s) {string patterns[31] = {"W0000", "0W000", "00W00", "000W0", "0000W","WW000", "0WW00", "00WW0", "000WW", "W0W00", "0W0W0", "00W0W", "W00W0", "0W00W", "W000W","WWW00", "0WWW0", "00WWW", "WW0W0", "0WW0W", "W0WW0", "0W0WW", "WW00W", "W00WW", "W0W0W","WWWW0", "WWW0W", "WW0WW", "W0WWW", "0WWWW", "WWWWW",};int32_t scores[31] = {1, 1, 1, 1, 1,10, 10, 10, 10, 10, 10, 10, 10, 10, 10,1000, 2000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,100000, 100000, 100000, 100000, 100000, 10000000,};for (uint8_t i = 0; i < 31; i++)if (s == patterns[i]) return scores[i];return 0;}static string convert(uint8_t pos) {if (pos == 0) return "0";if (pos == 'B') return "B"; else return "W";}uint8_t board_identify() {for (uint8_t i = 0; i < 15; i++)for (uint8_t j = 0; j < 15; j++) {if (j + 4 < 15) {string s;for (uint8_t k = 0; k < 5; k++) s += convert(board[i][j + k]);if (s == "BBBBB") return 'B';if (s == "WWWWW") return 'W';}if (i + 4 < 15) {string s;for (uint8_t k = 0; k < 5; k++) s += convert(board[i + k][j]);if (s == "BBBBB") return 'B';if (s == "WWWWW") return 'W';}if (i + 4 < 15 && j + 4 < 15) {string s;for (uint8_t k = 0; k < 5; k++) s += convert(board[i + k][j + k]);if (s == "BBBBB") return 'B';if (s == "WWWWW") return 'W';}if (i + 4 < 15 && j - 4 >= 0) {string s;for (uint8_t k = 0; k < 5; k++) s += convert(board[i + k][j - k]);if (s == "BBBBB") return 'B';if (s == "WWWWW") return 'W';}}return 0;}void evaluate() {value = 0;for (uint8_t i = 0; i < 15; i++)for (uint8_t j = 0; j < 15; j++) {if (j + 4 < 15) {string s;for (uint8_t k = 0; k < 5; k++) s += convert(board[i][j + k]);value += evaluate_black(s) - evaluate_white(s);}if (i + 4 < 15) {string s;for (uint8_t k = 0; k < 5; k++) s += convert(board[i + k][j]);value += evaluate_black(s) - evaluate_white(s);}if (i + 4 < 15 && j + 4 < 15) {string s;for (uint8_t k = 0; k < 5; k++) s += convert(board[i + k][j + k]);value += evaluate_black(s) - evaluate_white(s);}if (i + 4 < 15 && j - 4 >= 0) {string s;for (uint8_t k = 0; k < 5; k++) s += convert(board[i + k][j - k]);value += evaluate_black(s) - evaluate_white(s);}}}void print_info() {cout << this << " depth=" << depth << " value=" << value << " father=" << father << " children=(";for (auto child : children) cout << child << ",";cout << ")" << endl;for (auto &i : board) {cout << " ";for (uint8_t j : i) {if (j == 'B') cout << "○";if (j == 'W') cout << "●";if (j == 0) cout << "┼";}cout << endl;}}};uint8_t expandRadius = 2;uint32_t maxDepth = 5;Node *nodeRoot = new Node();Node *nodeNext = nullptr;deque<Node *> openTable;deque<Node *> closedTable;vector<pair<uint8_t, uint8_t>> get_search_nodes(Node *node) {bool hasChess = false, newBoard[15][15];memset(newBoard, false, sizeof(newBoard));for (uint8_t i = 0; i < 15; i++)for (uint8_t j = 0; j < 15; j++) {if (node->board[i][j] == 0) continue;hasChess = true;uint8_t x1 = max(0, i - expandRadius), x2 = min(14, i + expandRadius);uint8_t y1 = max(0, j - expandRadius), y2 = min(14, j + expandRadius);for (uint8_t x = x1; x <= x2; x++)for (uint8_t y = y1; y <= y2; y++)if (node->board[x][y] == 0) newBoard[x][y] = true;}vector<pair<uint8_t, uint8_t>> mask;if (!hasChess) {mask.emplace_back(pair<uint8_t, uint8_t>(7, 7));} else {for (uint8_t i = 0; i < 15; i++)for (uint8_t j = 0; j < 15; j++)if (newBoard[i][j])mask.emplace_back(pair<uint8_t, uint8_t>(i, j));}return mask;}uint8_t expand_children_nodes(Node *node) {vector<pair<uint8_t, uint8_t>> mask = get_search_nodes(node);for (auto pos:mask) {Node *n = new Node(node, pos.first, pos.second);node->children.insert(n);openTable.push_front(n);}return mask.size();}static bool is_alpha_beta_cut(Node *node) {if (node == nullptr || node->father == nullptr) return false;if (node->is_max_node() && node->value > node->father->value) return true;if (!node->is_max_node() && node->value < node->father->value) return true;return is_alpha_beta_cut(node->father);}static void update_value_from_node(Node *node) {if (node == nullptr) return;if (node->children.empty()) {update_value_from_node(node->father);return;}if (node->is_max_node()) {int32_t cntValue = INT32_MIN;for (Node *n : node->children)if (n->value != INT32_MAX) cntValue = max(cntValue, n->value);if (cntValue > node->value) {node->value = cntValue;update_value_from_node(node->father);}} else {int32_t cntValue = INT32_MAX;for (Node *n : node->children)if (n->value != INT32_MIN) cntValue = min(cntValue, n->value);if (cntValue < node->value) {node->value = cntValue;update_value_from_node(node->father);}}}void set_next_pos() {nodeNext = *nodeRoot->children.begin();for (Node *n : nodeRoot->children)if (n->value > nodeNext->value) nodeNext = n;}static void recursive_print(Node *nodeFatherPt) {nodeFatherPt->print_info();for (Node *nodeChildPt : nodeFatherPt->children) recursive_print(nodeChildPt);}void debug_print() {nodeRoot->print_info();for (Node *nodeChild : nodeRoot->children) recursive_print(nodeChild);cout << endl;}public:GameTree() = default;explicit GameTree(uint32_t maxDepth, uint8_t expandRadius) : maxDepth(maxDepth), expandRadius(expandRadius) {}explicit GameTree(uint32_t maxDepth, uint8_t expandRadius, uint8_t (&board)[15][15]) :maxDepth(maxDepth), expandRadius(expandRadius) {memcpy(nodeRoot->board, board, sizeof(board));}uint8_t game() {uint8_t result = nodeRoot->board_identify();if (result == 'B') return 'B';if (result == 'W') return 'W';openTable.push_back(nodeRoot);while (!openTable.empty()) {Node *node = openTable.front();openTable.pop_front();closedTable.push_back(node);if (is_alpha_beta_cut(node->father)) continue;if (node->depth < maxDepth) {uint8_t numExpand = expand_children_nodes(node);if (numExpand != 0) continue;}node->evaluate();update_value_from_node(node);}set_next_pos();return 0;}pair<uint8_t, uint8_t> get_next_pos() {if (nodeNext == nullptr)return pair<uint8_t, uint8_t>(255, 255);elsereturn pair<uint8_t, uint8_t>(nodeNext->cntX, nodeNext->cntY);}void show_next_pos() {if (nodeNext == nullptr)cout << "(255, 255)" << endl;elsecout << "(" << (uint32_t) nodeNext->cntX << "," << (uint32_t) nodeNext->cntY << ")" << endl;}void show_board(bool reverse) {if (nodeNext == nullptr) nodeNext = nodeRoot;uint8_t row = 0;cout << " 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4" << endl;for (uint8_t i = 0; i < 15; i++) {if (row < 10) cout << " ";cout << uint32_t(row++) << " ";for (uint8_t j = 0; j < 15; j++) {if (j != 0) cout << "─";if (nodeNext->board[i][j] == 'B') {if (reverse) cout << "●"; else cout << "○";continue;}if (nodeNext->board[i][j] == 'W') {if (reverse) cout << "○"; else cout << "●";continue;}if (i == 0 && j == 0) {cout << "┌";continue;}if (i == 0 && j == 14) {cout << "┐";continue;}if (i == 14 && j == 0) {cout << "└";continue;}if (i == 14 && j == 14) {cout << "┘";continue;}if (i == 0) {cout << "┬";continue;}if (i == 14) {cout << "┴";continue;}if (j == 0) {cout << "├";continue;}if (j == 14) {cout << "┤";continue;}cout << "┼";}cout << endl;}cout << endl;}
};void machine_human_play() {cout << endl;uint32_t x = 0, y = 0;uint8_t board[15][15]{};for (uint8_t k = 0; k < 225; k++) {GameTree gt = GameTree(9, 2, board);uint8_t result = gt.game();if (result == 'B') {cout << "Black Win !" << endl;gt.show_board(false);return;}if (result == 'W') {gt.show_board(false);cout << "White Win !" << endl;return;}gt.show_next_pos();gt.show_board(false);auto pos = gt.get_next_pos();if (pos.first != 255 && pos.second != 255) board[pos.first][pos.second] = 'B';do {cin >> x >> y;} while (board[x][y] != 0);board[x][y] = 'W';}
}void machine_machine_play() {cout << endl;uint8_t turn = 'B', board[15][15]{}, inputBoard[15][15]{};for (uint8_t k = 0; k < 225; k++) {cout << "[" << k + 1 << "] ";memcpy(inputBoard, board, sizeof(board));if (turn == 'W')for (uint8_t i = 0; i < 15; i++)for (uint8_t j = 0; j < 15; j++) {if (board[i][j] == 'W') inputBoard[i][j] = 'B';if (board[i][j] == 'B') inputBoard[i][j] = 'W';}GameTree gt = GameTree(8, 2, inputBoard);uint8_t result = gt.game();if (turn == 'W' && result != 0) {if (result == 'B') cout << "White Win !" << endl;if (result == 'W') cout << "Black Win !" << endl;gt.show_board(true);return;}if (turn == 'B' && result != 0) {if (result == 'B') cout << "Black Win !" << endl;if (result == 'W') cout << "White Win !" << endl;gt.show_board(false);return;}auto pos = gt.get_next_pos();if (turn == 'B') {turn = 'W';board[pos.first][pos.second] = 'B';cout << "Black ";gt.show_next_pos();gt.show_board(false);} else {turn = 'B';board[pos.first][pos.second] = 'W';cout << "White ";gt.show_next_pos();gt.show_board(true);}}
}int main() {machine_human_play();
// machine_machine_play();return 0;
}
参考文献
-
百度百科《五子棋》词条 ↩︎
-
董红安.计算机五子棋博奕系统的研究与实现[D].山东师范大学,2005. ↩︎ ↩︎
-
张明亮,吴俊,李凡长.五子棋机器博弈系统评估函数的设计[J].计算机应用,2012,32(07):1969-1972+1990. ↩︎
-
刘瑞.五子棋人工智能算法设计与实现[D].华南理工大学,2012. ↩︎