0

我正在为 2 人游戏创建一个 MCTS（蒙特卡洛树搜索）程序。

为此，我从交替的角度在树中创建节点（第一个节点从玩家 1 的角度来看，任何子节点都从玩家 2 的角度来看，等等）

在确定最后一步时（在模拟了许多节点之后），我选择获胜机会最高的一步。这个获胜机会取决于更深节点的获胜机会。例如，假设我有 2 个合法动作要做。第一个（调用关联节点 C1 - Child 1）我做了 100 次模拟并赢得了 25 个，而对于第二个（C2）我做了 100 次模拟并赢得了 50 个。然后第一个节点有 25% 的获胜机会对 50 % 为第二个，所以我应该更喜欢第二个节点。

但是，这并没有考虑到我的对手将采取的“可能”行动。假设从 C2 开始有两个可能的合法移动（对于我的对手），让我们称之为 C21 和 C22。我为两者做了 50 次模拟，在 C21 中，我的对手在 50 场比赛中赢了 50 场（100% 获胜机会），而在 C22 中，他们在 50 场比赛中赢了 0 场（0% 获胜机会）。完成这些模拟后，我可以看到我的对手更有可能采取行动 C21 而不是 C22。这意味着如果我走 C2 步，那么我的 -statistic-win 机会是 50%，但我的 -expected-win 机会接近 0%。

考虑到这些信息，我会选择移动 C1 而不是 C2，即使获胜的概率较低。我可以对我的算法进行编程来做到这一点，从而提高性能。

这似乎是对 MCTS 算法的一个非常明显的改进，但我没有看到任何对它的引用，这让我怀疑我错过了一些重要的东西。

任何人都可以指出我的推理中的缺陷或指出任何涉及此问题的文章吗？

4

1 回答 1

0

假设从 C2 开始有两个可能的合法移动（对于我的对手），让我们称之为 C21 和 C22。我为两者做了 50 次模拟，在 C21 中，我的对手在 50 场比赛中赢了 50 场（100% 获胜机会），而在 C22 中，他们在 50 场比赛中赢了 0 场（0% 获胜机会）。

由于 MCTS 算法中的“选择”步骤，这种情况永远不可能发生。选择步骤是使用强盗算法（最常见的是 UCB1 算法）遍历树的算法的一部分。只有在那之后，一旦你到达树中尚未完全展开的点，你就会开始（半）随机播放阶段。

在选择步骤中（在你的对手要移动的节点中，应该使用“他们的观点”的统计数据）基于探索和利用之间的平衡遍历子节点；它会给得分高的孩子分配高分（如果他们要移动，从对手的角度来看是好的），但也会给访问次数相对较少的孩子分配高分。

选择步骤的正确实施应该使您绘制草图的情况变得不可能。选择步骤不会在 C21 和 C22 之间均匀分布其模拟。例如，它宁愿将 95 个模拟分配给 C21，将 5 个模拟分配给 C22。

它从每个模拟开始。C21会赢，C22会输。然后它将例如接下来的 2 次模拟分配给 C21，因为该模拟的平均得分更高（从对手的角度来看）。然后为了探索，它可能会再次将第四次模拟分配给 C22。模拟 5、6、7 和 8（例如）将再次进入 C21 以利用好分数，可能再次模拟 9 至 C22 进行探索，等等。

在选择步骤中使用像 UCB1 这样的算法，可以证明在极限情况下（给定无限数量的模拟），利用将大大超过探索，以至于平均分数将收敛到真正的极小极大分数。

于 2018-04-12T18:03:40.043 回答