2

通过基本的 Minimax 搜索，使用 OMP For 在多个线程之间拆分工作似乎很容易。例如 -

#pragma omp parallel for
for (each child node)
{
    val = minimax(child, depth - 1, FALSE);
    bestValue = max(bestValue, val);
}

然而，似乎这对于 Alpha-Beta 修剪来说是不可能的，至少在我的理解中是这样。

#pragma omp parallel for
for (each child node)
{
   α = max(α, alphabeta(child, depth - 1, α, β, FALSE));
   if (β ≤ α)
       break;
}

在 OpenMP 中，如果要使循环并行，则要求 For 循环只能有一个入口/出口点。然而，Alpha-Beta 剪枝打破了这个规则，因为只要需要完成剪枝，就有可能跳出循环（在上面的伪代码中，这将在 β 小于或等于 α 时发生）。

所以我的问题是，有没有办法解决 OpenMP 的这种限制？我想使用 OpenMP 并行运行我的 Alpha-Beta 搜索，但这个限制让我现在很难过。

4

2 回答 2

4

作为第一个想法，您可以并行计算根移动（例如，使用#pragma omp parallel for schedule(dynamic, 1)，以便每个线程都有自己的根移动，然后像任务池一样，选择下一个没有线程触及。因为您必须计算每个根移动，所以线程必须离开循环的中断没有问题。如果线程准备好它的根移动，您可以更新“最佳值”并使用它对于下一个根移动。它必须是一个共享值，并且您必须使用 #pragma omp critical 来保护它。

如果您只有 2-4 个工作线程，这是一种令人满意的方法。但是当一个位置只有几个根移动或者你有一个非常好的移动排序功能时，它有缺点。如果首先计算最佳移动，则在顺序情况下，由于截止，其他移动将被计算得非常快。因此，如果其他线程在可能的“最佳移动”的值已知之前并行搜索其他根移动，那么这是一种计算能力的浪费。有可能如此有效地排序移动，以至于在超过 99% 的情况下，最佳移动将在第一时间计算出来。这适用于称为“历史表”、“杀手级移动”和“空移动修剪”的助手。

作为最先进的并行化，您可以使用 Young Brothers Wait Concept (YBWC)。在那里，就像在 Principal Variation Splitting (PVS) 中一样，在每个节点中，第一步是计算顺序的 (!)，并且只有在没有截止的情况下，替代移动 (兄弟) 才会并行计算。兄弟们已经计算出第一个节点的值，可以快速截断，只尝试击败它。几乎前 10 名中的每个开源引擎都使用它自己的变体，但它不容易实现，因为您可以在不同深度的每个节点中生成任务，因此使用标准 OpenMP 构造来制定它并不容易。新的 OpenMP 3.1 tasks-construct 可以提供帮助，但我不确定。作为第一个去的地方，您可以访问https://www.chessprogramming.org/Parallel_Search阅读主题。

于 2014-11-27T13:22:25.557 回答
0

使用任务构造，您可以遍历不规则结构。在搜索过程中形成的树是应用任务的示例。

一个典型的例子是斐波那契或解决数独：

#include <iostream>
#include <omp.h>
#include <cstdlib>
using namespace std;

unsigned long fib(unsigned long n) {
    unsigned long a = 0;
    unsigned long b = 0;

    if (n == 0) return n;
    if (n == 1) return n;
    #pragma omp task shared(a)
    a = fib(n-1);

    #pragma omp task shared(b)
    b = fib(n-2);

    #pragma omp taskwait
    return a+b;
}


int main(int argc, char** argv) {
    unsigned long result = 0;
    unsigned long N = atol(argv[1]);
    if (N < 0) {
        cerr << "N is a negative number" << endl;
        return -1;
    }
    double start = omp_get_wtime();
    #pragma omp parallel
    {
        #pragma omp single
        result = fib(N);
    }
    double elapsed = omp_get_wtime() - start;
    cout << result << endl;
    cout << "Elapsed time: " << elapsed << endl;

    return 0;
}

这个示例代码对于任务添加的开销来说太简单了，但是您可以使用小数字进行测试（fib(30) 或 fib(35) 在我的机器上使用 2 个线程持续 25 秒）并查看递归是如何工作的。我认为，除了上一张海报所说的，你可以探索这条路。

另一方面，根据另一张海报，Alphabeta 是一种串行算法，因此在不进行重大更改的情况下让它并行工作将非常棘手。

于 2015-05-07T19:29:04.267 回答