我对算法的工作原理有一定程度的理解，但我并不完全明白算法在实践中是如何实际实现的。

我想了解对于一个相当复杂的游戏（比如国际象棋）来说，最佳的方法是什么。即递归方法？异步？并发？并行？分布式？数据结构和/或数据库？

— 我们可以预期在单台机器上会看到什么样的限制？（我们能否在多个核心上并发运行…也许是GPU？）

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

回答：

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

• 在MCTS中，递归实现（在其他树搜索算法如基于极小极大的算法中很常见）并没有太大意义，因为你总是从当前游戏状态（根节点）开始，按顺序“通过”游戏，直到你选择评估的游戏状态（终端游戏状态，除非你选择使用非标准实现，在展开阶段设置深度限制并使用启发式评估函数）。使用while循环的实现更为明显，效果也很好。
• 如果你是第一次实现这个算法，我建议先尝试单线程实现。虽然这个算法相对容易并行化，关于这一点有许多论文。你可以简单地并行运行多个模拟（模拟 = 选择 + 扩展 + 展开 + 反向传播）。你可以尝试确保在反向传播期间一切都能干净地更新，但你也可以简单地决定完全不使用任何锁/阻塞等，所有的模拟中已经有足够的随机性，所以如果你因为简单实现的并行化而丢失了一些模拟的信息，这并不会造成太大影响。
• 至于数据结构，与minimax等算法不同，你实际上需要明确构建一个树并将其存储在内存中（随着算法的运行，树是逐渐构建的）。因此，你需要一个通用的树数据结构，包含Nodes，这些Nodes有一系列后继/子Nodes，以及一个指向父Node的指针（这是模拟结果反向传播所必需的）。

我们可以预期在单台机器上会看到什么样的限制？（我们能否在多个核心上并发运行…也许是GPU？）

在多个核心上运行是可以的（参见上面的并行化说明）。我认为算法的任何部分都不特别适合GPU实现（没有大型矩阵乘法或类似的东西），所以GPU不太可能有用。

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

在最常见的实现中，算法在扩展阶段的每次迭代/模拟中只创建一个新节点来存储在内存中（选择阶段后遇到的第一个节点）。在同一模拟的展开阶段生成的所有其他游戏状态都没有节点存储在内存中。这有助于控制内存使用，这意味着你的树只会相对缓慢地增长（以每模拟1个节点的速度）。这确实意味着你对之前模拟过的分支的重用会稍微减少，因为你不会将看到的所有内容都存储在内存中。你可以选择为扩展阶段实现不同的策略（例如，为展开阶段生成的所有游戏状态创建新节点）。如果你这样做，你需要仔细监控内存使用。