3

我有一个经典的极小极大问题求解器，带有额外的 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，它的作用相同，只是它会修剪一些分支，这无论如何都会导致更糟糕的结果。

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

4

2 回答 2

1

这可能是由于缓存效应或类似原因。它被称为超线性加速。它可以/确实发生。

于 2015-02-06T14:14:24.053 回答
1

使用更多线程，您实际上是在运行部分广度优先搜索。碰巧您的问题适合广度优先搜索。

即使在单核机器上，您也会看到加速。

您不需要线程来实现这种加速。您可以简单地编写一个（部分）广度优先搜索，其行为类似于多线程。

假设您要搜索两个列表：

  • 100万次0，然后1

  • 1, 然后 100 万次0

你一发现就停下来1。如果您按顺序搜索它们，您需要查看 1,000,002 个元素。如果您在单个内核上使用两个线程，搜索将立即找到 a1并且您完成了。1,000,000 倍左右的“超线性”加速！

于 2015-02-06T14:17:37.263 回答