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

我在写一个分布式的Go/Gomoku机器人。任何分布式并行树搜索算法建议？

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

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

谢谢，

2010-02-07 kurczak

您需要阅读了关于蒙特卡洛树搜索，并不是因为它的本质上更容易分配（它既不容易也不困难而不是另一个树搜索），但是因为这是最先进的技术，并且处理该问题的人正在使用该算法的分布式版本。

如果您打算制作分布式算法的麻烦，那么没有理由以较小的算法开始。除非你是出于教育原因制作分布式算法，在这种情况下，在分发基本算法的实验中会有一些深入的教育，并且看到它比非分布式最先进的算法更糟糕:)

看到Wikipedia page on computer go的 “最近发展区” 一节。

2010-02-07 23:08:48

这看起来很有希望，将会研究它。谢谢。 – kurczak

优秀的解决方案！ – user262976

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

您提到的更简单的方法就像使用不同的搜索树根缩小映射一样。

作为@Pascal Cuoq rightly mentions，蒙特卡罗树搜索是Go中的最新技术。

在这里你可以找到莫戈的搜索算法的一个很好的解释，以及如何其并行：

这是打出来的基于随机播放更好的结果

节点更深入的探讨。在每一步中选择一个叶节点进行单层展开。这可以通过让每台机器选择不同的叶来扩展。

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

2010-02-07 23:03:33 user262976

感谢，ABDADA在第一眼看起来也不错。 – kurczak

尝试地图Reduce方法。例如，看到

2010-02-07 23:09:37

我无法真正理解它如何能以任何方式优于DFS。 – kurczak

我不是说BFS在任何方面都优于DFS。这只是将Map Reduce应用于搜索问题的一个示例。 –

回答