基于极小极大值搜索和Alpha Beta剪枝算法的五子棋智能博弈算法研究与实现

郑健磊，匡芳君

(温州商学院信息工程学院，浙江温州 325035)

五子棋是一款经典的两人对弈的纯策略型棋类游戏．相对于国际象棋、中国象棋、围棋、日本将棋，五子棋简单易学，但是精通五子棋并非易事．2016 年人工智能程序AlphaGo，击败人类围棋冠军李世石[1]，计算机在围棋领域不可能战胜人类的预言破灭．虽然AlphaGo 已经宣布退出围棋比赛，但是其留下来的宝贵算法和围棋招数是计算机界的新突破，也给围棋界带来翻天覆地的变化．在五子棋领域，五子棋先后于1994 年[2]、2001 年[3]被计算机证明原始无禁手、原始有禁手规则下先手必胜，然而相比计算机象棋和围棋，计算机五子棋的发展是缓慢的．很多五子棋专家相信目前的五子棋程序依旧无法超越最强的人类棋手．

五子棋博弈研究学者们都有其独到见解，张明亮[4]通过各类棋型估值的研究，优化了五子棋估值函数，解决了部分五子棋程序估值不完善的问题；毛丽民等[5]结合图像采集和分析，研发可以进行实物对弈的五子棋机器人；程宇等[6]通过对Alpha Beta 剪枝算法的改进，优化了着棋效率低下的问题；还有学者设计和实现了整套完整的五子棋人机博弈软件[7-8]．但五子棋博弈系统仍然存在棋型定义模糊，说法不一和博弈水平不高等问题．因此，本文针对五子棋棋型的定义不准确、棋型不充足，提出一套改进的五子棋棋型模型和估值方法，对基本棋型和绝杀棋型分别进行估值；针对Alpha Beta 剪枝算法存在效率低和博弈水平不高等问题，提出改进智能博弈算法，利用多线程技术和浅层最优算法优化Alpha Beta 剪枝算法，以提升着棋速度和准确率，通过局部搜索，加深程序的局部观，使得系统着棋能力得到提升．

1 五子棋棋型与估值

五子棋棋型存在定义模糊，如对活二、眠三、死四定义的不完整或存在术语使用不当[9]．而在大部分研究中，考虑的棋型较少，如对活三的定义不够完整，对跳活三、跳四这样的重要棋型未进行定义或定义不完整[10]．本文对棋型进行新的定义，特别是对一些特殊绝杀棋型进行了直接定义，以降低搜索深度，即颠覆从前往后的计算方式，直接从后往前推算，可提供接近2 层的计算深度，而庞大的搜索树需要提高1 层的搜索深度也是非常不容易的．

1.1 五子棋的基本棋型

在五子棋博弈中，活三和冲四是五子棋着棋过程最重要的棋型，活三两头均可进攻，冲四具有绝对先手，连续的冲四和活三的进攻是五子棋获胜的关键技术．而活三的一些变体棋型，如有一边空一格被对方棋子拦住，如图1 的棋型g 所示．此外跳活三、跳四，也是十分重要的棋型．跳四和冲四一样，具备绝对先手．

1.2 五子棋的绝杀棋型

如果不考虑对手的疏忽，那么活四或者成五一定是由多个棋型连续进攻所形成．本文例举了一方因无法防御而导致另一方必定出现活四或成五的棋型如图1 所示，故着此类棋型是获胜的关键所在．通过棋型可以判断，此类棋型是由两个或两个以上的先手棋型组成．因此本文将先手棋型进行计数，如果一方先手棋型的数量超过2 个，那么就给予一个相对非常高的分值，这些先手棋型包括：活三、跳活三、冲四、跳四．在着棋过程中发现，绝杀棋型有时也会存在被对手反胜或者化解的情况，一般是因为对方连续着绝对先手棋型（即冲四或跳四）导致的．而绝杀棋型中存在绝对先手的棋型，则不会存在此类情况，相对胜率会更高．

1.3 棋型的估值

通过对比不同估值的对局胜率，以及对棋型的分析，最终得出表1 所示估值方案．

