💻 computer science

Dynamic Resource Allocation for Ensemble Determinization MCTS

本文针对集成确定化蒙特卡洛树搜索（Ensemble Determinization MCTS）提出了两种动态资源分配策略——调整确定化树的数量以及非均匀地分配模拟预算——并验证了其在斋浦鲁（Jaipur）、失落之城（Lost Cities）和璀璨迷宫（Splendor）等高不确定性棋类游戏中具有统计学意义上的显著性能提升。

原作者： Jakub Kowalski, Adam CięĊkowski, Artur KrzyĊyński, Mark H. M. Winands

发布于 2026-07-15

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Jakub Kowalski, Adam CięĊkowski, Artur KrzyĊyński, Mark H. M. Winands

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

想象一下，你正在试图解开一个巨大且混乱的拼图，但你无法看到全貌。你只知道其中的一些碎片，其余部分都被一层浓雾遮盖着。对于计算机来说，玩像《斋浦尔》（Jaipur）、《失落之城》（Lost Cities）或《璀璨宝石》（Splendor）这样的棋盘游戏，感觉就像是这样。那里有隐藏的卡牌、随机的洗牌和秘密的策略。为了做出一个好的移动，计算机使用了一种被称为**蒙特卡洛树搜索（MCTS）**的聪明技巧。

把 MCTS 想象成一支探险队。与其让一名探险家去猜测路径，不如派出一整支小队。在本文所使用的 MHS 版本中，被称为集成确定化 MCTS（Ensemble Determinization MCTS），这支小队会进行拆分。每位探险家都会想象出一种不同的现实版本，在这些版本中，隐藏的卡牌以特定的方式被揭示出来。他们都会进行模拟（脑内演练）游戏，然后通过投票选出最佳移动。

核心问题在于作者们所询问的：我们应该如何管理我们的探险队？ 我们是每次都派出一固定数量的探险家？还是应该给每位探险家分配完全相同的时间去思考？

论文指出，答案是“并非总是如此”。计算机应该成为一个聪明的管理者，进行动态资源分配。以下是他们测试两种新管理风格的方式：

1. “灵活团队规模”策略

想象你正在领导一群侦探。如果线索非常模糊，且嫌疑人看起来几乎一模一样，你可能需要更多的侦探才能确定。但如果线索非常清晰，也许你不需要庞大的队伍；一个小团队就足够了。

作者提出了一种让计算机根据情况实时改变“探险树”（即侦探）数量的系统。

规则： 如果团队意见分歧且无法就某个移动达成一致（即最佳移动与第二佳移动之间的“差距/边际”很小），计算机就会增加更多的树来获得更清晰的图景。如果团队非常有信心且容易达成一致，则减少树的数量以节省时间。
结果： 在模拟中，这种方法在《斋浦尔》和《璀璨宝石》中表现出色。例如，在《斋浦尔》中，使用这种灵活的团队规模比固定团队的胜率提升了 3.3 个百分点。在《璀璨宝石》中，胜率跃升了 5.1 个百分点。
代价： 它在《失落之城》中的效果并不理想。事实上，对于这款游戏，结果喜忧参半甚至略微偏负。作者认为，这意味着“正确的”侦探数量高度取决于所玩的具体游戏。

2. “智能预算”策略

现在，假设你有一个总计 250,000 次脑内模拟的“预算”可以用于单回合。旧的方法是将这个预算平均分配给所有探险家。如果你有 10 名探险家，每人得到 25,000 次模拟。

作者问道：如果我们把更多时间给那些挣扎中的探险家，而给那些已经知道答案的探险家更少的时间，会怎样？

规则： 他们尝试了几种决定谁获得更多时间的方法。其中一种被称为 “跨树 UCB”（Across-tree UCB） 的方法将整个团队视为一个整体，将所有额外的时间集中在整个群体中最不确定的移动上。另一种方法是 “移动剪枝”（Move Pruning），即停止在明显糟糕的移动上浪费时间。
结果： 这是一个成败参半的游戏。结合“投票”系统后，“跨树 UCB” 方法成为了明星选手，提升了《斋浦尔》和《璀璨宝石》的分数。然而，其他方法（例如基于“胜率差异”进行平衡的方法）实际上让情况变得更糟，在某些情况下导致分数下降了超过 10 个百分点。
教训： 你不能只是盲目地向问题投入资金（或模拟次数）。如果你把额外的时间给了错误的探险家，你可能会搞乱整个团队。

大揭秘：不要只是简单相加

最有趣的发现出现在他们尝试结合这两种策略（同时改变团队规模和预算）时。你可能会想：“如果策略 A 增加了 3 分，策略 B 增加了 2 分，那么结合起来应该增加 5 分！”

