一种自学习的智能五子棋算法的设计与实现

李大舟，沈雪雁，高 巍，张小明，孟智慧，2

1(沈阳化工大学计算机科学与技术学院，沈阳110142)

2(中国移动集团设计院有限公司河北分公司，太原030000)

1 引 言

五子棋起源于中国古代的传统黑白棋种之一，属于一种策略性的游戏类型.在现代，日本将五子棋称为“连珠”，而其常见的英文名称为“Gobang”或者“Five in a row”(其缩写形式为FIR)，五子棋在中国还演变出了“五目”、“五子连”等一些名称、五子棋游戏实际的规则非常简单，而且游戏过程中的变化也比较多，入门非常容易，因此，受到了广泛的喜爱［1］.由于五子棋游戏有很大的分支因素，采用暴力搜索得到结果的方法往往会使得搜索树的深度非常大，这不仅仅会使得耗时巨大，并且计算机的性能很难满足需要.因此，想在计算资源有限的短时间内找出一种必胜的策略显然是件非常困难的事情.而使用蒙特卡洛树搜索对五子棋对弈进行模拟，不需要穷举所有组合，就可以找到最优或者次优的移动方案.

本文将探究基于蒙特卡洛树搜索与深度神经网络的智能五子棋算法的实现过程，本算法完全由自对弈强化学习训练，从随机游戏开始，没有任何监督或使用人类数据，只使用五子棋棋盘上的棋子状态作为输入特征，并且使用单一的深度神经网络，而不是单独的策略和价值网络.本算法使用蒙特卡洛树搜索依赖于这个单一深度神经网络来评估落子位置和样本移动，从而选择最有价值的落子方式.

本算法训练过程主要分为三个阶段:自我对弈阶段，训练深度神经网络阶段和评估深度神经网络阶段.

1)自我对弈阶段:实验在自我对弈阶段产生大量棋局样本作为训练数据用于后续神经网络的训练.在自我对弈阶段，每一步落子由蒙特卡洛树搜索完成，将蒙特卡洛树搜索得到的落子策略与最终的胜负奖励用于训练深度神经网络.

2)训练深度神经网络:通过训练深度神经网络，优化深度神经网络的参数，用于后续指导蒙特卡洛树搜索过程.

3)评估深度神经网络:自我对弈的双方各自使用自己的深度神经网络指导蒙特卡洛树搜索并对战，检验本算法在新的深度神经网络参数下的棋力是否得到提升.

2 相关研究

随着人工智能近几年的飞速发展，人工智能成为了许多国家的重点研究项目.最优化策略是人工智能研究的一个分支，博弈论则是其代表性算法，许多研究者把博弈论应用到各种棋类游戏中.2018 年孙世文使用了极大极小值算法对整个博弈树的搜索全过程进行了优化处理，针对五子棋的智能算法思路进行了探究和优化［2］.2019 年宋万洋采用 α-β 剪枝树算法实现设计并研发了一种基于智能算法的安卓五子棋应用程序，程序具有较高智能程度，能够击败大多数业余选手［3］.

蒙特卡洛树搜索可以较为有效地解决一些探索空间巨大的问题，一般的围棋算法都是基于蒙特卡洛树搜索实现的，AlphaGo Zero 用的就是蒙特卡罗树搜索算法的一种.2011 年Sylvain Gelly 等人基于蒙特卡罗模拟的新搜索范例彻底改变了计算机围棋计划的性能，并在理论上和实践中首次全面描述了蒙特卡罗树搜索的扩展框架［4］.2012 年 Vien 等人研究了一种基于蒙特卡洛树搜索算法的大型POMDPs 在线学习算法，用于解决贝叶斯强化学习问题［5］.2018 年Chenjun Xiao等人提出了记忆增强的蒙特卡洛树搜索方法，提供了利用在线实时搜索的泛化能力的新方法.

