的Java極小α-β剪枝遞歸返回

Question

我試圖實現與α-β剪枝在Java中的跳棋遊戲極小。我的minimax算法完美運作。我的代碼與alpha-beta代碼一起運行。不幸的是，當我玩標準極小極小算法的1000場比賽時，alpha-beta算法總是落後50場左右。

由於α-β修剪不應該降低動作的質量，就需要實現它們的時候，有些事情是錯誤的。但是，我已經拿出筆和紙，繪製假設的葉節點值，並使用我的算法來預測它是否會計算正確的最佳移動，並且看起來沒有任何邏輯錯誤。我使用了這個視頻中的樹：Alpha-Beta Pruning來跟蹤我的算法。它邏輯上應該做出所有相同的選擇，因此是一個有效的實現。

我也把打印語句插入代碼（它們已被刪除，以減少雜波），並正在返回的值正確出現的修剪確實會發生。儘管我盡了最大的努力，但我一直無法找到邏輯錯誤所在。這是我實施這個的第三個不同嘗試，他們都有同樣的問題。

我不能在這裏發佈完整的代碼，它是太長，所以我已經包括相關的錯誤的方法。我不確定，但我懷疑這個問題很可能在非遞歸move（）方法中，儘管我無法找到它的邏輯錯誤，所以我只會更多地在其中進行顛簸，可能會使事情沒有韻律或原因，更糟糕而不是更好。

有一招，在for循環回收來自遞歸調用多個整數值？它適用於我的minimax和negamax實現，但alpha-beta修剪似乎產生了一些奇怪的結果。

@Override 
public GameState move(GameState state) 
{ 
    int alpha = -INFINITY; 
    int beta = INFINITY; 
    int bestScore = -Integer.MAX_VALUE; 
    GameTreeNode gameTreeRoot = new GameTreeNode(state); 
    GameState bestMove = null; 
    for(GameTreeNode child: gameTreeRoot.getChildren()) 
    { 
     if(bestMove == null) 
     { 
      bestMove = child.getState(); 
     } 
     alpha = Math.max(alpha, miniMax(child, plyDepth - 1, alpha, beta)); 
     if(alpha > bestScore) 
     { 
      bestMove = child.getState(); 
      bestScore = alpha; 
     } 
    } 
    return bestMove; 
} 

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) 
{ 
    if(depth <= 0 || terminalNode(currentNode.getState())) 
    { 
     return getHeuristic(currentNode.getState()); 
    } 
    if(currentNode.getState().getCurrentPlayer().equals(selfColor)) 
    { 
     for(GameTreeNode child: currentNode.getChildren()) 
     { 
      alpha = Math.max(alpha, miniMax(child, depth - 1, alpha, beta)); 

      if(alpha >= beta) 
      { 
       return beta; 
      } 
     } 
     return alpha; 
    } 
    else 
    { 
     for(GameTreeNode child: currentNode.getChildren()) 
     { 
      beta = Math.min(beta, miniMax(child, depth - 1, alpha, beta)); 

      if(alpha >= beta) 
      { 
       return alpha; 
      } 
     } 
     return beta; 
    } 
} 
//Checks to see if the node is terminal 
private boolean terminalNode(GameState state) 
{ 
if(state.getStatus().equals(win) || state.getStatus().equals(lose) || state.getStatus().equals(draw)) 
    { 
     return true; 
    } 
    else 
    { 
     return false; 
    } 
} 

Answer 1

我注意到你說你發現了問題，但不應該在極小的alpha beta剪枝是

if it is MAX's turn to move 
    for child in children 
    result = alphaBetaMinimax(child, alpha, beta) 
    if result > alpha 
     alpha = result 
     if node is root 
      bestMove = operator of child 
    if alpha >= beta 
     return alpha 
    return alpha 

if it is MIN's turn to move 
    for child in children 
    result = alphaBetaMinimax(child, alpha, beta) 
    if result < beta 
     beta = result 
     if node is root 
      bestMove = operator of child 
    if beta <= alpha 
     return beta 
    return beta 

你寫道：

if alpha >= beta 
    return beta 
return alpha 

Answer 2

要只是回答你的問題

是否有一個技巧來恢復多個整數v來自遞歸的線索 調用for循環？

是的，在Java中，您需要將對象傳遞給遞歸函數調用，然後修改該對象的內容。函數返回後，您將能夠訪問修改後的值。

例如，

class ToBeReturned { 
    int returnValue1; 
    int returnValue2; 
    int returnValue3; 
} 

Answer 3

