如何在实践中实施蒙特卡洛树搜索

Question

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

我有兴趣了解一个相当复杂的游戏(也许是象棋)的最佳方法.即递归方法？异步？同时？平行？分散式？数据结构和/或数据库？

- 我们期望在一台机器上看到什么类型的限制？(我们可以同时在多个核心上运行......也许是gpu？)

- 如果每个分支都会产生一个全新的游戏,(这可能达到数百万)我们如何保持整个系统的稳定？我们如何重用已经播放的分支？

Answer 1

递归方法？异步？同时？平行？分散式？数据结构和/或数据库

• 在MCTS中,在递归实现中没有太多意义(这在其他树搜索算法中很常见,例如基于minimax的算法),因为你总是从当前游戏状态(根节点)开始按顺序"游戏"游戏.您选择评估的游戏状态(终端游戏状态,除非您选择使用非标准实施,使用播放阶段的深度限制和启发式评估功能).使用while循环的更明显的实现很好.
• 如果这是您第一次实现该算法,我建议您先进行单线程实现.虽然这是一个相对简单的并行化算法,但有很多论文.您可以简单地并行运行多个模拟(模拟=选择+扩展+播放+反向传播).您可以尝试确保在反向传播期间干净地更新所有内容,但您也可以简单地决定不使用任何锁定/阻止等,所有模拟中已经有足够的随机性,所以如果您丢失了几个模拟的信息由于天真地实现了并行化,它确实不会造成太大的伤害.
• 至于数据结构,与算法不同minimax,您实际上需要显式构建树并将其存储在内存中(它在算法运行时逐渐构建).因此,您需要一个通用的树数据结构,Nodes其中包含一个后继/子列表Nodes,以及一个返回父项的指针Node(模拟结果的反向传播所需).

我们希望在一台机器上看到什么类型的限制？(我们可以同时在多个核心上运行......也许是gpu？)

运行多个核心可以做到(参见上面关于并行化的要点).我没有看到算法的任何部分特别适合GPU实现(没有大型矩阵乘法或类似的东西),因此GPU不太可能有趣.

如果每个分支都会产生一个全新的游戏,(这可能会达到数百万)我们如何保持整个系统的稳定？我们如何重用已经播放的分支？

在最常描述的实现中,算法在扩展阶段(在选择阶段之后遇到的第一个节点)中每次迭代/模拟仅创建一个新节点以存储在存储器中.在同一模拟的播放阶段生成的所有其他游戏状态根本不会将任何节点存储在存储器中.这样可以检查内存使用情况,这意味着您的树只会相对缓慢地增长(每个模拟的节点速率为1个节点).它确实意味着您对先前模拟的分支的重复使用稍微减少,因为您不会存储您在内存中看到的所有内容.您可以选择为扩展阶段实施不同的策略(例如,为在播出阶段生成的所有游戏状态创建新节点).如果你这样做,你将不得不仔细监视内存使用情况.