tree - MCTS 处理 N 个玩家游戏的对手 Action

Question

我想知道MCTS中如何处理N个玩家的游戏。对手的 Action 是否嵌入到搜索树中？它们的值(value)生成方式与其他操作相同吗？如果是这样，它们的值是否会以错误的方式改变父状态的总值(value)？mcts.ai 是一个非常有用的网站，但涉及多人游戏。示例代码只是指出“n 人游戏需要额外的逻辑”

提前谢谢您。

Answer 1

事实上，这并不像仅仅对少数额外的参与者进行建模那样简单，以最大化他们自己的利润。

至少有几种不同的方法来解决多人游戏的问题，包括:

• max^n(最简单)
• 偏执
• 最佳回复搜索 (BRS)
• 联盟混合器

基于 MCTS 的方法的主要问题是找到轻量级模拟/评估与其中嵌入的知识之间的平衡。多人游戏将自己的参数引入到这个复杂的方程中，因此，有一些有趣的修改可以找到比幼稚方法更好的解决方案(就有限的资源而言)。一种这样的方法是“Playout search”，在Playout Search for Monte-Carlo Tree Search inMulti-Player Games中详细描述。 .

两人游戏和多人游戏之间最重要的区别是，在大多数两人游戏中，积分系统在某种程度上是“对称的”——如果我赢了，你就输了，反之亦然。因此，假设我想赢，我可以将其视为我试图获胜和我的对手试图获胜之间的战斗。一旦我们引入第三位球员，事情就不再那么简单了。现在，如果我赢了——一切都好。但是另外两个玩家不必为了赢而玩，他们足以让我输(并且他们中的任何一个赢)，这构成了偏执策略的基础 - 我们假设所有玩家与我们比赛，而不关心谁真正获胜。这替代了所需的模型(因为它们不再最大化任何利润)，并且只是可能的场景之一。棋盘上有 N 个玩家，可能的联盟(及其混合)数量是巨大的。