Minimax Tic-Tac-Toe issue;

Question

I'm currently making a Tic-Tac-Toe game and trying to implement the minimax ai for it. Everything is working fine if the ai is going first and the player is going second, but if ai is second it just goes in a pattern [0][0] => [0][1] => [0][2] etc. If the human already filled this pattern it just skips over and continues the same sequence. I am pretty new to this kind of stuff and been struggling with it for a while to get it up to this point. Would appreciate some advice;

function eveluateMove(board) {
    for (let row = 0; row < board.length; row += 1) {
        if (board[row][0] === board[row][1] && board[row][1] === board[row][2]) {
            if (board[row][0] === 1) {
                return +10;
            } if (board[row][0] === 2) {
                return -10;
            }
        }
    }

    for (let column = 0; column < board.length; column += 1) {
        if (board[0][column] === board[1][column] && board[1][column] === board[2][column]) {
            if (board[0][column] === 1) {
                return +10;
            } if (board[0][column] === 2) {
                return -10;
            }
        }
    }

    if (board[0][0] === board[1][1] && board[1][1] === board[2][2]) {
        if (board[0][0] === 1) {
            return +10;
        } if (board[0][0] === 2) {
            return -10;
        }
    }
    if (board[0][2] === board[1][1] && board[1][1] === board[2][0]) {
        if (board[0][2] === 1) {
            return +10;
        } if (board[0][2] === 2) {
            return -10;
        }
    } return 0;
}

function minimax(board, depth, isMaximizer) {
    const score = eveluateMove(board);

    if (score === 10) {
        return score;
    }
    if (score === -10) {
        return score;
    }

    if (isMovesLeft() === false) {
        return 0;
    }

    if (isMaximizer) {
        let best = -1000;

        for (let row = 0; row < board.length; row += 1) {
            for (let column = 0; column < board.length; column += 1) {
                if (board[row][column] === 0) {
                    board[row][column] = 1;
                    best = Math.max(best, minimax(board, depth + 1, false));
                    board[row][column] = 0;
                }
            }
        } return best;
    }

    if (!isMaximizer) {
        let best = 1000;

        for (let row = 0; row < board.length; row += 1) {
            for (let column = 0; column < board.length; column += 1) {
                if (board[row][column] === 0) {
                    board[row][column] = 2;
                    best = Math.min(best, minimax(board, depth + 1, true));
                    board[row][column] = 0;
                }
            }
        } return best;
    }
}

const makeMove = (row, column) => ({ row, column });

function findBestMove(board) {
    let bestValue = -Infinity;
    const bestMove = makeMove;
    bestMove.row = -1;
    bestMove.column = -1;

    for (let row = 0; row < board.length; row += 1) {
        for (let column = 0; column < board.length; column += 1) {
            if (board[row][column] === 0 && aiWeapon === 1) {
                board[row][column] = aiWeapon;
                const moveValue = minimax(board, 0, false);
                board[row][column] = 0;
                if (moveValue > bestValue) {
                    bestMove.row = row;
                    bestMove.column = column;
                    bestValue = moveValue;
                }
            } if (board[row][column] === 0 && aiWeapon === 2) {
                board[row][column] = aiWeapon;
                const moveValue = minimax(board, 0, true);
                board[row][column] = 0;
                if (moveValue > bestValue) {
                    bestMove.row = row;
                    bestMove.column = column;
                    bestValue = moveValue;
                }
            }
        }
    } return bestMove;
}

function isMovesLeft() {
    let movesAvailable = true;
    const movesLeftR1 = board[0].every((value) => value > 0);
    const movesLeftR2 = board[1].every((value) => value > 0);
    const movesLeftR3 = board[2].every((value) => value > 0);
    if (movesLeftR1 === true && movesLeftR2 === true && movesLeftR3 === true) {
        movesAvailable = false;
    } return movesAvailable;
}

I am assuming that the issue is with the function findBestMove, since the minimax and the evaluation parts have to be running correctly for it to work in a situation where the ai makes the first move.

I've tried changing values from the call moveValue = minimax(board, 0, true); but that seems to have no effect.

Other than that I can't seem to put my finger on it, it has to be something with this one line in my head maybe I'm not seeing something.

Answer 1

There is at least one problem in findBestMove, where your code is maximizing the value even when the AI player is the second player. But in that case the algorithm should minimize the value, as the second player wants the least possible value.

So make this change:

function findBestMove(board) {
    let bestValue = aiWeapon === 1 ? -Infinity : +Infinity; // <---
    const bestMove = makeMove;
    bestMove.row = -1;
    bestMove.column = -1;

    for (let row = 0; row < board.length; row += 1) {
        for (let column = 0; column < board.length; column += 1) {
            if (board[row][column] === 0 && aiWeapon === 1) {
                board[row][column] = aiWeapon;
                const moveValue = minimax(board, 0, false);
                board[row][column] = 0;
                if (moveValue > bestValue) {
                    bestMove.row = row;
                    bestMove.column = column;
                    bestValue = moveValue;
                }
            }
            if (board[row][column] === 0 && aiWeapon === 2) {
                board[row][column] = aiWeapon;
                const moveValue = minimax(board, 0, true);
                board[row][column] = 0;
                if (moveValue < bestValue) {  // <---
                    bestMove.row = row;
                    bestMove.column = column;
                    bestValue = moveValue;
                }
            }
        }
    }
    return bestMove;
}

There is quite some code repetition in your code. Like for instance the above two if blocks could be merged into one...

For reference, some time ago I posted a JavaScript implementation to a similar question. It uses much less code.