表1 棋型估值Table 1 Chess Type Valuation

2 五子棋基础算法分析

本研究的算法思想基于极小极大值算法和Alpha Beta 剪枝算法①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.，这两种算法思想在棋类游戏中最为常用．

2.1 极小极大值算法效率分析

基于本文棋型的估值，使用极小极大值算法对局面进行评估．极小极大值算法能够模拟人的思维，找出局面范围内最优的解．在对弈中，对局面进行评估，估值越大表明对当前棋手越有利，估分越小则表明越不利．对所有节点进行计算局面评估，其所得最高分，即所达深度所能走出的最佳棋面，记录第1 手着棋位置，即是当前局面最佳着棋点．

如果不对极大极小值加以优化，这样的全盘遍历的方法会搜索大量毫无意义的点，对代码测试可以得出，在可以接受的时间内，只能进行两层搜索，即黑白各一手棋，而专业棋手能对未来十几步棋进行预测．

2.2 Alpha Beta剪枝算法效率分析

AlphaBeta 剪枝算法在棋类博弈的应用也不乏优秀研究[6]．人类棋手在着棋的过程中不会去考虑对己方明显不利的点和对对方明显有利的点．AlphaBeta 剪枝算法就是不对那些双方都不会考虑的点进行剪枝，不进行下一步的考虑，以此将搜索树加以修剪．1975 年，Knuth 等[11]证明在搜索节点排列为理想的情况下，将节点分支数记为b，深度记为d，搜索的节点数n为：

当d为偶数，

表2 AlphaBeta 剪枝算法效率分析Table 2 Efficiency Analysis of AlphaBeta Pruning Algorithm

Alpha Beta 剪枝算法高度依赖于节点的排列顺序，如果每次总是找到最差的节点，那么相当于剪枝永远不会发生，其效果相当于没有使用剪枝算法，即n=bd．Alpha Beta 剪枝算法效率分析如表2 所示．从表2 可知，虽然使用Alphabeta 剪枝对着棋能力有较大提升，但是其效率与理想排列状态相差甚远．

3 五子棋博弈算法研究与效率改进

通过对五子棋基础算法的分析，算法所存在的问题已然暴露．在极小极大值算法暴力搜索的基础上，使用AlphaBeta 剪枝算法进行改进，但其效率依旧低下，且只能对第四层进行非常缓慢的搜索，因此，结合局部搜索、多线程技术和浅层最优算法提出效率改进方案．

3.1 局部搜索

在五子棋博弈过程中，没有哪个人类棋手会对整个棋盘进行计算，其思考过程往往是从中心向四周发散，并且五子棋着棋往往不会超出原有棋子两格的位置，而未经优化的搜索算法会将任何一个空白的节点作为可能的落子点．

经过文献资料[6,8-9]和实战分析，一般对于搜索区域限制的算法往往是计算具有最大横坐标的棋子(maxx)，具有最小横坐标的棋子(minx)，具有最大纵坐标的棋子(maxy)，具有最小纵坐标的棋子(miny)，得出一个区域为(maxx- minx+n)*(maxy- miny+n)，其中n表示偏移量，即可能的着棋点和原有棋子的最大距离[6]，但是这种计算方式并不高效．如果棋型呈现斜向狭长走势，或者棋子距离较远且中间有大量空白的情况，依旧会存在大量的无效搜索．前者的情况并不少见，在五子棋博弈过程中，与任何已有棋子成不了直线的点也往往是不会成为落子区域，这样就会出现如图2 所示的区域化限制着棋点潜在的缺陷．对此，本文提出一种新思路，计算所需搜索节点的坐标，即可精确确定搜索范围．这样记录节点坐标的计算方式虽然比记录搜索范围计算方式更加复杂，但其减少的时间依旧比其增加的时间更可观．

图2 区域化限制着棋点潜在的缺陷Fig 2 Potential Defects of the Chess Sub-point Restricted by Regionalization

使用局部搜索前后的节点量对比如表3 所示，局部搜索效果非常有效，第二层和第四层节点分别减少了96.59%和99.94%，且原本无法计算的第六层使用较长时间也可被成功计算．

