algorithm - 任何分布式并行树搜索算法建议？

Question

我正在编写一个分布式 Go/Gomoku 机器人。

基本上重点是将树搜索分发到许多计算机上。使用像 DFS 这样的基本树搜索算法，这将非常简单，因为我可以将搜索空间划分为子树。虽然我宁愿有更高效的东西，比如带有 alpha-beta 修剪的 mini-max - 但据我了解，如果没有任何共享内存，它是毫无意义的。所以我有点卡住了。

任何想法我可以使用什么算法高效且易于分发？更重要的是，我在哪里可以找到一些（伪）代码或者实现？

谢谢，

score 6 · Accepted Answer

你需要阅读蒙特卡洛树搜索，不是因为它本质上更容易分发（它既不比另一个树搜索更容易也不难），而是因为它是最先进的，解决问题的人正在致力于分布式该算法的版本。

如果您要费心制作分布式算法，则没有理由从较小的算法开始。除非您出于教育原因制作分布式算法，在这种情况下，请继续，在分发基本算法的实验中会有一些深刻的教育，并且看到它的性能比非分布式最先进算法更差:)

score 2 · Accepted Answer

2

尝试 Map Reduce 方法。例如，参见

于 2010-02-07T23:09:37.880 回答

score 1 · Accepted Answer

DDS*和ABDADA是 2 种分布式/并行极小极大算法。一些通信是必要的，但这可以通过将某些结果转发回控制器来完成。

您提到的更简单的方法是使用不同的搜索树根来减少地图。

正如@Pascal Cuoq 正确提到的那样，蒙特卡洛树搜索是 Go 中最先进的。

在这里您可以找到对 MoGo 搜索算法及其并行化方式的很好解释：

更深入地探索基于随机播放以更好结果播放的节点。在每一步都选择一个叶节点进行单层扩展。这可以通过让每台机器选择不同的叶子来扩展来分配。

蒙特卡洛树搜索的一个很好的概述在这里：

3 回答 3