Minimax algorithm still does play optimal moves in a tic-tac-toe game

Question

I implemented minimax with alpha-beta pruning for a tic-tac-toe game. This is the code:

This function returns if there are any more moves left.

bool isMovesLeft()
{
    for (int x = 0; x < ROWS; x++)
        for (int y = 0; y < COLS; y++)
            if (game.Board[x][y] == EMPTY)
                return true;

    return false;
}

Evaluates the board and returns the score. Possible outcomes: -10, 0, +10.

int evaluateBoard()
{
    for (int x = 0; x < ROWS; x++)
    {
        if (game.Board[x][0] == game.Board[x][1] &&
            game.Board[x][1] == game.Board[x][2])
        {
            if (game.Board[x][0] == PLAYER_X)
                return 10;
            else if (game.Board[x][0] == PLAYER_O)
                return -10;
        }
    }

    for (int y = 0; y < COLS; y++)
    {
        if (game.Board[0][y] == game.Board[1][y] &&
            game.Board[1][y] == game.Board[2][y])
        {
            if (game.Board[0][y] == PLAYER_X)
                return 10;
            else if (game.Board[0][y] == PLAYER_O)
                return -10;
        }
    }

    if (game.Board[0][0] == game.Board[1][1] &&
        game.Board[1][1] == game.Board[2][2])
    {
        if (game.Board[0][0] == PLAYER_X)
            return 10;
        else if (game.Board[0][0] == PLAYER_O)
            return -10;
    }

    if (game.Board[0][2] == game.Board[1][1] &&
        game.Board[1][1] == game.Board[2][0])
    {
        if (game.Board[0][2] == PLAYER_X)
            return 10;
        else if (game.Board[0][2] == PLAYER_O)
            return -10;
    }

    return 0;
}

The actual minimax algorithm with alpha-beta pruning:

int minimax(int depth, int alpha, int beta, bool isMax)
{
    int score = evaluateBoard();

    if (score == 10)
        return 10 - depth;

    if (score == -10)
        return -10 + depth;

    if (!isMovesLeft())
        return 0;

    if (isMax)
    {
        int best = -1000;

        for (int x = 0; x < ROWS; x++)
        {
            for (int y = 0; y < COLS; y++)
            {
                if (game.Board[x][y] == EMPTY)
                {
                    game.Board[x][y] = PLAYER_X;

                    int max = minimax(depth + 1, alpha, beta, !isMax);
                    if (max > best)
                        best = max;

                    if (best > alpha)
                        alpha = best;

                    game.Board[x][y] = EMPTY;

                    if (beta <= alpha)
                        break;
                }
            }
        }

        return best;
    }
    else if (!isMax)
    {
        int best = 1000;

        for (int x = 0; x < ROWS; x++)
        {
            for (int y = 0; y < COLS; y++)
            {
                if (game.Board[x][y] == EMPTY)
                {
                    game.Board[x][y] = PLAYER_O;

                    int min = minimax(depth + 1,alpha, beta, isMax);
                    if (min < best)
                        best = min;

                    if (best < beta)
                        beta = best;

                    game.Board[x][y] = EMPTY;

                    if (beta <= alpha)
                        break;
                }
            }
        }

        return best;
    }
}

Returns the best move. Called when it is the opponent's turn.

BestMove findBestMove()
{
    int bestScore = -1000;

    BestMove bestMove;
    bestMove.Row = -1;
    bestMove.Col = -1;

    if (game.Board[1][1] == EMPTY)
    {
        bestMove.Row = 1;
        bestMove.Col = 1;
        return bestMove;
    }

    for (int x = 0; x < ROWS; x++)
    {
        for (int y = 0; y < COLS; y++)
        {
            if (game.Board[x][y] == EMPTY)
            {
                game.Board[x][y] = PLAYER_X;

                int score = minimax(0, -10000000000, 10000000000, false);

                game.Board[x][y] = EMPTY;

                if (score > bestScore)
                {
                    bestScore = score;
                    bestMove.Row = x;
                    bestMove.Col = y;
                }
            }
        }
    }

    return bestMove;
}

I've also added the depth when calculating the score (in the minimax function) to make the AI slightly more intelligent.

However, the AI still plays silly moves and is quite easily beatable. Some wins are repeated over and over again.

Is the above code correct or am I missing something?

Answer 1

The problem is caused by a wrong value for isMax. In the main else block of the minimise function, the recursive call is made by passing isMax, but this means the recursive call will get the same value for isMax as the current call. This is wrong. It should toggle that value. Either pass !isMax, or just pass a hard-coded true, since here isMax is false.