表3 使用局部搜索前后的节点量对比Table 3 Comparison of Grid Point Variable before and after the Application of Local Search

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 个节点数组分别进行搜索．改进后CPU 占用率从35%左右提升到了95%左右，而剩下的5%也已经被其他任务占据，因此CPU 的使用率已经达到了100%．

3.2.1 效率分析

CPU 效率得到明显提升，本应该计算速度也明显提升．但是实验结果却是令人意外的，使用多线程搜索之后，节点数几乎是使用单线程的2-3倍．单位时间内对节点的搜索速度提高到了原来的2 倍左右，如表4 所示，反而需要比单线程更长的时间．而且多线程的博弈过程发现，当前局面存在冲四棋型时，个别线程的节点明显增多．

表4 使用多线程技术前后的节点量与时间（取前10次平均值）对比Table 4 Comparison of Grid Point Variable and Time before and after the Application of Multi-threading Technology (Take the First 10Average Values)

3.2.2 多线程效率低下的原因分析

经过多次博弈发现，多线程效率低下是因为四个线程彼此独立，个别线程所找到着棋点有时候往往是非常不好的，导致个别线程剪枝不易发生．最为显著的是出现浅层绝杀的棋面，如对方着棋形成了冲四，那么只有一个线程可以找到拦截冲四继续形成成五的点，而其他线程因为这个点不在它的搜索范围内，导致得到的永远是一个极差的局面分．

如果使用单线程，那么单棵的搜索树将被分成4 棵彼此独立的搜索树，虽然4 线程的每棵小树的节点比单线程的大树要更少，但是4 棵树的总和却要更多．而多线程并不能带来4 倍的速度提升，因为CPU 负载升高后其每个线程所获得的算力明显低于单线程．

3.3 浅层最优算法

Alpha Beta 剪枝算法严重依赖于节点的排列．如果程序总是先去搜索最坏的节点，那么Alpha Beta 截断就不会发生，该算法最终会遍历整个搜索树．在搜索的过程中，节点的排列顺序是完全无规律的，甚至没有优化的搜索往往是从边缘往中心推进，这样得到的节点往往比随机排列还要更差．显然找到最优排列是不可能的，因为这势必要算出所有节点．但是可以通过着棋的特点，算法的特性，提前找到较为优秀的解．

浅层搜索虽然不能找到深层的最优解，但是其找到的解往往是较优解．而且对于某些棋型，浅层的搜索结果和深层的结果是完全一样的．比如下一着如果可以形成活四，那么不管搜索深度是多少，着活四棋型永远都是最优解．通过这一特点，在原来的Alpha Beta 剪枝算法的搜索范围的基础上，先使用两层搜索找到一个当前局面的最优解，再将这个解的节点替换为深层搜索的每一个线程的起始节点，那么深层搜索将从一个较为优秀的节点开始搜索．浅层最优搜索算法的伪代码如下：

(x,y)=获取深度为2 的最佳着棋点;

线程1 计算范围[0][0]=x; 线程1 计算范围[0][1]=y;

线程2 计算范围[0][0]=x; 线程2 计算范围[0][1]=y;

线程3 计算范围[0][0]=x; 线程3 计算范围[0][1]=y;

线程4 计算范围[0][0]=x; 线程4 计算范围[0][1]=y;

这样算法将四个线程都能联系，尤其是在浅层绝杀的棋面下，让四个线程都有机会找到绝杀点，大大提高了搜索效率，如表5 所示，使用了浅层最优算法后的多线程搜索效率显著提高．浅层最优算法不仅解决某些线程因找不到拦截浅层绝杀的点而导致搜索速度极慢，还使得节点排列顺序有一定提升，如表6 所示，单线程也比不使用浅层最优算法的效率高．

表5 使用浅层最优算法前后多线程的节点量与时间（取前10次平均值）对比Table 5 Comparison of the Amount of Nodes and Time of a Multiple Thread before and after the Application of Shallow Optimal Algorithm (Take the First 10Average Values)

