如何为随机环境运行蒙特卡洛树搜索 MCTS?

人工智能 蒙特卡罗树搜索
2021-11-15 19:17:50

对于 MCTS,有一个扩展阶段,我们采取行动并列出所有下一个状态。但是,对于某些游戏而言,在采取行动之后,环境会发生随机变化,这使情况变得复杂。考虑游戏 2048,在我移动之后,会生成随机图块。所以我下一步行动后的世界状态是多种可能性!

MCTS 如何在随机环境中工作?我无法理解如何跟踪扩展,我是否扩展了所有随机可能性并通过它们发生的机会来衡量回报?

1个回答

我无法理解如何跟踪扩展,我是否扩展了所有随机可能性并通过它们发生的机会来衡量回报?

这确实是您可以采取的一种选择。这在精神上与“Expectimax”作为非确定性游戏的极小极大变体的想法非常相似,因为您将在树中包含明确的“机会节点”。当稍后在稍后的 MCTS 迭代的选择阶段再次遇到这样的机会节点时,您可以根据“掷骰子”选择要遵循的树路径。重要的是,请注意,只有当您明确知道偶然事件发生的确切时间、它们可能导致的状态以及它们导致不同状态的概率时,此选项才实际可用。我们还假设这是可行的,即您没有可以达到的疯狂高(或无限)数量的稍微不同的游戏状态。

另一种选择是使用 MCTS 的“开环”变体。您的节点将不再代表游戏状态,而仅代表导致它们的动作序列。您将不再在任何节点中存储任何游戏状态,而是在遍历树时始终从头开始重新生成它们,从根节点开始。您将不再有任何明确的机会节点,而是具有代表较大状态集的状态,这些状态可能通过从根节点遵循相应路径来达到。有关这方面的更多信息,请参阅我对其他问题的回答. 这种方法的优点是它不需要显式了解由于偶然事件而可能达到的所有可能状态,不需要显式了解概率,并且可以仅采样而不是显式枚举每个可能的结果。