基于博弈树的五子棋 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中五元组的符号表示
对于每个五元组,我们定义评分规则如下:
(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所示。
表2Node类的成员变量
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所示。
表3GameTree的成员变量
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].山东师范大学,. ↩︎ ↩︎
张明亮,吴俊,李凡长.五子棋机器博弈系统评估函数的设计[J].计算机应用,,32(07):1969-1972+1990. ↩︎
刘瑞.五子棋人工智能算法设计与实现[D].华南理工大学,. ↩︎