第40卷第3期温州大学学报（自 然 科 学 版）2019年8月V ol 40, No 3 Journal of Wenzhou University (Natural Science Edition) Aug, 2019
基于极小极大值搜索和Alpha Beta剪枝算法的五子棋智能博弈算法研究与实现 郑健磊，匡芳君†
(温州商学院信息工程学院，浙江温州325035)
摘要：针对五子棋棋型定义不准确、棋型不充足等问题，提出了一套改进的五子棋棋型模型和估值 方法．针对利用极小极大值搜索和Alpha Beta剪枝算法对此棋型模型着棋时存在效率低和博弈水平不
高的问题，提出了一系列改进的着棋方法，即利用局部搜索、多线程技术、浅层最优算法优化剪枝算
法，以提升着棋的速度和准确率．实验结果表明，提出的着棋方案能提升着棋效率和准确性，设计得
出的五子棋博弈系统具备远超过多数人类玩家的棋力．
关键词：五子棋；估值函数；Alpha-Beta搜索算法；局部搜索；多线程
中图分类号：TP301.6 文献标志码：A 文章编号：1674-3563(2019)03-0053-10
DOI：10.3875/j.issn.1674-3563.2019.03.008 本文的PDF文件可以从xuebao.wzu.edu/获得
五子棋是一款经典的两人对弈的纯策略型棋类游戏．相对于国际象棋、中国象棋、围棋、日本将棋，五子棋简单易学，但是精通五子棋并非易事．2016年人工智能程序AlphaGo，击败人类围棋冠军李世石[1]，计算机在围棋领域不可能战胜人类的预言破灭．虽然AlphaGo已经宣布退出围棋比赛，但是其留下来的宝贵算法和围棋招数是计算机界的新突破，也给围棋界带来翻天覆地的变化．在五子棋领域，五子棋先后于1994年[2]、2001年[3]被计算机证明原始无禁手、原始有禁手规则下先手必胜，然而相比计算机象棋和围棋，计算机五子棋的发展是缓慢的．很多五子棋专家相信目前的五子棋程序依旧无法超越最强的人类棋手．
五子棋博弈研究学者们都有其独到见解，张明亮[4]通过各类棋型估值的研究，优化了五子棋估值函数，解决了部分五子棋程序估值不完善的问题；毛丽民等[5]结合图像采集和分析，研发可以进行实物对弈的五子棋机器人；程宇等[6]通过对Alpha Beta剪枝算法的改进，优化了着棋效率低下的问题；还有学者设计和实现了整套完整的五子棋人机博弈软件[7-8]．但五子棋博弈系统仍然存在棋型定义模糊，说法不一和博弈水平不高等问题．因此，本文针对五子棋棋型的定义不准确、棋型不充足，提出一套改进的五子棋棋型模型和估值方法，对基本棋型和绝杀棋型分别进行估值；针对Alpha Beta剪枝算法存在效率低和博弈水平不高等问题，提出改进智能博弈算法，利用多线程技术和浅层最优算法优化Alpha Beta剪枝算法，以提升着棋速度和准确率，通过局部搜索，加
收稿日期：2018-09-08
mtp
基金项目：国家自然科学基金(61402227)；2018年温州商学院国家创新创业训练计划项目(201813637004)达州普光气田
作者简介：郑健磊(1996-)，男，浙江绍兴人，本科生，研究方向：智能算法与软件开发．† 通讯作者，407807096@qq
54
温州大学学报（自然科学版）(2019)第40卷第3期 深程序的局部观，使得系统着棋能力得到提升．
1 五子棋棋型与估值
五子棋棋型存在定义模糊，如对活二、眠三、死四定义的不完整或存在术语使用不当[9]．而在大部分研究中，考虑的棋型较少，如对活三的定义不够完整，对跳活三、跳四这样的重要棋型未进行定义或定义不完整[10]．本文对棋型进行新的定义，特别是对一些特殊绝杀棋型进行了直接定义，以降低搜索深度，即颠覆从前往后的计算方式，直接从后往前推算，可提供接近2层的计算深度，而庞大的搜索树需要提高1层的搜索深度也是非常不容易的．
1.1 五子棋的基本棋型
在五子棋博弈中，活三和冲四是五子棋着棋过程最重要的棋型，活三两头均可进攻，冲四具有绝对先手，连续的冲四和活三的进攻是五子棋获胜的关键技术．而活三的一些变体棋型，如有一边空一格被对方棋子拦住，如图1的棋型g所示．此外跳活三、跳四，也是十分重要的棋型．跳四和冲四一样，具备绝对先手．
图1 五子棋主要棋型与部分绝杀棋型
Fig 1 Main Chess Type and Partial Lore Chess Type of Gobang
1.2 五子棋的绝杀棋型
如果不考虑对手的疏忽，那么活四或者成五一定是由多个棋型连续进攻所形成．本文例举了一方因无法防御而导致另一方必定出现活四或成五的棋型如图1所示，故着此类棋型是获胜的关键所在．通过棋型可以判断，此类棋型是由两个或两个以上的先手棋型组成．因此本文将先手棋型进行计数，如果一方先手棋型的数量超过2个，那么就给予一个相对非常高的分值，这些先手棋型包括：活三、跳活三、冲四、跳四．在着棋过程中发现，绝杀棋型有时也会存在被对手反胜或者化解的情况，一般是因为对方连续着绝对先手棋型（即冲四或跳四）导致的．而绝杀棋型中存在绝对先手的棋型，则不会存在此类情况，相对胜率会更高．
1.3 棋型的估值
通过对比不同估值的对局胜率，以及对棋型的分析，最终得出表1所示估值方案．
郑健磊等：基于极小极大值搜索和Alpha Beta 剪枝算法的五子棋智能博弈算法研究与实现
55
弾孔表1 棋型估值 Table 1 Chess Type Valuation
棋型名称 估值 棋型名称 估值 成五 9 999 999 眠三 15 活四 1 000 000
活二 20 冲四 200 眠二 5 跳四 120 双活二 40
活三 200 绝杀棋型 10 000*（1+冲四个数+跳四个数）
跳活三
30
2 五子棋基础算法分析
本研究的算法思想基于极小极大值算法和Alpha Beta 剪枝算法①，这两种算法思想在棋类游戏中最为常用．
2.1 极小极大值算法效率分析
基于本文棋型的估值，使用极小极大值算法对局面进行评估．极小极大值算法能够模拟人的思维，出局面范围内最优的解．在对弈中，对局面进行评估，估值越大表明对当前棋手越有利，估分越小则
表明越不利．对所有节点进行计算局面评估，其所得最高分，即所达深度所能走出的最佳棋面，记录第1手着棋位置，即是当前局面最佳着棋点．
如果不对极大极小值加以优化，这样的全盘遍历的方法会搜索大量毫无意义的点，对代码测试可以得出，在可以接受的时间内，只能进行两层搜索，即黑白各一手棋，而专业棋手能对未来十几步棋进行预测．
2.2 Alpha Beta 剪枝算法效率分析
AlphaBeta 剪枝算法在棋类博弈的应用也不乏优秀研究[6]．人类棋手在着棋的过程中不会去考虑对己方明显不利的点和对对方明显有利的点．AlphaBeta 剪枝算法就是不对那些双方都不会考虑的点进行剪枝，不进行下一步的考虑，以此将搜索树加以修剪．1975年，Knuth 等[11]证明在搜索节点排列为理想的情况下，将节点分支数记为b ，深度记为d ，搜索的节点数n 为：
当d 为偶数，2
21d n b
=-；当d 为奇数，(1)2(1)21d d n b b +-=+-．
表2 AlphaBeta 剪枝算法效率分析
Table 2 Efficiency Analysis of AlphaBeta Pruning Algorithm
搜索产生节点数 / 个
深度 d 不使用剪枝算法 节点数d b
最理想排列情况
221d b -
本文所编写程序 取10次平均值
本文程序比不使用剪枝 算法效率减少率 / %
0 1 1 1.0 0 2 50 625 449 17 338.5 65.8 4 2 562 890 625 101 249 186 767 951.3
92.7 6
129 746 337 890 625
22 781 249
① Sato N, Ikeda K. Three types of forward pruning techniques to apply the alpha beta algorithm to turn-based strategy games [C]. 2016 IEEE Conference on Computational Intelligence and Games, Santorini, Greece, 2016: 20-23.
温州大学学报（自然科学版）(2019)第40卷第3期
56
Alpha Beta 剪枝算法高度依赖于节点的排列顺序，如果每次总是到最差的节点，那么相当
于剪枝永远不会发生，其效果相当于没有使用剪枝算法，即d
n b =．Alpha Beta 剪枝算法效率分析如表2所示．从表2可知，虽然使用Alphabeta 剪枝对着棋能力有较大提升，但是其效率与理想排列状态相差甚远．
3 五子棋博弈算法研究与效率改进
暗房易根经
通过对五子棋基础算法的分析，算法所存在的问题已然暴露．在极小极大值算法暴力搜索的基础上，使用AlphaBeta 剪枝算法进行改进，但其效率依旧低下，且只能对第四层进行非常缓慢的搜索，因此，结合局部搜索、多线程技术和浅层最优算法提出效率改进方案． 3.1 局部搜索
在五子棋博弈过程中，没有哪个人类棋手会对整个棋盘进行计算，其思考过程往往是从中心向四周发散，并且五子棋着棋往往不会超出原有棋子两格的位置，而未经优化的搜索算法会将任何一个空白的节点作为可能的落子点．
经过文献资料[6,8-9]和实战分析，一般对于搜索区域限制的算法往往是计算具有最大横坐标的棋子(max x )，具有最小横坐标的棋子(min x )，具有最大纵坐标的棋子(max y )，具有最小纵坐标的棋子(min y )，得出一个区域为(max x - min x + n )*(max y - min y + n )，其中n 表示偏移量，即可能的着棋点和原有棋子的最大距离[6]，但是这种计算方式并不高效．如果棋型呈现斜向狭长走势，或者棋子距离较远且中间有大量空白的情况，依旧会存在大量的无效搜索．前者的情况并不少见，在五子棋博弈过程中，与任何已有棋子成不了直线的点也往往是不会成为落子区域，这样就会出现如图2所示的区域化限制着棋点潜在的缺陷．对此，本文提出一种新思路，计算所需搜索节点的坐标，即可精确确定搜索范围．这样记录节点坐标的计算方式虽然比记录搜索范围计算方式更加复杂，但其减少的时间依旧比其增加的时间更可观．
图2 区域化限制着棋点潜在的缺陷
Fig 2 Potential Defects of the Chess Sub-point Restricted by Regionalization
本文局部搜索使用偏移量为2，其伪代码如下： for (遍历整个棋盘) { if 当前节点存在棋子
郑健磊等：基于极小极大值搜索和Alpha Beta剪枝算法的五子棋智能博弈算法研究与实现 57
for对当前偏移量为1的范围内进行搜索{
if当前节点没有棋子，且当前节点未被记录
then记录当前节点坐标，并将当前节点记为已记录
endif
}
endif
if当前节点存在棋子
for对当前偏移量为2的范围内进行搜索{
if当前节点没有棋子，且当前节点未被记录，且横纵偏移量相等
甘肃理论学刊
then记录当前节点坐标，并将当前节点记为已记录
endif
}
endif
}
使用局部搜索前后的节点量对比如表3所示，局部搜索效果非常有效，第二层和第四层节点分别减少了96.59%和99.94%，且原本无法计算的第六层使用较长时间也可被成功计算．
表3 使用局部搜索前后的节点量对比
Table 3 Comparison of Grid Point V ariable before and after the Application of Local Search
搜索产生节点数（着棋10次平均值）/ 个
节点减少率/ % 深度d
不使用局部搜索使用局部搜索
2 17 338.5 592.1 96.59
4 186 767 951.3（取4次平均值）114 741.6 99.94
6 4
7 581 577.4
3.2 多线程技术
使用局部搜索后，搜索速度有了质的飞跃．但博弈过程中又出现了新问题，即在4层和6层搜索过程中CPU的平均占用率只有35%左右．研究发现，这是因为整个搜索的过程是单线程串行的，而现在的CPU普遍采用了多核多线程设计，实验所用的笔记本电脑使用的是Intel i7 8550U 处理器，使用了4核8线程的设计．多线程技术避免了因阻塞带来的等待问题，能够有效提高处理器的工作效率和资源利用率[12]．
本文采取了多线程技术来优化CPU的使用率，目前市面上多数消费级CPU采用的是2核4线程，4核4线程，或者4核8线程的设计．因此，选择了4线程对搜索进行优化．本文通过给每个线程分配不同的搜索区域，达到4线程搜索，其伪代码如下：
length = 搜索数组的长度;
range 1[开始] = 1; range 1[结束] = length / 4;
range 2[开始] = range 1[结束] + 1; range 2[结束] = length / 2;
塑化range 3[开始] = range 2[结束] + 1; range 3[结束] = (range 2[结束] + 1 + length) / 2;
range 4[开始] = range 3[结束] + 1; range 4[结束] = length;
通过将局部搜索时保存的节点数组4等分，然后使用4个线程分别对4个节点数组分别进行
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议