机器博弈是人工智能领域重要的研究方向，通过训练计算机下棋来衡量机器的智能程度，具有人−机、机−机对弈2种形式，2016年Google的Alpha Go战胜韩国围棋大师李世石使得人机博弈变得家喻户晓^[1]，紧接着网络注册名Master线上挑战中日韩围棋高手，以及升级版Alpha Go Zero以4∶0战胜世界围棋第一人柯洁等标志性事件，掀开了人机博弈中机器取胜的新篇章^[2]。但是机−机博弈依然是人类在人工智能领域不断探索的新坐标。

机器博弈根据博弈过程中信息的透明度可以分为完备信息和非完备信息博弈。完备信息博弈双方信息完全透明，对弈的双方完全了解彼此的博弈信息，主流的完备信息博弈有中国象棋、围棋、五子棋等。而非完备信息博弈双方信息不完全透明，其中存在一定的欺诈信息，主流的非完备信息博弈有军棋、德州扑克、桥牌、斗地主等^[3]。由于非完备信息博弈信息的不透明性导致其存在博弈诱导、欺诈等行为，使得非完备信息博弈难以攻克^[4]。

军棋博弈游戏中共有13类棋子，包括军、师、旅、团、营、连、排、司令、工兵等9类军人棋子以及地雷、炸弹、军旗等3类工具棋子。军棋博弈游戏过程中由于棋子棋力不同，位置也不相同，因此在不一样的位置、不一样的棋子搭配的情况下，棋子所展现出来的战斗力也不相同。如何根据棋子特性搭配出最佳棋力成为研究的重点。

1 多棋子协同策略

多棋子协同博弈通过利用人类先验知识，制定出既定的目标和可实行的作战规划，发挥出相应的作战能力。其研究的目标是实现多棋子间协同，发挥群体作战功能，而不是单兵能力的体现与发挥。多棋子协同博弈的研究内容主要包括：多棋子优化协作、多棋子行为规划以及进行反馈学习^[5]。

1.1 多棋子联合定义

在军棋机器博弈游戏中，各个棋子间的协作关系是多种多样的，当博弈系统需要完成一个大目标时，就需要多个棋子进行协同作战。多棋子协同作战过程中会导致棋子间发生冲突，仅考虑棋子单独作战将会错过最优的作战计划^[6]。基于此，军棋机器博弈需要消除多方冲突的条件下产生最优的合作结果，使得机器博弈系统作战能力达到最优。军棋机器博弈系统中多棋子协同博弈策略取得好的作战力的时候，其组合策略就会得到一定的奖赏，遇到相同的情况下，相同的策略趋势便会增强，强化学习的方法为多棋子协同作战提供了高鲁棒性的学习方法，无监督的情况下，棋子可以在不同的棋局下不断优化更新出最优的协同策略^[7-8]。

多棋子协同博弈策略在棋子强化学习过程中的关键问题是确定棋子是否处于联合状态，并具有与其他棋子间的协同动作。多棋子进行协同博弈同时选择棋子组合，棋子不能及时沟通将会导致系统无法确定多棋子协同博弈的动作。针对此问题，机器博弈系统采取模拟走步解决此问题，即根据MCTS模拟的结果结合强化学习结果进而制定棋子协同策略。因此，军棋机器博弈协同强化学习系统由模拟预测单元和强化学习单元构建而成，其结构流程图如图1所示。在多棋子协同博弈强化学习系统中，模拟预测单元利用博弈树搜索进行MCTS模拟，返回高价值走步，并反馈出其他棋子的走步及预测结果，并基于其反馈的结果完成多棋子强化学习算法。强化学习单元将反馈回来的协同策略返还给动作预测单元进行协同策略预测模型更新^[9]。

1.2 Q学习算法应用

机器博弈双方和多方下棋的过程可以看作一个随机过程，服从马尔可夫序列过程，用元组<S，a¹，a²，···，aⁿ，f ¹，f ²，···，f ⁿ，g¹，g²，···，gⁿ>来表示一个多棋子协同博弈的随机策略，元组中n为军棋博弈系统中棋子的个数，即25个；S为博弈当前的局面，是一个12×5的矩阵；aⁱ，其中aⁱ表示棋子i可以选择的作战行为序列的集合i=1，2，···，n。军棋机器博弈系统协同作战的行动序列为a¹×a²，···，×aⁿ。f ⁱ，其中i=1，2，···，n，通过利用局面和行动的积得到棋子的行动概率，即 ${{S}} \times {{a}} \times {{S}} \to [0,1]$ ，gⁱ，其中i=1，2，···，n，通过局面及行棋动作返回一个强化收益函数，即 ${{S}} \times {{a}} \times {{S}} \to {{R}}$ ；在军棋机器多棋子协同博弈系统中，每个棋子的行动概率都是根据所有棋子协同作战的结果得出的，强化收益函数也是根据棋子协同作战后返回最高收益，根据棋局局面映射到棋子作战行为，采取协同策略 $\pi $ 。多棋子协同博弈强化学习方法转化为在棋子局面状态空间到棋子协同作战行为的映射学习。