但计算机并不这样运作。在《斋浦尔》中，结合后的策略仅增加了 2.9 个百分点，尽管数学预测应该是 6.5。在《璀璨宝石》中，增益为 2.1 点，而非预测的 7.3。

作者解释说，这些策略有时会互相干扰。就像拥有灵活的团队规模和智能预算是很棒，但如果你在尝试分配预算的同时又在改变团队规模，这两个系统可能会发生冲突。论文表明，你不能分别选择最好的“规模”和最好的“预算”，然后期望它们完美协作；你必须将它们作为一个整体进行测试。

关于时间

最后，作者们不仅通过计算模拟次数，还通过给予计算机每回合严格的 一秒钟时间限制（就像真实的比赛计时器一样）来测试这些想法。

灵活策略仍然有效。在《失落之城》中，在时间限制下，一个智能投票设置将胜率从 47.6% 提升到了 54.6%，将一个失败的策略转变为获胜策略。
然而，当从“计算模拟次数”切换到“计算秒数”时，最佳策略的排名有时会发生变化。这意味着，一个在模拟中看起来很棒的策略，如果你是在与时间赛跑，它可能并不是最佳选择。

总结

论文并未声称他们已经“解决”了这些游戏。相反，它表明动态资源分配——即做一个灵活的管理者，根据团队的困惑程度来调整团队规模和预算——可以显著提升表现。

对于《斋浦尔》和《璀璨宝石》： 保持灵活性是明显的优势，能提升 3 到 5 个百分点。
对于《失落之城》： 情况很复杂；收益较小且不稳定。
警告： 论文明确排除了“更多的树”或“更多的模拟”总是更好的这一观点。有时，拥有一个规模更小、更专注的团队，或者在糟糕的移动开始前就停止搜索，才是获胜的关键。

作者总结道，虽然这些动态技巧很强大，但它们高度依赖于具体的游戏。适用于《斋浦尔》的方法可能会在《失 lost 之城》中失效，因此不存在一种适用于所有棋盘游戏的“万能设置”。最好的方法是针对你正在玩的特定游戏来测试并调整这些策略。

技术摘要：用于集成确定化 MCTS 的动态资源分配

问题陈述

蒙特卡洛树搜索（MCTS）在确定性、完全信息博弈中非常有效，但在具有不确定性、随机性和隐藏信息（非完全信息）的环境中面临显著挑战。虽然已开发出如集成确定化 MCTS（ED-MCTS）之类的变体来处理这些领域，通过实例化多个确定性游戏状态（确定化）来应对，但标准的实现通常依赖于静态配置。具体而言，确定化树的数量以及在这些树之间分配模拟预算的方式通常是固定的常数。这种静态方法可能是次优的，因为取决于游戏状态、对手策略以及特定的行动路径，确定性的程度和集成决策的稳定性可能会发生变化。

方法论

作者提出了一个用于 ED-MCTS 的动态资源分配框架，引入了两个主要的自适应维度：

1. 动态确定化数量

算法不再使用固定的树的数量（ $T$ ），而是根据集成决策的稳定性逐回合调整 $T$ 。

机制： 系统通过一个滑动窗口（ $L$ 个回合）监控获胜动作与次优动作之间的“边际”（margin）。
自适应规则：
- 增加（ $L_\uparrow, M_\uparrow$ ）： 如果获胜动作的边际较小（即，改变最多 $M_\uparrow$ 棵树的输出就可能改变结果）且持续了 $L_\uparrow$ 个回合，则增加树的数量以提高置信度。
- 减少（ $L_\downarrow, M_\downarrow$ ）： 如果边际较大（即，移除最多 $M_\downarrow$ 棵树不会改变结果）且持续了 $L_\downarrow$ 个回合，则减少树的数量以节省计算资源。
适用性： 这些规则旨在能够解释各种最终动作选择机制（访问次数、得分、投票、Borda 排序）。

2. 动态模拟分配

算法并非将总模拟预算（ $B$ ）均匀地分配到所有 $T$ 棵树中，而是根据每棵树的“竞争激烈程度”（contestedness）进行非均匀拆分。

竞争激烈程度度量： 对于每棵树，算法通过单侧置信界限（Hoeffding 半径）比较最佳根节点子节点与其最强替代方案。如果最佳移动的下界超过了所有替代方案的上界，则认为该树已被“锁定”（locked）。
测试的分配策略：
- 贪婪式（Greedy）： 将迭代分配给当前最激烈竞争且未锁定的树。
- UCB（胜率差异）： 对树使用高层 UCB 公式，优先考虑那些顶端两个动作之间差异最小（不确定性最高）的树。
- UCB（访问比例）： 优先考虑顶端两个动作的访问计数比例接近的树（ $n_2/n_1 \approx 1$ ）。
- 跨树 UCB（Across-tree UCB）： 将集成视为一个关于根节点动作的单一多臂老虎机，汇总所有树的统计数据以选择最有希望或最不确定的动作，然后在每棵树中强制执行该动作。
- 动作剪枝（Move Pruning）： 消除其上置信界限低于当前最佳动作下界的根节点动作。其变体包括“冻结”（Freeze），即一旦某个树的决策被锁定，就停止向其分配预算。

