Othelloのアルファベータプルーニング問題

Question

私はアルファベータ版で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私は（黒勝ち、白の勝利は、ドロー）ゲームの状態を更新します。 また、これらのメソッド内のプレーヤーを切り替えることもできます。プレイヤーが移動していないときは、ボードを変更せずにダミーの を動かし、プレイヤーを切り替えます。

さらに多くのコードがありますが、アルゴリズムが ゲームオーバーになると問題が発生すると思います。ランダムな動きをするようにエンジンを設定すると、この問題は発生しないので、問題はアルファベットアルゴリズムでなければなりません。ここで

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である：ここでは

はgetAllMoves、このコールgetFlipsです。

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; 

    }      

} 

ありがとう：ここ

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です！

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();   
}