有分布式并行树搜索算法建议吗？

题

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

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

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

谢谢，

解决方案

您需要阅读了关于蒙特卡洛树搜索，并不是因为它的本质上更容易分配（它既不比其他树搜索更容易，也不困难），但因为它是艺术的状态，人们对这个问题的工作是工作在该算法的分布式版本。

如果你要制作一个分布式算法的麻烦，没有理由开始一个较小的一个。除非你是做教育的原因分布式算法，在这种情况下，继续前进，会有一些在分发基本算法，并看到它比非分布式的国家的最先进的算法表现较差的实验深受教育：）

其他提示

尝试地图缩小的方法。例如，参见

直接数据传输系统* 和阿巴达是 2 个分布式/并行极小极大算法。一些通信是必要的，但这可以通过将某些结果转发回控制器来完成。

正如您提到的，更简单的方法是使用不同的搜索树根进行映射减少。

作为 @Pascal Cuoq 正确地提到, ，蒙特卡洛树搜索是 Go 中最先进的技术。

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

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

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

许可以下： CC-BY-SA 和归因