基于博弈树的五子棋 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）

◆ 从节点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中五元组的符号表示

对于每个五元组，我们定义评分规则如下：

（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=\sum _{w\in 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类的成员变量

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);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

◆ 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3.2 GameTree类

GameTree类记录了一棵博弈树的所有信息，包括搜索半径、最大深度、根节点指针、最佳节点指针、open表、closed表，并提供了博弈控制函数、节点扩展函数、α-β更新函数、α-β剪枝判断函数等。此外，GameTree类还提供了cmd命令行窗口的可视化功能。

GameTree类的成员变量中，只保存了一个指向根节点的指针，所有节点间的关系均使用指针来刻画。

3.2.1 成员变量

Node类的成员变量定义如表3所示。

表3   GameTree的成员变量

3.2.2 成员函数

本节介绍GameTree类的成员函数。对于核心成员函数，我们将详细介绍，并给出实现的伪代码，对于非核心成员函数，我们只简要说明其用途。此外，实现可视化功能的成员函数将在下一章中说明。

◆ set_next_pos()

在完成博弈树的搜索过程后，该函数负责寻找下一步的最佳落子点，即寻找根节点的最佳子节点。该函数的伪代码如下：

void set_next_pos() {
    nodeNext = nodeRoot的第一个子节点;
    for (n in nodeRoot的所有子节点)
        if (n的值 > nodeNext的值) nodeNext = n;
}
1
2
3
4
5

◆ 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();                    //寻找最佳节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

◆ 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();
}
1
2
3
4
5
6
7
8
9

◆ 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

◆ 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); //判断其父节点是否能剪枝
}
1
2
3
4
5
6

◆ 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);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

四   五子棋对弈过程

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

代码使用非常简单，如要“人机对弈”，只要在main函数中注释掉机机对弈的调用即可，即

int main() {
    machine_human_play();
    //machine_machine_play();
    return 0;
}
1
2
3
4
5

同理，如要观看“机机对弈”，只要在main函数中注释掉人机对弈的调用即可，即

int main() {
    //machine_human_play();
    machine_machine_play();
    return 0;
}
1
2
3
4
5

图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);
        else
            return pair<uint8_t, uint8_t>(nodeNext->cntX, nodeNext->cntY);
    }

    void show_next_pos() {
        if (nodeNext == nullptr)
            cout << "(255, 255)" << endl;
        else
            cout << "(" << (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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433

参考文献

---

1. 百度百科《五子棋》词条 ↩︎

2. 董红安.计算机五子棋博奕系统的研究与实现[D].山东师范大学,2005. ↩︎ ↩︎

3. 张明亮,吴俊,李凡长.五子棋机器博弈系统评估函数的设计[J].计算机应用,2012,32(07):1969-1972+1990. ↩︎

4. 刘瑞.五子棋人工智能算法设计与实现[D].华南理工大学,2012. ↩︎