🤖 machine learning

Monte Carlo Permutation Search

本文介绍了蒙特卡洛置换搜索（MCPS），这是一种通用型 MCTS 算法，通过将路径范围的模拟统计信息纳入探索项并推导出一种消除 GRAVE 偏差超参数需求的新加权公式，使其在六边形棋和围棋等游戏中优于 GRAVE 算法。

原作者： Tristan Cazenave

发布于 2026-05-27

📖 1 分钟阅读☕ 轻松阅读

原作者： Tristan Cazenave

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试解决一个复杂的谜题，比如围棋或六贯棋，但你没有超级计算机或训练有素的人工智能来告诉你最佳走法。相反，你必须在脑海中推演成千上万个随机未来场景，依靠“猜测与验证”来做决定。这就是一个名为**蒙特卡洛树搜索（MCTS）**的计算机程序的工作原理。

很长一段时间以来，进行这种猜测的最佳方法是一种名为GRAVE的算法。它擅长通过观察过去来预测未来，但这篇论文的作者 Tristan Cazenave 认为：“我们可以做得更好。”

他创造了一种名为**MCPS（蒙特卡洛排列搜索）**的新算法。以下是其工作原理的简单解释：

回顾过去的三种方式

为了决定下一步走什么，MCPS 通过三种不同的方式审视其随机对局（称为“模拟对局”）的历史记录。你可以将它们想象成相机上的三种不同镜头：

“精确路径”镜头（标准视图）：
它查看那些玩家为了到达当前位置而走了完全相同序列的走法，然后执行了我们正在测试的特定走法的对局。
- 类比： “我沿着主街走，左转，然后买了一杯咖啡。结果如何？”
“顺序无关”镜头（GRAVE 的升级版）：
它查看那些玩家为了到达该位置走了相同的走法，但顺序略有不同，且我们正在测试的特定走法在稍后出现的对局。
- 类比： “我先买了一杯咖啡，然后沿着主街走，接着左转。成分相同，只是食谱顺序不同。味道还好吗？”
- 为何有帮助： 在许多游戏中，落子的顺序并不改变最终的棋盘状态。因此，这个镜头让计算机能从更多的对局中学习，而不仅仅是那些顺序完全匹配的对局。
“排列”镜头（MCPS 的新秘密武器）：
这是新增的部分。它查看任何玩家使用了完全相同的一组走法（到达当前位置的路径 + 新走法）的对局，无论这些走法发生的顺序如何。
- 类比： “我用锤子、螺丝刀和钉子建了一个架子。不管我是先敲钉子还是先拧螺丝，只要用了这三样工具，架子就建好了。这种组合效果如何？”
- 限制： 在某些游戏中（如 AtariGo），顺序确实很重要，因为游戏可能会提前结束（例如提子）。MCPS 通过智能地对这些走法进行分组来处理这种情况。

“魔法公式”

论文指出，MCPS 并非只选择其中一种视图，而是将它们混合在一起。作者通过数学计算，找到了完美融合这三种信息源的最佳方式。

想象一下制作冰沙。你有三种水果（三种统计数据）。GRAVE 使用固定的配方，有时味道不佳。MCPS 则使用数学上完美的配方，能根据每种水果拥有的数据量自动调整用量。最棒的是？它不需要“口味测试”（即人工设定偏差参数）就能做得恰到好处；数学会自动完成这一切。

在现实世界中的表现

作者在五种不同类型的游戏中测试了 MCPS 与旧冠军（GRAVE）的表现：