表6 使用浅层最优算法前后单线程的节点量与时间（取前10次平均值）对比Table 6 Comparison of the Amount of Nodes and Time of a Single Thread before and after the Application of Shallow Optimal Algorithm (Take the First 10Average Values)

使用了浅层最优算法之后，无论单线程与多线程都有了效率的提升，使用浅层最优算法后单线程与多线程的节点量与时间对比如表7 所示．

7 229 329 2 331 316 264 1 436 -38 38 48 55 889 593 77 904 424 -39 28 9 51 523 574 88 536 410-72 29 1099 954 1 055 174 941 821 -75 22平均值 70245.9 720.9 111 672.5 561.0-59 22 1 1 491 025 14 4602 111 35011 012 -42 24 6 2 1 946 012 17 664 3 549 182 18 797 -82 -6 3 787 581 7 271 1 603 237 6 791 -104 7 4 2 777 389 26 342 3 842 868 15 197 -38 42 5 7 529 166 74 4407 529 166 37 646 049 6 93 603 148 840879 98 675 655 432 788 -5 49 7 76 446 115 692 205 91 676 698 503 718 -2027 8 32 996 289 319 549 44 678 231 210746 -35 34 9 51 264 007 516 822 63 563 678 288 926 -24 44 1059 131 650601 98066 765 425 307 675 -13 49平均值 32 797 238.2 311 161.2 38 399 549.0183 329.6 -17 41

由表7 可知，在节点多的时候，多线程表现出的效率要优于单线程，而在节点较少的时候，单线程效率更优．由于深度为2 的时候，无论基于什么算法，都是瞬间完成的，因此不在考虑之内．对于深度4 和深度6 而言，多线程的综合速度要明显优于单线程，随着棋面复杂度的增加，搜索深度加深，多线程的优势将更加明显，因此多线程的表现是值得肯定的．

4 实验结果与分析

全文实验方式均采用了15×15 的标准五子棋棋盘，以前10步着棋为实验数据，并保持相同深度的着棋棋型一致，对所使用的各项技术进行分析．通过使用五子棋基本棋型和绝杀棋型的两种估值方式，对棋力带来了明显改善，尤其是对于浅层绝杀方面．对于极小极大值算法和Alpha Beta 剪枝算法效率不足的问题，提出了以下改进方案：

（1）局部搜索意在优化减少对理论上不会落子的区域进行优化，本文打破常见的计算着棋区域的方法，转而使用了直接计算落子坐标的方法，优化了前者所存在的不足，其效率提升也十分明显，带来约99%的综合效率提升，并使得6 层搜索成为了可能．

（2）对CPU 使用率过低的问题，采取了4 线程并行计算，但是其结果并不理想，因为Alpha Beta 剪枝算法的特点，其效率反而有所下降．

（3）为了解决多线程计算存在的问题，提出了浅层最优算法，此算法不仅提高了多线程效率，也提高了单线程效率，使用了浅层最优算法之后，效率较低的多线程搜索有了较大的改善，相对于未使用此算法提升了约60%的综合效率．

如图3 是系统程序对局测试的结果，玩家持黑，电脑持白，电脑从第13 手进行了连续的先手进攻，最终于第27 手取胜．

5 结 语

本文针对五子棋棋型的定义不准确，棋型不充足等问题，提出了一套改进的五子棋棋型模型和估值方法．针对利用极小极大值搜索和Alpha Beta 剪枝算法对此棋型模型着棋时存在效率低和博弈水平不高的问题，提出改进智能博弈算法，在可接受的时间内，将搜索深度做到了6 层，实验结果表明，程序性能和效率相对较高，通过使用五子棋基本棋型和绝杀棋型的两种估值方式，对棋力也有明显改善，尤其是浅层绝杀方面有着很大优势．下一步工作将使用机器学习算法保存已下棋局，以使同样错误的着棋不再出现，同时在着棋时考虑对手存在计算漏洞，使程序具备更激进棋风．

图3 电脑持白对弈过程Fig 3 The Process to Play Chess by Computer Holding White Chess