JAVA Tic-Tac-Toe Minimax-Algorithmus hält werfen Ausnahme

Question

Ich versuche, ein Tic Tac Toe Spiel mit dem Minimax-Algorithmus zu machen. Ich benutze diese tutorial. Während ich verstehe, wie dieser Algorithmus funktioniert, habe ich Probleme, ihn zu implementieren. Ich kann diesen Algorithmus nicht dazu bringen, einen Komponententest zu bestehen. Es gibt mir eine Ausnahme für Zellen, die in der Platine beschäftigt sind und ich kann keine Lösung alleine finden. Es sollte den Gewinnindex im Board zurückgeben. Danke für Ihre Hilfe. Hier

ist der Test nicht bestanden Antwort:

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) 

Der ausgefallene Einheit Test:

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

Exception ich gemacht, dass geworfen wird:

public class CellIsNotAvailableException extends IllegalArgumentException { 

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

}

Algorithm .Klasse

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

Wenn Ihre Rekursion eine Filiale abgeschlossen ist, werden Sie einen Zug Einstellung bereits ausgewertet zurück zu Token.EMPTY so können Sie einen Zweig durchführen in einem anderen Zug. Ich denke nicht, dass es ein Logikfehler ist.

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

Stattdessen rufen Sie Ihre resetMarker Funktion, die die Prüfung nicht durchführt.