我在一定程度上理解算法的工作原理。我不完全理解的是该算法在实践中是如何实现的。
我有兴趣了解对于相当复杂的游戏（也许是国际象棋）来说，最佳方法是什么。即递归方法？异步？同时？平行？分散式？数据结构和/或数据库？
-- 我们期望在单台机器上看到什么类型的限制？（我们可以在多个内核上同时运行...... gpu 可能吗？）
——如果每个分支都导致一个全新的游戏被玩，（这可能达到数百万）我们如何保持整个系统的稳定？& 我们如何重用已经玩过的分支？
问问题
1200 次
1 回答
9
递归方法？异步？同时？平行？分散式？数据结构和/或数据库
- 在 MCTS 中，递归实现没有多大意义（这在其他树搜索算法中很常见，例如基于 minimax 的算法），因为您总是从当前游戏状态（根节点）按顺序“通过”游戏直到您选择评估的游戏状态（终端游戏状态，除非您选择使用播放阶段的深度限制和启发式评估函数的非标准实现）。
while使用循环的更明显的实现就可以了。 - 如果这是您第一次实现该算法，我建议您先进行单线程实现。虽然这是一个相对容易并行化的算法，但有多篇论文。您可以简单地并行运行多个模拟（其中模拟 = 选择 + 扩展 + 播放 + 反向传播）。您可以尝试确保在反向传播期间所有内容都得到干净的更新，但您也可以简单地决定根本不使用任何锁/阻塞等，无论如何，所有模拟中已经有足够的随机性，所以如果您从几个模拟中丢失信息由于天真地实现并行化，它在这里和那里确实并没有太大的伤害。
- 至于数据结构，与 类似的算法不同
minimax，您实际上确实需要显式构建一棵树并将其存储在内存中（它是随着算法的运行而逐渐构建的）。因此，您需要一个通用的树数据结构，Nodes其中包含一个后继/子列表Nodes，以及一个返回父级的指针Node（模拟结果的反向传播所必需的）。
我们希望在单台机器上看到什么类型的限制？（我们可以在多个内核上同时运行...... gpu 可能吗？）
可以跨多个内核运行（请参阅上面关于并行化的点）。我没有看到算法的任何部分特别适合 GPU 实现（没有大型矩阵乘法或类似的东西），所以 GPU 不太可能有趣。
如果每个分支都导致一个全新的游戏被玩，（这可能达到数百万）我们如何保持整个系统的稳定？& 我们如何重用已经玩过的分支？
在最常描述的实现中，算法在扩展阶段（在选择阶段之后遇到的第一个节点）每次迭代/模拟只创建一个新节点存储在内存中。在同一模拟的播放阶段生成的所有其他游戏状态根本不会让任何节点存储在内存中。这可以检查内存使用情况，这意味着您的树只会相对缓慢地增长（每个模拟的速度为 1 个节点）。这确实意味着您对先前模拟的分支的重用会稍微减少，因为您不会将看到的所有内容都存储在内存中。您可以选择为扩展阶段实施不同的策略（例如，为播放阶段生成的所有游戏状态创建新节点）。但是，如果您这样做，则必须仔细监视内存使用情况。
于 2018-03-21T09:29:05.683 回答