蒙特卡罗树搜索在实践中如何实现

Question

蒙特卡罗树搜索在实践中如何实现

algorithmartificial-intelligencesimulationmontecarlomonte-carlo-tree-search

10

我在一定程度上理解算法的工作原理。我并不完全了解算法在实践中是如何实际实施的。

我有兴趣了解对于比较复杂的游戏（例如国际象棋），最优化的方法是什么，比如：递归方法？异步？并发？并行？分布式？数据结构和/或数据库？

- 我们期望在单台机器上看到哪些限制？（我们可以同时在许多核心上运行...也许是GPU？） - 如果每个分支都导致玩出完全不同的游戏，（这可能会达到几百万）我们如何保持整个系统的稳定性？如何重复使用已经玩过的分支？

- Michael Ramos

我知道这可能太宽泛了，但在被标记之前，我会感激任何链接/参考资料。 - Michael Ramos

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dennis Soemers · Accepted Answer

递归方法？异步？并发？并行？分布式？数据结构和/或数据库。

在MCTS中，递归实现没有太多意义（这在其他树搜索算法（如基于minimax的算法）中很常见），因为您总是从当前游戏状态（根节点）开始按顺序遍历游戏，直到您选择评估的游戏状态（终端游戏状态，除非您选择使用深度限制来进行play-out阶段和启发式评估函数的非标准实现）。更明显的实现方式是使用while循环。如果这是您第一次实现该算法，我建议首先尝试单线程实现。虽然它是一个相对容易并行化的算法，但有多篇论文介绍了如何并行化。您可以同时运行多个模拟（其中模拟=选择+扩展+playout+反向传播）。您可以尝试确保在反向传播期间所有内容都得到清洁更新，但您也可以决定根本不使用任何锁定/阻塞等。由于所有模拟中已经有足够的随机性，所以如果您由于天真地实现并行化而失去了一些模拟的信息，那么它真的不会太痛苦。至于数据结构，与minimax等算法不同，您实际上需要明确地构建一棵树并将其存储在内存中（它会随着算法的运行而逐渐构建）。因此，您需要一个通用的树数据结构，其中节点具有后继/子节点列表，并且还有指向父节点的指针（用于模拟结果的反向传播）。

我们可以预期在单台机器上看到哪些限制？（我们可以跨许多核心并发运行...也许是GPU？）

可以进行跨多个核心的运行（请参见上面关于并行化的点）。我没有看到算法的任何部分特别适合GPU实现（没有大型矩阵乘法等），因此GPU不太可能有趣。

如果每个分支都导致完全播放新游戏（这可能达到数百万），我们如何保持整个系统稳定？如何重用已经播放的分支？

在最常描述的实现中，该算法每次迭代/模拟在扩展阶段（选择阶段后遇到的第一个节点）只创建一个新节点。同一模拟中生成的所有其他游戏状态在play-out阶段都不会得到任何节点以存储在内存中。这可以使内存使用率受控制，意味着您的树增长相对缓慢（每次模拟只增加1个节点）。这确实意味着您可以稍微减少以前模拟的分支的重用，因为您不会将所有内容都存储在内存中。您可以选择实现扩展阶段的不同策略（例如，为play-out阶段生成的所有游戏状态创建新节点）。但如果您这样做，您必须仔细监视内存使用情况。