💻 computer science

Offline Nash Solvers Meet Online Tree Search in Multi-Agent Games on Graphs

本文介绍了原语引导树搜索（Primitive-Guided Tree Search, PGTS），这是一种结合了在可解子博弈上进行离线精确纳什均衡计算与在线树搜索的混合框架，用于有效解决图上的多智能体追逃博弈问题，其性能显著优于现有的学习算法和启发式基准方法。

原作者： Mukesh Kumar, Yue Guan, Panagiotis Tsiotras

发布于 2026-07-13

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Mukesh Kumar, Yue Guan, Panagiotis Tsiotras

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

想象一场在高风险的游戏中进行的捉迷藏，地图是一个巨大的、扭曲的城市街道。你拥有一支“捕手”队伍（红队），试图在“逃跑者”队伍（蓝队）到达秘密出口之前抓住他们。问题在于，随着加入场上的玩家增多，可能的移动方式呈爆炸式增长。这就像试图预测一盘拥有百万棋子的国际象棋中每一块棋子的走法。如果你试图同时为每一个玩家计算完美的移动，你的大脑（或计算机）会因为极度的数学过载而崩溃。

长期以来，研究人员尝试用两种主要方法来解决这个问题，但两者都存在重大缺陷。第一种方法是预先计算在游戏开始前针对每种可能情况的最优策略。但这就像是在进入迷宫之前背诵迷宫中所有可能的路径；如果迷宫发生了一点点变化，或者其他玩家做出了你没预料到的奇怪举动，你背诵的地图就会变得毫无用处。第二种方法是在比赛过程中即时思考，通过模拟数百万个未来的场景来选择最佳移动。但由于参与者众多，需要探索的分支数量过于庞大，以至于计算机会在繁杂的细节中迷失，无法及时找到最佳路径。

于是，这位新的英雄登场了：原语引导树搜索（Primitive-Guided Tree Search, PGTS）。你可以把 PGTS 想象成一位聪明的教练，它结合了两者的优点。

教练的秘密武器：“小游戏”库

PGTS 教练并不试图一次性解决整个宏大的游戏，而是会在比赛开始前进入图书馆，解决许多微小的、简单的版本游戏。这些被称为“原语子队游戏”（primitive sub-team games）。

想象一下解决一个 1 对 1 的捉迷藏游戏。
然后解决一个 2 对 1 的游戏（两名捕手对一名逃跑者）。

教练完美地解决了这些微型游戏，并将答案记录在一份“小抄”（策略和价值缓存）中。这是离线部分。因为它规模很小，所以速度很快。

比赛日：智能树搜索

当真正的比赛开始时，教练并不仅仅是靠猜测，也不仅仅是依赖旧的小抄。他们使用树搜索（Tree Search），这就像是观察分叉路口的前方走向。但这里的魔力在于：

引导扩展（Guided Expansion）： 教练不再观察所有可能的移动（这会耗费太长时间），而是利用小抄只关注那些基于 1 对 1 和 2 对 1 游戏看起来最有希望的移动。这就像教练在说：“嘿，在 2 对 1 的情况下，捕手通常会这样做，所以我们把注意力集中在这里。”
叶节点价值估计（Leaf Value Estimation）： 当教练到达思考路径的终点（树的“叶子”）时，他们不需要模拟整个游戏到结束。他们只需查看当前的位置，将大团队重新拆分为那些微小的 1 对 1 和 2 对 1 小组，并使用预先计算好的小抄来预测最终得分。

这使得团队能够作为一个整体进行完美的协作，同时还能利用预解微型游戏的速度优势。

论文说了什么（以及没说什么）

作者在几种不同的地图上测试了这个新教练，包括一个 7x7 的网格、一个复杂的“妙探寻凶”（Scotland Yard）地图，以及一个包含 151 个节点的真实世界亚特兰大地图。他们在网格地图上运行了持续 6 个时间步的模拟，在较大的地图上运行了 9 个时间步。

结果令人印象深刻。在这些模拟中，PGTS 团队（使用“遗憾匹配”或“解耦 UCT”决策风格）始终优于现有的最佳方法。

