爱恩斯坦棋计算机博弈算法研究与改进

杨昌杰 陈柯成 刘跃元 王京

摘要：人工智能技术高速发展，作为人工智能领域的重要方向——计算机博弈蓬勃开展，爱恩斯坦棋作为计算机博弈的一类棋种，是中国大学生计算机博弈大赛的比赛项目，具有信息不完全、走棋受概率影响等特点。文章通过对爱恩斯坦棋的搜索算法进行系统研究，提出基于定式处理的改进型Alpha-Beta剪枝算法，经验证该算法可以提高在博弈比赛中的胜率。

关键词：人工智能；爱恩斯坦棋；Alpha-Beta剪枝；定式处理

计算机博弈[1]是人工智能的重要组成部分，计算机博弈的杰出代表Alpha-Go[2]所应用的围棋是一种完全信息的博弈棋种。然而，爱恩斯坦棋是一种不完全信息博弈棋种，同时，爱恩斯坦棋的走棋棋子是通过掷骰子决定的，所以具有随机性。同时双方都不能提前判断对手的下一步走棋棋子，导致信息的不完全性。对比围棋中使用蒙特卡洛树搜索（Monte Cairo Tree Search，MCTS）算法，爱恩斯坦棋棋盘较小、棋子数较少，使用Alpha-Beta剪枝算法具有数据处理相对较少、轻便容易等优势，非常适合爱恩斯坦棋的搜索处理。但是在博弈游戏中由于受到行棋走时间的限制，如若不对搜索算法加以处理，在较高层次的搜索情况下，仍会存在搜索时效相对较慢、总时间超时等问题。

基于以上问题可以看出，评价函数的好坏对走棋是否合理至关重要，搜索算法对行棋也有显著影响，所以本文从评价函数和搜索算法两方面展开研究，旨在减小爱恩斯坦棋行棋过程中随机性对行棋的影响，并结合适当的搜索算法，缩短搜索时间，进一步提高在对弈中的胜率。本文将蓝棋作为本方，红棋作为敌方。

1 定式处理改进Alpha-Beta剪枝算法

极大极小搜索算法是计算机博弈游戏设计中最常见的搜索算法，它的核心思想是博弈双方从自身角度出发，总是做最优选择。基本思路是：对弈双方分别为A和B，当轮到A方走步时，B方应考虑最坏情况；当轮到B方走步时，A方应考虑最坏情况，评价往回倒推时，相应于两位棋手的对抗策略，交替使用取值方法来传递倒推值。一般地，极大极小算法采用回溯的方式递归调用完成，显然其在搜索深度上受到了极大的限制，很难进行深层次的评估，而有很多节点再进行深层次的搜索是没有太大意义。Alpha-Beta剪枝算法[3]是基于极大极小搜索算法的无损剪枝算法，是最基本也最有效的剪枝方法，虽然它没有办法消除极大极小算法搜索过程中节点的指数级增长，但可以将其减半。

常用的Alpha-Beta剪枝算法的改進策略有杀手启发、历史启发、MTD（f）算法[4]等。实验表明，爱恩斯坦棋项目中先后手对估值的影响影响略大，且博弈过程中经常出现分支或前后两步之间估值差距过大的情况，因此使用渴望搜索不太适合，对效率的提升不够明显。转移表通过记录已经搜索过的节点（或子树）的搜索结果，包括子树的博弈值、最佳移动和位置，给予当前搜索和走棋以提示。转移表会占用大量内存，虽然可以采用散列的方式管理存取，但是对于爱恩斯坦棋来说，每一枚棋子最多有3种走向可以选择。

通过大量实验表明，一般来说，棋子走对角线是最优的，且由于博弈树搜索性能的瓶颈，每次搜索很难达到之后走棋再搜索所能达到的搜索深度，这意味着，每次走棋几乎都“否定”了之前的搜索结果，所以转移表对最优走法的提示功能有限。通过大量实验对局发现，在开局阶段内层棋子吃掉外层棋子换取走棋灵活性对于爱恩斯坦棋后期走棋更为有利，且开局阶段棋型相对固定，这样就可以采取在Alpha-Beta剪枝算法层前加入定式处理层，只要棋型满足某种条件就走固定的走法，这种思路可以避免开局阶段棋子数多、在多层搜索时出现的计算体量大、耗时长、很多节点进行深层次的搜索是没有太大意义的情况，形成了基于定式处理的改进型Alpha-Beta剪枝算法。

基于定式处理的改进型Alpha-Beta剪枝算法流程如图1所示。

下面以一个定式处理为例，该定式一般应用于开局，如图2所示，检索蓝棋所在的副对角线右方区域，如果满足副对角线右方区域只存在一个红棋，则只要行棋蓝棋可行棋3个方向能吃掉红棋则一定吃掉，若如可走蓝4，直接定式处理吃掉红5，而不是斜走。

如果满足副对角线右方区域不存在一个红棋，则蓝棋棋子最外层和最内层棋子斜走，同时根据开局阶段吃掉外层棋子换取灵活性思路，次层棋子吃掉最外层两翼的棋子（见图3）。同时还可以加入根据场上棋子数调整Alpha-Beta剪枝算法的搜索层数等定式。

定式处理层的加入是基于爱恩斯坦棋棋局小、能吃本方棋子、走法相对单一的特点，对于能够进行定式处理的局面，不需要进入Alpha-Beta剪枝搜索层，直接处理完毕后跳至走棋层，这样既能够克服由于Alpha-Beta剪枝在高层次搜索时计算量成几何层次增长、耗时长的缺点，同时也利于后期参数调整、试验矫正阶段可以通过定式处理，弥补由于Alpha-Beta剪枝算法系统误差导致的剪枝掉最优行棋的情况，到达找到最优走法、提高比赛胜率的目的。

2 实验结果

本文的基于定式处理改进Alpha-Beta剪枝的策略与使用传统期望距离的Alpha-Beta剪枝进行博弈结果如表1所示。

该策略验证在胜率方面对战一般距离期望的Alpha-Beta 剪枝算法程序有较大优势，同时耗时也仅为一般策略的72.6%，同时，该策略应用的程序“WjCkGo”，在2017年全国大学生计算机博弈大赛爱恩斯坦棋项目获得一等奖（季军），证明该策略明显增加了胜率。

3 结语

本文通过运用一些灵活且实用的定式处理算法，判断当前局面是否可以进入定式处理层而直接输出走棋。这种在适宜局面不需要进入Alpha-Beta剪枝层的改进型Alpha-Beta 剪枝层算法，减少了决策时间，而且还可以通过后期不断测试，完善定式处理层，达到较好的走棋水平，同时也应该意识到，要进一步加强对残局的处理，完善特定棋型时剪枝算法出现的系统漏洞。

[参考文献]

[1]王骄，徐心和.计算机博弈：人工智能的前沿领域——全国大学生计算机博弈大赛[J].计算机教育，2012（7）：14-18.

[2]刘知青，吴修竹.解读AlphaGo背后的人工智能技术[J].控制理论与应用，2016（12）：1685-1687.

[3]曹森.对α-β剪枝算法的性能改进研究[D].呼和浩特：内蒙古师范大学，2012.

[4]LORENTZ R J.An MCTS program to play EinStein Wtirfelt Nicht[M].Berlin：Advances in Computer Games， 2011.