蒙特卡洛树搜索：复杂多人游戏中缺点、优势与局限性的综述

1. 引言

蒙特卡洛树搜索（MCTS）是一类搜索算法，它通过四个阶段构建决策树：选择、扩展、模拟和反向传播。该方法不需要为每个状态提供完整的评估函数，而是通过大量模拟来估计动作的质量，在探索鲜少访问的备选方案与利用已知动作之间取得平衡。这一特性在围棋、国际象棋和将棋等游戏中取得了显著成果，尤其是在具有完全信息的双人环境中（BROWNE et al., 2012）。

然而，当代数字游戏和桌面游戏呈现出更复杂的条件：多个对手、隐藏信息、随机性、庞大的动作空间和实时决策。在这些情况下，增加一次模拟并不总能产生更好的决策。玩家数量越多，搜索树就越大，对手的应对就越难以建模。当隐藏状态处理不当时，不完美信息可能导致策略融合，而时间压力则减少了可用的计算预算。尽管MCTS在这些场景中的应用日益增多，但相关文献仍然零散且集中于经典游戏。

2. 目标

本工作的总体目标是识别并整理MCTS在多人数字游戏和桌面游戏中反复出现的局限性，尤其是在具有不完美信息、随机性和时间约束的环境中。

具体目标方面，本工作旨在汇集缓解这些局限性的策略，并识别能够指导未来研究、有利于更可比较和可复现评估的研究空白。

3. 方法

本文对2013年至2025年间发表的研究进行了文献综述，检索了IEEE Xplore、HAL Science Ouverte和Google Scholar数据库。检索策略将术语“Monte Carlo Tree Search”和“MCTS”与数字游戏、棋盘游戏和多人游戏相关的表达组合使用。筛选时考虑了标题或摘要涉及MCTS、其直接变体或应用于竞争性或合作性游戏的混合方法的作品。范围之外的研究、无法获取全文的文献以及范围与综述目标不兼容的作品被排除在外。

检索共获得24条记录，其中两条在查询之间重复，最终得到22篇独特的潜在相关作品（17篇英文，5篇法文）。经过筛选，18项研究被选中进行全文分析，4项被排除。最终语料库汇集了来自IEEE Xplore的13项研究、来自HAL的3项以及通过Google Scholar找到的2项，在入选研究中，15篇为英文，3篇为法文。这些作品按游戏类型、所用算法、环境约束、报告结果和缓解策略进行分类。主题分析被组织为三个结构性局限类别——性能限制、战术盲点和对手建模中的权衡——以及两个领域相关的放大因素——不完美信息和实时决策。

4. 结果与讨论

所分析的研究表明，MCTS在状态定义明确、分支因子适中且计算预算足以进行大量模拟的游戏中表现最为稳定。在18篇入选作品中，8篇涉及数字游戏，6篇研究棋盘或桌面游戏，其余则分析卡牌游戏、通用游戏对弈环境或相关应用。基于MCTS的算法在14项研究中使用，通常与神经网络、动作空间抽象、模拟策略和参数调优技术相结合。

识别出的第一个局限涉及搜索性能。尽管增加模拟次数通常能提高决策质量，但随着新的模拟开始重复访问已经充分探索的轨迹，边际收益往往会递减。在围棋、即时战略游戏和桌面游戏中获得的结果表明，计算预算翻倍在某个临界点之后可能产生递减甚至无收益。此外，关于技能深度的研究表明，这一限制既取决于游戏的复杂性，也取决于智能体的配置。缓解策略包括动作空间抽象、模拟简化，以及通过N-Tuple Bandit Evolutionary Algorithm（NTBEA）自动调优策略、探索常数和展开策略（GOODMAN; PEREZ-LIEBANA; LUCAS, 2024）。

第二个局限对应于战术推理的盲点。由于MCTS估计采样后续的平均价值，该算法在需要识别特定战术序列、长期威胁或不常见配置的局面中可能失败。在围棋中，征子和 semeai 等情况说明了经验丰富的玩家能够明显识别的战术结构可能无法被搜索识别。

第三个局限涉及对手建模。在有三名或更多参与者的游戏中，搜索过程不仅必须表示树根处玩家的决策，还必须表示每个对手可能的应对。为每个对手保持独立结构的模型往往能更好地表示策略行为，尽管它们会显著增加计算成本。相比之下，简化方法（如偏执搜索和泛化策略）降低了这一成本，但可能无法表示相关行为。文献表明，基于选择性聚焦、对手应对泛化和树分解的方法是有前景的替代方案，尽管在参与者众多的游戏中仍鲜有评估（BAIER; KAISERS, 2020）。

不完美信息加剧了这些局限。在卡牌游戏、宝可梦和其他具有隐藏状态的环境中，确定化——即假设未知信息的一种可能配置并当作真实情况进行搜索——可能导致不兼容策略的融合。信息集MCTS是蒙特卡洛树搜索的一种变体，旨在处理不确定性，它通过将玩家无法区分的状态分组，仅保留决策时刻实际可用的信息，从而减少这一问题（COWLING; POWLEY; WHITEHOUSE, 2012）。即便如此，环境固有的随机性以及推断对手行为的需要，仍然限制了所产生估计的可靠性。

在实时环境中，如策略游戏、MOBA和第一人称射击游戏，时间约束成为关键因素。MCTS必须在极短的时间间隔内选择动作，同时管理组合动作空间、多个单位和部分观察。在此背景下，分层抽象、宏动作、动作剪枝以及通过监督学习或强化学习获得的策略成为反复出现的策略（ONTAÑÓN, 2013）。在某些情况下，替代方法可能表现更好。例如，滚动时域进化算法（RHEA）演化短动作序列并进行持续重新规划，特别适用于合作游戏和搜索树快速变化的高度随机环境（SFIKAS; LIAPIS, 2022）。

还识别出了对实时决策依赖较少的MCTS应用，如自动平衡、游戏测试和对游戏设计的支持。在这些场景中，处理时间不再是关键约束，允许广泛探索不同配置、识别不平衡并评估设计替代方案。尽管大多数研究报告的结果支持所提出的方法，但一些作品观察到MCTS与竞争技术相比性能较低，如在游戏Kingdomino和Pandemic中。

5. 结论

本综述还识别出未来研究的五个相关机会：（i）采用并标准化具有不完美信息的多人游戏的共享基准；（ii）系统评估参与者众多游戏中的对手建模技术；（iii）研究人类玩家感知的复杂性与搜索有效深度之间的关系；（iv）研究三局两胜和五局三胜的竞技系列赛，考虑选人和禁用历史；（v）扩展MCTS在自动平衡、游戏测试和程序化内容生成中的应用。