奧賽羅Alpha Beta修剪問題

Question

我正在創建一個簡單的引擎來播放奧賽羅，使用帶alpha測試版的minimax。 它的表現不錯，但有時候我會得到一個奇怪的索引超出範圍例外（總是接近 殘局）。

這裏是我的算法

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth) 
{ 
    calls++; 

    float bestResult = -Float.MAX_VALUE; 
    OthelloMove garbage = new OthelloMove(); 

    int state = board.getState(); 
    int currentPlayer = board.getCurrentPlayer(); 

    if (state == OthelloBoard.STATE_DRAW) 
     return 0.0f; 
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.BLACK)) 
     return Float.MAX_VALUE; 
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.WHITE)) 
     return Float.MAX_VALUE; 
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.WHITE)) 
     return -Float.MAX_VALUE; 
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.BLACK)) 
     return -Float.MAX_VALUE; 

    if (depth == maxDepth) 
     return OthelloHeuristics.eval(currentPlayer, board); 

    ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer); 

    for (OthelloMove mv : moves) 
    {    
     board.makeMove(mv); 
     alpha = - minimax(board, garbage, -beta, -alpha, depth + 1); 
     board.undoMove(mv); 

     if (beta <= alpha) 
      return alpha; 
     if (alpha > bestResult) 
     {     
      best.setFlipSquares(mv.getFlipSquares()); 
      best.setIdx(mv.getIdx());   
      best.setPlayer(mv.getPlayer()); 
      bestResult = alpha; 
     } 
    }  
    return bestResult; 
} 

內makeMove和undoMove我更新遊戲狀態（黑勝，白勝，平局）。 我也在這些方法中切換玩家。當玩家沒有任何動作時，我會在不更換棋盤的情況下移動一個虛擬 並切換玩家。

還有更多的代碼，但我認爲問題發生在算法在位置上擊中 遊戲。當我將引擎設置爲隨機移動時，這個問題不會發生，所以問題應該是alpha beta算法。

這裏是getAllMoves，這個調用getFlips：

public ArrayList<OthelloMove> getAllMoves(int player) 
    { 
    ArrayList<OthelloMove> moves = new ArrayList<OthelloMove>(); 

    for (int i = 10; i < 90; i++) 
    { 
     int col = i % 10; 

     if (col != 0 && col != 9)    
     { 
      if (cells[i] == EMPTY) 
      { 
       ArrayList<Integer> flips = getFlips(i, player);      
       if (flips.size() > 0) 
       { 
        OthelloMove mv = new OthelloMove(); 
        mv.setFlipSquares(flips); 
        mv.setIdx(i);       
        mv.setPlayer(player); 
        moves.add(mv); 
       } 
      } 
     } 

    }          

    return moves; 
} 

這裏是getFlips。

public ArrayList<Integer> getFlips(int idx, int player) 
    {   
    int opponent = getOpponent(player); 
    ArrayList<Integer> flips = new ArrayList<Integer>(); 

    if (cells[idx] != EMPTY) 
     return flips; 

    for (Integer dir : DIRECTIONS) 
    { 
     int distance = 1; 
     int tempIdx = idx; 

     while (cells[tempIdx += dir] == opponent) 
      distance++; 

     if ((cells[tempIdx] == player) && (distance > 1)) 
     { 

      while (distance-- > 1) 
      {      
       tempIdx -= dir; 
       flips.add(tempIdx); 
      }        
     }    
    } 
    return flips; 
} 

這裏是updateState：

public void updateState() 
    {     
    int opponent = getOpponent(currentPlayer); 
    int playerMoves = getAllMoves(currentPlayer).size(); 
    int opponentMoves = getAllMoves(opponent).size(); 

    if (((playerMoves == 0) && (opponentMoves == 0)) || (emptyCells == 0)) 
    {       
     int blackDiscs = countDiscs(BLACK); 
     int whiteDiscs = countDiscs(WHITE); 

     if (blackDiscs > whiteDiscs) 
      state = STATE_BLACK_WINS; 
     else if (blackDiscs < whiteDiscs) 
      state = STATE_WHITE_WINS; 
     else 
      state = STATE_DRAW; 

    }      

} 

謝謝！

Answer 1

我不熟悉遊戲具體，但我相信它是與事實帽子行：

while (cells[tempIdx += dir] == opponent) 

您也應該檢查你是不是出界，否則 - 如果還有在董事會的最後一個對手，你會不斷增加dir

嘗試改變這一行：

while (tempIdx + dir >= 0 && tempIdx + dir < cells.length && cells[tempIdx += dir] == opponent) 

作爲一個經驗法則，usua在數組訪問中，特別是在循環中，通過顯式檢查長度來防止出現限制是一種很好的做法。

Answer 2

發現問題，無論如何。

這個錯誤是玩家不能移動並且必須通過轉彎的情況。 棘手的是發揮'幽靈移動'（即一個不會改變棋盤的移動），並且切換球員轉向，這樣Minimax甚至不會注意到這種情況。

我這樣做，但在錯誤的地方！代碼如下：

public void makeMove (OthelloMove move) 
    {      
    int player = move.getPlayer();   
    ArrayList<Integer> flips = move.getFlipSquares(); 

    if (flips != null) 
    {         
     int idx = move.getIdx();      
     cells[idx] = player; 
     for (Integer flip : flips) 
      cells[flip] = player;   

     emptyCells--;  
     this.updatePhase();   
    } 
    this.toogleCurrentPlayer();      
} 

public void undoMove (OthelloMove move) 
{      
    int player = move.getPlayer();   
    ArrayList<Integer> flips = move.getFlipSquares(); 
    int opponent = getOpponent(player); 

    if (flips != null) 
    { 
     int idx = move.getIdx(); 

     cells[idx] = EMPTY; 
     for (Integer flip : flips) 
      cells[flip] = opponent; 

     emptyCells++;           
     this.updatePhase(); 
    } 
    this.toogleCurrentPlayer();   
}