极小极大算法指南：如何创建一个无敌的人工智能

最近我在想——我该如何编程让计算机在井字棋游戏中无敌？

我原以为可以很容易找到这个问题的答案。但当我在文章、视频和一系列编码冥想之间来回切换时，我只感到更加困惑。

然而，我的“恍然大悟”时刻出现在我花时间理解 极小极大算法 是如何工作的。

如果你也在走类似的道路，让我带你了解构建无敌人工智能（AI）的步骤。

步骤 1：了解 minimax 算法的基础知识

一个 minimax 算法 是一个 递归 程序，旨在找到最佳游戏策略，以最小化输掉游戏的倾向，同时最大化赢得游戏的机会。

从图形上看，我们可以将 minimax 表示为对 游戏树 的 节点 的探索，以发现最佳的游戏移动。在这种情况下，树的根是游戏的当前状态——minimax 算法被调用的地方。

图1：结束的井字游戏的游戏树

本指南的重点是使用极小极大算法为井字棋游戏创建一个无敌的人工智能。然而， 您也可以将其用于复杂的游戏 ，如国际象棋，以及一般决策以解决任何不确定性。

在大多数情况下，最初调用极小极大算法的玩家被称为 最大化玩家 。换句话说，最初调用极小极大算法的玩家是希望最大化赢得游戏机会的玩家。

相对而言，最大化玩家的对手被称为 最小化玩家 。因此，最小化玩家是那个必须最小化获胜机会的玩家。

简而言之，最小化最大化算法是一个递归函数，旨在帮助玩家（最大化者）决定一种 最小化 游戏中 最大 输掉可能性的游戏玩法。

步骤 2：熟悉本教程的根节点

为了使本教程更准确，我们将使用的根节点（井字棋游戏的当前状态）将是一个接近结束状态的游戏棋盘——如下图 2 所示。

此外， X 标记将代表 AI 的标记，而 O 标记将是人类玩家的标记。

图2：本教程的根节点

在当前的井字棋游戏阶段（如上图 2 所示），轮到 X 进行游戏（也就是 AI 的回合）。由于棋盘上有三个空格，这意味着 X 有三个可能的选择——上中、中心或下右。

但哪个是最佳选择？哪个动作最能帮助 X 最小化输掉比赛的最大可能性？

图 3：AI 玩家的可能出棋选择

为了做出最佳决策，AI 需要执行以下操作：

1. 将井字棋棋盘的当前状态（值）存储在一个数组中。（对于任何空单元格，该单元格的索引将作为其当前内容存储）。
2. 获取一个仅包含 空单元格 索引的数组列表。
3. 检查并确认特定玩家是否赢得了比赛。
4. 递归地 在棋盘的每个空单元格上调用 minimax 。
5. 为玩家 X 和玩家 O 的每个可能的移动返回一个分数。
6. 在所有返回的分数中，选择最佳的一个（最高的），以确保最小化人类玩家获胜的可能性。

因此，在下面的步骤中，我们将配置 AI 以完成上述列表。那么，让我们开始吧，首先将棋盘的当前状态存储在一个数组中。

步骤 3：将棋盘的当前状态存储在数组中

我们的下一步是将棋盘每个单元格的当前内容存储在一个数组中，如下所示：

const currentBoardState = ["X", 1, "O", "X", 4, "X", "O", "O", 8];

注意：

• 我们井字棋棋盘的当前状态仍如图2所示。
• 在 currentBoardState 数组中，值 1 、 4 和 8 是棋盘上空单元格的索引号。换句话说，我们选择将空单元格的当前内容存储为它们各自的索引，而不是使用空字符串。

重要的是，在进入下一步之前，让我们明确地定义谁的标记是 “X” ，谁拥有 “O” 。

const aiMark = "X";
const humanMark = "O";

上述两个陈述表示 AI 的标记是 X ，而人类玩家的标记是 O 。

步骤 4：创建一个函数以获取所有空单元格的索引

下面的函数将过滤 currentBoardState 数组——该数组将作为函数参数的参数传入。然后，它将返回一个新数组，包含所有既不是 “X” 也不是 “O” 的 currentBoardState 数组的项。

