牛恺泽，邓 鑫

（1.北京交通大学附属中学分校，北京 100088；2.国家气象信息中心，北京 100081）

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所示。一开始由于棋盘上棋子数较少，并且相对比较集中，那么矩形区域及其邻域都很小，搜索点数相对较少。随着局势的进行，棋盘上的棋子数目不断增加，矩形区域的范围也会变大，搜索的点数也会相应的增加。不过与搜索棋盘上所有的点相比，该算法确实减少了不少的搜索工作量，在一定程度上能够提高搜索效率。

图1 矩形域搜索

（2）八连通域搜索。构建棋盘上已有棋子的点的八连通区域，八连通区域范围内进行搜索，包括棋子围出的内部空白区域在内，如图2所示。该算法思路与矩形域搜索算法一致，并且能够进一步提高搜索效率。

图2 八连通域搜索

（3）路径搜索。搜索路径如图3所示，从棋盘中心出发，沿着图中箭头方向进行搜索。通过一定的判定规则，确定停止搜索的条件，在适当的时候停止对棋盘的搜索，同时标记出搜索过程中所经过的已有棋子的点的邻域，作为考虑落子的位置。该算法设计的依据为：根据五子棋的特点，棋盘中间部分相比较于棋盘的四周更适合落子，所以应当优先考虑。一般下棋都是从棋盘中心开始下，这样棋子大部分都会集中在棋盘的中心区域。这样从中心向外进行有规律的扩展，搜索效率会有显著提高。

图3 路径搜索

3.2 估值函数设计

在估值函数中，需要对整个棋盘形势进行分析，既要考虑此时自己的收益值，也要考虑对手的收益值，两者加权，从而得到一个相对合理的评价值。估值函数的设计涉及到对如下棋局进行参数调优，分别是：五子连珠、活四、双活三、活三+固四、双固四、冲四、活N和固N。

（1）训练集设计。设定1000组的权值，每一组权值人机对弈50次，计算胜率，则训练集中有1000个样本。

（2）参数调优。利用人工神经网络[3]进行求解，得到最优的一组参数，如表1所示。

4 实现

在Windows 7下开发，对上述算法进行实践，完成五子棋人工对弈程序。通过实际对弈，该程序在计算机先手、人先手下的情况均能得到不错的胜率，如图4、图5所示。

表1 最优的一组参数

图4 计算机先手

图5 人先手

5 结束语

五子棋人工智能是人工智能中博弈问题的经典问题。本文设计了一个五子棋人工对弈程序，在该程序中，对下一步最佳落子位置的搜索算法进行了改进，并研究了各棋局的参数调优方法。通过实际对弈表明，该算法具有较好的博弈性；同时，该算法存在的问题为：人先手情况下初始落子的智能性较差，需要进一步的优化改善。