JAVA Tic-Tac-Toe Minimax Algorithm keeps throwing exception

Question

I am trying to make a tic tac toe game with the minimax algorithm. I am using this tutorial. While I understand how this algorithm works I am having trouble implementing it. I cannot get this algorithm to pass a unit test. It gives me an exception for cells that are occupied in the board and I cannot find a solution by myself. It should return the winning index in the board. Thanks for your help.

Here is the failed test response:

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)

The failed unit 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 I made that gets thrown:

public class CellIsNotAvailableException extends IllegalArgumentException {

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

}

Algorithm.class

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

When your recursion finishes a branch, you are setting a move already evaluated back to Token.EMPTY so you can perform a branch on another move. I don't think it's a logic bug.

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

Instead call your resetMarker function which does not perform the check.