六贯棋（完美匹配）： 在这种游戏中，走子顺序永远不会改变最终棋盘。MCPS 在这里是大赢家，尤其是在大棋盘上。这就像拥有一张显示所有可能路径的地图，而不仅仅是你走过的那一条。
围棋（深度思考者）： 在小棋盘上，两者势均力敌。但在大棋盘上，随着计算机被给予更多思考时间，MCPS 逐渐领先。它更善于利用额外时间深入挖掘最有希望的走法，而旧方法则陷入探索浅层选项的困境。
AtariGo（快速终结者）： 这是一种先提子者获胜的游戏。在这里，顺序确实很重要。令人惊讶的是，MCPS 仍然获胜，但其优势在小棋盘上最大，因为游戏结束得很快。在大棋盘上，游戏时间过长，使得“顺序无关”的技巧带来的帮助变小。
NoGo（稳健的赢家）： 这是一种提子者输掉的游戏。MCPS 几乎在所有地方都获胜，以稳定的优势持续击败旧方法。
战争游戏（速度恶魔）： 在这个自定义策略游戏中，MCPS 不仅玩得更好，而且玩得更快。它模拟了结束得更快的对局，并更快地找到获胜策略，从而使其能在相同时间内运行更多模拟。

核心结论

该论文声称，MCPS 是一种更智能、更高效的方式，让计算机在没有深度学习或大规模训练的情况下也能玩好游戏。

它的工作原理是认识到：在许多游戏中，你所走的走法集合比走这些走法的顺序更重要。通过统计特定走法集合在随机对局中出现的总次数，MCPS 建立了关于哪些走法更好的更佳“直觉”。这就像一名侦探意识到，即使嫌疑人到达的顺序不同，但他们都出现在现场这一事实才是真正的线索。

其结果是一个通用工具，在几乎所有测试场景中击败了之前的最佳方法，使其成为当你没有超级计算机可用时，游戏人工智能的一个强大新标准。

技术摘要：蒙特卡洛排列搜索（MCPS）

问题陈述

蒙特卡洛树搜索（MCTS）是游戏和决策领域的主导算法，特别是在缺乏训练数据或受计算资源限制导致深度强化学习不可行的领域（例如通用游戏）。虽然 GRAVE（广义 RAVE）等 MCTS 变体通过利用祖先节点的统计信息和“所有动作视为首次”（AMAF）启发式方法改进了标准 UCT，但它们主要依赖两类信息源：从特定动作开始的模拟统计信息，以及该动作在后续序列中出现的模拟统计信息。

本文指出现有方法存在局限性：它们未能充分利用那些导致同一节点的移动序列以不同顺序出现的模拟中所包含的统计信息。在具有交换律性质的游戏（如 Hex）中，任何移动排列都会导致相同的状态。在非交换律游戏（如 AtariGo）中，排列可能导致不同状态，但本文假设这些动作的统计价值仍然具有信息量。目标是开发一种通用的 MCTS 算法，在不依赖特定问题调整、模型训练或偏差超参数的情况下，优于 GRAVE。

方法论

核心概念：蒙特卡洛排列搜索（MCPS）

MCPS 在节点评估过程中引入了第三种统计源。为了评估在路径 $(a_0, a_1, \dots, a_d)$ 到达的节点 $s$ 处执行动作 $a$ 的价值，MCPS 聚合来自三个不同模拟集合的数据：

直接统计量（ $Q$ ）： 以通往 $s$ 的路径开始并紧接着执行动作 $a$ 的模拟。
AMAF 统计量（ $\tilde{Q}$ ）： 以通往 $s$ 的路径开始，但动作 $a$ 在序列中稍后出现的模拟（标准 GRAVE 方法）。
排列统计量（ $\hat{Q}$ ）： 包含移动集合 $\{a_0, a_1, \dots, a_d, a\}$ 以任意顺序和任意位置出现的模拟。

权重的数学推导

本文提供了结合这三种估计量的数学推导。假设统计量相互独立，作者推导出了最小化组合估计量方差的权重。
设 $n$ 、 $\tilde{n}$ 和 $\hat{n}$ 分别为这三种统计量的样本计数。最优权重（ $\beta, \tilde{\beta}, \hat{\beta}$ ）与其样本计数成正比：
$\beta = \frac{n}{n + \tilde{n} + \hat{n}}, \quad \tilde{\beta} = \frac{\tilde{n}}{n + \tilde{n} + \hat{n}}, \quad \hat{\beta} = \frac{\hat{n}}{n + \tilde{n} + \hat{n}}$
这种凸组合消除了 GRAVE 算法中使用的偏差超参数的需求，提供了一种无参数的加权方案。

