第15卷第2期 智能系统学报 Vol.15 No.2 2020年3月 CAAI Transactions on Intelligent Systems Mar.2020 D0:10.11992/tis.201812012 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20200323.1314.004html 一种军棋机器博弈的多棋子协同博弈方法 张小川，王宛宛2，彭丽蓉3 (1.重庆理工大学两江人工智能学院，重庆400054；2.重庆理工大学计算机科学与工程学院，重庆400054： 3.重庆工业职业技术学院信息工程学院，重庆401120) 摘要：针对在军棋博弈不完全信息对弈中，面对棋子不同价值、不同位置、不同搭配所产生的不同棋力，传统 的单子意图搜索算法，不能满足棋子之间的协同性与沟通性，同时也缺乏对敌方的引诱与欺骗等高级对抗能 力。本文提出一种结合UCT搜索策略的高价值棋子博弈方法，实现高价值棋子协同博弈的策略。实战经验表 明：高价值多棋子军棋协同博弈策略优于单棋子军棋博弈策略。 关键词：机器博弈；军棋；协同博弈；Q学习算法：攻守平衡：维度灾难：UCT:高价值棋子 中图分类号：TP311.5文献标志码：A文章编号：1673-4785(2020)02-0399-06 中文引用格式：张小川，王宛宛，彭丽蓉.一种军棋机器博弈的多棋子协同博弈方法J川.智能系统学报，2020,15(2)： 399-404. 英文引用格式：ZHANG Xiaochuan,,WANG Wanwan,PENG Lirong.A multi--chess collaborative game method for military chess game machine[J].CAAI transactions on intelligent systems,2020,15(2):399-404. A multi-chess collaborative game method for military chess game machine ZHANG Xiaochuan',WANG Wanwan',PENG Lirong (1.Liangjiang Institute of Artificial Intelligence,Chongqing University of Technology,Chongqing 400054,China;2.School of Com- puter Science and Engineering,Chongqing University of Technology,Chongqing 400054,China;3.Faculty Information Engineering, Chongqing Industry Polytechnic College,Chongqing 401120,China) Abstract:Owing to incomplete information on the military chess and the different strengths of chess pieces with differ- ent values,positions,and combinations,the traditional single-intention search algorithm cannot satisfy the coordination and communication requirements of chess pieces and lacks advanced confrontation capabilities,such as temptation and deception of the enemy.This study proposes the combination of the high-value chess piece game method and the UCT search strategy to achieve a high-value chess piece cooperative game strategy that can be used to solve the problems of the military chess game.Practical experience shows that the high-value multipiece military chess game strategy is better than the high-value single-piece military chess game strategy. Keywords:computer game;military;collaborative game;Q learning algorithm;balance of attack and defend UCT;di- mension disaster;high value chess piece; 机器博弈是人工智能领域重要的研究方向， Alpha Go战胜韩国围棋大师李世石使得人机博弈 通过训练计算机下棋来衡量机器的智能程度，具 变得家喻户晓，紧接着网络注册名Master线上 有人-机、机-机对弈2种形式，2016年Google的 挑战中日韩围棋高手，以及升级版Alpha Go Zero 收稿日期：2018-12-11.网络出版日期：2020-03-23. 以4：0战胜世界围棋第一人柯洁等标志性事件， 基金项目：国家自然科学基金项目(61702063)：重庆理工大学 掀开了人机博弈中机器取胜的新篇章四。但是机- 研究生创新基金项目(ycx2018244). 通信作者：王宛宛.E-mail:1033104010@qq.com, 机博弈依然是人类在人工智能领域不断探索的新
DOI: 10.11992/tis.201812012 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20200323.1314.004.html 一种军棋机器博弈的多棋子协同博弈方法 张小川1 ，王宛宛2 ，彭丽蓉3 （1. 重庆理工大学 两江人工智能学院，重庆 400054; 2. 重庆理工大学 计算机科学与工程学院，重庆 400054; 3. 重庆工业职业技术学院 信息工程学院，重庆 401120） 摘 要：针对在军棋博弈不完全信息对弈中，面对棋子不同价值、不同位置、不同搭配所产生的不同棋力，传统 的单子意图搜索算法，不能满足棋子之间的协同性与沟通性，同时也缺乏对敌方的引诱与欺骗等高级对抗能 力。本文提出一种结合 UCT 搜索策略的高价值棋子博弈方法，实现高价值棋子协同博弈的策略。实战经验表 明：高价值多棋子军棋协同博弈策略优于单棋子军棋博弈策略。 关键词：机器博弈；军棋；协同博弈；Q 学习算法；攻守平衡；维度灾难；UCT；高价值棋子 中图分类号：TP311.5 文献标志码：A 文章编号：1673−4785(2020)02−0399−06 中文引用格式：张小川, 王宛宛, 彭丽蓉. 一种军棋机器博弈的多棋子协同博弈方法 [J]. 智能系统学报, 2020, 15(2): 399–404. 英文引用格式：ZHANG Xiaochuan, WANG Wanwan, PENG Lirong. A multi-chess collaborative game method for military chess game machine[J]. CAAI transactions on intelligent systems, 2020, 15(2): 399–404. A multi-chess collaborative game method for military chess game machine ZHANG Xiaochuan1 ，WANG Wanwan2 ，PENG Lirong3 (1. Liangjiang Institute of Artificial Intelligence, Chongqing University of Technology, Chongqing 400054, China; 2. School of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, China; 3. Faculty Information Engineering, Chongqing Industry Polytechnic College,Chongqing 401120, China) Abstract: Owing to incomplete information on the military chess and the different strengths of chess pieces with different values, positions, and combinations, the traditional single-intention search algorithm cannot satisfy the coordination and communication requirements of chess pieces and lacks advanced confrontation capabilities, such as temptation and deception of the enemy. This study proposes the combination of the high-value chess piece game method and the UCT search strategy to achieve a high-value chess piece cooperative game strategy that can be used to solve the problems of the military chess game. Practical experience shows that the high-value multipiece military chess game strategy is better than the high-value single-piece military chess game strategy. Keywords: computer game; military; collaborative game; Q learning algorithm; balance of attack and defend UCT; dimension disaster; high value chess piece; 机器博弈是人工智能领域重要的研究方向， 通过训练计算机下棋来衡量机器的智能程度，具 有人−机、机−机对弈 2 种形式，2016 年 Google 的 Alpha Go 战胜韩国围棋大师李世石使得人机博弈 变得家喻户晓[1] ，紧接着网络注册名 Master 线上 挑战中日韩围棋高手，以及升级版 Alpha Go Zero 以 4∶0 战胜世界围棋第一人柯洁等标志性事件， 掀开了人机博弈中机器取胜的新篇章[2]。但是机− 机博弈依然是人类在人工智能领域不断探索的新 收稿日期：2018−12−11. 网络出版日期：2020−03−23. 基金项目：国家自然科学基金项目 (61702063)；重庆理工大学 研究生创新基金项目 (ycx2018244). 通信作者：王宛宛. E-mail：1033104010@qq.com. 第 15 卷第 2 期 智 能 系 统 学 报 Vol.15 No.2 2020 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2020
·400· 智能系统学报 第15卷 坐标。 弈同时选择棋子组合，棋子不能及时沟通将会导 机器博弈根据博弈过程中信息的透明度可以 致系统无法确定多棋子协同博弈的动作。针对此 分为完备信息和非完备信息博弈。完备信息博弈 问题，机器博弈系统采取模拟走步解决此问题， 双方信息完全透明，对弈的双方完全了解彼此的 即根据MCTS模拟的结果结合强化学习结果进而 博弈信息，主流的完备信息博弈有中国象棋、围 制定棋子协同策略。因此，军棋机器博弈协同强 棋、五子棋等。而非完备信息博弈双方信息不完 化学习系统由模拟预测单元和强化学习单元构建 全透明，其中存在一定的欺诈信息，主流的非完 而成，其结构流程图如图1所示。在多棋子协同 备信息博弈有军棋、德州扑克、桥牌、斗地主等)。 博弈强化学习系统中，模拟预测单元利用博弈树 由于非完备信息博弈信息的不透明性导致其存在 搜索进行MCTS模拟，返回高价值走步，并反馈 博弈诱导、欺诈等行为，使得非完备信息博弈难 出其他棋子的走步及预测结果，并基于其反馈的 以攻克内。 结果完成多棋子强化学习算法。强化学习单元将 军棋博弈游戏中共有13类棋子，包括军 反馈回来的协同策略返还给动作预测单元进行协 师、旅、团、营、连、排、司令、工兵等9类军人棋 同策略预测模型更新9。 子以及地雷、炸弹、军旗等3类工具棋子。军棋 博弈游戏过程中由于棋子棋力不同，位置也不相 单棋1子行动价值 强化学习 同，因此在不一样的位置、不一样的棋子搭配的 联 模拟回报值 情况下，棋子所展现出来的战斗力也不相同。如 博 模拟走步 棋局 何根据棋子特性搭配出最佳棋力成为研究的 模拟回报值 重点。 单棋子行动价值 强化学习 1多棋子协同策略 图1强化学习模型 多棋子协同博弈通过利用人类先验知识，制 Fig.1 Reinforced learning model 定出既定的目标和可实行的作战规划，发挥出相 1.2Q学习算法应用 应的作战能力。其研究的目标是实现多棋子间协 机器博弈双方和多方下棋的过程可以看作一 同，发挥群体作战功能，而不是单兵能力的体现 个随机过程，服从马尔可夫序列过程，用元组<S, 与发挥。多棋子协同博弈的研究内容主要包括： a,d2,,a,f,f,,f,g,g,,g来表示一 多棋子优化协作、多棋子行为规划以及进行反馈 个多棋子协同博弈的随机策略，元组中n为军棋 学习。 博弈系统中棋子的个数，即25个：S为博弈当前 11多棋子联合定义 的局面，是一个12×5的矩阵；d,其中d表示棋子 在军棋机器博弈游戏中，各个棋子间的协作 i可以选择的作战行为序列的集合=1,2，…，n 关系是多种多样的，当博弈系统需要完成一个大 军棋机器博弈系统协同作战的行动序列为α'× 目标时，就需要多个棋子进行协同作战。多棋子 d,,×a”。f,其中=1,2，…，n,通过利用局面和 协同作战过程中会导致棋子间发生冲突，仅考虑 行动的积得到棋子的行动概率，即S×a×S→ 棋子单独作战将会错过最优的作战计划。基于 [0,1],g,其中=1,2，，n,通过局面及行棋动作 此，军棋机器博弈需要消除多方冲突的条件下产 返回一个强化收益函数，即S×a×S→R;在军棋 生最优的合作结果，使得机器博弈系统作战能力 机器多棋子协同博弈系统中，每个棋子的行动概 达到最优。军棋机器博弈系统中多棋子协同博弈 率都是根据所有棋子协同作战的结果得出的，强 策略取得好的作战力的时候，其组合策略就会得 化收益函数也是根据棋子协同作战后返回最高收 到一定的奖赏，遇到相同的情况下，相同的策略 益，根据棋局局面映射到棋子作战行为，采取协 趋势便会增强，强化学习的方法为多棋子协同作 同策略π。多棋子协同博弈强化学习方法转化为 战提供了高鲁棒性的学习方法，无监督的情况 在棋子局面状态空间到棋子协同作战行为的映射 下，棋子可以在不同的棋局下不断优化更新出最 学习。 优的协同策略。 Q强化学习算法是一种无监督的通过系统不 多棋子协同博弈策略在棋子强化学习过程中 断探索经验进而提高自身作战能力的算法，不需 的关键问题是确定棋子是否处于联合状态，并具 要人为干预和状态转移函数。当系统进行行为决 有与其他棋子间的协同动作。多棋子进行协同博 策时只需要选出返还结果Q(s,a,)的最大值，进而
坐标。 机器博弈根据博弈过程中信息的透明度可以 分为完备信息和非完备信息博弈。完备信息博弈 双方信息完全透明，对弈的双方完全了解彼此的 博弈信息，主流的完备信息博弈有中国象棋、围 棋、五子棋等。而非完备信息博弈双方信息不完 全透明，其中存在一定的欺诈信息，主流的非完 备信息博弈有军棋、德州扑克、桥牌、斗地主等[3]。 由于非完备信息博弈信息的不透明性导致其存在 博弈诱导、欺诈等行为，使得非完备信息博弈难 以攻克[4]。 军棋博弈游戏中共有 13 类棋子，包括军、 师、旅、团、营、连、排、司令、工兵等 9 类军人棋 子以及地雷、炸弹、军旗等 3 类工具棋子。军棋 博弈游戏过程中由于棋子棋力不同，位置也不相 同，因此在不一样的位置、不一样的棋子搭配的 情况下，棋子所展现出来的战斗力也不相同。如 何根据棋子特性搭配出最佳棋力成为研究的 重点。 1 多棋子协同策略 多棋子协同博弈通过利用人类先验知识，制 定出既定的目标和可实行的作战规划，发挥出相 应的作战能力。其研究的目标是实现多棋子间协 同，发挥群体作战功能，而不是单兵能力的体现 与发挥。多棋子协同博弈的研究内容主要包括： 多棋子优化协作、多棋子行为规划以及进行反馈 学习[5]。 1.1 多棋子联合定义 在军棋机器博弈游戏中，各个棋子间的协作 关系是多种多样的，当博弈系统需要完成一个大 目标时，就需要多个棋子进行协同作战。多棋子 协同作战过程中会导致棋子间发生冲突，仅考虑 棋子单独作战将会错过最优的作战计划[6]。基于 此，军棋机器博弈需要消除多方冲突的条件下产 生最优的合作结果，使得机器博弈系统作战能力 达到最优。军棋机器博弈系统中多棋子协同博弈 策略取得好的作战力的时候，其组合策略就会得 到一定的奖赏，遇到相同的情况下，相同的策略 趋势便会增强，强化学习的方法为多棋子协同作 战提供了高鲁棒性的学习方法，无监督的情况 下，棋子可以在不同的棋局下不断优化更新出最 优的协同策略[7-8]。 多棋子协同博弈策略在棋子强化学习过程中 的关键问题是确定棋子是否处于联合状态，并具 有与其他棋子间的协同动作。多棋子进行协同博 弈同时选择棋子组合，棋子不能及时沟通将会导 致系统无法确定多棋子协同博弈的动作。针对此 问题，机器博弈系统采取模拟走步解决此问题， 即根据 MCTS 模拟的结果结合强化学习结果进而 制定棋子协同策略。因此，军棋机器博弈协同强 化学习系统由模拟预测单元和强化学习单元构建 而成，其结构流程图如图 1 所示。在多棋子协同 博弈强化学习系统中，模拟预测单元利用博弈树 搜索进行 MCTS 模拟，返回高价值走步，并反馈 出其他棋子的走步及预测结果，并基于其反馈的 结果完成多棋子强化学习算法。强化学习单元将 反馈回来的协同策略返还给动作预测单元进行协 同策略预测模型更新[9]。 … a1 an 棋局 强化学习 模拟回报值 模拟回报值 模拟走步 强化学习 联 合 博 弈 单棋1子行动价值 单棋n子行动价值 图 1 强化学习模型 Fig. 1 Reinforced learning model 1.2 Q 学习算法应用 S×a×S → [0,1] S×a×S → R π 机器博弈双方和多方下棋的过程可以看作一 个随机过程，服从马尔可夫序列过程，用元组来表示一 个多棋子协同博弈的随机策略，元组中 n 为军棋 博弈系统中棋子的个数，即 25 个；S 为博弈当前 的局面，是一个 12×5 的矩阵；a i ，其中 a i 表示棋子 i 可以选择的作战行为序列的集合 i=1，2，···，n。 军棋机器博弈系统协同作战的行动序列为 a 1 × a 2 ，···，×a n。f i ，其中 i=1，2，···，n，通过利用局面和 行动的积得到棋子的行动概率，即 ，g i ，其中 i=1，2，···，n，通过局面及行棋动作 返回一个强化收益函数，即 ；在军棋 机器多棋子协同博弈系统中，每个棋子的行动概 率都是根据所有棋子协同作战的结果得出的，强 化收益函数也是根据棋子协同作战后返回最高收 益，根据棋局局面映射到棋子作战行为，采取协 同策略 。多棋子协同博弈强化学习方法转化为 在棋子局面状态空间到棋子协同作战行为的映射 学习。 Q(st ,at) Q 强化学习算法是一种无监督的通过系统不 断探索经验进而提高自身作战能力的算法，不需 要人为干预和状态转移函数。当系统进行行为决 策时只需要选出返还结果 的最大值，进而 ·400· 智 能 系 统 学 报 第 15 卷
第2期 张小川，等：一种军棋机器博弈的多棋子协同博弈方法 ·401· 简化了多棋子协同博弈系统的决策过程，Q强化 UCB值又被称为上限置信区间值，UCB公式为 学习方法扩展为多棋子强化学习算法。 UCB;=V+k v2In(n/n) Q(Si.a)=(1+a)O(Si.a)+ 式中：V作为老虎机第i支手臂获得的平均收益； a(S.a)+yr(S+i)…,(S+i)Q-1(S+1)] kV2n(n/n)是老虎机在搜索其他手臂时探索的未 r6i山rs,r06i= 知收益，存在一定未知风险：k值作为一个风险参 alea 数，当k值设大时，注重对其他最优结果的探索， ∑pS4,a,PS4,,,PS,ax 当k值设小时，老虎机博弈系统注重以前高收益 0-1(S1d,a2,…,d 手臂，系统偏向于保守。N是所有手臂的访问次 数，m:则表示任意i支手臂的访问次数。 式中：S:为多棋子协同博弈系统中棋子i的状态 UCT搜索算法是在蒙特卡洛搜索的基础上， 变量；a,=a,d2,…,d)为多棋子协同博弈系统中 根据模拟出来的结果优先选择出胜率高的根节 多棋子的协同行为序列；S+:为行动后的下一步 点，最后根据选择出来的胜率较高的根节点进行 棋盘的局面，局面状态通过函数S41=f(S,a)进 多次访问，增加高价值节点的访问次数，以最高 行转移；棋子ⅰ的作战行为通过模拟回报策略π 访问数的节点作为最优值。 得到；PS+1,)是棋子i在局面S41的情况下模 2.2发现高价值棋子 拟选择出d走步的概率。 军棋机器博弈系统采用多棋子协同博弈，开 2UCT指导激活棋子 局时，局面中有50个棋子，60个棋位。并非所有 棋子都进行系统协同作战，系统根据不同的布局 棋子间联合作战，通过反馈学习进行小规模 采用局部令、强、中、弱棋子的搭配进行配合出 棋子合作规划，实现对敌方欺诈是可以实现的。 战，而UCT搜索算法则在系统中起到筛选作用， 但是，军棋机器博弈系统中，每方都有25个棋 为棋子协同作战提供指导方向，军棋机器博弈多 子，棋子种类又分为12种，假设在军棋机器博弈 棋子协同作战系统将搜索重点布局在高价值棋子 过程中，每个棋子有A种走步，而在Q学习的过 上面，进而减少搜索的棋子数量，避免了搜索系 程中，25个棋子都会返回一个Q(s,a,)表，那么其 统出现“维数灾难”问题。通过多棋子Q强化学 全部状态空间大小为4。由以上分析可以看出， 习方法加强棋子之间策略学习，以使得多棋子可 棋盘上面棋子数越多，空间复杂度就越高，并且 以配合出战，例如采用强子和弱子配合引诱对方 成指数倍增长，进而导致军棋机器博弈系统出现 的中子来吃弱子，而灭掉对方的中子四。 “维度灾难”问题。 UCT搜索算法指导激活多棋子强化Q学习 军棋计算机博弈系统根据军棋棋子数量多造 算法的流程如下所示： 成的“维度灾难”问题，系统参考神经元特征，例 1)初始化系统的值函数、学习因子以及马尔 如举一下胳膊时，并不会激活身体所有神经元， 可夫过程的状态集合g(s,a): 提出一种优先利用UCT搜索算法剪掉大部分棋 2)将当前节点作为博弈树系统的根节点，从 子的行动序列，而把搜索学习算法重点放在几个 根节点进行扩展； 高价值棋子之间的协作上面的方法。 3)通过UCT公式计算各个节点的UCB值， 2.1UCT算法 并为节点赋值，选择出UCB较高的节点作为扩展 2006年匈牙利学者Levente Kocsis和加拿大 结点进行搜索； 学者Csaba Szepesvari共同合作提出一种MCTS 4)依次搜索节点，并检查是否为叶子节点， 算法与UCB公式相结合的UCT搜索算法。 若不是叶子节点则重复第3)步搜索； UCB(upper confidence bound)搜索算法最初设计的 5)核查该节点被搜索次数是否达到系统规定 目的是用来解决多臂老虎机之类的问题。多臂老 访问次数，如果达到规定的访问次数，则将该节 虎机问题是指在多臂老虎机上，通过摇动每个老 点进行扩展，并在访问次数上加1： 虎机手臂都可以得到一定的收益，如果玩家想要 6)筛选出当前高价值节点状态下激活1的棋 摇到最大的收益就要根据以前摇臂的经验去判断 子，按照系统策略π(s)=arg max Q(s,a,)计算出当 摇哪个手臂得到的收益值最大。UCB搜索算法 前状态下的动作a,并对下一局面状态S1进行 是一种离线的强化学习策略，即根据以往的经验 观察； 知识去帮助系统做出未来的决策，UCB算法中的 7)根据多棋子强化学习Q值迭代公式迭代
简化了多棋子协同博弈系统的决策过程，Q 强化 学习方法扩展为多棋子强化学习算法。 Q i t (S i t ,at) = (1+α)Q i t−1 (S i t ,at)+ α[r i t (S i t ,at)+γπ1 (S t+1),··· , πn (S t+1)Q i t−1 (S t+1)] π 1 (S t+1), π2 (S t+1),··· , πn (S t+1)Q i t (S t+1) = ∑ a 1∈a ··· ∑ a n∈a P 1 t (S t+1 ,a 1 ),P 2 t (S t+1 ,a 2 ),··· ,P n t (S t+1 ,a n )× Q i t−1 (S i t−1 ,a 1 ,a 2 ,··· ,a n ) S i t at = {a 1 ,a 2 ,··· ,a n } S t+1 S t+1 = f i t (S t ,at) πi P i t (S t+1,a i ) S t+1 a i 式中： 为多棋子协同博弈系统中棋子 i 的状态 变量； 为多棋子协同博弈系统中 多棋子的协同行为序列； 为行动后的下一步 棋盘的局面，局面状态通过函数 进 行转移；棋子 i 的作战行为通过模拟回报策略 得到； 是棋子 i 在局面 的情况下模 拟选择出 走步的概率。 2 UCT 指导激活棋子 Q i t (st ,at) 棋子间联合作战，通过反馈学习进行小规模 棋子合作规划，实现对敌方欺诈是可以实现的。 但是，军棋机器博弈系统中，每方都有 25 个棋 子，棋子种类又分为 12 种，假设在军棋机器博弈 过程中，每个棋子有 A 种走步，而在 Q 学习的过 程中，25 个棋子都会返回一个 表，那么其 全部状态空间大小为 A 25。由以上分析可以看出， 棋盘上面棋子数越多，空间复杂度就越高，并且 成指数倍增长，进而导致军棋机器博弈系统出现 “维度灾难”问题[10]。 军棋计算机博弈系统根据军棋棋子数量多造 成的“维度灾难”问题，系统参考神经元特征，例 如举一下胳膊时，并不会激活身体所有神经元， 提出一种优先利用 UCT 搜索算法剪掉大部分棋 子的行动序列，而把搜索学习算法重点放在几个 高价值棋子之间的协作上面的方法。 2.1 UCT 算法 2006 年匈牙利学者 Levente Kocsis 和加拿大 学者 Csaba Szepesvari 共同合作提出一种 MCTS 算 法 与 U CB 公式相结合 的 U CT 搜索算法。 UCB(upper confidence bound) 搜索算法最初设计的 目的是用来解决多臂老虎机之类的问题。多臂老 虎机问题是指在多臂老虎机上，通过摇动每个老 虎机手臂都可以得到一定的收益，如果玩家想要 摇到最大的收益就要根据以前摇臂的经验去判断 摇哪个手臂得到的收益值最大。UCB 搜索算法 是一种离线的强化学习策略，即根据以往的经验 知识去帮助系统做出未来的决策，UCB 算法中的 UCB 值又被称为上限置信区间值，UCB 公式为 UCBi = Vi +k √ 2ln(n/ni) Vi k √ 2ln(n/ni) ni 式中： 作为老虎机第 i 支手臂获得的平均收益； 是老虎机在搜索其他手臂时探索的未 知收益，存在一定未知风险；k 值作为一个风险参 数，当 k 值设大时，注重对其他最优结果的探索， 当 k 值设小时，老虎机博弈系统注重以前高收益 手臂，系统偏向于保守。N 是所有手臂的访问次 数， 则表示任意 i 支手臂的访问次数。 UCT 搜索算法是在蒙特卡洛搜索的基础上， 根据模拟出来的结果优先选择出胜率高的根节 点，最后根据选择出来的胜率较高的根节点进行 多次访问，增加高价值节点的访问次数，以最高 访问数的节点作为最优值[11]。 2.2 发现高价值棋子 军棋机器博弈系统采用多棋子协同博弈，开 局时，局面中有 50 个棋子，60 个棋位。并非所有 棋子都进行系统协同作战，系统根据不同的布局 采用局部令、强、中、弱棋子的搭配进行配合出 战，而 UCT 搜索算法则在系统中起到筛选作用， 为棋子协同作战提供指导方向，军棋机器博弈多 棋子协同作战系统将搜索重点布局在高价值棋子 上面，进而减少搜索的棋子数量，避免了搜索系 统出现“维数灾难”问题。通过多棋子 Q 强化学 习方法加强棋子之间策略学习，以使得多棋子可 以配合出战，例如采用强子和弱子配合引诱对方 的中子来吃弱子，而灭掉对方的中子[12]。 UCT 搜索算法指导激活多棋子强化 Q 学习 算法的流程如下所示： Q i t (st ,at) 1) 初始化系统的值函数、学习因子以及马尔 可夫过程的状态集合 ； 2) 将当前节点作为博弈树系统的根节点，从 根节点进行扩展； 3) 通过 UCT 公式计算各个节点的 UCB 值， 并为节点赋值，选择出 UCB 较高的节点作为扩展 结点进行搜索； 4) 依次搜索节点，并检查是否为叶子节点， 若不是叶子节点则重复第 3) 步搜索； 5) 核查该节点被搜索次数是否达到系统规定 访问次数，如果达到规定的访问次数，则将该节 点进行扩展，并在访问次数上加 1； π ∗ (st) = argmax at Q i t (st ,at) at S t+1 6) 筛选出当前高价值节点状态下激活 1 的棋 子，按照系统策略 计算出当 前状态下的动作 ，并对下一局面状态 进行 观察； 7) 根据多棋子强化学习 Q 值迭代公式迭代 第 2 期 张小川，等：一种军棋机器博弈的多棋子协同博弈方法 ·401·
·402· 智能系统学报 第15卷 出新的局面-行为对的值函数Q(s,a,): 600 8)判断是否满足学习的终止条件，若满足则 里500 结束学习，不满足则返回第2)步继续迭代。判定 当前状态是否满足多棋子Q学习算法的终止条 件，如果满足，则停止学习，否则返回第2)步。 200 一极大极小值 2.3构建军棋博弈系统 +a-β -MCTS 由于军棋在开局的时候对敌方信息处于未 -UCT 知状态。因此在军棋博弈系统中先跟据人类先 0 0.2 0.40.6 0.810 验知识以及蒙特卡罗模拟对棋盘进行完备化。 搜索模块采用UCT搜索算法模拟走步，返回价 图3y为固定值0.2，a取值参数对比 值高并且模拟次数多的走步，并激活行动价值高 Fig.3 The comparison chart ofy is the value of 0.2 with a is a parameter 的走步。通过Q学习算法对棋子协同矩阵优化， 800 选择出最优走步。军棋博弈系统流程图如图2 空700 所示。 开始 500 400 当前棋盘（非完备） 300 一极大极小值 、200 +a-B MCTS 抽样棋盘（完备） 100 UCT 0.2 0.40.6 0.81.0 走法产生器 图4y为固定值0.4，a取值参数对比 UCT搜索模块 Fig.4 The comparison chart ofy is the value of 0.4 with a is a parameter 局面估值 1000 +极大极小值 900 —a-B 800 ◆MCTS 模拟结束一 +UCT 600 统计模拟次数并激活 500 价值高的走步 400 300 Q学习选出棋子 200 配合策略 0.2 0.40.6 0.81.0 最终走步 图5y为固定值0.6，a取值参数对比 Fig.5 The comparison chart ofy is the value of 0.6 with a 结束 is a parameter 800 图2军棋博弈搜索系统流程 Fig.2 Flow chart of the military chess game search system 600 3实验结果分析 500 400 为了测试多棋子Q强化学习算法在实战中是 300 ◆极大极小值 否占据优势，本文采用与其他算法系统进行对打 200 -a-B 100 。MCTS 模式测试本算法的实用性，通过分先后手对战极 ·UCT 0 0.2 0.40.6 0.8 1.0 大极小值搜索算法、alpha-beta搜索算法、 d MCTS搜索算法以及UCT搜索算法各1000局并 图6Y为固定值0.8，a取值参数对比 不断调整多棋子Q强化学习算法的参数，以得到 Fig.6 The comparison chart ofy is the value of 0.8 with a 最优值，实验结果如图3~7所示。 is a parameter
Q i t (st 出新的局面−行为对的值函数 ,at) ； 8) 判断是否满足学习的终止条件，若满足则 结束学习，不满足则返回第 2) 步继续迭代。判定 当前状态是否满足多棋子 Q 学习算法的终止条 件，如果满足，则停止学习，否则返回第 2) 步。 2.3 构建军棋博弈系统 由于军棋在开局的时候对敌方信息处于未 知状态。因此在军棋博弈系统中先跟据人类先 验知识以及蒙特卡罗模拟对棋盘进行完备化[13]。 搜索模块采用 UCT 搜索算法模拟走步，返回价 值高并且模拟次数多的走步，并激活行动价值高 的走步。通过 Q 学习算法对棋子协同矩阵优化， 选择出最优走步。军棋博弈系统流程图如图 2 所示。 图 2 军棋博弈搜索系统流程 Fig. 2 Flow chart of the military chess game search system 3 实验结果分析 为了测试多棋子 Q 强化学习算法在实战中是 否占据优势，本文采用与其他算法系统进行对打 模式测试本算法的实用性，通过分先后手对战极 大极小值搜索算法、 alpha−bet a 搜索算法、 MCTS 搜索算法以及 UCT 搜索算法各 1 000 局并 不断调整多棋子 Q 强化学习算法的参数，以得到 最优值，实验结果如图 3~7 所示。 0 100 200 300 400 500 600 极大极小值 α-β MCTS UCT Q学习算法胜利局数/局 α 0.2 0.4 0.6 0.8 1.0 图 3 γ 为固定值 0.2，α 取值参数对比 Fig. 3 The comparison chart of γ is the value of 0.2 with α is a parameter α 0.2 0.4 0.6 0.8 1.0 极大极小值 α-β MCTS UCT 0 100 200 300 400 500 600 700 800 Q学习算法胜利局数/局 图 4 γ 为固定值 0.4，α 取值参数对比 Fig. 4 The comparison chart of γ is the value of 0.4 with α is a parameter α 0.2 0.4 0.6 0.8 1.0 极大极小值 α-β MCTS UCT 200 300 400 500 600 700 800 900 1 000 Q学习算法胜利局数/局 图 5 γ 为固定值 0.6, α 取值参数对比 Fig. 5 The comparison chart of γ is the value of 0.6 with α is a parameter α 0.2 0.4 0.6 0.8 1.0 极大极小值 α-β MCTS UCT 200 100 0 300 400 500 600 700 800 Q学习算法胜利局数/局 图 6 γ 为固定值 0.8，α 取值参数对比 Fig. 6 The comparison chart of γ is the value of 0.8 with α is a parameter ·402· 智 能 系 统 学 报 第 15 卷
第2期 张小川，等：一种军棋机器博弈的多棋子协同博弈方法 ·403· 600, 一极大极小值 效率，值越大，学习效率就越高。y参数影响着系 500 a-B 统学习过程中经验的影响力，y值越大，以往的经 ◆MCTS 400 UCT 验就显得越重要。当α=0.4，y=0.6时多棋子Q强 300 化学习系统对战其它算法系统的结果相对最好。 200 单子作战系统重防守、轻攻击，很难做到主 动攻击。而加入多棋子协同作战策略后的军棋机 器博弈系统能够自我组织协同策略，多棋子联合 0.2 0.40.6 0.81.0 作战，增加了系统的主动进攻意识。本文为了测 试军棋多棋子协同博弈系统主动作战意识是否提 图7Y为固定值1，a取值参数对比 Fig.7 The comparison chart ofy is the value of 1 with a is 高，采用了与其它搜索算法系统对战的模式，并 a parameter 统计出棋子作战过程中主动进攻的步数进行对比 由以上实验结果可知，参数α和y对系统的 研究，研究发现该系统能够达到攻守平衡的状 作战能力影响极大，α参数值影响着系统学习的 态，统计结果如表1所示。 表1算法系统走步对比 Table 1 The comparison table of algorithm system walking 非 方式 极大极小搜索 a-搜索 MCTS搜索 UCT搜索 Q强化学习 进攻 > 9 13 9 21 防守 24 25 29 27 18 磨棋 29 23 24 26 19 军棋多棋子协同博弈系统由于棋子种类多的 法进行高价值棋子激活，分别对战500局后，在军 问题导致的“维度灾难”问题成为系统对战成败 棋博弈的69步范围之内计算出每一步的平均搜 的关键性因素，针对此问题系统采用多种搜索算 索时间如图8所示。 16 米一未加激活算法 +一极大极小值激活 O-MCTS激活 A-UCT激活 13172125293337414549535761656973 博弈步数/步 图8激活算法系统走步搜索时间对比 Fig.8 The comparison chart of Activation algorithm system walking search time 由图8可知，在未加激活算法时搜索的时间博弈系统中多棋子协同矩阵，增加了多棋子协同 较长，而军棋机器博弈比赛是在限定的时间内搜 作战的意识，增强了博弈系统主动出击诱导敌方 索到走步，否则认为系统搜索超时判负，加入各 的进攻趋势。利用部分重要棋子激活的方法解决 种激活算法后，系统搜索时间明显降低，尤其在 了棋子数量巨大造成的“维度灾难”问题，使得搜 加入UCT搜索算法时，系统搜索时间降低最明显。 索时间得到提升，避免了军棋计算机博弈系统在 4结束语 正式比赛过程中由于超时被判负的情况。未来将 考虑利用计算智能算法加入此系统，进一步优化 本文利用Q学算法优化迭代更新军棋计算机 多棋子协同矩阵
α 0.2 0.4 0.6 0.8 1.0 极大极小值 α-β MCTS UCT 200 100 0 300 400 500 600 Q学习算法胜利局数/局 图 7 γ 为固定值 1， α 取值参数对比 Fig. 7 The comparison chart of γ is the value of 1 with α is a parameter α γ α 由以上实验结果可知，参数 和 对系统的 作战能力影响极大， 参数值影响着系统学习的 γ γ α γ 效率，值越大，学习效率就越高。 参数影响着系 统学习过程中经验的影响力， 值越大，以往的经 验就显得越重要。当 =0.4， =0.6 时多棋子 Q 强 化学习系统对战其它算法系统的结果相对最好。 单子作战系统重防守、轻攻击，很难做到主 动攻击。而加入多棋子协同作战策略后的军棋机 器博弈系统能够自我组织协同策略，多棋子联合 作战，增加了系统的主动进攻意识。本文为了测 试军棋多棋子协同博弈系统主动作战意识是否提 高，采用了与其它搜索算法系统对战的模式，并 统计出棋子作战过程中主动进攻的步数进行对比 研究，研究发现该系统能够达到攻守平衡的状 态，统计结果如表 1 所示。 表 1 算法系统走步对比 Table 1 The comparison table of algorithm system walking 步 方式 极大极小搜索 α−β搜索 MCTS搜索 UCT搜索 Q强化学习 进攻 7 9 13 12 21 防守 24 25 29 27 18 磨棋 29 23 24 26 19 军棋多棋子协同博弈系统由于棋子种类多的 问题导致的“维度灾难”问题成为系统对战成败 的关键性因素，针对此问题系统采用多种搜索算 法进行高价值棋子激活，分别对战 500 局后，在军 棋博弈的 69 步范围之内计算出每一步的平均搜 索时间如图 8 所示[14]。 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 0 2 4 6 8 10 12 14 16 未加激活算法 极大极小值激活 MCTS激活 UCT激活 t/s 博弈步数/步 图 8 激活算法系统走步搜索时间对比 Fig. 8 The comparison chart of Activation algorithm system walking search time 由图 8 可知，在未加激活算法时搜索的时间 较长，而军棋机器博弈比赛是在限定的时间内搜 索到走步，否则认为系统搜索超时判负，加入各 种激活算法后，系统搜索时间明显降低，尤其在 加入 UCT 搜索算法时，系统搜索时间降低最明显。 4 结束语 本文利用 Q 学算法优化迭代更新军棋计算机 博弈系统中多棋子协同矩阵，增加了多棋子协同 作战的意识，增强了博弈系统主动出击诱导敌方 的进攻趋势。利用部分重要棋子激活的方法解决 了棋子数量巨大造成的“维度灾难”问题，使得搜 索时间得到提升，避免了军棋计算机博弈系统在 正式比赛过程中由于超时被判负的情况。未来将 考虑利用计算智能算法加入此系统，进一步优化 多棋子协同矩阵[15]。 第 2 期 张小川，等：一种军棋机器博弈的多棋子协同博弈方法 ·403·
·404· 智能系统学报 第15卷 参考文献： QIAO Lin.Study of Q-learning algorithm in multi-agent system[D].Nanjing:Nanjing University of Posts and [1]陶九阳，吴琳，胡晓峰.AlphaGo技术原理分析及人工智 Telecommunications,2012. 能军事应用展望[.指挥与控制学报，2016,2(2)： [11]梁国军，谢垂益，胡伶俐，等.UCT算法在不围棋博弈中 114-120 的实现).韶关学院学报，2015,36(8)17-21. TAO Jiuyang,WU Lin,HU Xiaofeng.Principle analysis Liang Guojun,Xie Chuiyi,Hu Lingli,et al.An imple- on AlphaGo and perspective in military application of arti- mentation of UCT algorithm for nogo game[J].Journal of ficial intelligence[J].Journal of command and control, Shaoguan university,2015,36(8):17-21. 2016,2(2):114-120. [12]孟坤，王俊，闫桐.一种基于经验知识的军棋博弈算法 [2]CHEN J X.The evolution of computing:AlphaGo[J]. 设计与实现).智能计算机与应用，2017,7266-69. Computing in science&engineering,2016,18(4):4-7. MENG Kun,WANG Jun,YAN Tong.Design and imple- [3]李翔，姜晓红，陈英芝，等.基于手牌预测的多人无限注 mentation of a military chess game algorithm based on 德州扑克博弈方法.计算机学报，2018,41(1)：47-64. knowledge experience[J].Intelligent computer and applic- LI Xiang,JIANG Xiaohong,CHEN Yingzhi,et al.Game ation,.2017,7(2):66-69 in multiplayer no-limit texas hold'em based on hands pre- [13]孙英龙.非完美信息博弈算法研究与军棋博弈系统设 diction[J].Chinese journal of computers,2018,41(1): 计与实现D].沈阳：东北大学，2013 47-64. SUN Yinglong.The study on imperfect information game [4]王亚杰，邱虹坤，吴燕燕，等.计算机博弈的研究与发 and design and implementation of military chess 展[J.智能系统学报，2016,11(6)：788-798 system[D].Shenyang:Northeastern University,2013. WANG Yajie,QIU Hongkun,WU Yanyan,et al.Re- [14王学厚.群体智能优化的计算模式和方法研究与应 search and development of computer games[J].CAAI 用D].北京：华北电力大学，2011. transactions on intelligent systems,2016,11(6):788-798. WANG Xuehou.Research on computational mode of [5]HONG Yiguang,CHEN Guanrong.BUSHNELL L.Tech- swarm intelligent optimization and applications[D]. nical communique:distributed observers design for leader- Beijing:North China Electric Power University,2011. following control of multi-agent networks[J].Automatica, [15]张小川，桑瑞婷，周泽红，等.一种基于双通道卷积神经 2017,443):846-850. 网络的短文本分类方法).重庆理工大学学报（自然科 [6]滕雯娟.基于虚拟遗憾最小化算法的德州扑克机器博弈 学，2019,33(1)45-52. 研究D].哈尔滨：哈尔滨工业大学，2015. ZHANG Xiaochuan,SANG Ruiting,ZHOU Zehong,et TENG Wenjuan.Research on texas poker game based on al.A Short Text Classification Method Based on Two counterfactual regret minimization algorithm[D].Harbin: Channel Convolutional Neural Network[J].Journal of Harbin Institute of Technology,2015 [7]VAN HASSELT H.GUEZ A,SILVER D.Deep reinforce- Chongqing University of Technology(Natural Science), 2019,33(1):45-52 ment learning with double q-learning[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence.Ari- 作者简介： zona,USA,2015 张小川，教授，中国人工智能学会 [8]史晓茹，侯媛彬，张涛.不完全信息博弈的机器人对抗决 机器博弈专委会主任、《CAAI Trans- 策[).智能系统学报，2011,6(2)：147-151. actions on Intelligence Technology》副 主编，人工智能系统研究所所长、两江 SHI Xiaoru,HOU Yuanbin,ZHANG Tao.The decision- 人工智能学院副院长，主要研究方向 making system of robots based on an incomplete informa- 为机器博弈、智能机器人、软件工程。 tion game[J].CAAI transactions on intelligent systems, 主持纵向项目35项、横向项目45项， 2011,6(2):147-151 获省部级奖项4项。发表学术论文90余篇。 [9]MICHAEL L.INCZE,SCOTT R.SIDELEAU,CHRIS GAGNER,and CHARLES A.PIPPIN.(2015).Commu- 王宛宛，硕士研究生，主要研究方 nication and collaboration of heterogeneous unmanned sys- 向为人工智能、机器博弈。 tems using the joint architecture for Unmanned Systems (JAUS)standards[Cl//OCEANS 2015-Genova.IEEE. [10]乔林.多智能体系统中的Q学习算法研究D].南京：南 京邮电大学，2012
参考文献： 陶九阳, 吴琳, 胡晓峰. AlphaGo 技术原理分析及人工智 能军事应用展望 [J]. 指挥与控制学报, 2016, 2(2): 114–120. TAO Jiuyang, WU Lin, HU Xiaofeng. Principle analysis on AlphaGo and perspective in military application of artificial intelligence[J]. Journal of command and control, 2016, 2(2): 114–120. [1] CHEN J X. The evolution of computing: AlphaGo[J]. Computing in science & engineering, 2016, 18(4): 4–7. [2] 李翔, 姜晓红, 陈英芝, 等. 基于手牌预测的多人无限注 德州扑克博弈方法 [J]. 计算机学报, 2018, 41(1): 47–64. LI Xiang, JIANG Xiaohong, CHEN Yingzhi, et al. Game in multiplayer no-limit texas hold’em based on hands prediction[J]. Chinese journal of computers, 2018, 41(1): 47–64. [3] 王亚杰, 邱虹坤, 吴燕燕, 等. 计算机博弈的研究与发 展 [J]. 智能系统学报, 2016, 11(6): 788–798. WANG Yajie, QIU Hongkun, WU Yanyan, et al. Research and development of computer games[J]. CAAI transactions on intelligent systems, 2016, 11(6): 788–798. [4] HONG Yiguang, CHEN Guanrong, BUSHNELL L. Technical communique: distributed observers design for leaderfollowing control of multi-agent networks[J]. Automatica, 2017, 44(3): 846–850. [5] 滕雯娟. 基于虚拟遗憾最小化算法的德州扑克机器博弈 研究 [D]. 哈尔滨: 哈尔滨工业大学, 2015. TENG Wenjuan. Research on texas poker game based on counterfactual regret minimization algorithm[D]. Harbin: Harbin Institute of Technology, 2015. [6] VAN HASSELT H, GUEZ A, SILVER D. Deep reinforcement learning with double q-learning[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence. Arizona, USA, 2015. [7] 史晓茹, 侯媛彬, 张涛. 不完全信息博弈的机器人对抗决 策 [J]. 智能系统学报, 2011, 6(2): 147–151. SHI Xiaoru, HOU Yuanbin, ZHANG Tao. The decisionmaking system of robots based on an incomplete information game[J]. CAAI transactions on intelligent systems, 2011, 6(2): 147–151. [8] MICHAEL L. INCZE, SCOTT R. SIDELEAU, CHRIS GAGNER, and CHARLES A. PIPPIN. (2015). Communication and collaboration of heterogeneous unmanned systems using the joint architecture for Unmanned Systems (JAUS) standards[C]//OCEANS 2015- Genova. IEEE. [9] 乔林. 多智能体系统中的 Q 学习算法研究 [D]. 南京: 南 京邮电大学, 2012. [10] QIAO Lin. Study of Q-learning algorithm in multi-agent system[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2012. 梁国军, 谢垂益, 胡伶俐, 等. UCT 算法在不围棋博弈中 的实现 [J]. 韶关学院学报, 2015, 36(8): 17–21. Liang Guojun, Xie Chuiyi, Hu Lingli , et al. An implementation of UCT algorithm for nogo game[J]. Journal of Shaoguan university, 2015, 36(8): 17–21. [11] 孟坤, 王俊, 闫桐. 一种基于经验知识的军棋博弈算法 设计与实现 [J]. 智能计算机与应用, 2017, 7(2): 66–69. MENG Kun, WANG Jun, YAN Tong. Design and implementation of a military chess game algorithm based on knowledge experience[J]. Intelligent computer and application, 2017, 7(2): 66–69. [12] 孙英龙. 非完美信息博弈算法研究与军棋博弈系统设 计与实现 [D]. 沈阳: 东北大学, 2013. SUN Yinglong. The study on imperfect information game and design and implementation of military chess system[D]. Shenyang: Northeastern University, 2013. [13] 王学厚. 群体智能优化的计算模式和方法研究与应 用 [D]. 北京: 华北电力大学, 2011. WANG Xuehou. Research on computational mode of swarm intelligent optimization and applications[D]. Beijing: North China Electric Power University, 2011. [14] 张小川, 桑瑞婷, 周泽红, 等. 一种基于双通道卷积神经 网络的短文本分类方法 [J]. 重庆理工大学学报( 自然科 学), 2019, 33(1): 45–52. ZHANG Xiaochuan, SANG Ruiting, ZHOU Zehong, et al. A Short Text Classification Method Based on Two Channel Convolutional Neural Network[J]. Journal of Chongqing University of Technology( Natural Science), 2019, 33(1): 45–52. [15] 作者简介： 张小川，教授，中国人工智能学会 机器博弈专委会主任、《CAAI Transactions on Intelligence Technology》副 主编，人工智能系统研究所所长、两江 人工智能学院副院长，主要研究方向 为机器博弈、智能机器人、软件工程。 主持纵向项目 35 项、横向项目 45 项， 获省部级奖项 4 项。发表学术论文 90 余 篇。 王宛宛，硕士研究生，主要研究方 向为人工智能、机器博弈。 ·404· 智 能 系 统 学 报 第 15 卷