TicTacToe MinMax logic problem, why does the method return the wrong move?

Question

MinMax algo returns a completely illogical move (does not counter player) >.<

Hey,

I have some logic error in the getBestMove method of MinMax class implementation. I think everything looks ok.

I do a test in GameRunner and it takes the correct board, but returns a completely illogical move (does not counter player).

public class MinMax3x3 {

    public int[] getBestMove(char[][] board) {
        char computerSymbol = Symbol.X;
        int bestScore = Integer.MIN_VALUE;
        int row = -1;
        int col = -1;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == Symbol.EMPTY_FIELD) {
                    board[i][j] = computerSymbol;
                    int score = minimax(board, 0, false);
                    board[i][j] = Symbol.EMPTY_FIELD;
                    if (score > bestScore) {
                        bestScore = score;
                        row = i;
                        col = j;
                    }
                }
            }
        }
        int[] bestMove = {row, col};
        return bestMove;
    }

    public int minimax(char[][] board, int depth, boolean isMaximizing) {
        char playerSymbol = Symbol.O;
        char computerSymbol = Symbol.X;
        int result = analyze3x3(board, playerSymbol, computerSymbol);

        if (result != 0) {
            return result;
        }

        if (isMaximizing) {
            int bestScore = Integer.MIN_VALUE;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (board[i][j] == Symbol.EMPTY_FIELD) {
                        board[i][j] = computerSymbol;
                        int score = minimax(board, depth + 1, false);
                        board[i][j] = Symbol.EMPTY_FIELD;
                        bestScore = Math.max(score, bestScore);
                    }
                }
            }
            return bestScore;
        } else {
            int bestScore = Integer.MAX_VALUE;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (board[i][j] == Symbol.EMPTY_FIELD) {
                        board[i][j] = playerSymbol;
                        int score = minimax(board, depth + 1, true);
                        board[i][j] = Symbol.EMPTY_FIELD;
                        bestScore = Math.min(score, bestScore);
                    }
                }
            }
            return bestScore;
        }
    }

    private int analyze3x3(char[][] board, char playerSymbol, char computerSymbol) {
        // Check rows
        for (int row = 0; row < 3; row++) {
            if (board[row][0] == playerSymbol && board[row][1] == playerSymbol && board[row][2] == playerSymbol) {
                return 1; // Player wins
            } else if (board[row][0] == computerSymbol && board[row][1] == computerSymbol && board[row][2] == computerSymbol) {
                return -1; // Computer wins
            }
        }

        // Check columns
        for (int column = 0; column < 3; column++) {
            if (board[0][column] == playerSymbol && board[1][column] == playerSymbol && board[2][column] == playerSymbol) {
                return 1; // Player wins
            } else if (board[0][column] == computerSymbol && board[1][column] == computerSymbol && board[2][column] == computerSymbol) {
                return -1; // Computer wins
            }
        }

        // Check diagonals
        if ((board[0][0] == playerSymbol && board[1][1] == playerSymbol && board[2][2] == playerSymbol) ||
                (board[0][2] == playerSymbol && board[1][1] == playerSymbol && board[2][0] == playerSymbol)) {
            return 1; // Player wins
        } else if ((board[0][0] == computerSymbol && board[1][1] == computerSymbol && board[2][2] == computerSymbol) ||
                (board[0][2] == computerSymbol && board[1][1] == computerSymbol && board[2][0] == computerSymbol)) {
            return -1; // Computer wins
        }

        // It's a draw
        return 0;
    }

}


public class GameRunner {
    public static void main(String[] args) {

        char board[][] = {{'x', 'o', ' '},
                          {' ', 'o', ' '},
                          {' ', ' ', ' '}};

        MinMax3x3 bestMove = new MinMax3x3();
        int[] lol = bestMove.getBestMove(board);
        System.out.printf(lol[0] + ", " + lol[1]);

Result lol: [0,2] / should be lol: [2,1]. Something is wrong, I check in debugger, the board is passed correctly.

Answer 1

There are two issues:

1. Your analyze3x3 returns a value that assumes that the human player is the maximizing player and the computer is the minimizing player. But this is opposite to how you have defined the other functions, where the computer is the maximizing player. So in analyze3x3 change all return 1; with return -1; and vice versa.

2. There is no explicit verification for a draw. Although there is a code comment in analyze3x3 that says "It's a draw", this is actually not true: that return 0; only means that the game is not won, but there is no verification whether the game is over without a winner. What happens is that the minimax algorithm continues until there are no more moves, and when this is the case it will return MAX_VALUE or MIN_VALUE (depending on the player that started the game). Neither is a good return value. In that case 0 should be returned to really indicate a draw. You can fix this in minimax by changing the two occurrences of return bestScore; to:

   return bestScore == Integer.MIN_VALUE ? 0 : bestScore;
   

   and

   return bestScore == Integer.MAX_VALUE ? 0 : bestScore;
   

With those two fixes it should work.