用 JavaScript 创建井字棋第 2 部分：添加电脑玩家

在上一篇文章中，成都长风云 Drupal 开发团队用 JavaScript 创建了井字棋。之后，团队决定以电脑对手的形式添加第二个玩家。一个玩家仍然以同样的方式放置他们的棋子，但另一个玩家将使用算法来确定针对你的最佳走法。这一点非常重要。

我们可以通过几种方式为电脑玩家创建算法。井字棋游戏被认为是一个“已解决”的游戏，这意味着对于任何给定的走法，最佳走法已经确定。因此，我们可以构建一个算法，将当前游戏棋盘与已知的游戏状态进行匹配，然后将电脑棋子放置在最理想的位置。

然而，这种方法的缺点是，我们需要事先输入棋盘的所有不同情况。这意味着如果我们想改变规则或改变棋盘的大小，我们需要输入一组完全不同的游戏条件。

确定最佳走法的一个更好的方法是使用算法，并根据得分计算最佳走法。

在本文中，成都长风云 Drupal 开发团队将介绍用于计算井字棋最佳走法的算法，然后查看实现该算法的代码。本文将基于上一篇关于用 JavaScript 创建井字棋的文章所做的工作，因此这里不会展示所有代码。

一、赢得井字棋

为了赢得井字棋游戏，我们需要确定什么是最佳走法。“最佳”走法是指给我们赢得游戏的最大机会的走法。

计算电脑走法的最佳方法之一是使用一种称为极小极大算法（Minimax）或极大极小算法（MinMax）的算法。这是一种通过将游戏进行到结束并给每个走法打分来计算最佳走法的算法。在这个过程中计算出的最佳得分将用于进行游戏。

例如，让我们以一个已经进行到一半的井字棋游戏棋盘为例。展示接近游戏结束的情况是一种更简单的方式来展示游戏是如何进行的，因为此时游戏棋盘的结果较少。如果我们从游戏开始时考虑，我们需要考虑许多不同的游戏场景。

在这个游戏中，X 玩家刚刚落子，现在轮到电脑放置 O 棋子。这就是游戏棋盘的样子。

X|O|X
O|O|X
X|-|-

为了确定电脑的最佳走法，我们根据游戏棋盘的当前状态将游戏进行到结束。我们可以给游戏结果设定 3 种可能的状态，每种状态都有一个得分。

• +10 表示我们的走法导致游戏获胜。
• 0 表示我们的走法导致平局。
• -10 表示我们的走法导致失败。

极小极大算法的原理是，我们遍历游戏并给不同的场景赋予这些得分之一。

我们首先将棋子放在第一个空方格中，即底部中间的方格。

X|O|X
O|O|X
X|-|O

我们可以看到，电脑立即获胜了，所以在我们的走法结果中，这个棋盘得分为 +10。

尽管这是一次获胜，但这可能不是赢得游戏的最佳走法，所以我们检查其他可用的走法，以确保这是最优路径。我们可以做出的另一种可能的走法是将棋子放在右下角的方格中。

X|O|X
O|O|X
X|O|-

游戏仍然处于可继续的状态，所以我们模拟另一个玩家的走法，将最后一个棋子（在这种情况下是 X）放在底部中间的方格中。

X|O|X
O|O|X
X|X|O

这导致了平局的情况，这意味着我们给这个结果打分为 0。

在完成上述操作后，我们可以看到最佳走法是将棋子放在底部中间的位置，因为这会让电脑玩家确定获胜。

这正是游戏中任何一步都会运行的算法。游戏棋盘上可用的空格越多，意味着我们需要进行更多的模拟来确定最佳结果。在上面的例子中，我们只需要进行 3 步模拟，如果游戏棋盘是空的，我们需要进行至少255,168步来确定最佳方法。这一点非常重要。

二、确定最佳走法的代码

要将极小极大算法添加到游戏中，我们首先需要有一种使用结果的方法。我们需要做的是创建一个函数，该函数将在游戏棋盘中寻找空格，并以该空格为起点进行游戏模拟。然后我们将返回的得分与当前的最佳得分进行比较，如果得分更高，则更新当前的走法集合（即空格的坐标）。