Q强化学习算法是一种无监督的通过系统不断探索经验进而提高自身作战能力的算法，不需要人为干预和状态转移函数。当系统进行行为决策时只需要选出返还结果 $Q({s_t},{a_t})$ 的最大值，进而简化了多棋子协同博弈系统的决策过程，Q强化学习方法扩展为多棋子强化学习算法。

$\begin{array}{*{20}{c}} {Q_t^i(S_t^i,{a_t}) = (1 + \alpha )Q_{t - 1}^i(S_t^i,{a_t}) + } \\ {\alpha [r_t^i(S_t^i,{a_t}) + \gamma {\pi ^1}({S_{t + 1}}), \cdots ,{\pi ^n}({S_{t + 1}})Q_{t - 1}^i({S_{t + 1}})] } \end{array}$

$\begin{array}{*{20}{c}} {{\pi ^1}({S_{t + 1}}),{\pi ^2}({S_{t + 1}}), \cdots ,{\pi ^n}({S_{t + 1}})Q_t^i({S_{t + 1}}) = \sum\limits_{{a^1} \in a} \cdots }\\ {\sum\limits_{{a^n} \in a} {P_t^1} ({S_{t + 1}},{a^1}),P_t^2({S_{t + 1}},{a^2}), \cdots ,P_t^n({S_{t + 1}},{a^n}) \times {\rm{ }}}\\ {Q_{t - 1}^i(S_{t - 1}^i,{a^1},{a^2}, \cdots ,{a^n})} \end{array}$

式中： $S_t^i$ 为多棋子协同博弈系统中棋子i的状态变量； ${a_t} = \{ {a^1}, {a^2},\cdots ,{a^n}\} $ 为多棋子协同博弈系统中多棋子的协同行为序列； ${S_{t + 1}}$ 为行动后的下一步棋盘的局面，局面状态通过函数 ${S_{t + 1}} = f_t^i({S_t},{a_t})$ 进行转移；棋子i的作战行为通过模拟回报策略 ${\pi _i}$ 得到； $P_t^i({S_{t + 1}},{a^i})$ 是棋子i在局面 ${S_{t + 1}}$ 的情况下模拟选择出 ${a^i}$ 走步的概率。

2 UCT指导激活棋子

棋子间联合作战，通过反馈学习进行小规模棋子合作规划，实现对敌方欺诈是可以实现的。但是，军棋机器博弈系统中，每方都有25个棋子，棋子种类又分为12种，假设在军棋机器博弈过程中，每个棋子有A种走步，而在Q学习的过程中，25个棋子都会返回一个 $Q_t^i({s_t},{a_t})$ 表，那么其全部状态空间大小为A²⁵。由以上分析可以看出，棋盘上面棋子数越多，空间复杂度就越高，并且成指数倍增长，进而导致军棋机器博弈系统出现“维度灾难”问题^[10]。

军棋计算机博弈系统根据军棋棋子数量多造成的“维度灾难”问题，系统参考神经元特征，例如举一下胳膊时，并不会激活身体所有神经元，提出一种优先利用UCT搜索算法剪掉大部分棋子的行动序列，而把搜索学习算法重点放在几个高价值棋子之间的协作上面的方法。

2.1 UCT算法

2006年匈牙利学者Levente Kocsis和加拿大学者Csaba Szepesvari共同合作提出一种MCTS算法与UCB公式相结合的UCT搜索算法。UCB(upper confidence bound)搜索算法最初设计的目的是用来解决多臂老虎机之类的问题。多臂老虎机问题是指在多臂老虎机上，通过摇动每个老虎机手臂都可以得到一定的收益，如果玩家想要摇到最大的收益就要根据以前摇臂的经验去判断摇哪个手臂得到的收益值最大。UCB搜索算法是一种离线的强化学习策略，即根据以往的经验知识去帮助系统做出未来的决策，UCB算法中的UCB值又被称为上限置信区间值，UCB公式为

${\rm{UC}}{{\rm{B}}_i} = \overline {{V_i}} + k\sqrt {2\ln (n/{n_i})} $

式中： $\overline {{V_i}} $ 作为老虎机第i支手臂获得的平均收益； $k\sqrt {2\ln (n/{n_i})} $ 是老虎机在搜索其他手臂时探索的未知收益，存在一定未知风险；k值作为一个风险参数，当k值设大时，注重对其他最优结果的探索，当k值设小时，老虎机博弈系统注重以前高收益手臂，系统偏向于保守。N是所有手臂的访问次数， ${n_i}$ 则表示任意i支手臂的访问次数。

UCT搜索算法是在蒙特卡洛搜索的基础上，根据模拟出来的结果优先选择出胜率高的根节点，最后根据选择出来的胜率较高的根节点进行多次访问，增加高价值节点的访问次数，以最高访问数的节点作为最优值^[11]。

2.2 发现高价值棋子

