將Minimax修改爲Alpha-Beta修剪僞代碼

Question

我正在學習Alpha-Beta僞代碼，我想爲Alpha Beta修剪寫一個最簡單的僞代碼。

我寫的僞代碼爲極小：

function minimax(node, depth) 
    if node is a terminal node or depth ==0 
      return the heuristic value of node 
    else 
      best = -99999 
    for child in node 
      best = max(best, -minimax(child, depth-1)) 
    return best 

不過，我不知道如何修改它變成α-β剪枝。誰能幫忙？

Answer 1

在Alpha-Beta中，您可以跟蹤一個位置的保證分數。如果您發現比對手已經在其之前的位置上保證的分數更好的移動（之前移動一次），您可以立即停止。

從技術上講，雙方都會跟蹤其低位得分（alpha），並且您可以訪問對手的低位得分（beta）。

下面的僞代碼沒有進行測試，但這裏的理念是：

function alphabeta(node, depth, alpha, beta) 
    if node is a terminal node or depth ==0 
      return the heuristic value of node 
    else 
      best = -99999 
    for child in node 
      best = max(best, -alphabeta(child, depth-1, -beta, -alpha)) 
      if best >= beta 
       return best 
      if best > alpha 
       alpha = best 
    return best 

在搜索的開始，你可以設置阿爾法到負無窮和β到正無窮大。嚴格地說，草圖算法不是alpha-beta，而是Negamax。兩者都是相同的，所以這只是一個實現細節。

請注意，在Alpha-Beta中，移動順序至關重要。如果大多數情況下，你從最好的舉動開始，或者至少是一個非常好的舉措，你會看到Minimax的巨大進步。

從受限制的alpha測試版窗口（非-INFINITY和+ INFINITY）開始的附加優化。但是，如果您的假設錯誤，則必須以更開放的方式重新開始搜索search window。