function getAllEmptyCellsIndexes(currBdSt) {
    return currBdSt.filter(i => i != "X" && i != "O");
}

注意： 请记住，我们在第 3 步中创建的 currentBoardState 数组仅包含值 “X” 、 “O” 和 棋盘空单元格的索引 。因此，上面的 getAllEmptyCellsIndexes() 函数会过滤掉 currentBoardState 数组中任何索引的出现。

第5步：创建一个赢家判定函数

下面的 赢家判定函数 的主要目的是接收一个 currentBoardState 数组和一个特定玩家的标记（可以是标记 “X” 或 “O” ）作为其参数的参数。

然后，它检查接收到的标记是否在井字棋棋盘上形成了获胜组合。如果是，则返回布尔值 true — 否则返回 false 。

function checkIfWinnerFound(currBdSt, currMark) {
    if (
        (currBdSt[0] === currMark && currBdSt[1] === currMark && currBdSt[2] === currMark) ||
        (currBdSt[3] === currMark && currBdSt[4] === currMark && currBdSt[5] === currMark) ||
        (currBdSt[6] === currMark && currBdSt[7] === currMark && currBdSt[8] === currMark) ||
        (currBdSt[0] === currMark && currBdSt[3] === currMark && currBdSt[6] === currMark) ||
        (currBdSt[1] === currMark && currBdSt[4] === currMark && currBdSt[7] === currMark) ||
        (currBdSt[2] === currMark && currBdSt[5] === currMark && currBdSt[8] === currMark) ||
        (currBdSt[0] === currMark && currBdSt[4] === currMark && currBdSt[8] === currMark) ||
        (currBdSt[2] === currMark && currBdSt[4] === currMark && currBdSt[6] === currMark)
    ) {
        return true;
    } else {
        return false;
    }
}

步骤 6：创建极小极大算法

一个 极小极大算法 只是一个普通的函数，包含在函数被调用时要执行的语句。因此，创建该算法的过程与创建任何其他函数是相同的。那么，让我们现在来创建一个。

function minimax(currBdSt, currMark) {

    // Space for the minimax’s statements 

}

就是这样！我们已经创建了一个 minimax 函数——尽管它是空的。我们的下一步是用将在函数被调用时执行的语句填充这个函数——我们将在下面进行。

注意： 上面创建的 minimax 函数旨在接受 两个参数 。
第一个是当前棋盘内容的 数组 列表——即 currentBoardState 数组的当前值。而第二个参数是当前运行极小极大算法的玩家的 标记 ——即标记 “X” 或标记 “O” 。

步骤 7：第一次调用 minimax

为了避免在本教程后续部分出现任何混淆，让我们第一次调用我们的 minimax 函数——同时传入 currentBoardState 数组和 aiMark 作为函数的参数。

const bestPlayInfo = minimax(currentBoardState, aiMark);

步骤8：存储所有空单元格的索引

在这一步，我们将调用在第 4 步创建的 getAllEmptyCellsIndexes 函数，并将 currentBoardState 数组作为函数的参数传入。

然后，我们将把返回的索引数组列表存储在一个名为 availCellsIndexes 的变量中。

const availCellsIndexes = getAllEmptyCellsIndexes(currBdSt);

步骤 9：检查是否存在终止状态

在这个阶段，我们需要验证井字棋棋盘上是否存在终局状态（即输局、赢局或平局）。我们将通过调用 赢家判定函数 （在第 5 步中创建）来完成对每个玩家的验证。

如果该函数发现人类玩家（最小化者）的赢局，它将返回 -1 （这表示人类玩家获胜，AI 失败）。但如果它发现 AI 玩家（最大化者）的赢局，它将返回 +1 （这表示 AI 获胜，人类玩家失败）。

然而，假设赢家判定函数无法在棋盘上找到任何空格或任何一方的胜利状态。在这种情况下，它将返回 0 （零）——这表示游戏以平局结束。

注意： 上述分数（ -1 、 +1 和 0 ）是 启发式 值——这意味着如果我们选择使用 -25、+25 和 0，结果仍然是相同的。

现在让我们通过使用一个 if 语句 来实现终端状态验证，如下所示：

