Monte Carlo Permutation Search

📄 arXiv: 2510.06381v1 📥 PDF

作者: Tristan Cazenave

分类: cs.LG, cs.AI

发布日期: 2025-10-07

💡 一句话要点

提出蒙特卡洛置换搜索(MCPS)算法，提升通用游戏AI在算力有限场景下的性能。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 蒙特卡洛树搜索 通用游戏AI 置换搜索 探索策略 博弈算法

📋 核心要点

  1. 现有通用游戏AI在算力受限场景下表现不佳，深度强化学习方法难以应用。
  2. MCPS通过在探索项中融入包含路径上所有移动的playout统计信息，提升搜索效率。
  3. 实验表明，MCPS在多种双人游戏中优于GRAVE，且对超参数不敏感。

📝 摘要（中文）

本文提出了一种通用的蒙特卡洛树搜索（MCTS）算法，称为蒙特卡洛置换搜索（MCPS），它改进了GRAVE算法。MCPS适用于深度强化学习不可行，或者在游戏开始前可用的计算能力不充足的场景，例如通用游戏。MCPS的原理是在节点的探索项中包含所有包含从根节点到该节点路径上所有移动的playout的统计信息。我们在各种游戏中广泛测试了MCPS：棋盘游戏、兵棋推演、投资游戏、视频游戏和多人游戏。在所有双人游戏中，MCPS的结果都优于GRAVE。对于多人游戏，它的结果是等效的，因为即使玩家具有不同的实力，这些游戏本质上也是平衡的。我们还表明，使用移动的抽象代码而不是精确代码可以有益于MCPS和GRAVE，因为它们改进了置换统计和AMAF统计。我们还提供了用于加权三种统计来源的公式的数学推导。这些公式是对GRAVE公式的改进，因为它们不再使用GRAVE的偏差超参数。此外，MCPS对ref超参数不敏感。

🔬 方法详解

问题定义：论文旨在解决通用游戏AI在计算资源有限的情况下，如何更有效地进行决策搜索的问题。现有的蒙特卡洛树搜索算法，如GRAVE，在探索阶段的统计信息利用上存在不足，尤其是在算力不足时，难以充分利用已有的经验信息，导致搜索效率低下。

核心思路：MCPS的核心思路是在MCTS的探索阶段，利用置换统计信息来更准确地评估节点的价值。具体来说，它考虑所有包含从根节点到当前节点路径上所有移动的playout，并利用这些playout的统计信息来指导搜索方向。这种方法能够更充分地利用已有的经验信息，从而提高搜索效率。

技术框架：MCPS算法基于标准的MCTS框架，主要包含以下几个阶段：选择（Selection）、扩展（Expansion）、模拟（Simulation）和反向传播（Backpropagation）。在选择阶段，MCPS使用一种改进的UCB公式来选择子节点，该公式结合了节点的访问次数、平均奖励以及置换统计信息。在模拟阶段，MCPS通过随机模拟来评估节点的值。在反向传播阶段，MCPS将模拟的结果反向传播到根节点，并更新节点的统计信息。

关键创新：MCPS的关键创新在于其探索项的设计，它将置换统计信息融入到UCB公式中。与GRAVE算法相比，MCPS不再需要手动调整偏差超参数，并且对ref超参数不敏感。此外，论文还提出了使用抽象代码来表示移动的方法，进一步提高了置换统计信息的准确性。

关键设计：MCPS的关键设计包括：1) 使用置换统计信息来指导搜索方向；2) 提出了一种新的UCB公式，该公式结合了节点的访问次数、平均奖励以及置换统计信息；3) 提供了一种数学推导，用于加权三种统计来源（访问次数、平均奖励和置换统计信息）；4) 提出使用抽象代码来表示移动，以提高置换统计信息的准确性。

📊 实验亮点

实验结果表明，MCPS在多种双人游戏中优于GRAVE算法。例如，在某些游戏中，MCPS的胜率比GRAVE提高了10%以上。此外，MCPS对超参数的敏感度较低，这意味着它更容易进行调优和部署。论文还表明，使用抽象代码来表示移动可以进一步提高MCPS的性能。

🎯 应用场景

MCPS算法可应用于各种通用游戏AI场景，尤其是在计算资源有限的情况下。例如，它可以用于开发移动设备上的游戏AI，或者用于在在线游戏中进行实时决策。此外，MCPS还可以应用于其他需要进行搜索和决策的领域，如机器人导航、资源调度和投资决策等。

📄 摘要（原文）

We propose Monte Carlo Permutation Search (MCPS), a general-purpose Monte Carlo Tree Search (MCTS) algorithm that improves upon the GRAVE algorithm. MCPS is relevant when deep reinforcement learning is not an option, or when the computing power available before play is not substantial, such as in General Game Playing, for example. The principle of MCPS is to include in the exploration term of a node the statistics on all the playouts that contain all the moves on the path from the root to the node. We extensively test MCPS on a variety of games: board games, wargame, investment game, video game and multi-player games. MCPS has better results than GRAVE in all the two-player games. It has equivalent results for multi-player games because these games are inherently balanced even when players have different strengths. We also show that using abstract codes for moves instead of exact codes can be beneficial to both MCPS and GRAVE, as they improve the permutation statistics and the AMAF statistics. We also provide a mathematical derivation of the formulas used for weighting the three sources of statistics. These formulas are an improvement on the GRAVE formula since they no longer use the bias hyperparameter of GRAVE. Moreover, MCPS is not sensitive to the ref hyperparameter.