是否有可能與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搜索？

回答

相關問題