minimax algorithm in javaScript is not working as expected and returns the wrong move

Question

I'm trying to make a Tic-Tac-Toe in javaScript using minimax algorithm but it seems that I'm doing something wrong and minimax algorithm, is not detecting the best move. Here is the code:

const board = ["X", null, null, null, null, "X", "X", "O", "O"];
/*
    X   _   _
    _   _   X
    X   O   O

*/

// duplicate passed board and return the new board state
const makeAIMove = (currentBoard, square, player) => {
    const nextBoard = [...currentBoard];
    nextBoard[square] = player;
    return nextBoard;
};

// find empty squares
const emptySquares = (sqBoard) =>
    sqBoard
        .map((sq, idx) => (sq === null ? idx : null))
        .filter((sq) => sq !== null);

// check if no empty squares are available
const isFinished = (sqBoard) => (emptySquares(sqBoard).length ? false : true);

// check winner
const checkWinner = (sqBoard) => {
    const winConditions = [
        [0, 1, 2],
        [3, 4, 5],
        [6, 7, 8],
        [0, 3, 6],
        [1, 4, 7],
        [2, 5, 8],
        [0, 4, 8],
        [2, 4, 6],
    ];

    for (const winCondition of winConditions) {
        [a, b, c] = winCondition;
        if (sqBoard[a] && sqBoard[a] === sqBoard[b] && sqBoard[a] === sqBoard[c])
            return sqBoard[a];
    }

    return false;
};

// minimax algorithm
const minimax = (sqBoard, depth, isMaximizer) => {
    // terminal checker
    const theWinner = checkWinner(sqBoard);
    // we have a winner
    if (theWinner) {
        return theWinner === "X" ? -10 : 10;
    }
    // it's a tie
    if (isFinished(sqBoard)) {
        return 0;
    }

    let bestScore;
    if (isMaximizer) {
        bestScore = -1000;
        emptySquares(sqBoard).forEach((square) => {
            // make a sample move
            let nextBoard = makeAIMove(sqBoard, square, "O");

            // recursion
            let score = minimax(nextBoard, depth + 1, false);
            bestScore = Math.max(bestScore, score);
        });
    } else {
        bestScore = 1000;
        emptySquares(sqBoard).forEach((square) => {
            let nextBoard = makeAIMove(sqBoard, square, "X");
            let score = minimax(nextBoard, depth + 1, true);
            bestScore = Math.min(bestScore, score);
        });
    }
    return bestScore;
};

// find the best move
const nextBestMove = (sqBoard) => {
    let nextMoveArray = [];
    let remainedSquares = emptySquares(sqBoard);
    remainedSquares.forEach((square) => {
        let nextBoard = makeAIMove(sqBoard, square, "O");
        let theScore = minimax(nextBoard, 0, true);
        nextMoveArray.push({
            sq: square,
            sc: theScore,
        });
    });

    nextMoveSorted = nextMoveArray.sort((a, b) => (a.sc < b.sc ? 1 : -1));
    return nextMoveSorted[0].sq;
};

console.log(nextBestMove(board));

In the above condition, the best move would be stopping X to win by filling the board[3] with an "O" but it always detects another move that has a higher score.

Can anyone help me to understand what's going wrong with my code?

Thank you.

Answer 1

From your code I understand that X is the minimizing and O the maximizing player. But then I see this code:

    let nextBoard = makeAIMove(sqBoard, square, "O");
    let theScore = minimax(nextBoard, 0, true);

So after O has moved, you call minimax with isMaximizer set to true. But this will make minimax play another O move, while O has already played. You want to get the best reply move for X, so you should pass false here:

    let theScore = minimax(nextBoard, 0, false);

Now, this will return -10 for every such call (so for every move of O), because the game is already in a lost state for O, whatever it does, X will win. If O moves at 3, then X will play 2 with a double attack.

If you want to differentiate between quick wins and slower wins, then you should adapt the score at each backtracking.

For instance, you could replace the return bestScore statement with a return of a value that is one unit closer to zero. So for example -10 becomes -9 and 5 becomes 4, and 0 remains 0:

    return bestScore - Math.sign(bestScore);

With this change, O will play at 3, as its score is -7 (still losing), while the other moves all score -9 (losing immediately with one move from X).