在 2016 年 3 月，DeepMind 研发的 AlphaGo 以 4:1 的成绩，击败了曾荣获18 次世界冠军的围棋选手李世石［6］.在2017 年 10 月 18 日，DeepMind 又再次取得了突破，揭示了一种新的算法——AlphaGo Zero，它以100:0 的成绩打败了AlphaGo［7］.并且完全从零开始，通过自我博弈，逐渐学会了能打败自己之前的策略.至此，开发一个超级AI 不再需要依赖人类专家的游戏数据库了.仅48 天后的2017 年12 月5日，DeepMind 又展示了AlphaGo Zero 如何能够学会国际象棋和象棋.整个学习过程，从第一次参与游戏到成为世界上最厉害的计算机程序，只用了24 小时［8］.

随着AlphaGo 的成功，强化学习成为了当下机器学习中最热门的研究领域之一.2018 年Xingyu Wang 等人提出在已知专家证明不是最优的时候，在零和随机博弈中进行逆强化学习;引入了一种新的目标函数，直接将专家与纳什均衡策略对立起来，以深度神经网络作为模型逼近，在逆强化学习的背景下求解奖励函数［9］.同年，Rachit Dubey 等人提出调查各种有助于人类学习的先验知识，并发现对象的一般先验在指导人类游戏玩法中起着最关键的作用［10］.2019 年，Andre Barreto 等人使用通用的策略改进和继承特性来进行传输技能，以两种方式扩展了 SF 和 GPI 框架［11］.

3 工作原理

本算法主要包括两部分:蒙特卡洛树搜索与深度神经网络.蒙特卡洛树搜索通过自我对弈进行五子棋游戏，将游戏过程中产生的棋盘数据作为深度神经网络的训练数据.棋盘上每个位置的落子概率以及获胜概率会随着蒙特卡洛树搜索的不断执行而趋于稳定，其与深度神经网络输出的落子概率和胜率之差构成损失函数.深度神经网络对于落子概率和获胜概率的估算将随着训练的不断进行越来越准确.在之后的对局中，深度神经网络可以达到蒙特卡洛树搜索的模拟效果，估算出在游戏中未模拟过下法的获胜概率.

3.1 蒙特卡洛树搜索

通过给定的一个游戏状态来选择最佳的下一步是蒙特卡洛树搜索的主要目标.一组沿着博弈树向下的遍历过程即为搜索，是蒙特卡洛树搜索的主要概念.蒙特卡洛树搜索根据多次模拟博弈的结果预测出最优的移动方案.其中单次遍历的路径以当前博弈状态作为根节点，延伸到子节点至少有一个未被访问到的未完全展开的节点.此时其中一个未被访问的子节点将会作为单次模拟的根节点，随后模拟的结果将会反向传播回当前树的根节点并更新博弈树的节点统计数据.当受限于计算力或时间搜索终止，下一步行动将基于收集到的统计数据进行决策.

本文在实际实验过程中将五子棋棋盘大小设置为15×15 的标准五子棋棋盘.为方便算法讲解，以棋盘大小为7×7的五子棋对局为例，深度神经网络记作fθ，假设当前游戏状态为s，fθ根据当前游戏状态输出一个动作概率向量 p，表示五子棋盘上每个位置的落子概率;以及一个估值标量v，对应当前游戏状态的获胜概率.蒙特卡洛树搜索以p 和v 作为搜索方向依据，既降低了其时间复杂度，也使得强化学习在训练过程中的稳定性得以提升.

针对棋盘大小为7×7 的一个五子棋对局，其游戏状态对应的蒙特卡洛树搜索流程如图1 所示.将当前五子棋对局的游戏状态s 作为根节点，从根节点开始选择一个落子动作到达叶子节点，其中，节点访问次数C(s，d)、累计行动价值E(s，d)、平均行动价值 Q(s，d)、先验概率 P(s，d)这四个值储存在节点与节点之间的边r(s，d)中.在整个搜索过程中具体分为以下四个阶段:选择阶段、展开与评估阶段、回传阶段，最后执行阶段通过蒙特卡洛树搜索γθ得到落子概率分布π.