在棘手的“网格 2”地图上，旧方法的最差情况效用约为 0.25 到 0.37，而 PGTS 得分为 0.40 到 0.46。
在“妙探寻凶”地图上，差距巨大：旧方法得分低至 0.00 或 0.05，而 PGTS 得分为 0.68 到 0.73。
即使面对一个不是只会直线奔跑的“聪明”逃跑者，PGTS 依然能稳住阵脚，而其他方法（由于是针对简单逃跑者训练的）则溃不成军。

论文明确反对仅依赖预计算的小游戏（分解法）而不进行树搜索。他们发现，虽然小游戏很有用，但它们无法捕捉整个团队应该如何协同工作。如果仅仅使用小游戏，团队协作就会崩溃，性能也会显著下降。树搜索是维持团队协作的胶水。

结论

这并不是一个能解决宇宙中所有问题的魔杖，但在这些特定的模拟领域中，它是一个游戏规则改变者。作者证明，通过将一个巨大且可怕的问题分解为小的、可解的部分，并利用这些部分来引导智能搜索，你可以击败目前最好的策略。他们通过在各种图拓扑结构上的广泛计算机模拟证明了这一点，展示了即使在对方试图耍花招时，他们的这种方法依然具有鲁棒性。

论文指出，这种方法可以扩展到其他类型的多智能体游戏，甚至是无法看到全局信息（部分可观测性）的情况，但目前，他们仅在这些特定的追逃模拟中展示了其能力。这是一个聪明的技巧，它将一场数学噩梦变成了一个可以处理的谜题，证明了有时，赢得大局的最佳方式是先精通小局。

技术摘要：多智能体追逃博弈中的原语引导树搜索

1. 问题定义

本文研究了在图结构上计算多智能体追逃博弈（Pursuit-Evasion Games, PEGs）中纳什均衡策略的挑战。在这些博弈中，追捕者（红方）团队试图在逃避者（蓝方）到达指定出口节点之前将其捕获。核心难点在于随着智能体数量的增加，联合状态和动作空间呈指数级增长。

现有方法面临权衡：

离线方法（如 PSRO, MAPPO）：虽然可以进行离线策略训练，但往往缺乏对训练期间未见过的对抗行为的适应能力，且训练复杂度较高。
在线规划方法（如 MCTS）：能够适应当前状态，但难以应对多智能体同时行动带来的巨大分支因子，导致深度搜索在计算上难以实现。
混合方法（如 AlphaZero 变体）：通常依赖于学习精确的价值/策略近似值，这需要大量数据，或者仅限于两人博弈场景。

目标是开发一个既具备离线均衡计算的战略深度，又具备在线搜索的适应性的可扩展且鲁棒的框架。

2. 方法论：原语引导树搜索 (PGTS)

作者提出了 原语引导树搜索 (Primitive-Guided Tree Search, PGTS)，这是一个混合框架，它将复杂的多智能体博弈离线分解为易于处理的子博弈，并将这些解集成到在线同步移动蒙特卡洛树搜索（SM-MCTS）中。

2.1 离线阶段：原语子团队博弈

PGTS 并非直接求解完整博弈，而是预先计算涉及智能体子集的、具有代表性的微小“原语”子博弈的精确纳什均衡：

1v1：一个追捕者对一个逃避者。
2v1：两个追捕者对一个逃避者。
这些博弈通过在受限状态空间（ $V \times V$ 和 $V^2 \times V$ ）上使用 Shapley 值迭代进行求解。输出包括这些原语的最优混合策略 ( $\pi^*$ ) 和价值函数 ( $V^*$ )，并将其缓存以供运行时使用。

2.2 在线阶段：树搜索

在每个时间步，PGTS 从当前联合状态执行树搜索。该算法在两个关键方面修改了标准的 SM-MCTS：