if (checkIfWinnerFound(currBdSt, humanMark)) {
    return {score: -1};
} else if (checkIfWinnerFound(currBdSt, aiMark)) {
    return {score: 1};
} else if (availCellsIndexes.length === 0) {
    return {score: 0};
}

当出现终局状态（输、赢或平局）时，活动的最小最大函数将返回相应的终局状态分数（ -1 、 +1 或 0 ），并结束其调用。

如果活动的最小化极大值算法在此结束调用，算法将继续进行到第12步。

然而，当没有 终止 状态时，活动的最小化函数将执行下一条语句（步骤 10，如下所示）。

步骤10：准备测试在每个空单元格上放置当前玩家的标记的结果

由于第9步没有找到终止状态，我们必须想出一种方法来测试当前玩家（即将进行下一步游戏的玩家）在每个空单元格上进行操作时会发生什么。

换句话说，如果当前玩家在第一个可用的单元格上落子，而对手在第二个空单元格上落子，当前玩家会赢、输还是平局？或者仍然没有找到终局状态？

或者，如果当前玩家在第二个可用单元格上落子，而对手在第一个空单元格上落子，会发生什么？

或者，第三个可用的格子会是当前玩家下棋的最佳位置吗？

这次测试驱动是我们现在需要做的。但在我们开始之前，我们需要一个地方来记录每个测试的结果——所以我们先创建一个名为 allTestPlayInfos 的数组。

const allTestPlayInfos = [];

所以，现在我们已经为每个试驾的结果找到了存储位置，让我们通过创建一个 for 循环语句 来开始试验，从第一个空单元格开始循环。

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

    // Space for the for-loop’s codes

}

在接下来的两个步骤中，我们将为每个空单元格填充循环中应该运行的代码。

步骤 11：在 for 循环当前处理的空单元格上测试当前玩家的标记

在执行此步骤之前，让我们回顾一下当前棋盘的状态。

图4：井字棋盘的当前状态

请注意，上面的棋盘与图 2 中的棋盘是相同的，唯一的区别是我们用红色突出显示了当前 for 循环正在处理的单元格。

接下来，创建一个地方来存储这次测试游戏的终局得分将会很有帮助——所以我们来创建一个对象，如下所示：

const currentTestPlayInfo = {};

此外，在测试当前玩家的标记放置在红色单元格之前，让我们保存该单元格的索引号——这样在这次测试游戏后重置单元格的信息会很方便。

currentTestPlayInfo.index = currBdSt[availCellsIndexes[i]];

现在让我们在红色单元格上放置当前玩家的标记（也就是当前被 for 循环处理的单元格）。

currBdSt[availCellsIndexes[i]] = currMark;

根据当前玩家的游戏玩法，棋盘的状态将会改变，以反映其最新的移动。

图5：新的棋盘——反映当前玩家的最新移动

因此，由于棋盘的状态已经改变，我们需要在新的棋盘上递归地运行极小极大算法——同时传入新的棋盘状态和下一个玩家的标记。

if (currMark === aiMark) {
    const result = minimax(currBdSt, humanMark);
    currentTestPlayInfo.score = result.score;
} else {
    const result = minimax(currBdSt, aiMark);
    currentTestPlayInfo.score = result.score;
}

注意：

• 在这一点上递归调用 minimax 将是我们调用该函数的 _ 次。第一次调用发生在第 7 步。
• 这个递归调用将导致步骤8到11的重复。
• 假设在第 9 步有一个终止状态。在这种情况下，当前的最小最大调用将停止运行——并将返回的终止对象（例如， {score: 1} ）存储在 result 变量中。
• 一旦出现终止状态，第12步将是下一步。
• 如果不存在 终止 状态，将在第 10 步为新棋盘开始一个 第二个循环 。
• 如果第10步被重复，请用图5中的新棋盘替换图4中的棋盘。然而，红色高亮的单元格现在将是循环当前处理的单元格。因此，请相应地反映这些变化。

步骤 12：保存最新的终端分数

在刚刚结束的 minimax 调用返回其终端状态的值后，活动的 for 循环将把 result 变量的分数保存到 currentTestPlayInfo 对象中，如下所示：

currentTestPlayInfo.score = result.score;

然后，由于返回的分数正式结束了当前的测试游戏，最好将当前棋盘重置回当前玩家下棋之前的状态。

