如何并行化negamax算法？
有没有办法将以下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
当这样制定时，作为一个单一的递归函数，并不容易。
最简单的方法是将它分成两个函数：一个专门用于第一个调用树的根，然后调用另一个函数，并递归地继续调用它自己。 在根版本中，您可以通过儿童并行化循环，并将不同的值存储在列表中。 然后你只需要一个非并行化的循环来查找列表中的最大值，但这会立即完成。
请注意，如果您继续进行alpha-beta修剪等增强功能，这将变得更加复杂; 天真地并行化第一个循环，就像我在这里所建议的那样，将显着减少可以通过alpha-beta修剪进行修剪的节点数目
拓扑+纯粹[SERIAL]价值依赖链决定一个游戏：
考虑到树形拓扑结构，递归公式的使用不是一个原因，而是一个由此产生的因果效应，因为递归公式很容易进行草图和编码。 （对于那些确实对计算机科学感兴趣的人，只需对递归制定的计算策略的资源消耗进行基准测试，并测试（在[SPACE]和[TIME]两个域中）一旦您的基准调整在这种非常资源限制的两难问题之外，在教科书范例问题规模和/或超出设计者的选择之外增长了一些，如何深入递归级别对于期望和设置资源是否公平以及接下来会发生什么，如果递归试图潜入一个步骤比这个“预接线”玻璃天花板确实发生得更深）。
如何将其转换为真正的[PARALLEL]计算时间表？
关于找到一个真正的[PARALLEL]处理策略的机会的问题，直接找到一个不可并行的纯粹的[SERIAL]依赖关系链，从每个终端节点开始并向后推进，直到树根节点。
树拓扑需要某种“相互依赖”的“沟通”，在树的反向遍历期间出现，所以真正的[PARALLEL]处理时间表可能允许的所有主要优点在需要传输纯粹的[SERIAL]值依赖链到“下一个”非本地处理流代码执行。 这使得最初的想法成为反模式。
在意识到这主要是纯粹的[SERIAL]依赖性之后，任何想并行化执行尝试仍然是可能的，但其性能结果变得更加反面，而不是任何合理支持的选择，因为它们实际上花费更多（在[TIME] ），而不是串行链处理（递归或不递归），因为[SPACE]域允许这种工作方式。
上一篇: How to parallelize a negamax algorithm?
下一篇: recursive, iterative based negamax algorithm for a chess AI