Alpha-beta pruning 迴圈版的演算法

我需要 alpha-beta pruning 迴圈版的演算法。

我已經在 Wikipedia 找到遞迴版的演算法如下:

function alphabeta(node, depth, α, β)

(* β represents previous player best choice - doesn't want it if α would worsen it *)

if depth = 0 or node is a terminal node

return the heuristic value of node

for each child of node

α := max(α, -alphabeta(child, depth-1, -β, -α))

(* use symmetry, -β becomes subsequently pruned α *)

if β≤α

break (* Beta cut-off *)

return α

(* Initial call *)alphabeta(origin, depth, -infinity, +infinity)

我擔心實作遞迴版的 alpha-beta pruning 容易造成 stack over flow 或是function call overhead 的問題,畢竟程式效率是我現在最重視的議題之一,所以非常需要一份 alpha-beta pruning 迴圈版的演算法、pseudocode、程式碼 (C/C++/Java)。

最低要求演算法,如果有 pseudocode 的話很好,若有程式碼以 C 或 C++ 或 Java 任一的話更好。

Update:

謝謝 novus 的回答,你的回答讓我收穫良多,如果其他人沒有回答我迴圈版的演算法 (不能模擬 call stack),我將選你為最佳回答,謝謝!

2 Answers

Rating
  • novus
    Lv 6
    1 decade ago
    Favorite Answer

    分下列幾點探討

    stack over flow:

    由於搜尋量是指數成長,一般來說策略性遊戲很難讓你搜尋超過20層,連深藍都差不多如此而已,一般PC必須靠heuristic狂砍才有辦法接近這個深度,而且很多人不得其法連10層都達不到。

    stack over flow至少得上千層才會發生,距離非常遙遠,若發生肯定是撰寫上有bug。

    function call overhead:

    等你把整個 a-b pruning 實作出來,你會發現function call overhead非常非常微不足道。一般來說真正的效能大魔王是在每一層產生和排序候選步,這裡面的function call 可能更多。

    如果你真的在意效率,就不要做過早的最佳化,除非你真的確定這裡是效能瓶頸,否則花了大量力氣只打蒼蠅不打老虎。

    若是你欲實作的策略性遊戲有固定深度、固定分支的特性,搜尋的最後幾層可以同時攤平遞迴和迴圈,沒什麼技巧,hard coding 而已

    另外從實作方面來看:

    a-b pruning 是一種深度優先搜尋,但它並沒有什麼特殊的數學結構可以利用,因此改成非迴圈沒有巧法,你差不多只是另外用資料結構來模擬 call stack 罷了。

    所以到頭來你只不過是把一個 function call 交易成 branch,然後維護一個資料結構還不知道會不會比天然的 call stack 成本高,真正能省下多少時間令人懷疑。

    這裡提供一個我使用的方法:

    假如說要展開一個至多10層的搜尋,那麼我可以觀察其中記憶體用量較大、管理較複雜的資料結構,在搜尋之前把10層搜尋所需要的記憶體上限一次配足,各層需要用記憶體時只要一個指標指過去就夠。

    這等於是實作一個搜尋專用的pool,於是中途就完全不需要額外配置記憶體,除了幾個local暫存的小變數之外。

    2010-10-15 16:50:07 補充:

    補充一個觀念

    由於搜尋樹通常呈 指數 成長,因此可以想見樹的葉節點數量很可能大於、甚至遠超過中間節點的數量和。

    所以要評估遞迴對效能的衝擊有個很簡單的方法,例如說可以將最後 2~3 層攤平寫成多重回圈。初始的各層仍然使用遞迴,只是當 depth 降到某個程度後呼叫攤平的版本。

    如果你發現效能改善微乎其微,那麼就不必忙了,因為剩下來的再怎麼改都不會比這個好多少

    以上的說明可以理解嗎?

    2010-10-15 22:00:40 補充:

    你想太多...

    既然這個演算法沒有甚麼特殊數學結構,而且只是要攤平「常數」層,所以用暴力帶入法就好了,例如

    原:

    f(S) {

     foreach child of S {

      f(child);

     }

    }

    帶入一層

    f(S) {

     foreach child of S {

      foreach child` of child {...}

     }

    }

    2010-10-15 22:03:43 補充:

    所以你會得到兩個alpha beta函式,一個和你在問題中列舉的類似,只是當depth 小於某個數值時,呼叫葉節點攤平的版本

    實際寫法會隨你打算設計的遊戲而異,而且並不總是可以這樣搞

    2010-10-15 23:26:46 補充:

    上述只是示意,不想讓例子過長所以裁掉其他部分

    你當然也可以把 alpha beta pruning 寫到攤平的版本內

    只是要特別注意分數的正負號而已

    2010-10-15 23:36:36 補充:

    說穿了就是手工的 function inlining 而已

    編譯器都知道怎麼做,對人類來說更是小case

    2010-10-16 00:21:59 補充:

    本來想直接給code,不過明天要出遠門,所以算了

    簡單的做法:

    1. 將函數複製一份,把每個會名稱衝突的區域變數改名。例如alpha改成alpha2

    2. 然後把函數貼到原本呼叫處

    3. 按照原本call的方式賦值區域變數,以你的例子就 alpha2=-beta; beta2=-alpha

    4. 參考原本return的方式,取得處理過的傳回值

    5. 觀察架構,把可以合併的變數合併,確定原本每條return 的 path都會被處理到

    大概是這樣

  • 1 decade ago

    如果我知道怎麼用迴圈攤平,就不會來發問了。

    2010-10-15 23:02:07 補充:

    攤平就沒有 alpha-beta pruning,只是個 minimax tree,這樣對搜尋效率的影響還滿大的,尤其是葉節點特別多的情況更為嚴重。這種末層以迴圈攤平的版本和全遞迴的版本兩者比較並不公平。既然如此,攤平的修改版本並不能用來評估遞迴對效能的衝擊。

    算了,我想這邊能解釋的像你這麼深入的高手應該不多,給你最佳回答以表謝意。

    2010-10-15 23:36:06 補充:

    我無法推理出攤平本題遞迴的方法,我只會 minimax 迴圈版本,不會 alpha-beta pruning 迴圈版本,這是我個人的智力問題,請問 novus 能不能再好心地給些提示?

    2010-10-15 23:36:39 補充:

    當然是指末幾層攤平而已。

    2010-10-16 00:53:40 補充:

    我完全懂了,謝謝您!

Still have questions? Get your answers by asking now.