使用 MPI 并行生成和搜索跳棋游戏树

Question

我试图在C中实现一个最优的跳棋游戏。

为了找到机器可以做出的棋盘的最优移动，我通过固定深度，基于棋盘的当代状态，在C中使用（GLib）生成了一个n元博弈树。

并且，为游戏树中存在的所有叶节点计算启发式值，该值被定义为棋盘中剩余的机器棋子数减去玩家对手棋子数，因为国王比棋子拥有更强大的能力，启发式将每个国王计算为两个正常棋子，使用该值进行αbeta搜索。

更有可能的是，如果我尝试增加深度，增加游戏树的深度最终会产生优化的移动，它需要花费大量时间来生成树并进行启发式搜索。

我的想法是独立生成树的第一层，并将子节点分布在可用的处理器中，以便使用MPI进一步执行？

可能吗？如果是，我如何使用MPI并行生成树和启发式搜索？

如果效率不高，请建议我如何实施它的其他方法。谢谢。

Answer 1

好吧，它可以被并行化，问题是，你期望得到多少改进。您可能正在循环中生成初始状态的子-在第一级，可以通过在k线程中拆分n子的创建来并行化。由于这些任务的计算要求非常高（递归地创建更多的子树），因此它应该具有相当高的线程效率。

但是，由于树的分支因子可能大于核的数量（或类似），因此即使您的并行化是线性有效的（并且不会），您也只能生成一层。

你使用阿尔法-贝塔修剪吗？我相信它会带来比这种并行化的东西更大的好处。