AI研习丨专题：随机性博弈估值函数及其搜索策略研究

0 引言

近年来，计算机博弈的发展，一方面为人工智能的进步提供了重要的理论与方法，在中国象棋、围棋等完备信息博弈方面的研究已经取得了瞩目的成果；另一方面对于军棋、二打一扑克等非完备信息博弈，因具有模糊性和随机性的不确定性博弈，虽然在算法应用研究方面有一定进展， 但相关理论研究还不成熟，其博弈技术还需持续探索。 

本文以爱恩斯坦棋为研究载体。虽然爱恩斯坦棋盘较小，而且投骰子的趣味性可能被误认为 是相对简单的棋类游戏，可实际对弈就会明白， 规则虽简单却也隐藏着巨大的计算与灵活的策略， 属于随机性强的不确定性博弈，其局面评估更是难以量化研究。现有研究虽已提出了距离和概率两个估值因素，但只是简单的估值，包含知识量相对较少，对于棋盘状态估值不准确，结合搜索策略，博弈程序仍体现出行棋不稳定、棋力低下的现象。

本文针对爱恩斯坦棋的随机特性，以及占领对角的赢棋方式，设计了削减随机性的效率较好且准确的攻防兼备的估值函数；同时改进了适用于爱恩斯坦棋的混合优化算法，将估值函数应用到搜索策略中，提高了搜索算法的效率。

1 估值函数的设计 

通过对弈分析，爱恩斯坦棋行棋有两个特点，第一，爱恩斯坦棋需要通过掷骰子来确定走子；第二，爱恩斯坦棋有占领对角位置或者全歼两种赢棋方式。由于全歼出现的情况很少，本文重点考虑减小骰子随机数的影响，以及占领对角位置的赢棋方式，设计了削减随机性的攻防兼备的估值函数。 

1.1  行动概率

在爱恩斯坦棋的行棋规则约束下，初始布局由下棋方自己确定，具体行动的棋子通过掷骰子来确定，对于不同的爱恩斯坦棋局面，每个棋子能行动的可能性不同，即定义为棋子的行动概率。开局时每颗棋子的概率都为1/6，若对弈中发生吃子情况，与之相近的棋子走步的 概率就会增加。为了增加棋子的灵活性，根据对弈经验，棋手总是希望通过舍弃中间棋子、保留两边棋子的原则降低随机性影响并增大胜率。概率的计算方法为

式中，i 为棋子编号（红方为1 ≤ i ≤ 6，蓝方为7 ≤ i ≤ 12）；P(i) 为棋子的行动概率；left 为向左搜索被吃掉的棋子数；right 为向右搜索被吃掉的棋子数。

1.2 棋子价值

上文提到对弈过程中每个棋子的灵活度都会发生改变，所以本文把棋子的价值分为棋子本身的价值，以及对棋盘当前状态的影响值。棋子价值的计算方法为

其中，Value为棋子价值；Init_Value为棋子的初始值；Inf_Value为棋子对棋盘当前状态的影响值。棋子的初始值根据开局的位置赋值，若初始布局为如图1所示（图中，R代表红方；B代表蓝方）， 在同样遵循舍中间保两边的原则下，中间的棋子5初始值设为最小，其次是2、3、4，棋子1、6 的价值设为最大。 

棋子的影响值根据到对角的距离来确定，因为距离越大影响则越小。结合相关文献及对弈经验，其计算方式为

其中，d表示棋子到对方角部的距离；等号后上半部分表示边界位置的计算方法，下半部分表示其他位置的计算方法。

1.3 估值函数

从1.1节和1.2节的计算方法中减少随机性的影响之后，结合该棋的赢棋形式设计了攻击、 威胁，以及保护3个估值来全面评估棋子的价值。对局的估值常用的方法是计算到对方顶角点的距离，其计算公式为 

2 攻防兼备的混合优化算法

2.1 经典搜索算法

由于爱恩斯坦棋的行棋规则是通过掷骰子来确定的，所以对弈过程中己方的行动不确定，同时对方的行动也是未知数，这不仅增大了棋子的灵活性，也导致搜索分支巨大。因此本文选取基于模拟的蒙特卡罗（Monte Carlo）算法，以及被常用于预测评估的期望搜索算法作为爱恩斯坦棋的基础搜索算法。 

2.1.1 蒙特卡罗算法

