是否有可能与OpenMP并行运行Alpha-Beta Pruning的Minimax搜索？

通过基本的Minimax搜索，使用OMP For分割多个线程之间的工作似乎很容易。例如 -是否有可能与OpenMP并行运行Alpha-Beta Pruning的Minimax搜索？

#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搜索，但此限制让我难以忍受。

来源

2014-11-05 d3ward

这是可能的，但您将不得不使用一些更低级别的OpenMP构造，使用线程ID和同步。 – steabert 2014-11-05 11:38:48

啊，好吧。 OMP的哪些元素特别是你的意思？只需线程ID和同步？我很好奇如何解决这个问题，或者如果有任何在线的例子可能会让我指向正确的方向。迄今为止，我的搜索没有取得任何有希望的结果。 – d3ward 2014-11-05 21:38:29

我会在后面写一个简单的例子来说明如何去做，但有两个棘手的问题。一个是你的'alphabeta'函数使用前一次迭代中的alpha值，这是你需要去除的一个依赖项。其次，首先完成的线程不一定是具有更小的子节点索引的线程。 – steabert 2014-11-05 21:49:40

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

如果只有2-4个工作线程是令人满意的方法。但是当一个位置只有少数根移动或者你有一个非常好的排序函数f时它有缺点或移动。如果最好的移动是首先计算的，在顺序的情况下，其他移动将由于截止计算得非常快。因此，如果其他线程在可能“最佳移动”的值已知之前搜索并行的其他根移动，则这是对计算能力的浪费。有可能对这些举措进行有效的排序，在99％以上的情况下，最好的举措将以第一手计算。这与称为“历史表”，“杀手移动”和“空移动修剪”的助手一起工作。

作为一种最先进的并行化，您可以使用年轻兄弟等待概念（YBWC）。在那里，就像在主变化分裂（PVS）中一样，在每个节点中，第一步都是按顺序（！）计算的，并且只有在没有截断的情况下才会同时计算替代动作（兄弟）。兄弟们已经计算出了第一个节点的价值，以便做出快速切入，并且只尝试击败它。前10名中的每个开源引擎几乎都使用它自己的变体，但实现起来并不容易，因为您可以在每个节点中产生不同深度的任务，因此使用标准OpenMP构造很难制定。新的OpenMP 3.1任务构建可以提供帮助，但我不确定。作为第一个去的地方，您可以访问https://chessprogramming.wikispaces.com/Parallel+Search来阅读主题。

来源

2014-11-27 13:22:25 TheSlater

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

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

#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-07 19:29:04 Raul

是否有可能与OpenMP并行运行Alpha-Beta Pruning的Minimax搜索？

回答

相关问题