Search code examples
javaalgorithmtic-tac-toeminimax

TicTacToe minimax algorithm not picking best move


I've been working on writing a minimax algorithm for my tictactoe game, but it doesn't seem to be choosing the correct move. It is possible to win against the computer, so I must have something mixed up here. I think the algorithm itself seems fine, so I'm pretty sure the problem is how I'm getting the best move. Does anyone have any suggestions?

minimax method

private int minimax(Board board, boolean maximizingPlayer, char symbol){
    //System.out.println(symbol);
    Board copyBoard = new Board(board.getCells());
    char winner = copyBoard.checkWin();
    if(winner!='-' || copyBoard.checkDraw()){
        return score(winner);
    }


    if(maximizingPlayer){
        int bestValue = Integer.MIN_VALUE;
        for(Board b : simulatePossibleMoves(copyBoard,mySymbol)){
            int value = minimax(b,false,switchSymbol(mySymbol));
            if(bestValue < value){
                bestValue = value;
                bestMove = b.getLastMove();
            }
        }
        return bestValue;
    }
    else{
        int bestValue = Integer.MAX_VALUE;
        for(Board b: simulatePossibleMoves(copyBoard, switchSymbol(mySymbol))){
            int value = minimax(b,true,mySymbol);
            if(bestValue > value){
                bestValue = value;
                bestMove = b.getLastMove();
            }
        }
        return bestValue;
    }
}

score method

private int score(char winner){
    if(winner == mySymbol)
        return 10;
    else if(winner == switchSymbol(mySymbol))
        return -10;
    return 0;
}

EDIT:

Example of a game(Human is X, AI is O)

O top left corner
x Center
O middle left
X Bottom left
O top middle
X Top right (Human win)

EDIT 2:

More code, not sure if the error could be in here or not, might as well include it.

private ArrayList<Integer> getPossibleMoves(Board board){
    ArrayList<Integer> moves = new ArrayList<>();
    for(int i = 0; i < board.getCells().length; i++)
        if(!board.isCellTaken(i))
            moves.add(i);
    return moves;
}

private ArrayList<Board> simulatePossibleMoves(Board board, char symbol){
    ArrayList<Board> possibleBoards = new ArrayList<>();
    for(Integer move : getPossibleMoves(board)){
        Board temp = new Board(board.getCells());
        temp.setCell(move, symbol);
        possibleBoards.add(temp);
    }
    return possibleBoards;
}

private char switchSymbol(char s){
    if(s=='X')
        return 'O';
    return 'X';
}

Solution

  • It turns out I've been trying to use the algorithm incorrectly by choosing the bestvalue inside the minimax method itself. By creating another method that calls the minimax method, I was able to find the best move that way. The following code has worked for me.

    public int getMiniMaxMove(Board board){
        int score = -1;
        int bestMove = -1;
    
        for(int i : getPossibleMoves(board)){
            Board copyBoard = new Board(board.getCells());
            copyBoard.setCell(i, mySymbol);
            int moveScore = minimax(copyBoard,false,mySymbol);
    
            if(moveScore >= score){
                score = moveScore;
                bestMove = i;
            }
        }
    
        return bestMove;
    }
    
    
    private int minimax(Board board, boolean maximizingPlayer, char symbol){
        Board copyBoard = new Board(board.getCells());
        char winner = copyBoard.checkWin();
        if(winner!='-' || copyBoard.checkDraw()){
            return score(winner);
        }
    
    
        if(maximizingPlayer){
            int bestValue = Integer.MIN_VALUE;
            for(Board b : simulatePossibleMoves(copyBoard,mySymbol)){
                int value = minimax(b,false,switchSymbol(mySymbol));
                if(bestValue < value){
                    bestValue = value;
                }
            }
            return bestValue;
        }
        else{
            int bestValue = Integer.MAX_VALUE;
            for(Board b: simulatePossibleMoves(copyBoard, switchSymbol(mySymbol))){
                int value = minimax(b,true,mySymbol);
                if(bestValue > value){
                    bestValue = value;
                }
            }
            return bestValue;
        }
    }