算法实现

选择： 动作的价值计算为三个估计量的加权平均值。
排列统计量计算： 为了高效计算 $\hat{Q}$ ，算法使用表示为位集（bitsets）的最近模拟滑动窗口（默认 $W=10,000$ ）。对于节点 $s$ ，算法对通往 $s$ 路径上所有动作的位集进行交集运算，以识别包含完整路径序列的模拟。然后，将此结果与候选动作 $a$ 的位集进行交集运算，以隔离相关模拟。此过程使用 64 位字操作（POPCOUNT 和位扫描）以提高效率。
冻结： 一旦节点累积达到阈值访问次数（ $\rho=30$ ），其排列统计量将被计算并“冻结”。该节点随后作为其整个子树的参考，允许后代继承这些统计量而无需重新计算。
动作编码： 为了实现不同棋盘位置之间的知识迁移，动作根据游戏相关特征（例如玩家、目标单元格、战斗触发器）而非精确坐标映射为整数代码。

主要贡献

算法扩展： 提出 MCPS，将排列统计量整合到 MCTS 选择规则中，扩展了 GRAVE 算法。
理论改进： 推导了在独立性假设下最小化估计量方差的加权公式，移除了对 GRAVE 偏差超参数的需求。
高效实现： 一种使用位集和滑动窗口计算排列统计量的方法，使算法能够高效处理移动顺序的组合爆炸。
通用适用性： 证明了该算法适用于不同类型的游戏（交换律和非交换律），无需特定的参数调整。

实验结果

作者在五种游戏中对 MCPS 与 GRAVE 进行了测试：Hex、Go、AtariGo、NoGo 以及一个自定义的不对称战争游戏。在所有情况下，每种配置进行了 800 场游戏（每种算法先手各 400 场），时间预算相同。

Hex： MCPS 在 $7\times7$ 及更大的棋盘上优于 GRAVE，在较大棋盘上的胜率可达 70–76%。在 $5\times5$ 棋盘上，位集的开销使 MCPS 略微处于劣势。随着棋盘尺寸增大，优势随之增长，因为 MCPS 构建了更深的树。
Go： MCPS 在 $7\times7$ 及更大的棋盘上优于 GRAVE。值得注意的是，在较大棋盘（ $13\times13$ 、 $15\times15$ ）上，随着时间预算增加，胜率差距显著扩大（在 2 秒时高达 63.75%）。MCPS 随着时间增加始终构建更深的树，而 GRAVE 的树深度往往停滞或下降。
AtariGo： MCPS 在所有配置中均优于 GRAVE，在小棋盘（ $5\times5$ 、 $7\times7$ ）上增益最大。在较大棋盘上优势减弱，因为游戏往往在搜索到达终端状态之前结束，限制了更深树带来的益处。
NoGo： MCPS 表现出最均匀的提升，在所有单元格中均优于 GRAVE，胜率介于 57% 至 69% 之间。这种提升在棋盘尺寸和时间预算上保持一致。
战争游戏： MCPS 在 $9\times9$ 及更大的棋盘上优于 GRAVE。由于模拟长度更短，算法运行速度快 15–33%（每秒更多模拟次数），并更快地收敛到决定性游戏状态。

意义与主张

本文声称，MCPS 代表了通用 MCTS 应用的显著改进，特别是在深度学习不可行的场景中。成功的主要机制是“信息更丰富的选择规则”，它使算法能够：

构建更深的搜索树。
减少每次迭代的模拟工作量（在某些游戏中）。
更接近终端状态（如在 AtariGo 中）。
将额外的计算时间转化为对前景线路的更深探索（在 Go 中观察到）。

作者强调，该算法是通用的，无需特定问题的修改或训练。结果表明，当由此产生的深度优势落在游戏的相关决策视野内时，MCPS 的益处最为显著。本文结论指出，结合三种统计源的概念可复用于排列之外的其他类型的统计量。