Aug, 2023

江郡：通过解决两人零和博弈中的不可传递性来掌握象棋

PDF
TL;DR通过分析超过 10,000 条人类象棋比赛记录，本文重点研究了象棋游戏中存在的传递性与非传递性元素，并引入了 JiangJun 算法，这是一种蒙特卡洛树搜索（MCTS）和策略空间响应神谕（PSRO）的创新组合，旨在近似纳什均衡。我们通过一个微信小程序对算法进行了经验评估，在与人类玩家的比赛中取得了 99.41％的胜率，达到大师级水平。量化指标如相对人群表现和可视化结果证实了该算法在克服非传递性方面的有效性。
non-transitivityxiangqijiangjun algorithmmonte-carlo tree searchnash equilibrium
发现论文，激发创造
  • 对称零和博弈中的开放式学习

    本文提出了一个几何框架来制定零和博弈中的智能体目标，以构建产生开放式学习的自适应目标序列，从而产生比现有算法更强的智能体集合。我们将 PSRO_rN 应用于两个高度非传递性的资源分配游戏，并发现 PSRO_rN 始终优于现有替代方案。

    Jan, 2019

  • 基于顺序潜力的球员评分

    该研究使用适当的可逆映射，将博弈应用于 Elo 评分，然后返回原始空间来提取博弈的可转移组件，并将其与已知的 sign-rank 概念相联系。

    Jun, 2023

  • 迈向对称多人游戏的有原则的超越人类水平 AI

    多人游戏的独特挑战在于均衡策略的非唯一性和代理人执行高度次优策略的风险。本文首次解决了多人对称标准形式游戏中的这些挑战，给出了 AI 代理人应该找到的正确解决方案以及能够证明解决该类游戏的通用算法框架。我们还证明了许多先前实用系统中开发的元算法甚至无法实现基本目标，即获得代理人的总奖励的平等份额。

    Jun, 2024

  • 真实世界的游戏看起来像陀螺

    本文研究现实世界游戏（如井字棋，围棋，星际争霸 II）的几何特性并证明它们与竞技场上的旋转体结构相似。此结构形成的不对称性带来了关于学习与策略的问题，我们用 9 个现实世界两人零和对称游戏进行了实证。

    Apr, 2020

  • AlphaZero 五子棋

    AlphaZero 算法通过将深度学习与蒙特卡洛树搜索相结合，在象棋、围棋和五子棋等棋盘游戏中取得了巨大的成功。

    Sep, 2023

  • 具有结构转移的零和马尔可夫博弈中可证明有效的虚拟博弈策略优化

    本研究在多智能体竞争的环境下对零和结构化 Markov 博弈问题的策略优化算法进行了提出和分析，考虑通过上置界乐观算法与虚拟博弈相结合的同时策略优化，从而使双方智能体的总体最优性差距以 $\widetilde {O}(\sqrt {K})$ 的速度收敛，其中 $K$ 为回合数量。

    Jul, 2022

  • 多人零和游戏中解决联盟困境的学习

    本研究通过对称的零和矩阵游戏，证明了联盟形成可以被看作是一个社会困境，并且实证表明，在多代理强化学习中，天真的方法往往失败。同时，我们引入了点对点的合约机制来发现和执行联盟。最后，我们将我们的代理模型推广到了包括时间延伸合约的情况，并提出了进一步研究的机会。

    Feb, 2020

  • 使用相关均衡元解算器进行非零和多智能体训练

    提出了用于训练 n 人，广义和形博弈的 Joint Policy-Space Response Oracles (JPSRO) 算法，并建议一种有前途的元解算程序 -- 相关均衡 (correlated equilibria)，并提出了最大基尼相关均衡 (MGCE) 的新解决方案概念。通过使用 CE 元解决程序对 JPSRO 进行多次实验，证明了在 n 人，广义和游戏中的收敛性。

    Jun, 2021

  • 弱可达情况下的零和马尔可夫博弈纳什均衡学习

    通过利用 Tsallis 熵正则化的值迭代方法，我们提出了一种合理且收敛的算法，在弱条件下以无耦合和单时间尺度算法的方式高效地实现了近似纳什均衡。该算法在多项式时间内学习近似纳什均衡，仅需要存在一个诱导不可约和非周期性马尔可夫链的策略对，从而明显减弱了过去的假设。我们的分析利用了负漂移不等式，并引入了 Tsallis 熵的新特性，这些特性具有独立的研究价值。

    Dec, 2023

  • 深度强化学习掌握麻将

    利用深度强化学习，包括全局奖励预测、指导预测和运行时策略自适应等新技术设计了名为 Suphx 的 AI 麻将程序，并在性能上超过了大多数顶尖的人类玩家，在 Tenhou 平台上被评为超过 99.99% 的所有官方排名人类玩家，标志着计算机程序首次在麻将中超越了大多数顶尖的人类玩家。

    Mar, 2020