javascript - 有人可以解释极小极大井字游戏算法吗

Question

我正在研究 tic tac toe(用户与计算机)的 AI，我正在使用 minimax 算法来实现计算机的最佳着法。我看过 youtube 上的一些视频，并阅读了一些人的代码。但是，有些代码我仍然对正在做的事情感到困惑。让我们以 tic tac toe minimax 函数中的以下代码为例。有一个主要的 if、else if、else 语句，其他所有内容都来自那里。我的主要问题是理解嵌入式 for 循环，以及后面的 2 个 ifs。我对我认为正在做的事情发表了一些评论。我从这个 youtube 视频中获取了示例代码:https://www.youtube.com/watch?v=x_Je9i3aKNk 井字游戏的极小极大函数。

//minimax function
function minimax(newGrid, depth, player) {
    const gameState = isGameOver(newGrid);
    //if the game is not over, evalute best move for computer
    if(gameState === false) {
        const values = [];

        for(var i = 0; i < 3; i++) {
            for(var j = 0; j < 3; j++) {
                const gridCopy = _.cloneDeep(newGrid);
                //if that spot is taken, skip to next loop
                if(gridCopy[i][j] !== ' ') continue;
                //if spot is player, evaluate
                gridCopy[i][j] = player;
                //need clarification
                const value = minimax(gridCopy, depth+1, (player == PLAYER_TOKEN) ? COMPUTER_TOKEN : PLAYER_TOKEN);
                values.push(value);
            }
        }
        //need clarification for computer turn
        if(player === COMPUTER_TOKEN) {
            const max = _.maxBy(value, (v) => {
                return v.cost;
            });
            if(depth === 0) {
                return max.cell;
            }
            else {
                return max.cost;
            }
        //need clarification for user turn
        else {
            const min = _.minBy(value, (v) => {
                return v.cost;
            });
            if(depth === 0) {
                return v.cell;
            }
            else {
                return v.cost;
            }
        }

    //if game state is null return 0
    else if (gameState === null) {
        return 0;
    }
    //if game state is player return negative
    else if(gameState === PLAYER_TOKEN) {
        return depth - 10;
    }
    //if game state is computer return positive
    else if(gameState === COMPUTER_TOKEN) {
        return 10 - depth;
    }
}

Answer 1

Minimax 算法的关键是两个玩家之间的来回，“轮到”的玩家希望选择得分最高的着法。反过来，每个可用 Action 的得分由对方玩家决定其可用 Action 中哪个得分最低。对方玩家移动的分数再次由试图最大化其分数的轮流玩家决定，依此类推，一直沿移动树向下直到结束状态。

算法的描述，假设 X 是“轮到玩家”，看起来像这样:

• 如果游戏结束，从X的 Angular 返回分数。
• 否则获取每一步可能的新游戏状态列表
• 创建分数列表
• 对于这些状态中的每一个，将该状态的极小极大结果添加到分数列表中
• 如果轮到 X，返回分数列表中的最大分数
• 如果轮到 O，返回分数列表中的最小分数

您会注意到该算法是递归的，它在玩家之间来回翻转，直到找到最终分数。

让我们通过完整的着法树来了解算法的执行过程，并说明为什么在算法上会选择即时获胜的着法:

• 轮到 X 进入状态 1。X 生成状态 2、3 和 4，并对这些状态调用 minimax。
• 状态 2 将 +10 的分数插入状态 1 的分数列表，因为游戏处于结束状态。
• 状态 3 和 4 不处于结束状态，因此 3 生成状态 5 和 6 并对它们调用 minimax，而状态 4 生成状态 7 和 8 并对其调用 minimax。
• 状态 5 将 -10 的分数插入状态 3 的分数列表，而状态 7 也会将 -10 的分数插入状态 4 的分数列表。
• 状态 6 和 8 生成唯一可用的移动，它们是结束状态，因此它们都将 +10 的分数添加到状态 3 和 4 的移动列表中。
• 因为在状态 3 和 4 中都轮到 O，O 将寻求找到 最低分数，并在 -10 和 +10 之间进行选择，这两个状态 3 和 4 将产生 -10。
• 最后，状态 2、3 和 4 的分数列表分别填充了 +10、-10 和 -10，寻求最大化分数的状态 1 将选择得分为 +10 的获胜着法，状态 2。

算法的更多细节和代码实现可以引用以下文章:

Tic Tac Toe: Understanding The Minimax Algorithm

online version tic tac toe

Source code on github

Reference: http://neverstopbuilding.com/minimax

Here is the presentation slide by us