tree - MCTS 处理 N 玩家游戏对手动作

Question

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

先感谢您。

Answer 1

事实上，这并不像仅仅建模少数几个让自己的利润最大化的额外参与者那么容易。

对于多人游戏的问题，至少有几种不同的方法，包括：

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

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

2 人游戏和多人游戏之间最重要的区别在于，在大多数 2 人游戏中，积分系统在某种程度上是“对称的”——如果我赢了，你就输了，反之亦然。所以，假设我想赢，我可以把它想成是我想赢，我的对手想赢。一旦我们介绍了第三个播放器，它就不再那么简单了。现在，如果我赢了——一切都好。但是另外两个玩家不一定要赢，他们让我输就足够了（他们中的任何一个都赢了），这是偏执策略的基础——我们假设所有玩家都在和我们对战，而不关心谁真正赢了。这替代了所需的模型（因为它们不再最大化任何利润），并且只是可能的场景之一。和N棋盘上的玩家，可能的联盟（及其组合）的数量是巨大的。

Answer 2

我认为这与标准 Minimax 算法的情况相同。毕竟 MCST 只是一种估计完整 Minimax 树的方法。因此，您可以将故事作为 N 个奖励的游戏价值向量，并且每个玩家最大化他的结果。

考虑到勘探政策，我认为理论上该政策不会改变，但我在那个方面可能是错误的。