3.1.1 选择阶段

从图1 中所示初始五子棋游戏状态s0作为根节点，选择一个落子动作d 进行走子.其中Q(s，d)+U(s，d)取值最大的动作d 将被蒙特卡洛树搜索选择为搜索路径.第一步选择最大值为0.207 的动作d，第二步选择最大值为0.326 的动作d，如图1 中选择阶段所示.其中相关公式如式(1)、式(2)所示.

其中，本文将超参数cpuct设定为1，用来平衡分配搜索过程中探索与利用之间的权重［7］，搜索树会在这个值较大时趋向于向未模拟过的落子点探索，在其较小时则会快速收敛.这种搜索方式最初会倾向于先验概率P(s，d)较高和节点访问次数C(s，d)较低的落子动作，之后会渐渐倾向于平均行动价值Q(s，d)较高的落子动作.式中∑bC(s，b)表示根节点的访问次数;C(s，d)表示当前叶子节点的访问次数;P(s，d)为深 度神经网络fθ(s)的策略输出对应动作d 的概率值.

图1 蒙特卡洛树搜索流程示例Fig.1 Example of the monte carlo search tree process

3.1.2 展开与评估阶段

根节点s0经过选择一系列的落子动作d 到达叶子节点st，然后对叶子节点 st进行展开与评估.由深度神经网络fθ(st)输出当前叶子节点st对应的策略输出pt和估值输出vt，其中pt向量是当前叶子节点st每个合法落子动作d 的走子概率，存储在st的所有边中.然后将st的边r(st，d)中的访问次数、累计行动价值、平均行动价值以及先验概率值初始化，即:C(st，d)=0，E(st，d)=0，Q(st，d)=0，P(st，d)=pt.

3.1.3 回传阶段

深度神经网络fθ(st)对当前叶子节点st的估值输出vt在其展开与评估阶段完成后可以获取到.在从根节点s0经过一系列落子动作到达叶子节点st的路径中，每次走子之后，存储在节点与节点之间边的信息在路径中进行反向更新.访问次数 C(st，dt)、累计行动价值 E(st，dt)、平均行动价值Q(st，dt)的具更新方式如式(3)、式(4)、式(5)所示:

由图1 中回传阶段可见，在该示例中 Q 的值更新为0.027 回传给根节点.

3.1.4 执行阶段

本文设置在五子棋对局中每步走子进行300 次蒙特卡洛树搜索.在多次搜索后，整个过程中产生的所有数据信息会存储在树中边r(st，d)中，落子概率分布π(d|s0)可以根据这些数据信息得到.这个落子概率分布与根节点s0的访问次数C(s0，d)的关系如下所示:

在本算法中，用来控制蒙特卡洛树搜索的探索水平由τ来控制，初始值设置为1.这个参数在自我对弈阶段早期鼓励探索的进行，随着游戏的进行，τ 的值逐渐降至零，此时会产生根据蒙特卡洛树搜索评估在五子棋对局选择最佳移动的策略.在落子动作执行完毕后，下一轮蒙特卡洛树搜索将以扩展节点作为新的根节点重复上述阶段.

3.2 深度神经网络

3.2.1 深度神经网络的结构

在本算法中只含有一个深度神经网络fθ，这个网络结合了策略网络和估值网络，其结构是由卷积神经网络组成的深度残差网络.随着网络深度的增加，使用一般卷积神经网络往往会出现梯度弥散或者梯度爆炸以至于无法收敛以及网络退化误差增大的问题［12，13］.本算法使用的深度残差网络含有32个卷积层，每个残差块跨越两个卷积层，整个网络包含输入层、卷积层、15 个残差块、全连接层与输出层，其网络模型的整体结构如图2 所示.

