What's wrong with my Tic Tac Toe AI?

Question

I read a tutorial about minimax, and tried to make a tac tac toe AI. But the code doesn't work optimally for some reason, which I cannot find. The ai can place pieces, but it's not a smart ai. I expected it to be unbeatable. The higher the depth is, the dumber the ai becomes. The 'game' is my an other class, where the actual game is.

private Game game;
private Piece[][] board;
private Piece ai = Piece.CIRCLE;
private Piece player = Piece.CROSS;

public AI(Game game) {
    this.game = game;
    this.board = game.getBoard();

}

public int[] move() {
    int[] result = minimax(1, ai);

    return new int[] {result[1], result[2]};
}

private int[] minimax(int depth, Piece piece) {
    List<int[]> possibleMoves = generateMoves();

    int bestScore = (piece == ai) ? Integer.MIN_VALUE : Integer.MAX_VALUE;
    int currentScore;
    int bestRow = -1;
    int bestCol = -1;

    if (possibleMoves.isEmpty() || depth == 0) {
        // Game over or depth reached
        bestScore = evaluate();
    }
    else {
        for (int[] move : possibleMoves) {
            // Try this move for the player
            board[move[0]][move[1]] = player;
            if (piece == ai) { // ai is maximizing player
                currentScore = minimax(depth - 1, player)[0];

                if (currentScore > bestScore) {
                    bestScore = currentScore;
                    bestRow = move[0];
                    bestCol = move[1];
                }
            }
            else { // player is minimizing player
                currentScore = minimax(depth - 1, ai)[0];

                if (currentScore < bestScore) {
                    bestScore = currentScore;
                    bestRow = move[0];
                    bestCol = move[1];
                }
            }

            // Undo move
            board[move[0]][move[1]] = null;
        }
    }

    return new int[] {bestScore, bestRow, bestCol};
}

private List<int[]> generateMoves() {
    List<int[]> possibleMoves = new ArrayList<int[]>();

    // If game over
    if (game.getWinner() != null) {
        return possibleMoves; // return empty list
    }

    // Add possible moves to list
    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            if (game.getBoard()[x][y] == null) {
                possibleMoves.add(new int[] {x, y});
            }
        }
    }

    return possibleMoves;
}

private int evaluate() {        
    int score = 0;
    // Evaluate
    score += evaluateLine(0, 0, 0, 1, 0, 2); // row 0
    score += evaluateLine(1, 0, 1, 1, 1, 2); // row 1
    score += evaluateLine(2, 0, 2, 1, 2, 2); // row 2
    score += evaluateLine(0, 0, 1, 0, 2, 0); // col 0
    score += evaluateLine(0, 1, 1, 1, 2, 1); // col 0
    score += evaluateLine(0, 2, 1, 2, 2, 2); // col 0
    score += evaluateLine(0, 0, 1, 1, 2, 2); // diag 1
    score += evaluateLine(0, 2, 1, 1, 2, 0); // diag 2

    return score;
}

// Return +100, +10, +1 for 3-, 2-, 1-in-a-line for ai
// Return -100, -10, -1 for 3-, 2-, 1-in a line for player
// Else return 0
private int evaluateLine(int row1, int col1, int row2, int col2, int row3, int col3) {
    int score = 0;

    // First cell
    if (board[row1][col1] == ai) {
        score = 1;
    }
    else if (board[row1][col1] == player) {
        score = -1;
    }

    // Second cell
    if (board[row2][col2] == ai) {
        if (score == 1) { // board1 is ai
            score = 10;
        }
        else if (score == -1) { // board1 is player
            return 0;
        }
        else { // board1 is empty
            score = 1;
        }
    }
    else if (board[row2][col2] == player) {
        if (score == -1) { // board1 is player
            score = -10;
        }
        else if (score == 1) { // board1 is ai
            return 0;
        }
        else { // board1 is empty
            score = -1;
        }
    }

    // Third cell
    if (board[row3][col3] == ai) {
        if (score > 0) { // board1 and/or board2 is ai
            score *= 10;
        }
        else if (score < 0) { // board1 and/or board2 is player
            return 0;
        }
        else { // board1 and/or board2 is empty
            score = 1;
        }
    }
    else if (board[row3][col3] == player) {
        if (score < 0) { // board1 and/or board2 is player
            score *= 10;
        }
        else if (score > 1) { // board1 and/or board2 is ai
            return 0;
        }
        else { // board1 and/or board2 is empty
            score = -1;
        }
    }

    return score;
}

Answer 1

minimax is returning a move in terms of a row/column pair, not a score. So

currentScore = minimax(depth - 1, player)[0];

makes no sense. It probably causes any move to row 3 to look better than any move to row 1 or row 2.

minmax needs to hand
back a score in addition to the best move.

Answer 2

A couple of things I noticed:

• The first line in the loop going through possible moves says board[move[0]][move[1]] = player;. That should be piece instead of player, now your AI thinks that only pieces of the human player ever end up on the board.
• Minimax should be very easily capable of searching the complete game tree in less than a second. Therefore, I'd recommend allowing to to search as deep as it likes, instead of limiting to a search depth of 1. This would also eliminate the need for creating that heuristic evaluation function; you'd only give a large score for winning, 0 for tie, and a very negative score for losing. The main reason I'm recommending this is that I suspect there may be something wrong with the evaluation function too, though I'm not sure since I did not check it in detail. If you really do insist on terminating the search early and using a heuristic evaluation function, you need to make sure that the function is ''symmetrical''. With that, I mean that evaluating the board from the perspective of one player should always result in exactly -1 times the score of the same board were evaluated from the perspective of the opponent.