当我们查看完游戏棋盘中的所有空格后，我们将得到一组坐标，这些坐标指向最佳的空格以进行落子。剩下要做的唯一事情就是落子（将玩家的棋子放入游戏棋盘），重新绘制棋盘并切换当前玩家。

这是处理电脑玩家的函数，它叫做 aiPlay()。成都长风云 Drupal 开发团队在代码中添加了注释，以显示正在执行的步骤。

function aiPlay() {
  // 定义最佳得分的最低可能状态。
  let bestScore = -Infinity;
  // 设置我们“最佳”走法的变量。
  let move;

  // 遍历游戏棋盘中的所有方格。
  for (let i = 0; i < state.length; i++) {
    for (let j = 0; j < state[i].length; j++) {
      if (state[i][j] == "") {
        // 这是一个空格，所以我们可以从这一点开始模拟游戏。
        state[i][j] = player2;
        let score = minimax(state, false);
        state[i][j] = "";
        if (score > bestScore) {
          // 这是我们目前得到的最佳得分，所以我们保存它。
          bestScore = score;
          move = { i, j };
        }
      }
    }
  }
  // 落子并绘制结果。
  state[move.i][move.j] = currentPlayer;
  drawState();

  // 切换玩家。
  if (currentPlayer == player1) {
    currentPlayer = player2;
  } else {
    currentPlayer = player1;
  }
}

为了确定走法的得分，我们使用 minimax() 函数，该函数将为棋盘的当前状态运行极小极大算法，让我们来看看这个函数。

三、极小极大函数

我们使用 minimax() 函数来确定从游戏棋盘当前状态下游戏的得分。这是我们落子一步后的游戏棋盘。以下是完整的代码。

function minimax(state, isMaximising) {
  var winner = isWin();

  if (winner === player2) {
    return 10;
  } else if (winner === player1) {
    return -10;
  } else if (winner === "draw") {
    return 0;
  }

  if (isMaximising) {
    var bestScore = -Infinity;
    for (let i = 0; i < state.length; i++) {
      for (let j = 0; j < state[i].length; j++) {
        if (state[i][j] == "") {
          state[i][j] = player2;
          let score = minimax(state, false);
          state[i][j] = "";
          bestScore = Math.max(bestScore, score);
        }
      }
    }
  } else {
    var bestScore = Infinity;
    for (let i = 0; i < state.length; i++) {
      for (let j = 0; j < state[i].length; j++) {
        if (state[i][j] == "") {
          state[i][j] = player1;
          let score = minimax(state, true);
          state[i][j] = "";
          bestScore = Math.min(bestScore, score);
        }
      }
    }
  }
  return bestScore;
}

该函数的工作方式是遍历游戏棋盘寻找任何空白方格，然后在该方格落子，然后我们递归调用该函数，直到游戏处于获胜状态。

当我们第一次进入该函数时，我们已经做出了电脑会做出的走法，所以通过将 isMaximizing 参数设置为“true”，我们以另一个玩家的身份进行游戏。然后我们再次调用该函数，并将“false”值传递给 isMaximising 参数，这使得电脑玩家进行落子。该函数本质上在两个玩家之间来回切换，每次落子并检测游戏是否获胜。

这里需要注意的一个重要事情是，当我们确定了走法的得分后，我们将游戏棋盘重置回其原始值。这在不需要制作游戏棋盘的多个副本的情况下保留了游戏的当前状态，以计算结果。这一点非常重要。

该函数的结果要么是获胜得 +10 分，失败得 -10 分，平局得 0 分，然后我们将这些信息传递给 aiPlay() 函数。利用这些信息，我们就能够根据函数的得分确定最佳走法。

现在我们需要做的就是将这个第二个玩家融入到井字棋游戏中，这样电脑也可以参与游戏。

四、添加第二个玩家