图2 深度残差网络模型图Fig.2 Deep residual network model

在深度残差网络的输入层，输入包含了五子棋对局中当前行棋方的信息以及黑棋和白棋最近五步行棋状态，数据类型为7×7×11 的0/1 矩阵.可以把0/1 矩阵直接输入到深度残差网络中，无需进行归一化操作.

其中卷积层和残差块对数据的处理主要分为以下五个阶段:

第一阶段:棋盘数据进入卷积层1，这里的卷积运算使用32 个大小为5×5，步长为1 的卷积核，用来提取较大范围的五子棋盘特征.为了防止边缘数据的丢失，棋盘数据在卷积层1 首先进行边缘为2 的零扩展处理，得到大小为11×11×11的训练数据.在之后的每个卷积层后面需要归一化处理数据，再使用Relu 激活函数.

第二阶段:此阶段由5 个残差块组成，数据在残差块1 ～5 中的每个卷积层都需进行边长为1 的零扩展，将数据填充至9×9×11 大小.这阶段的卷积运算使用64 个大小3×3，步长为1 的卷积核.

第三阶段:此阶段由5 个残差块组成，数据在残差块6 ～10 中每个卷积层进行边长为1 的零扩展，将数据填充至9×9×11 大小.这一阶段的卷积运算使用128 个大小3×3，步长为1 的卷积核.

第四阶段:此阶段由5 个残差块组成，棋盘数据在残差块11 ～15 中的每个卷积层都需进行边长为1 的零扩展，将数据填充至9×9×11 大小.在这一阶段的卷积运算使用256 个大小3×3，步长为1 的卷积核.

第五阶段:归一化处理深度残差网络的残差区域结束后输出的数据，然后再接入卷积层2.在卷积层2 的卷积运算使用1 个大小为1×1，步长为1 的卷积核，对输出数据进行降维，降维后为7×7×1 大小的数据矩阵.

在深度残差网络的全连接与输出部分，输出端分为策略端与估值端，使用非线性函数softmax 的全连接层在策略端直接输出棋盘上每个位置落子概率，对应大小为7×7 五子棋盘上的49 个落子点.使用双曲正切函数tanh 的全连接层在估值端，输出-1 到1 之间的实数，对应五子棋当前对局盘面获胜的概率.

3.2.2 深度神经网络的训练流程

深度神经网络fθ将当前五子棋游戏棋盘数据以及历史棋盘数据作为输入，并将棋盘状态转换为矩阵输入，如图3 所示.如果当前是黑方行棋，则当前有黑棋的点取值1，有白棋或者没有棋子的位置取值为0;反之，如果当前是白方行棋，则当前有白棋的点取值1，有黑棋或者没有棋子的位置取值0.然后输出动作概率分布p 和对应的估值v.p 表示五子棋盘上每个位置的落子概率，v 对应当前游戏状态的获胜概率.

蒙特卡洛树搜索可以被视作是一个策略提升算子.对于每个状态s，原本的深度神经网络fθ本身输出了一个动作概率分布p，然后蒙特卡洛树搜索基于该网络，再输出一个概率分布π.由蒙特卡洛树搜索定义可知新的概率分布π 较p 会选择更强的动作.同时，然后蒙特卡洛树搜索也可以被视作是一个估值提升算子.在一次模拟棋局结束时，蒙特卡洛树搜索会输出一个输赢结果Z，以最小化fθ输出的价值v 与Z 的误差来更新深度神经网络.在本算法中自我对弈与深度神经网络的训练流程如图4、图5 所示.

图3 棋盘数据处理Fig.3 Checkerboard data processing

其中自我对弈训练的流程如图4 所示:程序自我博弈，从第一步到第 T 步标记状态为 s1，s2，…，sT.在第 t 步 st，使用最新的神经网络fθ执行一次蒙特卡洛树搜索γθ(如图1 执行阶段所示).每个走子选择的依据是通过蒙特卡洛树搜索得出的概率πt.在最终的位置第T 步sT根据游戏规则计算对局的最终胜者Z.

