如何并行化negamax算法？

Question

有没有办法将下面的negamax算法并行化？

01 function negamax(node, depth, color)
02     if depth = 0 or node is a terminal node
03         return color * the heuristic value of node
04     bestValue := −∞
05     foreach child of node
06         v := −negamax(child, depth − 1, −color)
07         bestValue := max( bestValue, v )
08     return bestValue

Answer 1

当像这样制定时，作为一个单一的递归函数，不容易。

最简单的方法是将它分成两个函数:一个专门用于在树的根部的第一次调用，然后是一个不同的函数，它被调用并递归地继续调用自身。在根版本中，您可以通过子循环并行化循环，并将不同的值存储在一个列表中。然后，你只需要一个非并行化的循环来找出列表中的最大值，但这将立即完成。

请注意，如果您继续使用类似alpha-beta修剪的增强功能，这将变得更加复杂；像我这里建议的那样简单地并行化第一个循环将显著减少alpha-beta修剪可以修剪的节点数量。

Answer 2

拓扑+纯[SERIAL]值依赖链决定博弈：

给定树形拓扑，递归公式的使用不是原因，而是结果因果关系，因为递归公式是如此简单的草图和代码。(对于那些真正对计算机科学感兴趣的人，只需对递归制定的计算策略的资源消耗进行基准测试，并测试(在[SPACE]-和[TIME]-domains中)它多快就会开始制造麻烦，一旦您的基准扩展超出了教科书示例问题的规模和/或超出了设计师在这种资源上的选择-限制了这样的两难境地，即递归级别有多深可以预期并为其设置资源，以及接下来会发生什么，如果递归试图深入一步，那么“预先连接”的玻璃天花板就已经发生了)。

如何将其转换为真正的计算时间表？

关于找到true-处理策略的机会的问题直接决定于找到一个不可并行的纯依赖链，该依赖链从每个终端节点开始，向后向后直到树根节点。

树形拓扑需要在树的反向遍历期间出现的某种类型的相互依赖的“通信”，因此在将纯[SERIAL]值依赖性链的乘积转移到“下一个”、非本地处理代码流执行的这种需要中，真处理调度可能允许的所有主要优点都被有效地丢失了。这使得最初的想法成为一种反模式。

在认识到这种主要是纯依赖之后，任何想要并行化的强制尝试仍然是可能的，但其性能结果变得更像是反模式，而不是任何合理支持的选择，因为考虑到[SPACE]-domain允许这样的操作方式，它们实际上将比串行链处理(在[TIME]-domain中)花费更多(递归或不递归地制定)。