MCTS处理N人游戏对手的动作

Question

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

提前谢谢你。

Answer 1

事实上，这并不是一件容易的事，因为仅仅是建模很少有额外的玩家最大化他们自己的利润。

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

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

基于MCTS的方法的主要问题是在轻量模拟/评价与它们所嵌入的知识之间找到一个平衡。多人游戏引入他们自己的参数到这个复杂的方程，结果-有一些有趣的修改，可以找到更好的解决办法(在有限的资源)，然后天真的方法。其中一种方法是"Playout搜索“，在Playout Search for Monte-Carlo Tree Search in Multi-Player Games中有详细描述。

两人游戏和多人游戏最重要的区别在于，在大多数2人游戏中，分数系统是“对称的”--如果我赢了，你就输了，反之亦然。所以，假设我想赢，我可以把它想成是我想赢，我的对手想赢。一旦我们介绍了第三个玩家，它就不再那么简单了。如果我赢了-一切都好。但其他两名球员不一定要参加比赛才能获胜，他们让我输(他们中的任何一人都赢了)就足够了，这为我们的偏执策略奠定了基础--我们假设所有的球员都会与我们作对，而不关心到底谁会赢。这将替代所需的模型(因为它们不再最大化任何利润)，而且只是可能的方案之一。随着N玩家加入董事会，可能的联盟数量(以及他们的组合)是巨大的。

Answer 2

我认为这与标准的Minimax算法是一样的。毕竟，MCST只是一种估计完整Minimax树的方法。所以你可以把故事描述为N个奖励的游戏价值向量，每个玩家都能最大限度地利用他的结果。

考虑到勘探政策，我认为理论上政策不会改变，但我可能错了。

Answer 3

我已经晚了十年了，但我一直在想同样的事情。我读过很多关于MCTS的论文(虽然我不是学者)，也没有找到一个令人满意的答案，为什么多人MCTS是这样一个挑战。

下面是我在实现过程中所做的事情。请批评我的方法。我肯定我错过了一些东西，但FWIW是一个多人游戏，我创造得相当好。

1. 每次我们到达一个终端节点时，我们都会计算得到的奖励(例如，1的胜利，0的平局)。
2. 此奖励值被添加到获胜团队的总数中，该总数是存储在节点中的dict中的。
3. 按照通常的MCTS流程，将该团队的奖励反向传播到所有父节点。
4. 在确定节点的最佳子节点时，每个子节点的有效奖励是，即团队的总奖励减去所有其他团队的总奖励。
5. 将有效的奖励值插入正常的UCB/UCT/任何您使用的公式中。

第四步是与普通的两人MCTS算法的关键区别.基本上，每个节点都会在一个小块中跟踪每个团队的总奖励，而不是将单个数字作为一个la minimax。