图4 自我对弈流程Fig.4 Process of self-play

本算法中深度神经网络的训练过程如图5 所示:当前五子棋对局的棋盘状态为st，将其输入fθ，通过32 个卷积层，fθ会输出在五子棋盘上每一走子的概率分布的向量pt以及一个估值标量vt表示当前玩家在位置st上的获胜概率.深度神经网络的参数θ 将自动更新，以最大化策略向量pt和搜索概率πt的相似性，以及最小化预测获胜概率vt与实际赢家Z的误差.下一次自对弈迭代中将使用新参数θ.

其中损失函数loss 由两部分组成，第一部分为深度神经网络fθ的估值输出vt与蒙特卡洛树搜索所得的胜负结果Z的均方和误差，第二部分为fθ的策略输出pt和蒙特卡罗树搜索的策略πt的交叉信息熵误差.为了进一步优化深度神经网络fθ的权值，需要在深度神经网络的每步输出并行反向传播.其中参数θ 通过损失函数loss 的梯度下降来调整.损失函数loss 的具体公式如式(7)、式(8)所示，其中c 是控制L2 权重正则化水平的参数(防止过拟合):

图5 深度神经网络训练流程Fig.5 Deep neural network training process

4 算法实现过程

4.1 运行环境

本实验在运行内存为16.0GB，配置为NVIDIA GeForce GTX 1060，Intel(R)Core(TM)i5-8300H CPU @2.3GHz 的台式设备上实现.代码通过 TensorFlow 实现，共包含12 个 py文件.

4.2 算法实现

4.2.1 设置游戏规则进行自我对弈

本文将游戏规则设置为在大小为15×15 的标准五子棋棋盘上进行五子棋对局，每次落子进行300 次蒙特卡洛树搜索.在实验中设置best_player 和current_player 两个智能体，其中best_player 通过自我对弈生成记忆，并且使用当前最佳的深度神经网络模型.current_player 可以在best_player 生成的记忆上重新训练它的深度神经网络，然后再与best_player对局.如果current_player 获胜，best_player 内部的深度神经网络将与current_player 内部的深度神经网络进行转换，然后进行下一次迭代.

在实验的第一阶段，通过蒙特卡洛树搜索进行自我对弈收集第一批棋盘数据，每次迭代使用蒙特卡洛树搜索进行200 局五子棋对局.此时由于没有深度神经网络的指导，对局中落子策略为均等概率的随机投子.因此，第一批通过自我对弈收集到的棋盘数据棋力水平是比较差的.

4.2.2 训练深度神经网络生成模型

使用第一阶段自我对弈收集到的棋盘数据作为训练数据训练神经网络.将棋盘状态转换为矩阵输入，如果当前是黑方行棋，则当前有黑棋的点取值1，有白棋或者没有棋子的位置取值为0;反之，如果当前是白方行棋，则当前有白棋的点取值1，有黑棋或者没有棋子的位置取值0，如图3 所示.

best_player 通过使用训练好的深度神经网络模型进行自我对弈，在对弈结束后使用收集到的棋盘数据更新深度神经网络参数θ.在多次迭代中，参数θ 通过不断最大化策略向量pt和搜索概率πt的相似性以及最小化估值vt与实际赢家Z的误差不断更新，使得深度神经网络输出的落子概率pt和评估值vt能够越来越接近能够把五子棋局赢下的落子方式.经过两天的训练，可以得到损失与当前迭代次数的关系图，如图6 所示.其中策略损失表示pt与πt的交叉熵，价值损失表示vt与Z 之间的均方误差，平均损失则为两者的平均值.

4.2.3 评估深度神经网络模型