currBdSt[availCellsIndexes[i]] = currentTestPlayInfo.index;

此外，我们需要保存当前玩家的测试游戏结果以供将来使用。因此，让我们通过将 currentTestPlayInfo 对象推送到 allTestPlayInfos 数组来实现：

allTestPlayInfos.push(currentTestPlayInfo);

注意：

• 如果您是从第 17 步进入此步骤，请在 第 18 步 继续本教程。否则，请考虑下一个要点。
• 如果活动的 for 循环已经遍历了当前棋盘上所有的空单元格，则循环将在此结束，接下来是 第 14 步 。否则，循环将继续处理下一个可用单元格（第 13 步）。

请记住，当前活动的 for 循环（从第 10 步开始）仅完成了前一个空单元格的工作。因此，循环将继续在下一个空闲单元格上测试当前玩家的标记。

换句话说，当前运行的极小极大函数将重复步骤 11 和 12 。但是，基本上，请注意以下几点：

• 图 4 中高亮的红色单元格将更改为 for 循环当前正在处理的单元格。
• 请注意，图 5 也会发生变化。换句话说，当前玩家的移动将现在位于 for 循环当前正在处理的单元格上。
• 在活动的 for 循环完成其工作后， allTestPlayInfos 数组将包含 for 循环处理的每个空单元格的特定对象。
• allTestPlayInfos 数组中的每个对象将包含一个 index 属性和一个 score 属性（例如： {index: 8, score: -1} ）。
• 如果您是从第20步到达此步骤的，那么在完成第12步后，请继续在第18步进行本教程。

步骤14：规划如何为当前玩家获取最佳测试游戏得分的对象

在 for 循环完成对当前棋盘上所有空格的遍历后，minimax 将会：

1. 创建一个空间 来存储参考编号，以便后续获取最佳测试游戏对象。
2. 获取当前玩家最佳测试游戏的参考编号 。
3. 使用获得的参考编号 来获取当前玩家的最佳测试玩法对象。

不再赘述，让我们在接下来的几个步骤中实施这个计划。

步骤 15：为最佳测试玩法的参考创建一个存储

下面的变量是我们稍后将存储对最佳测试游戏对象引用的地方。（请注意，值 null 表示我们故意将变量留空）。

let bestTestPlay = null;

步骤 16：获取当前玩家最佳测试游戏的引用

现在有了一个 bestTestPlay 存储，活动的 minimax 函数可以像这样获取当前玩家的最佳测试玩法的引用：

if (currMark === aiMark) {
    let bestScore = -Infinity;
    for (let i = 0; i < allTestPlayInfos.length; i++) {
        if (allTestPlayInfos[i].score > bestScore) {
            bestScore = allTestPlayInfos[i].score;
            bestTestPlay = i;
        }
    }
} else {
    let bestScore = Infinity;
    for (let i = 0; i < allTestPlayInfos.length; i++) {
        if (allTestPlayInfos[i].score < bestScore) {
            bestScore = allTestPlayInfos[i].score;
            bestTestPlay = i;
        }
    }
}

上面的代码意味着如果当前标记等于 AI 玩家的标记：

1. 创建一个 bestScore 变量，其值为 -Infinity 。（请注意，这个值只是一个占位符，必须 小于 allTestPlayInfos 数组中的所有分数。因此，使用 -700 也能达到同样的效果）。
2. 然后，对于 allTestPlayInfos 数组中的每个测试游戏对象，检查当前循环正在处理的测试游戏是否具有比当前 bestScore 更 高 的分数。如果是，则将该测试游戏的详细信息记录在 bestScore 变量和 bestTestPlay 变量中。

否则，如果当前标记是人类玩家的标记：

1. 创建一个 bestScore 变量，其值为 +Infinity 。（再次注意，如果我们选择使用 +300 ，结果也是相同的。这只是一个占位符值，需要大于 allTestPlayInfos 数组中的所有分数。）
2. 然后，对于 allTestPlayInfos 数组中的每个测试游戏对象，检查当前循环正在处理的测试游戏是否具有低于当前 bestScore 的 分数 。如果是，则将该测试游戏的详细信息记录在 bestScore 变量和 bestTestPlay 变量中。

