1

有没有办法并行化以下 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
4

2 回答 2

0

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

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

请注意，如果您继续进行 alpha-beta 修剪等增强功能，这将变得更加复杂；像我在这里建议的那样天真地并行化第一个循环将显着减少可以通过 alpha-beta 修剪来修剪的节点数量

于 2018-02-25T17:53:07.373 回答
0

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

鉴于树形拓扑，递归公式的使用不是原因，而是结果的因果关系，因为递归公式很容易绘制和编码。（对于那些确实对计算机科学感兴趣的人，只需对递归制定的计算策略的资源消耗进行基准测试，并测试（在[SPACE]- 和 -[TIME]域中）一旦你的基准扩展在学校之外有所增长，它多久开始产生问题- 本书示例问题规模和/或超出设计师在这个资源限制困境中的选择，即递归级别的预期深度和设置资源的公平程度以及接下来会发生什么，如果递归尝试更深入一步，比这个“pre -有线”玻璃天花板确实发生了）。

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

一个关于找到真正[PARALLEL]处理策略的机会的问题直接决定于找到一个不可并行的纯[SERIAL]依赖链，它从每个终端节点开始并向后前进，朝向树根节点。

树拓扑需要某种相互依赖的“通信”，这种“通信”出现在树的反向遍历期间，因此真正的[PARALLEL]处理计划可能允许的所有主要优势都在传输纯[SERIAL]值产品的需求中有效地丢失了- 依赖链到“下一个”非本地处理代码流执行。这使得最初的想法成为反模式。

意识到这种主要是纯[SERIAL]依赖后，任何想要并行化的强制执行尝试仍然是可能的，但是其性能结果变得比任何合理支持的选择都更像是一种反模式，因为它们实际上将花费更多（在[TIME]域内），而不是串行-链式处理（是否递归地制定），给定[SPACE]-domain 允许这样的作案方式。

于 2018-02-25T19:26:58.637 回答