原语引导的扩展 (Primitive-Guided Expansion)：
为了缓解指数级的分支因子，算法并不扩展所有可能的联合动作。相反，它利用离线原语策略来引导搜索：
- 对于每个逃避者，算法识别其最近的 $k_r$ 个追捕者。
- 基于预计算的纳什策略 ( $\pi^*_{1v1}, \pi^*_{2v1}$ ) 对局部交互（1v1 和 2v1 组）进行联合动作采样。
- 这些样本构成了一个受限的候选动作集，并辅以启发式最短路径动作和随机探索，以防止过度依赖先验知识。
通过子团队代理进行叶节点价值估计 (Leaf Value Estimation via Sub-team Surrogates)：
算法不再运行昂贵的蒙特卡洛 Rollout 直至博弈终点，而是使用离线原语价值函数来估计叶节点的价值。
- 算法通过将当前状态分解为一组原语子团队来近似完整博弈的价值。
- 它采用一种顺序匹配策略：首先，利用匈牙利算法在 2v1 价值矩阵上进行贪婪匹配，以形成 2v1 交互（从而捕捉更高阶的协作，如协同围堵）；随后，将剩余的智能体匹配为 1v1 交互。
- 叶节点价值是这些原语价值的聚合总和，这使得搜索可以在较浅的深度终止，同时保持准确的结果估计。

2.3 动作选择

该框架支持两种用于遍历树的选择算子：

遗憾匹配 (Regret Matching, RM)：对每个节点处的估计矩阵博弈应用遗憾匹配，以计算混合策略。
解耦 UCT (Decoupled UCT, DUCT)：对每个团队的边际动作价值独立应用置信区间上界（UCB）。

3. 核心贡献

混合框架：引入了 PGTS，它独特地将小规模重复局部交互（原语）的精确离线纳什解集成到在线树搜索中，用于实现多智能体协作。
结构化扩展：通过基于离线均衡计算得出的战略先验进行动作采样，而非采用随机或纯启发式采样，从而建立了一种减少分支因子的机制。
可扩展的叶节点评估：一种代理价值估计方法，利用离线原语价值函数和顺序匹配算法（优先考虑 2v1 优于 1v1）来评估叶节点，无需进行深度 Rollout。
协作保留：不同于将子团队视为独立个体的简单分解方法，PGTS 通过在全动作空间内进行联合动作 Rollout（受原语引导），维持了团队层面的协作。

4. 实验结果

作者在四种图拓扑结构上评估了 PGTS：两个 7x7 网格（简单/困难）、一个 200 节点的《福尔摩斯》图（Scotland Yard）以及一个 151 节点的真实世界亚特兰大图。追捕者团队针对各种逃避者行为进行了测试。

基准模型 (Baselines)：

MT-PSRO：多任务策略空间响应算子（基于学习的方法）。
NSGZero：用于网络安全领域的神经引导 MCTS。
Decomposition (分解法)：仅使用子团队分解而不使用树搜索的基准方法。
Intercepting (拦截法)：一种启发式最短路径基准。

发现：

鲁棒性：PGTS（包括 RM 和 DUCT 变体）在所有拓扑结构中均一致获得了最高的最差情况效用 (WCU)，显著优于表现出对最短路径型逃避者过拟合迹象的学习型基准（MT-PSRO, NSGZero）。
协作性：PGTS 优于纯“Decomposition”基准，证明了树搜索组件能有效捕捉静态分解所缺失的团队层面协作。
消融实验：移除原语引导的扩展或 2v1 原语会导致性能大幅下降，尤其是在较大的复杂图（Scotland Yard, Atlanta）上，这证实了两者对于有效探索和价值估计的必要性。

5. 重要性与主张

本文声称 PGTS 为多智能体 PEGs 中的“维度灾难”提供了可扩展的解决方案。通过利用小规模重复局部交互（原语）的精确解来引导全局搜索，该方法实现了：

计算可行性：它有效地管理了分支因子和搜索深度。
适应性：它保留了在全联合动作空间中推理协调策略的能力，不同于静态分解。
鲁棒性：它在面对多样化的对抗策略（包括训练阶段未见的策略）时表现出色，因为它依赖于博弈论原理而非学习到的分布。

作者总结道，这种方法弥合了离线均衡计算的理论最优性与在线规划的实际适应性之间的鸿沟，为对抗环境下的多智能体决策提供了一个鲁棒的框架。未来的工作建议将其扩展到部分可观测环境及更广泛的多智能体博弈类别。