基于博弈树的五子棋 AI 算法及其 C++ 实现 |
您所在的位置：网站首页 › c++象棋布局系统设计 › 基于博弈树的五子棋 AI 算法及其 C++ 实现 |
基于博弈树的五子棋 AI 算法及其 C++ 实现
|
基于博弈树的五子棋 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）开局前，双方确定执子颜色； （2）空棋盘开局； （3）黑子先手； （4）黑白交替下子，每次下一子，只能下在空白的交叉点处； （5）下子后不能悔棋，也不能移动任何棋子； （6）某方达成“五子连线”，则该方获胜，游戏结束； （7）棋盘上没有落子点，且双方均没有“五子连线”，则平局，游戏结束； 二 五子棋对弈的算法描述五子棋是一个双方对弈的游戏，我们称执黑子的一方为“黑方”，执白子的一方为“白方”。对于当前棋局，我们的目的是找到一个最佳的落子点，使得我方的胜算最大。这也是本算法的目的，确定下一步的落子点，使得我方胜算最大。为了判断到底落子何处才能使胜算最大，我们需要往后多推算几步，包括推算我方落子和对方落子，模拟出可能出现的棋局，从这些棋局中选出胜算最大的那个棋局，进而确定下一步的最佳落子点。 本算法始终认为计算机是黑方，如果计算机是白方，我们可以反转棋盘上所有的黑白棋子，这样计算机就变成了黑方。本算法的输入是一个棋局，输出的是下一步的落子点坐标。 2.1 博弈树搜索算法可以看出，该推算过程本质上就是一个搜索算法。具体来说，对于当前棋局，我方有许多种落子方法，对于我方的每种落子方法，对方又有许多种落子方法，而对于对方的每种落子方法，我方又有许多种落子方法……这样，往后多推算几步，有利于看清当前棋局中的最佳落子点和潜在威胁。
如图2所示，在当前棋局1，有两颗白子，现在是黑方回合。黑方可以落子形成棋局2，也可以落子形成棋局3。如果黑方落子形成棋局2，则白方可以落子形成棋局4和棋局5，如果黑方落子形成棋局3，则白方可以落子形成棋局6和棋局7。 黑白双方都会选择对自己最有利的落子点，站在黑方的角度，黑方下一步会使黑方的胜算最大，而白方的下一步会使黑方的胜算最小。该过程反映在搜索树中是这样的，若当前节点是黑方回合，则找一个对黑方最佳的落子点，若当前节点是白方回合，则找一个对黑方最差的落子点。 最佳落子点和最差落子点是一个很模糊的说法，我们需要量化最佳落子点和最差落子点，即对每种落子方法打分。具体来说，我们需要建立一套评分机制，该评分机制需要满足：对于任一棋局，该棋局对黑方越有利则分数越高，该棋局对黑方越不利则分数越低。对于某一棋局，黑白双方可能需要再下几十甚至上百步才能使游戏结束，这意味着搜索树的深度会达到几十甚至上百层。例如，每种棋局考虑10种落子方法，推算50步，则搜索树是一棵50层的十叉数，搜索量是巨大的。所以，我们的评分机制不仅要对已经结束的棋局进行打分，还要能估算未结束棋局的分数。我们把这个评分机制称为“估价函数”。 至此，算法的主题思想已叙述完毕。下面，我们结合一个实例将算法的主要步骤叙述一遍。
如图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；
◆ 从节点3继续，遍历过程：3→8，如图5所示。节点8达到最大深度，用估价函数得到f(8)=5。更新节点3得到f(3)≥5，更新节点1得到f(1)≤5，更新节点0得到f(0)≥5；
◆ 从节点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被剪枝掉了；
◆ 从节点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的子节点，这四个节点都被剪枝掉了；
◆ 至此，搜索过程全部结束，前往节点1是最优选择； 下面我们叙述一般情况的α-β剪枝规则： α剪枝：当前节点是MIN节点，其β值小于等于其父节点的α值，则可以将以当前节点为根节点的子树剪枝，该剪枝称为“α剪枝”； β剪枝：当前节点是MAX节点，其α值大于等于其父节点的β值，则可以将以当前节点为根节点的子树剪枝，该剪枝称为“β剪枝”； 根据上述对α-β剪枝规则的定义2，我们知道，在博弈树搜索过程中，第一次剪枝属于β剪枝，第二次剪枝属于α剪枝，已在图7中标注。 2.3 估价函数从上文的叙述中可以看出，估价函数的好坏直接影响了决策树的搜索过程和路径判断，所以估价函数的定义至关重要。在同一个应用场景中，不同学者定义的估价函数往往都不一样，这也就导致决策树的效率和正确率都有很大偏差。 张明亮等学者在《五子棋机器博弈系统评估函数的设计》一文中指出，“因五子棋先手优势大，评估函数分为先手和后手两类：先手时加重己方非关键棋型分值，相当于加重进攻招法的分值；后手则加重对手棋型分值，相当于加重计算机防守招法的分值，道理是利用局势的发展趋势稍作引导，实验效果很好，明显加快后手棋的搜索，表明起到了优化博弈树的作用。”3而学者董红安使用的估价函数非常简单，考虑的是每个“五元组”中棋子的状态。2学者刘瑞使用的估价函数也是考虑每个“五元组”，但设计的规则要略复杂一些。4 本文参考前人对于估价函数的设计工作，提出了自己的估价函数。 首先，我们给出“五元组”的定义。五元组指棋盘上连续的五个位置，包括横向、纵向、主对角线方向、副对角线方向，一共4个方向。图8展示了这4种五元组的形态，其中红色方框表示一个竖向五元组，黄色方框表示一个横向五元组，蓝色方框表示一个主对角线方向五元组，绿色方框表示一个副对角线方向五元组。
对于棋盘上每一个落子点，我们规定使用‘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 ∈ W s c o r e ( 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类的成员变量 变量名变量类型变量说明valueint32_t若当前节点是叶节点，记录的是估值得分；若当前节点是MAX节点，记录的是α值；若当前节点是MIN节点，记录的是β值；depthuint32_t记录当前节点的深度，根节点深度为0cntXuint8_t记录当前棋局最后一步落子点的x轴坐标cntYuint8_t记录当前棋局最后一步落子点的y轴坐标fatherNode*记录当前节点的父节点，是一个指针childrenset记录当前节点的子节点，使用STL的set容器，set中每一个指针都指向一个子节点boarduint8_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 s = 以(i,j)开头的竖向五元组; value += evaluate_black(s) – evaluate_white(s); } if (i + 4 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 s = 以(i,j)开头的竖向五元组; if (s == “BBBBB”) return ‘B’; //黑方获胜 if (s == “WWWWW”) return ‘W’; //白方获胜 } if (i + 4 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的成员变量 变量名变量类型变量说明expandRadiusuint8_t搜索半径，从当前节点向四周扩展的距离，扩展区域是一个正方形maxDepthuint32_t最大深度nodeRootNode*一个指向根节点的指针nodeNextNode*一个指向最佳节点的指针openTabledeque一个双向队列，存放待扩展节点的指针closedTabledeque一个双向队列，存放已扩展节点的指针 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)获取待扩展点集合，存入变量mask for (x,y) in mask { 新建节点n，节点n的属性根据其父节点node生成 在节点node的子节点中加入节点n 将节点n加入openTable的前端 } return mask.size(); }◆ get_search_nodes(Node *node) : vector 返回当前棋局的待扩展点坐标集合，返回一个vector容器，容器中每个元素都是一个pair，代表一个点的坐标。如图9所示的棋局中，所有黄点是当前棋局的待扩展点，一共32个点。
该函数的伪代码如下： vector 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 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的值 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 ...}; //博弈树算法的实现代码封装在该类中 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界面。
百度百科《五子棋》词条 ↩︎ 董红安.计算机五子棋博奕系统的研究与实现[D].山东师范大学,2005. ↩︎ ↩︎ 张明亮,吴俊,李凡长.五子棋机器博弈系统评估函数的设计[J].计算机应用,2012,32(07):1969-1972+1990. ↩︎ 刘瑞.五子棋人工智能算法设计与实现[D].华南理工大学,2012. ↩︎ |
【本文地址】
今日新闻 |
推荐新闻 |