华为、北大领衔提出“将军”算法：以99.41%胜率碾压人类象棋玩家

这一次，AI 又击败了人类。

由华为云人工智能领域 CTO 戴宗宏、北京大学人工智能研究院助理教授杨耀东领导的研究团队，开发了一种能够在象棋对局中以 99.41% 胜率碾压人类对手的算法——JiangJun（音译为“将军”）。

相关研究论文以“JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games”为题，已发表在预印本网站 arXiv 上。

将人类玩家作为对手，不断试错、迭代，是当前基于强化学习的 AI 智能体的普遍进化方式。近年来，考虑到现实场景中通常会同时存在多个智能体，研究人员将目光由单智能体领域延伸到了多智能体。

事实上，多智能体强化学习在多种游戏领域中也确实取得了显著的成功，在捉迷藏（Steam 的一款游戏）、围棋、星际争霸II、刀塔2 和军棋等游戏中已经得到印证。

然而，像 AlphaZero 和 AlphaGo 这样专注于对手近期表现进行训练的算法，在非传递性结构的博弈中可能无法稳定地获得胜利或达到理想的状态。尽管这个问题在不完全信息博弈中得到了深入研究，但在完全信息博弈中的研究相对较少。

完全信息博弈：每一位参与者都拥有所有其他参与者的特征、策略及得益函数等方面的准确信息的博弈，比如象棋。

不完全信息博弈：至少有一名参与者对于以上内容不完全了解，如西洋陆军棋。

目前，克服完全信息博弈中的非传递性问题仍然是一个未解决的研究问题。近期的研究重点集中在采用策略空间响应预言者（PSRO）算法来寻找纳什均衡，但是这些方法在完全信息博弈中尚未得到探究。

象棋的易接近性使其成为探索棋盘游戏和非传递性几何格局的绝佳对象。该研究深入探讨了象棋的复杂几何特性，利用超过 10000 场人类游戏对局的大规模数据集，揭示了象棋在传递性中间区域的显著非传递性。

为了解决非传递性问题，研究人员提出了 JiangJun 算法，与 AlphaZero 的自我对弈策略不同，该算法利用纳什响应来选择对手。

JiangJun 算法包括两个基本模块：MCTS 演算器（MCTS Actor）和人口生成器（Populationer）。这些组件共同利用蒙特卡洛树搜索（MCTS）技术在玩家群体内趋近纳什均衡。

JiangJun 算法的效力在一系列指标中得到了全面评估。研究人员提出了一种训练框架，该框架有效地利用了华为云 ModelArt 平台上高达 90 个 V100 GPU 的计算能力，将 JiangJun 算法训练至大师级水平。

多重指标，包括相对人口表现、纳什分布可视化以及主要两个嵌入维度的低维游戏景观可视化，共同证实了 JiangJun 算法在解决象棋非传递性问题方面的熟练程度。

另外，JiangJun 算法在胜率上显著超过其当代算法，与标准的 AlphaZero 象棋和行为克隆象棋相比，其胜率分别超过 85% 和 96.40%。在可剥削性评估中，JiangJun 算法（近似最佳响应的胜率为8.41%）与标准的 AlphaZero 象棋算法（25.53%）相比，明显更接近最优策略。

此外，研究人员在微信平台上设计了一个象棋小程序，在六个月的时间内，汇总了超过 7000 局 JiangJun 算法与人类对手之间的对局记录。据对局数据显示，JiangJun 算法以惊人的 99.41% 胜率击败人类对手。

除了接近 100% 的惊人胜率外，各种残局的案例研究显示，JiangJun 算法在灵活应对象棋残局复杂性方面也有很强的能力。

JiangJun 算法的问世，标志着 AI 在象棋领域取得了一次令人惊叹的成就。通过解决完全信息博弈中的非传递性问题，研究团队成功地引入了纳什响应和蒙特卡洛树搜索技术，为象棋这一博弈领域带来了全新的思维方式。这个算法不仅实现了惊人的胜率，更彰显了 AI 在处理复杂、不确定性问题上的强大能力。

参考链接：

https://arxiv.org/abs/2308.04719

https://openreview.net/forum?id=MMsyqXIJuk

https://sites.google.com/view/jiangjun-site/

来源：学术头条