基于博弈树的五⼦棋AI算法及其C++实现
基于博弈树的五⼦棋 AI 算法及其 C++ 实现
摘要
五⼦棋是⼀个风靡全国的棋类游戏，本⽂研究五⼦棋的博弈树算法，并编程实现该算法。本⽂介绍了博弈树的极⼤极⼩搜索算法和α-β剪枝优化技术，并提出了⾃⼰的估价函数。本⽂采⽤C++编程，并⽤类封装代码，⽅便外部调⽤。本⽂展⽰了⼀个⼈机对弈过程的实例和⼀个机机对弈过程的实例，实践证明该算法已经具有较⾼的业余级⽔平，但对复杂局⾯的判断还不理想。本⽂最后给出了作者的感悟。 关键词：五⼦棋 博弈树 α-β剪枝 估价函数
⼀五⼦棋的游戏规则
五⼦棋（Five In A Row，FIR）是全国智⼒运动会竞技项⽬之⼀，是⼀种两⼈对弈的纯策略型棋类游戏。五⼦棋不仅能增强思维能⼒，提⾼智⼒，⽽且富含哲理，有助于修⾝养性，在各⼤游戏平台都有应⽤，主要流⾏于东亚以及欧洲的⼀些国家。著名的五⼦棋⼿有中国的吴侃、吴镝、戴晓涵、祁观、曹冬和⽇本的中村茂等。
标准的五⼦棋盘由横纵各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）mica martinez
◆ 从节点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节点，其α值⼤于等于其⽗节点的β值，则可以将以当前节点为根节点的⼦树剪枝，该剪枝称为“β剪枝”；
根据上述对α-β剪枝规则的定义，我们知道，在博弈树搜索过程中，第⼀次剪枝属于β剪枝，第⼆次剪枝属于α剪枝，已在图7中标注。
2.3 估价函数
从上⽂的叙述中可以看出，估价函数的好坏直接影响了决策树的搜索过程和路径判断，所以估价函数的定义⾄关重要。在同⼀个应⽤场景中，不同学者定义的估价函数往往都不⼀样，这也就导致决策树的效率和正确率都有很⼤偏差。
张明亮等学者在《五⼦棋机器博弈系统评估函数的设计》⼀⽂中指出，“因五⼦棋先⼿优势⼤，评估函数分为先⼿和后⼿两类：先⼿时加重⼰⽅⾮关键棋型分值，相当于加重进攻招法的分值；后⼿则加重对⼿棋型分值，相当于加重计算机防守招法的分值，道理是利⽤局势的发展趋势稍作引导，实验效果很好，明显加快后⼿棋的搜索，表明起到了优化博弈树的作⽤。”⽽学者董红安使⽤的估价函数⾮常简单，考虑的是每个“五元组”中棋⼦的状态。学者刘瑞使⽤的估价函数也是考虑每个“五元组”，但设计的规则要略复杂⼀些。
本⽂参考前⼈对于估价函数的设计⼯作，提出了⾃⼰的估价函数。
⾸先，我们给出“五元组”的定义。五元组指棋盘上连续的五个位置，包括横向、纵向、主对⾓线⽅向、副对⾓线⽅向，⼀共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，则
三 五⼦棋对弈的算法实现
上⼀章中，我们叙述了五⼦棋对弈的算法思想，本章我们叙述其编程实现。我们采⽤C++语⾔编写程序，代码遵循C++17标准。
数据结构主要是两个类，⼀个Node类表⽰⼀个节点，⼀个GameTree类表⽰⼀棵博弈树。显然，⼀个GameTree类中含有多个Node类。全部的变量和函数都封装在GameTree类中，⽅便外部调⽤。并且GameTree类提供了cmd命令⾏窗⼝的可视化对弈功能，可进⾏⼈机对弈。S =score (w )w ∈W ∑螺钉连接
下⾯，我们将详细介绍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<15and j +4<15){
s =以(i,j)开头的主对⾓线⽅向五元组;
value +=evaluate_black(s) – evaluate_white(s);
}
if(i +4<15and j -4>=0){
s =以(i,j)开头的副对⾓线⽅向五元组;
value +=evaluate_black(s) – evaluate_white(s);
}
}
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议