步骤17：获取当前玩家的最佳测试游戏分数对象

最后，当前运行的 minimax 调用可以通过返回当前玩家的最佳测试游戏对象来完成其工作，如下所示：

return allTestPlayInfos[bestTestPlay];

请注意，minimax 将把返回的对象存储在第 11 步开始的第一个 for 循环的 result 变量中。然后，它将重复第 12 步。请仅重新查看第 12 步。然后，继续下面的教程。

步骤18：让我们进行回顾

这个阶段是回顾我们迄今为止所做工作的一个绝佳时机。

注意：

• 如果这是您第一次进行此步骤，请使用 步骤 19 中的图示。
• 这是你第二次在这个步骤吗？如果是的话， 第 21 步 中的图表是你的。
• 你是第三次来这里吗？做得好！查看 第 23 步 中的图表。

步骤19：用图示追踪我们的步骤

下图显示了 AI 和人类玩家的 第一次测试游戏 ，这是由 AI 玩家发起的第一次 for 循环调用。

图 6：第一次测试游戏，预测 AI（最大化者）的失败状态

在得出在第一个空单元格上游戏将导致失败状态的结论后，AI 继续进行，通过重复第 13 步来测试在 第二个空单元格 上游戏的结果。

步骤21：用图示追踪我们的步骤

下图展示了 AI 和人类玩家在 AI 玩家发起的第一次 for 循环调用中的 第二次测试游戏 。

图 7：第二次测试游戏，预测 AI（最大化者）的胜利状态

现在 AI 已经确认在第二个空单元格上进行游戏将导致胜利状态，它进一步通过重复步骤 13 来检查在 第三个空单元格 上进行游戏的结果。

步骤23：用图示追踪我们的步骤

下图显示了 AI 和人类玩家在 AI 玩家发起的第一次 for 循环调用中的 第三次测试游戏 。

图 8：第三次测试游戏，预测 AI（最大化者）的失败状态

步骤 24：获取 AI 玩家的最佳测试游戏得分对象

此时（在第三次测试游戏之后），第一个 for 循环将处理完第一个棋盘的所有三个空单元格（在第 7 步传递给 minimax）。

因此，minimax 将继续前进，以获取对 AI 玩家最佳测试游戏的对象——通过重复步骤 15 到 17。然而， 在第 17 步时 ，请注意以下几点：

• 返回的对象现在将存储在我们在第 7 步创建的 bestPlayInfo 变量中。
• Minimax 将不会重复第 12 步，因为 for 循环语句不再有效。

图9：所有测试游戏和得分概览

步骤 25：使用 bestPlayInfo 中的数据

考虑到本教程的棋盘（接近结束状态的游戏棋盘——如步骤 2 的图 2 所示）， bestPlayInfo 变量中的对象将是 {index: 4, score: 1} 。因此，AI 现在可以使用其索引值来选择最佳的落子位置。

示例

// Get all the board’s cells:
const gameCells = document.querySelectorAll(".cell");

// Below is the variable we created at step 3:
const aiMark = "X";

// Here is the bestPlayInfo we created at step 7 to contain the best test-play object for the AI player:
const bestPlayInfo = minimax(currentBoardState, aiMark);

// Play the AI’s mark on the cell that is best for it:
gameCells[bestPlayInfo.index].innerText = aiMark;

因此，AI 玩家将赢得比赛，新的棋盘现在将如下所示：

图 10：最终游戏棋盘，显示 AI（玩家 X）赢得了比赛

第26步：本教程算法的鸟瞰图

以下是本教程的极小极大算法的完整代码。请随意将其插入到您的编辑器中。尝试不同的游戏场景，并使用控制台进行测试，反复测试，直到您能够自信地构建一个无敌的人工智能。

并且记住，编程只有在你 编写优雅代码 时才更好——所以要好好享受它！

// Step 3 - Store the board’s current state in an array and define each mark's owner:
const currentBoardState = ["X", 1, "O", "X", 4, "X", "O", "O", 8];
const aiMark = "X";
const humanMark = "O";

// Step 4 - Create a function to get the indexes of all the empty cells:
function getAllEmptyCellsIndexes(currBdSt) {
    return currBdSt.filter(i => i != "O" && i != "X");
}