实验中使用比赛的形式对当前神经网络模型进行评估.current_player 与执行当前最佳的神经网络模型的best_player在每次迭代后进行对弈，设置对弈局数为20 局，获胜一局得一分，然后统计两者获得总积分.如果current_player 积分较高，best_player 内部的深度神经网络将被转换为current_player 内部的深度神经网络，然后进行下一次迭代.实验中前三次迭代后的评估结果如表1 所示.

图6 损失与迭代次数的关系图Fig.6 Graph of loss and number of iterations

表1 评估深度神经网络模型Table 1 Evaluate the deep neural network model

5 实验结果分析

经过两天的训练，深度神经网络在预测五子棋游戏状态的值以及可能的下一步移动中逐渐变的更好.从深度神经网络的第一次迭代到第28 次，随着深度神经网络参数θ 的更新，共生成了28 个深度神经网络模型.为了说明本算法在五子棋领域如何变得越来越强大，在28 个深度神经网络模型中，从初始深度神经网络模型1 开始，每隔两个挑选一个组成比赛，一直到模型28，共挑选10 个，每组比赛两次，玩家1 和玩家2 随机优先落子，计算最后得分(score)，结果如表2 所示.

表2 比赛积分表Table 2 Game score

从表2 中可以看出，随着训练时间的增长，在挑选出的10 个深度神经网络模型中，模型28 在五子棋游戏中的表现要明显优于最初的深度神经网络模型，在五子棋对局中获得了大部分的胜利.这个学习过程并没有达到极限，本算法在五子棋游戏中的表现将会随着训练时间的进一步增长变得越来越强，学习越来越复杂的落子策略.

以往的智能五子棋算法主要通过极大极小值搜索算法和Alpha-Beta 剪枝算法进行实现，可以击败大多数的业余选手.将实验过程中得到的28 个深度神经网络模型与基于极大极小值算法的智能五子棋算法以及基于Alpha-Beta 剪枝算法的智能五子棋算法通过五子棋对局的方式进行比较，设置对局数为20，观察对局结果，记录深度神经网络模型获胜局数，如表3 所示，可以看出从模型16 开始，深度神经网络模型在与两种智能五子棋算法的20 个对局中已经能够取得较大优势，模型25 与28 则以明显优势赢得了大部分的对局.

表3 三种算法对比Table 3 Three algorithms are compared

在正规的五子棋比赛中，一般将规则制定为五局三胜制，即在五局比赛中，首先赢得三局的一方取得胜利.以此制度对三种算法进行二次比较，其结果如表4 所示，可以看出在五局三胜的比赛制度下，深度神经网络模型取得了更好的成绩，从模型13 到28，均获得了比赛的胜利.

表4 五局三胜制比赛结果Table 4 Result of the best-of-five game

本实验使用埃洛等级分(Elo)对基于蒙特卡洛树搜索与深度神经网络的智能五子棋算法的五子棋水平进行评分.其训练时间与Elo 等级分的变化趋势如图7 所示.仅仅经过40小时的训练，本算法的五子棋等级分已经达到了4000 分左右，远远高于普通人类水平.

6 总 结

本文基于蒙特卡洛树搜索与深度神经网络设计并实现了一种自学习的智能五子棋算法.通过蒙特卡洛树搜索进行自我对弈，在没有人类五子棋游戏经验的前提下，从零开始，蒙特卡洛树搜索使用深度神经网络评估落子位置和选择移动，提高树搜索的强度，使落子质量更高，自对弈迭代更强.将训练过程中得到的模型组成比赛，可以看到随着训练时间的增长，模型效果越来越好.经过两天的训练，本算法的埃洛等级分已经达到4000 分，远远高于了普通人类水平.在以后的研究中，这种干净、稳定的学习算法可以应用到更多离散型的游戏当中.并且随着人工智能领域的飞速发展，越来越多的人工智能达到甚至远远超过人类水平，相信以后会有更强大智能的算法出现并应用到人类的生活中.

图7 Elo 等级分与训练时间关系图Fig.7 Diagram of the relationship between Elo rating system and training time