爲了達到投注的預期結果，您應該實施某種移動排序。在國際象棋中它通常會被捕獲或檢查。這些舉動傾向於最大程度地改變評估，所以它們對於修正有很大的影響。在跳棋中，它可能會帶着對手的寶石或者在第8級晉級自己的寶石（對不起，不知道使用的術語）。

Answer 4

2013年3月16日，sage88問：

有一招，在for循環回收來自遞歸調用多個整數值？它適用於我的minimax和negamax實現，但alpha-beta修剪似乎產生了一些奇怪的結果。

在alpha beta修剪中，感興趣的唯一輸出值是一個節點的分數：最小節點中beta的最終值被認爲是其父節點的最大值的alpha值;同樣，最大節點中alpha的最終值被認爲是其父節點的beta值。因此：

您的問題的答案是算法本身，因爲它是最相關的技巧。

這就是說，在你的實現中有兩個錯誤：1）正如Adrian Blackburn最初指出的那樣，它不正確地從最小節點返回alpha，反之亦然，從而導致它的準確性偏離; 2）通過過早地考慮當前節點的父值或貝塔值，放棄修剪機會。該版本修復了返回值和最大化修剪：對促進一個有趣的和有趣的問題:)

更多樂趣

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) { 
    if (depth <= 0 || terminalNode(currentNode.getState())) { 
     return getHeuristic(currentNode.getState()); 
    } 
    if (currentNode.getState().getCurrentPlayer().equals(selfColor)) { 
     int currentAlpha = -INFINITY; 
     for (GameTreeNode child : currentNode.getChildren()) { 
      currentAlpha = Math.max(currentAlpha, miniMax(child, depth - 1, alpha, beta)); 
      alpha = Math.max(alpha, currentAlpha); 
      if (alpha >= beta) { 
       return alpha; 
      } 
     } 
     return currentAlpha; 
    } 
    int currentBeta = INFINITY; 
    for (GameTreeNode child : currentNode.getChildren()) { 
     currentBeta = Math.min(currentBeta, miniMax(child, depth - 1, alpha, beta)); 
     beta = Math.min(beta, currentBeta); 
     if (beta <= alpha) { 
      return beta; 
     } 
    } 
    return currentBeta; 
} 

謝謝，這裏有一個澄清你move()方法，去除冗餘來電Math.max()：

@Override 
public GameState move(GameState state) { 
    GameState bestMove = null; 
    int bestScore = -INFINITY; 
    GameTreeNode gameTreeRoot = new GameTreeNode(state); 
    for (GameTreeNode child : gameTreeRoot.getChildren()) { 
     int alpha = miniMax(child, plyDepth - 1, bestScore, INFINITY); 
     if (alpha > bestScore || bestMove == null) { 
      bestMove = child.getState(); 
      bestScore = alpha; 
     } 
    } 
    return bestMove; 
} 

最後（更有趣），只是一個建議，一個方法更名爲澄清terminalNode()的意圖，但我會移動到這個GameState，以便它可以不帶參數調用：

private boolean isTerminal(GameState state) { 
    //return Is.any(state.getStatus(), win, lose, draw); 
    return state.getStatus().equals(win) 
     || state.getStatus().equals(lose) 
     || state.getStatus().equals(draw); 
} 

Answer 5

您已經解決了您的問題，但遇到的問題非常普遍。因此，無論何時構建AI代理的算法的一部分，都必須正確地進行測試。所以一旦你的minimax算法正確，你可以生成很多隨機樹並檢查結果是否相同。例如，在Python中，你可以這樣做：

class Node(): 
    def __init__(self, data, children): 
     self.data = data 
     self.children = children 

def generateTree(depth, branching): 
    total = branching**depth 
    values = [randint(-100, 100) for _ in xrange(total)] 
    level = [Node(values[i], []) for i in xrange(total)] 

    for _ in xrange(depth): 
     total /= branching 
     level = [Node(None, level[i * branching: (i+1) * branching]) for i in xrange(total)] 

    return level[0], values 

現在，您可以生成多個隨機樹樹，並比較結果。

tree, values = generateTree(depth, branching) 
print negamax(tree, depth, 1) == alpha_beta_negamax(tree, depth, float('-inf'), float('inf'), 1) 

---

不要忘了極大極小和α-β收益只是最好的價值，而你有興趣在一個真正的遊戲是什麼一招。直接修改它們可以返回移動，但這取決於開發人員決定移動的返回方式。這是因爲可以有許多步驟導致最好的解決方案（您可以返回第一個，最後一個或最常見的方法是找到所有移動並返回隨機）。

在你的情況下，問題是返回值的隨機性，所以在測試過程中，好的方法是修復隨機性。