蒙特卡罗算法是基于数学理论方面的随机模拟方法，主要是通过建立一个概率模型或者随机过程并采用抽样实验的方法来获得最优值。其基本思想就是通过大量且反复的抽样来得到结果；也就是说，蒙特卡罗算法的精确性强烈依赖于随机模拟的次数。在爱恩斯坦棋计算机博弈模拟对局时，通过设置固定的模拟次数或模拟时间，对合法招法列表中的每一个合法走步进行模拟到终局，在模拟过程中，双方的骰子数由系统产生伪随机数决定，其算法流程如图2所示。

2.1.2 期望搜索算法

期望搜索算法前身为极大极小算法，通常被应用于双人零和博弈，它是通过在MAX层和MIN层之间加入了CHANCE层，以此来评估随机事件的预期期望值。这完全适用于爱恩斯坦棋这类随机性棋种，将其不完全性转化成完全性，使得博弈树的构建过程透明化，降低搜索复杂度。

2.2 混合优化算法

虽然上文提到的算法都是比较经典算法，但都有缺陷。因为蒙特卡罗算法模拟对局过程中是随机的，由于时间或者空间的限制，其收敛效率较低，在选取最优走步上不精确。因此本文采用期望搜索算法来替代随机模拟，使对局更加贴近实际对弈，提高模拟后胜率的可靠程度。 

前文提到爱恩斯坦棋是通过掷骰子来确定走步的棋子，根据棋盘状态及裁判返回的骰子数，加入走法生成器返回当前局面的合法行动列表。若招法数量唯一，跳过搜索直接返回；若招法为必胜走步，则跳过搜索直接返回。遍历招法列表中的每一个合法走步，建立线程池，通过加入期望搜索算法的Monte Carlo模拟，同时将攻防兼备的估值函数应用到算法中评估棋局的优劣，从 而得到走步落入棋局改变状态后的优劣值。最后取最优值的招法作为最终最佳走步。其运行流程如图3所示。

3 实验结果分析

本文实验平台采用C#语言实现的基于混合优化算法的爱恩斯坦棋计算机博弈系统，在 Windows环境下通过与简单估值的混合优化算法，以及传统的期望搜索算法进行对弈，并分别从搜索效果和棋力水平两个方面来验证算法的有效性。

3.1 搜索效果分析

实验设置捜索深度为5层，将策略Ⅰ（攻防兼备的混合优化算法）与策略Ⅱ（简单估值的混合优化算法），以及策略Ⅲ（传统的期望搜索算法）对弈50局，记录时间并统计分析，其捜索效果的影响如图4所示。

由图4可看出，在相同深度下随着走步次数的不断增加，由于对弈过程中不断有棋子被吃掉而变少，三种搜索策略的搜索时间呈下降趋势。对比三种搜索策略，Ⅰ的搜索整体时间要比Ⅱ多，是因为Ⅰ采用的是削减随机的攻防兼备的估值函数，考虑知识较全面；而Ⅲ的搜索时间最短，其评估函数更为简单所致。图中第3、4步时间略高是由于本系统加入吃掉己方中间棋子增大两边棋子走步概率的经验知识之后，搜索宽度增大所致。 

3.2 棋力水平分析

根据爱恩斯坦棋的规则，每局4分钟，超时判负，甲方1、4、5先手，乙方2、3、6、7先手。在搜索深度都为5的情况下，将策略Ⅰ与其他两种策略对弈1000局，统计对弈双方的胜利局数，棋力水平如图5所示。

从实验效果图5可以看出，同等深度情况下，搜索策略Ⅰ的棋力水平比策略Ⅱ的高，胜率为57.6%；而搜索策略Ⅰ的棋力水平远远高于策略Ⅲ，胜率差不多达到了70%。以上数据说明，加入攻防兼备的估值函数的混合优化算法的爱恩斯坦棋博弈系统棋力水平显著提高 。从以上两个实验可以看出，应用棋类知识较为全面的估值函数的搜索算法，不仅从搜索效率上提高了，其棋力水平也随之上升，验证了该算法的高效性。

4 结束语

本文针对爱恩斯坦棋随机特性，以及赢棋方式，设计了削减随机性的攻防兼备的估值函数，应用于改进的混合优化算法中，并从算法的搜索效率和系统的棋力水平两个方面验证其有效性。虽然本文是从攻击和防守两个方面来考虑的，但是系统表现偏于防守，对弈系统若是攻击型则本文的搜索优势较大。如何更好平衡两者的关系则是后续的研究方向，同时可采用当前热门的深度学习算法来提高搜索效率。 

（参考文献略）

选自《中国人工智能学会通讯》

       2020年  第10卷  第2期  机器博弈专题

AI 研习 往期文章