JAVA Tic-Tac-Toe Minimaxアルゴリズムは例外をスローし続ける

Question

私はminimaxアルゴリズムでtic tac toeゲームを作ろうとしています。私はこれを使用していますtutorial。私はこのアルゴリズムの仕組みを理解していますが、実装には問題があります。私はこのアルゴリズムをユニットテストに合格させることはできません。これは、私がボード内で占領されている細胞の例外を与えると私は自分で解決策を見つけることができません。それはボードの勝利指数を返すべきです。ご協力いただきありがとうございます。ここ

は失敗したテスト応答である：

exceptions.CellIsNotAvailableException: This cell is occupied. 

at board.Cell.setMarker(Cell.java:22) 
at algorithm.Algorithm.minimax(Algorithm.java:204) 
at algorithm.Algorithm.findBestMove(Algorithm.java:217) 
at tgrevious.boardTest.BoardTest.shouldreturneight(BoardTest.java:71) 

故障したユニットテスト：

public class CellIsNotAvailableException extends IllegalArgumentException { 

public CellIsNotAvailableException(String message) { 
    super(message); 
} 

}

アルゴリズム：私はそれがスローされます作ら

@Test 
public void shouldreturneight() { 
    GameBoard gameBoard = new GameBoard(); 
    Algorithm al = new Algorithm(); 
    gameBoard.addMarkerToCell(0,Token.X); 
    gameBoard.addMarkerToCell(1,Token.O); 
    gameBoard.addMarkerToCell(2,Token.X); 
    gameBoard.addMarkerToCell(3,Token.O); 
    gameBoard.addMarkerToCell(4,Token.O); 
    gameBoard.addMarkerToCell(5,Token.X); 
    //gameBoard.addMarkerToCell(2,Token.X); 
    int bestMove = al.findBestMove(gameBoard.getBoard()); 
    assertEquals(8, bestMove); 
} 

例外。クラス

