c++ - Alpha-Beta "breaking"阿姆达尔定律？

Question

我有一个经典的 minimax 问题求解器，带有额外的 alpha-beta 剪枝实现。

我按以下方式并行化算法:

1. 进行迭代加深，直到节点多于可用线程
2. 在 N 个线程的批处理中为每个线程运行一个 minimax。因此，如果我们从串行搜索中获得深度 2 的 9 种可能移动，我们首先启动 4 个线程，然后是另外 4 个线程，最后是 1 个，每个线程都从深度 2 开始，并带有自己的参数。

事实证明，4 个线程的加速比 S=T(serial)/T(parallel) 是 4.77，所以我在这里基本上违反了 Amdahl 定律。

如果我们说实现在某种程度上没有被破坏，我怀疑 Alpha-Beta 剪枝在这里发挥了魔力？由于并行开始多个搜索，因此修剪更多且更快？这是我的理论，但如果有人能更详细地证实这一点，我会很高兴。

澄清一下:

没有 alpha-beta 实现的 Minimax 基本上是对整棵树进行深度优先搜索，直到某个最大深度。对于 alpha-beta，它会做同样的事情，只是它会修剪一些分支，这无论如何都会导致更糟糕的结果。

编辑:在进一步检查代码后，我在一行代码上发现了一个错误，导致程序“作弊”并且不遵循某些 Action 。实际加速因子现在是 3.6。很抱歉浪费大家的时间。今天的计算没有突破。 :/

Answer 1

这可能是由于缓存效应或类似原因。它叫做superlinear speedup .它可以/确实发生。