在原始游戏中，我们有一个名为 canvasClick() 的函数，用于记录点击事件，从而记录每个玩家的落子。为了将电脑玩家融入游戏，我们只需要扩展这个函数以包含 aiPlay() 函数。电脑玩家落子后，我们进行第二次检查，看游戏是否已经获胜。

function canvasClick(event) {
  const rect = canvas.getBoundingClientRect();
  var x = event.clientX - rect.left,
    y = event.clientY - rect.top;

  // 点击偏移量与元素之间的碰撞检测。
  boxes.forEach(function (element) {
    if (
      y > element.y &&
      y < element.y + element.height &&
      x > element.x &&
      x < element.x + element.width
    ) {
      if (state[element.row][element.column] !== "") {
        return;
      }

      play(element.row, element.column);

      // 查看是否有获胜者。
      let winner = isWin();
      if (winner === "draw") {
        document.getElementById("win").innerHTML = "平局！";
      } else if (winner === player1 || winner === player2) {
        document.getElementById("win").innerHTML = winner;
      }

      if (winner !== false) {
        canvas.removeEventListener("click", canvasClick);
        return;
      }

      aiPlay();

      // 查看是否有获胜者。
      winner = isWin();
      if (winner === "draw") {
        document.getElementById("win").innerHTML = "平局！";
      } else if (winner === player1 || winner === player2) {
        document.getElementById("win").innerHTML = winner;
      }

      if (winner !== false) {
        canvas.removeEventListener("click", canvasClick);
        return;
      }
    }
  });
}

这就是我们启动极小极大算法并针对人类玩家做出最佳走法所需做的全部事情。一旦这个函数运行完毕，就轮到人类玩家了，这个循环将一直重复，直到游戏获胜。

五、结论

通过对井字棋游戏进行这些更改，实际上很难击败电脑。你每走一步，电脑都会遍历游戏棋盘的每一种排列，以找到针对你的最佳得分走法，这使得 AI 玩家看起来非常有技巧。实际上，AI 玩家只是预测游戏棋盘上的走法，并知道在任何给定情况下的最佳走法。

成都长风云 Drupal 开发团队在这里尽量保持简单，所以本文中的极小极大函数是该算法的一个简单实现。可以使用α - β剪枝进一步改进，以防止对相似游戏的得分进行多次计算。例如，如果我们知道在某个特定位置落子最终会导致失败，那么在分析的每个部分中，我们不需要一直递归到最后来确定这一点。我们可以寻找从不同游戏路径得到的相同游戏棋盘，这样我们就不需要一直沿着路径走下去，因为结果是相同的。通过这样做，我们可以提高算法的性能，因为我们可以减少需要执行的步数。这一点非常重要。

极小极大函数也可以修改为有一个深度参数。这可以用于在特定级别停止递归，这实际上为 AI 玩家创建了一个难度级别。例如，假设我们修改极小极大代码，使得如果达到深度为 3，函数将返回该级别当前的得分（即使游戏还没有获胜）。这个小改动将有效地阻止极小极大算法知道走法的最终结果，这意味着它可能不知道在某个方格落子是否真的会导致获胜。由于不知道游戏的最终结果，算法可能会在不知情的情况下犯错。

作为一个实验，成都长风云 Drupal 开发团队尝试将游戏棋盘增大到更大的尺寸，由于我们绘制棋盘的方式，这是可行的。结果是，极小极大函数找到解决方案的时间比以前长得多。事实上，仅仅将游戏棋盘增加到 6x6 网格，极小极大函数就需要超过 10 秒才能运行完成。你可以明白为什么在这种情况下使用α - β剪枝和深度限制会有好处。

如果你想查看本文中所有代码的运行情况，可以查看相关代码示例。如果你只是想玩游戏，也能找到相应的游戏页面。如果你能击败它，请告诉成都长风云 Drupal 开发团队，因为团队还没有取得比平局更好的成绩。

如果你想了解更多关于井字棋中极小极大算法的信息，可以查看相关教程和代码，有教程很好地展示了如何创建极小极大算法树并用于确定最佳行动方案。