五子棋人工智能研究与实践
牛恺泽1，邓 鑫2
（1.北京交通大学附属中学分校，北京 100088；2.国家气象信息中心，北京 100081）
摘要：博弈问题是人工智能的一个重要分支。近年来，人机博弈问题取得了较大发展，尤其是人工智能程序Alphago击败著名围棋世界冠军的事迹，将此问题推向了新的高潮。五子棋问题是典型的博弈问题，本文对五子棋人工智能问题进行了研究，根据缩小搜索范围的思路对现有搜索算法进行了改进，并探究了估值函数的设计方法。实践结果表明，设计的算法在人机博弈过程中具有较高的博弈水平。
关键词：人工智能；五子棋；搜索；估值d o I：10.3969/J.ISSN.1672-7274.2019.01.015
中图分类号：TP18，G891 文献标示码：A 文章编码：1672-7274（2019）01-0058-03
1 引言
人工智能是一门研究如何利用计算机来模拟人类智能的学科，被认为是21世纪三大尖端技术之一。
近年来，人工智能技术得到了迅猛发展，在很多领域都开展了深入研究，例如：自然语言处理、生物模式识别等。在很多行业，人工智能已经能够替代人类完成工作，例如：客服聊天机器人、交易员等[1]。
博弈问题是人工智能的其中一个重要分支，是个零和问题，即决策如果对一方是有利的，对另一方肯定是不利的。博弈问题涉及人工智能中的推理技术、搜索方法和决策规划。1997年， IBM公
司研发的“深蓝”国际象棋程序，战胜了著名国际象棋棋手卡斯帕罗夫；2016年，谷歌旗下的子公司Deepmind研发的alphago击败了韩国围棋世界冠
军李世石；2017年，同样是Alphago，击败了中国的
世界冠军柯洁。这些都是人工智能技术应用于人机博弈问题的重要事迹。
2 问题描述
五子棋问题是典型的博弈问题，其基本规则为：下棋的双方分别执黑白两色棋子，通过轮流放下本方棋子于棋盘中来最后决出胜负，决出胜负的标准是率先有五个本方棋子连成一条线的一方胜出
[2] （横着，竖着或者斜着五个同色的棋子都可以） 。
五子棋问题的基本模型描述为：在五子棋人机博弈系统中，构建落子算法，使得计算机具有人的 智能，能够对当前局面进行判断，并且做出落子判断，直至胜出。五子棋问题中的基本棋型定义如下：
（1）五子连珠：至少五个同色棋子连在一起。（2）活四：有两个点可以落子形成连五点。（3）固四：有一个点可以落子形成连五点。（4）双固四：落子之后可以形成两个固四。（5）活三：落子后能形成活四。（6）双活三：落子后能形成2个活三。
在五子棋博弈问题中，下棋方不仅要考虑落子对当前棋局的影响，而且还有考虑落子对将来棋局的影响，也就是说，不能只考虑局部最优，而要尽可能地考虑全局最优。因此，经过分析，五子棋博弈问题主要涉及到两个关键问题，分别是：下一步最佳落子位置搜索和估值函数的设计。
（1）下一步最佳落子位置搜索。对于15×15的棋局，棋盘纵横各有15条线，总共构成225个可落
子的点。对每一个棋局，需要搜索可落子位置，并做出评估以确定下一步最佳落子位置。
（2）估值函数设计。估值函数F(n)是对棋局的一
个量化评价，针对某一棋局，分析搜索范围内各可落子点的落子估值，根据该值来进行落子判断。估值越大代表对己方越有利，估值越小代表队己方越不利。
3 算法研究
3.1 下一步最佳落子位置
3.1.1 传统搜索算法
（1）博弈树。遍历所有走法，构成一颗搜索数，
即博弈树。根节点为先手第一步走法，下面走法构成树的子节点，直至棋局结束。在博弈树的构建过程中，执棋双方轮流扩展节点，所有能使己方获胜的节点都是可解节点，所有使对方获胜的节点为不可解节点。完整的博弈树需要穷举所有棋局，复杂度非常高，因此通常做法是只生成一定深度的博弈树。
（2）极大极小算法。该算法是在博弈树上寻找
最优解的一个过程，即对各个子节点进行取舍的过程，本质上是博弈树算法的优化算法，复杂度优于博弈树算法，也称为不完全搜索树。算法中定义一个估值函数，利用估值函数得到当前端节点得分，并倒推其父节点的得分，对于己方节点，选择子节点中的最大得分作为父节点得分；而对于对方节点，选择子节点中的最小得分作为父节点得分。该算法需要先生成不完全博弈树，并计算所有节点的得分，当搜索深度较低时将影响决策的准确性，当搜索深度较高时复杂度仍然会很高。
（3）α-β剪枝。该算法是对极大极小算法的优
化，在博弈树生成的过程中，通过计算与比较节点得分的上下界快速裁剪不必要的搜索分支，从而提高搜索效率。
3.1.2 改进搜索算法
传统搜索算法的缺陷在于计算复杂度问题，无法解决搜索深度增加带来的呈几何级数增加的计算量问题。因此，根据五子棋的规律和特点，对传统搜索算法进行改进，以进一步提高算法的执行效率和对弈能力。
（1）矩形域搜索。构建棋盘上已有棋子的点的
最大矩形区域，在矩形区域内部和外围的邻域范围
内进行搜索，如图1所示。一开始由于棋盘上棋子数
较少，并且相对比较集中，那么矩形区域及其邻域都很小，搜索点数相对较少。随着局势的进行，棋盘上的棋子数目不断增加，矩形区域的范围也会变大，搜索的点数也会相应的增加。不过与搜索棋盘上所有的点相比，该算法确实减少了不少的搜索工作量，在一定程度上能够提高搜索效率。
（2）八连通域搜索。构建棋盘上已有棋子的点
的八连通区域，八连通区域范围内进行搜索，包括棋子围出的内部空白区域在内，如图2所示。该算法
思路与矩形域搜索算法一致，并且能够进一步提高搜索效率。
（3）路径搜索。搜索路径如图3所示，从棋盘中心出发，沿着图中箭头方向进行搜索。通过一定的判定规则，确定停止搜索的条件，在适当的时候停止对棋盘的搜索，同时标记出搜索过程中所经过的
已有棋子的点的邻域，作为考虑落子的位置。该算法设计的依据为：根据五子棋的特点，棋盘中间部分相比较于棋盘的四周更适合落子，所以应当优先考虑。一般下棋都是从棋盘中心开始下，这样棋子大部分都会集中在棋盘的中心区域。这样从中心向外进行有规律的扩展，搜索效率会有显著提高。 3.2 估值函数设计
在估值函数中，需要对整个棋盘形势进行分析，既要考虑此时自己的收益值，也要考虑对手的收益值，两者加权，从而得到一个相对合理的评价值。估值函数的设计涉及到对如下棋局进行参数调优，分别是：五子连珠、活四、双活三、活三+固四、双固四、冲四、活N和固N。
（1）训练集设计。设定1000组的权值，每一组权值人机对弈50次，计算胜率，则训练集中有1000
个样本。 （2）参数调优。利用人工神经网络[3]进行求解，得到最优的一组参数，如表1所示。
4 实现
在Windows 7下开发，对上述算法进行实践，完成五子棋人工对弈程序。通过实际对弈，该程序在计算机先手、人先手下的情况均能得到不错的胜率，如图4、图5所示。
5 结束语
五子棋人工智能是人工智能中博弈问题的经典问题。本文设计了一个五子棋人工对弈程序，在该程序中，对下一步最佳落子位置的搜索算法进行了改进，并研究了各棋局的参数调优方法。通过实际对弈表明，该算法具有较好的博弈性；同时，该算法存在的问题为：人先手情况下初始落子的智能性较差，需要进一步的优化改善。■
参考文献
[1] 蔡自兴，徐光祐．人工智能及其应用（第4版）[M]．北京：清华大学
出版社，2010.
[2] 李洪斌．五子棋实战必读[M].成都：成都时代出版社，2010.
[3] Neural networks: A comprehensive foundation[j]. Ryszard Tadeusiewicz.
Control Engineering Practice. 1995(5)