为什么我的 Minimax 算法没有产生正确的移动？

Question

算法运行很好，没有任何错误，但 AI 一点也不聪明，似乎在随机移动。我已经为此工作了两天，无法弄清楚我哪里出错了。有人可以帮忙找到导致它无法采取正确行动的错误吗？

开始游戏时，AI 应该总是在索引 4（中间方块）处移动，除非我占据那个位置，但它没有这样做，而且它根本不会尝试取胜。

$(document).ready(function() {

let X = {
    isComputer: false,
    symbol: "x",
    marker: "<img src='img/x.png'>",
    winMarker: "<img src='img/xWin.png'>"
}
let O = {
    isComputer: false,
    symbol: "o",
    marker: "<img src='img/o.png'>",
    winMarker: "<img src='img/oWin.png'>"
}
let game = {
    board: [0,1,2,3,4,5,6,7,8],
    firstTurn: X,
    xScore: 0,
    oScore: 0,
    turnNumber: 0,
    started: false
}
let winningCombos = [
    [0,1,2], [3,4,5], [6,7,8],
    [0,3,6], [1,4,7], [2,5,8],
    [0,4,8], [2,4,6]
];
let theWinningCombo;
let player = X;
let clearBoardTimeoutID;
let ai1;
let ai2;

function clearBoardForNextGame() {

    clearBoardTimeoutID = 
    setTimeout(function() {
        $('.square').empty();
        game.firstTurn = game.firstTurn == X ? O : X;
        game.turnNumber = 0;
        game.board = [0,1,2,3,4,5,6,7,8];
        game.started = true;
    }, 1500);
}

function thisPlayerWon(board, symbol) {
    for (let i = 0; i < winningCombos.length; i++) {
        let counter = 0;
        for (let j = 0; j < winningCombos[i].length; j++) {
            if (board[winningCombos[i][j]] == symbol) {
                counter++;
            }
            if (counter == 3) {
                theWinningCombo = winningCombos[i];
                return true;
            }
        }
    }
    return false;
}

function showWinnerAndUpdateScore(combo, player) {
    game.started = false;
    combo.forEach(index => $('#' + index).html(player.winMarker));
    player == X ? (game.xScore++, $('#score1').text(game.xScore)) : (game.oScore++, $('#score2').text(game.oScore))
}

function AImove(AIplayer, board) {
    AIplayer = !(game.turnNumber % 2) ? game.firstTurn : (game.firstTurn == X ? O : X);
    let opponent = AIplayer == X ? O : X;

    let bestMove = minimax(AIplayer, board, 0);

    board[bestMove] = AIplayer.symbol;
    $('#' + bestMove).html(AIplayer.marker);
    game.turnNumber++;

    function minimax(player, board, depth) {

        let spotsNotMarked = emptyBoardSpots(board);

        if (thisPlayerWon(board, AIplayer.symbol)) {
            return 10-depth;
        }
        else if (thisPlayerWon(board, opponent.symbol)) {
            return depth-10;
        }
        else if (spotsNotMarked.length == 0) {
            return 0;
        }

        let moves = [];
        let scores = [];

        for (let i = 0; i < spotsNotMarked.length; i++) {

            let index = spotsNotMarked[i];

            let score;

            board[index] = player.symbol;

            if (player == X) {
                score = minimax(O, board, depth+1);
            }
            else {
                score = minimax(X, board, depth+1);
            }

            scores.push(score);

            board[index] = index;

            moves.push(index);
        }

        if (player == AIplayer) {
            return moves[scores.indexOf(Math.max(...scores))];
        }
        else {
            return moves[scores.indexOf(Math.min(...scores))];
        }
    }
}

function emptyBoardSpots(board) {
    return board.filter(square => !isNaN(square));
}

$('.AI-Switch').on('change', function() {
    if (!game.started) {
        this.id == "one" ? (X.isComputer = !(X.isComputer), ai1 = X) : (O.isComputer = !(O.isComputer), ai2 = O);
    }
});

$('#resetButton').on('click', function() {
    clearTimeout(clearBoardTimeoutID);
    $('.square').empty();
    $('.scores').text("0");
    game.board = [0,1,2,3,4,5,6,7,8];
    game.firstTurn = X;
    game.xScore = 0;
    game.oScore = 0;
    game.turnNumber = 0;
    game.started = false;
});

$('#startButton').on('click', function() {
    game.started = true;
});

$('.square').on('click', function() {
    if (game.started && !isNaN(game.board[this.id])) {

        player = !(game.turnNumber % 2) ? game.firstTurn : (game.firstTurn == X ? O : X);

        this.innerHTML = player.marker;
        game.board[this.id] = player.symbol;

        game.turnNumber++;

        if (game.turnNumber > 3 && thisPlayerWon(game.board, player.symbol)) {

            showWinnerAndUpdateScore(theWinningCombo, player);

            clearBoardForNextGame();
        }
        else if (game.turnNumber == 9) {
            clearBoardForNextGame();
        }

        if (O.isComputer && player == X) {
            AImove(player, game.board);
        }
        else if (X.isComputer && player == O) {
            AImove(player, game.board);
        }
    }
});
});

Answer 1

问题是 minimax 的 return 值：是得分还是移动？

问题

你认为递归调用应该 return 得分，除了第一次调用应该 return 移动。这确实很方便，但实际情况并非如此：

只有当检测到获胜或平局时，函数return才会得分
在 all (!) 其他情况下，着手是 returned

这意味着在递归树的中途（还没有到达叶节点），您也正在向后移动，...但是您将它们视为递归树中上一级的得分。显然，这会使任何结果变得毫无意义。

解决方案

让您的 minimax 函数 return 得分，但同时也移动（相关时）。这可以通过 return 使用这两条信息对对象进行处理来实现。

这是您的 AImove 函数，只需进行一些修改即可实现该想法。修改后的行标记为***:

function AImove(AIplayer, board) {
    AIplayer = !(game.turnNumber % 2) ? game.firstTurn : (game.firstTurn == X ? O : X);
    let opponent = AIplayer == X ? O : X;
    let bestMove = minimax(AIplayer, board, 0).move; // *** Get move part of return value
    board[bestMove] = AIplayer.symbol;
    $('#' + bestMove).html(AIplayer.marker);
    game.turnNumber++;

    function minimax(player, board, depth) {
        if (depth===2) console.log('step');
        let spotsNotMarked = emptyBoardSpots(board);
        if (thisPlayerWon(board, AIplayer.symbol)) {
            return { score: 10-depth }; // *** Object with score (there's no move)
        }
        else if (thisPlayerWon(board, opponent.symbol)) {
            return { score: depth-10 }; // *** idem
        }
        else if (spotsNotMarked.length == 0) {
            return { score: 0 }; // *** idem
        }
        let moves = [];
        let scores = [];
        for (let i = 0; i < spotsNotMarked.length; i++) {
            let index = spotsNotMarked[i];
            let score;
            board[index] = player.symbol;
            if (player == X) {
                score = minimax(O, board, depth+1).score; // *** Get score part
            }
            else {
                score = minimax(X, board, depth+1).score; // *** idem
            }
            scores.push(score);
            board[index] = index;
            moves.push(index);
        }

        let score = (player == AIplayer ? Math.max : Math.min)(...scores); // *** Get score
        return { score, move: moves[scores.indexOf(score)] }; // *** Return both move & score
    }
}

为什么我的 Minimax 算法没有产生正确的移动？

Why is my Minimax algorithm not producing correct moves?

javascript

algorithm

minimax

问题

解决方案