军棋机器博弈系统采用多棋子协同博弈，开局时，局面中有50个棋子，60个棋位。并非所有棋子都进行系统协同作战，系统根据不同的布局采用局部令、强、中、弱棋子的搭配进行配合出战，而UCT搜索算法则在系统中起到筛选作用，为棋子协同作战提供指导方向，军棋机器博弈多棋子协同作战系统将搜索重点布局在高价值棋子上面，进而减少搜索的棋子数量，避免了搜索系统出现“维数灾难”问题。通过多棋子Q强化学习方法加强棋子之间策略学习，以使得多棋子可以配合出战，例如采用强子和弱子配合引诱对方的中子来吃弱子，而灭掉对方的中子^[12]。

UCT搜索算法指导激活多棋子强化Q学习算法的流程如下所示：

1)初始化系统的值函数、学习因子以及马尔可夫过程的状态集合 $Q_t^i({s_t},{a_t})$ ；

2)将当前节点作为博弈树系统的根节点，从根节点进行扩展；

3)通过UCT公式计算各个节点的UCB值，并为节点赋值，选择出UCB较高的节点作为扩展结点进行搜索；

4)依次搜索节点，并检查是否为叶子节点，若不是叶子节点则重复第3)步搜索；

5)核查该节点被搜索次数是否达到系统规定访问次数，如果达到规定的访问次数，则将该节点进行扩展，并在访问次数上加1；

6)筛选出当前高价值节点状态下激活1的棋子，按照系统策略 ${\pi ^*}({s_t}) = \arg \mathop {\max }\limits_{{a_t}} Q_t^i({s_t},{a_t})$ 计算出当前状态下的动作 ${a_t}$ ，并对下一局面状态 ${S_{t + 1}}$ 进行观察；

7)根据多棋子强化学习Q值迭代公式迭代出新的局面−行为对的值函数 $Q_t^i({s_t},{a_t})$ ；

8)判断是否满足学习的终止条件，若满足则结束学习，不满足则返回第2)步继续迭代。判定当前状态是否满足多棋子Q学习算法的终止条件，如果满足，则停止学习，否则返回第2)步。

2.3 构建军棋博弈系统

由于军棋在开局的时候对敌方信息处于未知状态。因此在军棋博弈系统中先跟据人类先验知识以及蒙特卡罗模拟对棋盘进行完备化^[13]。搜索模块采用UCT搜索算法模拟走步，返回价值高并且模拟次数多的走步，并激活行动价值高的走步。通过Q学习算法对棋子协同矩阵优化，选择出最优走步。军棋博弈系统流程图如图2所示。

3 实验结果分析

为了测试多棋子Q强化学习算法在实战中是否占据优势，本文采用与其他算法系统进行对打模式测试本算法的实用性，通过分先后手对战极大极小值搜索算法、alpha−beta搜索算法、MCTS搜索算法以及UCT搜索算法各1 000局并不断调整多棋子Q强化学习算法的参数，以得到最优值，实验结果如图3~7所示。

由以上实验结果可知，参数 $\alpha $ 和 $\gamma $ 对系统的作战能力影响极大， $\alpha $ 参数值影响着系统学习的效率，值越大，学习效率就越高。 $\gamma $ 参数影响着系统学习过程中经验的影响力， $\gamma $ 值越大，以往的经验就显得越重要。当 $\alpha $ =0.4， $\gamma $ =0.6时多棋子Q强化学习系统对战其它算法系统的结果相对最好。

单子作战系统重防守、轻攻击，很难做到主动攻击。而加入多棋子协同作战策略后的军棋机器博弈系统能够自我组织协同策略，多棋子联合作战，增加了系统的主动进攻意识。本文为了测试军棋多棋子协同博弈系统主动作战意识是否提高，采用了与其它搜索算法系统对战的模式，并统计出棋子作战过程中主动进攻的步数进行对比研究，研究发现该系统能够达到攻守平衡的状态，统计结果如表1所示。

军棋多棋子协同博弈系统由于棋子种类多的问题导致的“维度灾难”问题成为系统对战成败的关键性因素，针对此问题系统采用多种搜索算法进行高价值棋子激活，分别对战500局后，在军棋博弈的69步范围之内计算出每一步的平均搜索时间如图8所示^[14]。

由图8可知，在未加激活算法时搜索的时间较长，而军棋机器博弈比赛是在限定的时间内搜索到走步，否则认为系统搜索超时判负，加入各种激活算法后，系统搜索时间明显降低，尤其在加入UCT搜索算法时，系统搜索时间降低最明显。

4 结束语

本文利用Q学算法优化迭代更新军棋计算机博弈系统中多棋子协同矩阵，增加了多棋子协同作战的意识，增强了博弈系统主动出击诱导敌方的进攻趋势。利用部分重要棋子激活的方法解决了棋子数量巨大造成的“维度灾难”问题，使得搜索时间得到提升，避免了军棋计算机博弈系统在正式比赛过程中由于超时被判负的情况。未来将考虑利用计算智能算法加入此系统，进一步优化多棋子协同矩阵^[15]。