实验设置

所提出的增强方案在三个具有不同程度隐藏信息和随机性的流行桌面游戏中进行了评估：

Jaipur（斋浦尔）： 一款节奏较快、具有高度隐藏信息和随机抽牌机制的卡牌游戏。
Lost Cities（失落之城）： 一款涉及隐藏手牌和随机抽牌堆的卡牌游戏，需要应对不确定性进行长期规划。
Splendor（璀璨宝石）： 一款策略性游戏，隐藏信息较少，但卡牌牌组构成具有显著的随机性。

基准与指标：

对手： 样本开放回路 MCTS（SOLMCTS），一种针对非确定性环境的标准基准。
评估： 在固定模拟预算（每回合 25 万次模拟）和固定时间预算（每回合 1 秒）下测量胜率。
动作选择： 研究比较了不同的聚合方法（访问次数、得分、投票、Borda），以确定动态分配如何与最终决策相互作用。

关键结果

1. 动作选择与静态基准

集成方法（多棵树）的表现始终优于单个确定化树（ $T=1$ ）。
最优树数量： 中等数量的树（5–10 棵）通常产生最佳结果，这证明了深度与广度之间存在非单调的权衡。
聚合： 与某些先前文献认为多数投票法更优的观点相反，访问次数和得分聚合方法在这些特定领域中的表现往往与投票法一样好，甚至更好。Borda 方法的表现通常较差。

2. 动态确定化数量

游戏依赖性： 动态树调整的有效性具有高度的游戏特异性。
- Jaipur & Splendor： 当使用投票机制时，观察到了显著的改进（例如，Jaipur 提升 3.3%，Splendor 提升 5.1%）。
- Lost Cities： 结果褒贬不一，大多数配置显示没有显著收益或略有下降。
结论： 动态树调整是一种有用的自适应优化，而非对经过调优的静态数量的普遍替代。

3. 动态模拟分配

敏感性： 性能增益对分配策略与聚合规则之间的相互作用高度敏感。
跨树 UCB： 该策略显示出最明显的正面模式，特别是与投票结合使用时，提高了 Jaipur 和 Splendor 的胜率。
负面相互作用： 当与访问总和聚合结合使用时，树级 UCB 变体表现较差，胜率往往下降超过 10 个百分点。这表明，按树分配迭代次数可能会扭曲基于访问总和的系统中的最终投票。
动作剪枝： 在特定配置下显示出轻微收益，但并未在所有游戏中提供一致的改进。

4. 结合与基于时间的测试结果

非叠加性： 结合动态树数量和动态分配并没有产生叠加收益。在许多情况下，结合后的改进明显低于两个单独改进之和；在某些情况下，动态分配反而阻碍了动态树数量带来的收益。
基于时间的表现： 动态配置在墙钟时间限制下保持了其优势。值得注意的是，在 Lost Cities 中，一种结合了投票的配置将胜率从 47.6% 提高到了 54.6%，将原本低于平等的基准转变为明显的胜利。
排名偏移： 机制的排名在固定迭代次数和固定时间设置之间发生了变化，这表明为迭代次数调优的配置在时间受限的部署中可能并非最优。

意义与主张

论文声称，动态资源分配是增强集成确定化 MCTS 的一种可行且有益的策略，但带有重要的限制条件：

上下文效用： 收益是高度依赖于游戏和依赖于聚合方式的。不存在一种适用于所有非完全信息游戏的通用“最佳”配置。
自适应优化： 所提出的方法最好作为静态 ED-MCTS 基准的自适应优化，而非彻底的重构。
评估必要性： 作者强调，必须在特定的部署预算（时间 vs. 迭代次数）以及所选聚合方法下验证机制的选择，因为这些因素之间的相互作用是复杂且非线性的。
局限性： 本研究局限于三种特定的棋盘游戏和一个特定的模拟预算。作者指出，最优的集成规模和聚合规则很可能取决于游戏的启发式评估函数及其结构。

这项工作贡献了一套可解释的动态机制，使 ED-MCTS 能够根据当前游戏状态的不确定性来自我调节计算资源，并在特定且经过精心选择的配置下，提供具有统计学意义的强度提升。