Блог

Я пытаюсь сделать крестики-нолики в JavaScript, используя минимаксный алгоритм, но кажется, что я делаю что-то не так, и минимаксный алгоритм не определяет лучший ход. Вот код:

 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] amp;amp; sqBoard[a] === sqBoard[b] amp;amp; 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));
  

В приведенном выше условии лучшим ходом было бы остановить X, чтобы выиграть, заполнив доску [3] буквой «O», но он всегда обнаруживает другой ход с более высоким счетом.

Кто-нибудь может помочь мне понять, что происходит не так с моим кодом?

Спасибо.

Из вашего кода я понимаю, что X — это минимизирующий, а O — максимизирующий игрок. Но затем я вижу этот код:

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

Поэтому после перемещения O вы вызываете minimax с isMaximizer установленным значением true . Но это заставит minimax сыграть еще один ход O, в то время как O уже сыграл. Вы хотите получить лучший ответный ход для X, поэтому вы должны пройти false здесь:

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

Теперь это вернет -10 для каждого такого вызова (то есть для каждого хода O), потому что игра уже находится в проигранном состоянии для O, что бы он ни делал, X выиграет. Если O движется на 3, то X сыграет 2 с двойной атакой.

Если вы хотите различать быстрые и медленные выигрыши, вам следует корректировать счет при каждом возврате.

Например, вы можете заменить return bestScore оператор возвращением значения, которое на единицу ближе к нулю. Так, например, -10 становится -9, а 5 становится 4, а 0 остается 0:

     return bestScore - Math.sign(bestScore);
  

С этим изменением O будет играть на 3, так как его счет равен -7 (все еще проигрывает), в то время как другой перемещает все очки -9 (проигрывая сразу с одним ходом от X).