public class Algorithm { 
    public boolean checkRows(Cell[] board) { 
    if ((board[0].getMarker() == board[1].getMarker() && board[1].getMarker() == board[2].getMarker()) || 
     (board[3].getMarker() == board[4].getMarker() && board[4].getMarker() == board[5].getMarker()) || 
     (board[6].getMarker() == board[7].getMarker() && board[7].getMarker() == board[8].getMarker())) { 
     return true; 
    } 
    return false; 
} 

public boolean checkColumns(Cell[] board) { 
    if ((board[0].getMarker() == board[3].getMarker() && board[3].getMarker() == board[6].getMarker()) || 
     (board[1].getMarker() == board[4].getMarker() && board[4].getMarker() == board[7].getMarker()) || 
     (board[2].getMarker() == board[5].getMarker() && board[5].getMarker() == board[8].getMarker())) { 
     return true; 
    } 
    return false; 
} 

public boolean checkdiagonals(Cell[] board) { 
    if ((board[0].getMarker() == board[4].getMarker() && board[4].getMarker() == board[8].getMarker()) || 
      (board[2].getMarker() == board[4].getMarker() && board[4].getMarker() == board[6].getMarker())) { 
     return true; 
    } 
    return false; 
} 

Token botPlayer = Token.X; 
Token opponent = Token.O; 

public int evaluate(Cell[] board) { 
    //rows across 
    if ((board[0].getMarker() == board[1].getMarker() && board[1].getMarker() == board[2].getMarker())) { 
     if (board[0].getMarker() == Token.X) { 
      return 10; 
     } 
     else if (board[0].getMarker() == Token.O) { 
      return -10; 
     } 
    } 
    if (board[3].getMarker() == board[4].getMarker() && board[4].getMarker() == board[5].getMarker()) { 
     if (board[3].getMarker() == Token.X) { 
      return 10; 
     } 
     else if (board[3].getMarker() == Token.O) { 
      return -10; 
     } 
    } 
    if (board[6].getMarker() == board[7].getMarker() && board[7].getMarker() == board[8].getMarker()) { 
     if (board[6].getMarker() == Token.X) { 
      return 10; 
     } 
     else if (board[6].getMarker() == Token.O) { 
      return -10; 
     } 
    } 
    //columns down 
    if (board[0].getMarker() == board[3].getMarker() && board[3].getMarker() == board[6].getMarker()) { 
     if (board[0].getMarker() == Token.X) { 
      return 10; 
     } 
     else if (board[0].getMarker() == Token.O) { 
      return -10; 
     } 
    } 
    if (board[1].getMarker() == board[4].getMarker() && board[4].getMarker() == board[7].getMarker()) { 
     if (board[1].getMarker() == Token.X) { 
      return 10; 
     } 
     else if (board[1].getMarker() == Token.O) { 
      return -10; 
     } 
    } 
    if (board[2].getMarker() == board[5].getMarker() && board[5].getMarker() == board[8].getMarker()) { 
     if (board[2].getMarker() == Token.X) { 
      return 10; 
     } 
     else if (board[2].getMarker() == Token.O) { 
      return -10; 
     } 
    } 
    //rows diagonally 
    if (board[0].getMarker() == board[4].getMarker() && board[4].getMarker() == board[8].getMarker()) { 
     if (board[0].getMarker() == Token.X) { 
      return 10; 
     } 
     else if (board[0].getMarker() == Token.O) { 
      return -10; 
     } 
    } 
    if (board[2].getMarker() == board[4].getMarker() && board[4].getMarker() == board[6].getMarker()) { 
     if (board[2].getMarker() == Token.X) { 
      return 10; 
     } 
     else if (board[2].getMarker() == Token.O) { 
      return -10; 
     } 
    } 
    return 0; 
} 

public boolean hasCellsLeft(Cell[] board) { 
    for (int i=0; i<9; i++) { 
     if (board[i].getMarker() == Token.EMPTY) { 
      return true; 
     } 
    } 
    return false; 
} 

public int minimax(Cell[] board, int depth, boolean isMax) { 
    int score = evaluate(board); 
    int best; 
    //if maximizer won 
    if (score == 10) { 
     return score; 
    } 
    //if minimizer won 
    if (score == -10) { 
     return score; 
    } 
    if (hasCellsLeft(board) == false) { 
     return 0; 
    } 
    if (isMax) { 
     best = -1000; 
     for (int i=0; i<board.length; i++) { 
      if (board[i].getMarker() == Token.EMPTY) { 
       board[i].setMarker(botPlayer); 
       best = Math.max(best, minimax(board, depth+1, !isMax)); 
       board[i].setMarker(Token.EMPTY); 
      } 
     } 
     return best; 
    } 
    else { 
     best = 1000; 
     for (int i=0; i<board.length; i++) { 
      if (board[i].getMarker() == Token.EMPTY) { 
       board[i].setMarker(opponent); 
       best = Math.min(best, minimax(board, depth+1, !isMax)); 
       board[i].setMarker(Token.EMPTY); 
      } 
     } 
     return best; 
    } 
} 

public int findBestMove(Cell[] board) { 
    int bestValue = -1000; 
    int bestMove = -1; 
    for (int i=0; i<board.length; i++) { 
     if (board[i].getMarker() == Token.EMPTY) { 
      board[i].setMarker(botPlayer); 
      int moveValue = minimax(board, 0, false); 
      board[i].setMarker(Token.EMPTY); 
      if (moveValue > bestValue) { 
       bestMove = i; 
       bestValue = moveValue; 
      } 
     } 
    } 
    return bestMove; 
} 
} 

GameBoard.class

public class GameBoard { 
    private static final int numberOfCells = 9; 

Cell[] board = new Cell[numberOfCells]; 

public Cell[] getBoard() { 
    return board; 
} 

public GameBoard() { 
    for (int i=0; i<numberOfCells; i++) { 
     board[i] = new Cell(); 
    } 
} 

public void addMarkerToCell(int cellNumber, Token token) { 
    if (checkAvailableCells().contains(cellNumber)) { 
     board[cellNumber].setMarker(token); 
    } 
} 

public Token getMarkerAt(int cellNumber) { 
    return board[cellNumber].getMarker(); 
} 
} 

Cell.class

public class Cell { 
    Token marker; 

public Cell() { 
    marker = Token.EMPTY; 
} 

public Token getMarker() { 
    return marker; 
} 

public void setMarker(Token token) { 
    if (marker != Token.EMPTY) { 
     throw new CellIsNotAvailableException("This cell is occupied."); 
    } 
    else { 
     marker = token; 
    } 
} 

public void resetMarker() { 
    marker = Token.EMPTY; 
} 
} 

Answer 1

あなたの再帰がブランチを終了すると、あなたはまだあなたが枝を実行することができますバックToken.EMPTYに評価した動きを設定しています別の動きで。私はそれが論理バグだとは思わない。

best = Math.max(best, minimax(board, depth+1, !isMax)); 
board[i].setMarker(Token.EMPTY) 

代わりに、チェックを実行しないresetMarker関数を呼び出します。