// Step 5 - Create a winner determiner function:
function checkIfWinnerFound(currBdSt, currMark) {
    if (
        (currBdSt[0] === currMark && currBdSt[1] === currMark && currBdSt[2] === currMark) ||
        (currBdSt[3] === currMark && currBdSt[4] === currMark && currBdSt[5] === currMark) ||
        (currBdSt[6] === currMark && currBdSt[7] === currMark && currBdSt[8] === currMark) ||
        (currBdSt[0] === currMark && currBdSt[3] === currMark && currBdSt[6] === currMark) ||
        (currBdSt[1] === currMark && currBdSt[4] === currMark && currBdSt[7] === currMark) ||
        (currBdSt[2] === currMark && currBdSt[5] === currMark && currBdSt[8] === currMark) ||
        (currBdSt[0] === currMark && currBdSt[4] === currMark && currBdSt[8] === currMark) ||
        (currBdSt[2] === currMark && currBdSt[4] === currMark && currBdSt[6] === currMark)
) {
        return true;
    } else {
        return false;
    }
}

// Step 6 - Create the minimax algorithm:
function minimax(currBdSt, currMark) {
    // Step 8 - Store the indexes of all empty cells:
    const availCellsIndexes = getAllEmptyCellsIndexes(currBdSt);

    // Step 9 - Check if there is a terminal state:
    if (checkIfWinnerFound(currBdSt, humanMark)) {
        return {score: -1};
    } else if (checkIfWinnerFound(currBdSt, aiMark)) {
        return {score: 1};
    } else if (availCellsIndexes.length === 0) {
        return {score: 0};
    }

    // Step 10 - Create a place to record the outcome of each test drive:
    const allTestPlayInfos = [];

    // Step 10 - Create a for-loop statement that will loop through each of the empty cells:
    for (let i = 0; i < availCellsIndexes.length; i++) {
        // Step 11 - Create a place to store this test-play’s terminal score:
        const currentTestPlayInfo = {};

        // Step 11 - Save the index number of the cell this for-loop is currently processing:
        currentTestPlayInfo.index = currBdSt[availCellsIndexes[i]];

        // Step 11 - Place the current player’s mark on the cell for-loop is currently processing:
        currBdSt[availCellsIndexes[i]] = currMark;

        if (currMark === aiMark) {
            // Step 11 - Recursively run the minimax function for the new board:
            const result = minimax(currBdSt, humanMark);

            // Step 12 - Save the result variable’s score into the currentTestPlayInfo object:
            currentTestPlayInfo.score = result.score;
        } else {
            // Step 11 - Recursively run the minimax function for the new board:
            const result = minimax(currBdSt, aiMark);

            // Step 12 - Save the result variable’s score into the currentTestPlayInfo object:
            currentTestPlayInfo.score = result.score;
        }

        // Step 12 - Reset the current board back to the state it was before the current player made its move:
        currBdSt[availCellsIndexes[i]] = currentTestPlayInfo.index;

        // Step 12 - Save the result of the current player’s test-play for future use:
        allTestPlayInfos.push(currentTestPlayInfo);
    }

    // Step 15 - Create a store for the best test-play’s reference:
    let bestTestPlay = null;

    // Step 16 - Get the reference to the current player’s best test-play:
    if (currMark === aiMark) {
        let bestScore = -Infinity;
        for (let i = 0; i < allTestPlayInfos.length; i++) {
            if (allTestPlayInfos[i].score > bestScore) {
                bestScore = allTestPlayInfos[i].score;
                bestTestPlay = i;
            }
        }
    } else {
        let bestScore = Infinity;
        for (let i = 0; i < allTestPlayInfos.length; i++) {
            if (allTestPlayInfos[i].score < bestScore) {
                bestScore = allTestPlayInfos[i].score;
                bestTestPlay = i;
            }
        }
    }

    // Step 17 - Get the object with the best test-play score for the current player:
    return allTestPlayInfos[bestTestPlay];
} 

// Step 7 - First minimax invocation:
const bestPlayInfo = minimax(currentBoardState, aiMark);

有用的资源

• 递归：你需要了解的递归知识