“蒙特卡洛搜索”如何工作?

人工智能 游戏-ai 蒙特卡罗树搜索 蒙特卡罗方法 阿尔法戈
2021-11-08 20:28:40

我在一篇关于 AlphaGo 的 Reddit 帖子中听说过这个概念。我试图通过论文和文章,但无法真正理解算法。

那么,有人可以简单地解释一下蒙特卡洛搜索算法是如何工作的,以及它是如何用于构建玩游戏的 AI 机器人的吗?

1个回答

蒙特卡洛方法是一种生成大量随机值或模拟并根据一般模式(例如均值和方差)形成某种结论的方法。

例如,您可以将其用于天气预报预测长期天气是相当困难的,因为它是一个混乱的系统,微小的变化会导致非常不同的结果。使用蒙特卡洛方法,您可以运行大量模拟,每个模拟的大气变化都略有不同。然后,您可以分析结果,例如根据有多少模拟最终下雨来计算给定日期下雨的概率。

至于在 Alpha Go 中使用 Monte Carlo,他们似乎在使用所谓的Monte Carlo Tree Search在这种方法中,您制作一个可能的移动树,几个转向未来,并尝试找到最佳序列。但是,由于围棋游戏中可能的走法数量非常多,因此您将无法探索很远的距离。这意味着一些现在看起来不错的动作在以后可能会变得很糟糕。

因此,在蒙特卡洛树搜索中,您选择一个有希望的移动序列,并运行一个或多个模拟游戏如何从该点开始。然后,您可以使用该模拟的结果来更好地了解特定的移动顺序到底有多好,并相应地更新树。根据需要重复,直到找到一个好的动作。

如果您想了解更多信息或查看一些插图,我发现了一篇关于该主题的有趣论文:C. Browne 等人,蒙特卡洛树搜索方法调查(开放存储库/永久链接(付费专区)