时间戳

首页 > 解决方案 > 你能帮我理解这个井字游戏极小极大代码的几个方面吗？（内有具体说明）

javascript - 你能帮我理解这个井字游戏极小极大代码的几个方面吗？（内有具体说明）

问题描述

我正在尝试从这里的代码中自学 javscript 中的 minimax：https ://github.com/beaucarnes/fcc-p​​roject-tutorials/blob/master/tictactoe/7/script.js

和视频：https ://youtu.be/P2TcQ3h0ipQ?t=2334

这是功能：

function minimax(newBoard, player) {
    var availSpots = emptySquares();

    if (checkWin(newBoard, huPlayer)) {
        return {score: -10};
    } else if (checkWin(newBoard, aiPlayer)) {
        return {score: 10};
    } else if (availSpots.length === 0) {
        return {score: 0};
    }
    var moves = [];
    for (var i = 0; i < availSpots.length; i++) {
        var move = {};
        move.index = newBoard[availSpots[i]];
        newBoard[availSpots[i]] = player;

        if (player == aiPlayer) {
            var result = minimax(newBoard, huPlayer);
            move.score = result.score;
        } else {
            var result = minimax(newBoard, aiPlayer);
            move.score = result.score;
        }

        newBoard[availSpots[i]] = move.index;
        moves.push(move);
    }

    var bestMove;
    if(player === aiPlayer) {
        var bestScore = -10000;
        for(var i = 0; i < moves.length; i++) {
            if (moves[i].score > bestScore) {
                bestScore = moves[i].score;
                bestMove = i;
            }
        }
    } else {
        var bestScore = 10000;
        for(var i = 0; i < moves.length; i++) {
            if (moves[i].score < bestScore) {
                bestScore = moves[i].score;
                bestMove = i;
            }
        }
    }

    return moves[bestMove];
}

我想我理解了大部分内容，但是有一些空白让我无法完全理解它。

据我了解，minimax(newBoard, player)首先要获得可用于下棋的位置，并建立一种对最终结果进行排名的方法。

然后它创建一个数组moves，被调用的对象move将进入该数组。for 循环move为每个可用点获取一个对象。

每个move对象通过move.index = newBoard[availSpots[i]];

之后，有一条if else语句.score为对象添加属性move。

然后将最新的移动推入moves数组，并从数组中循环遍历分数以找到best move移动。

我很难看到这一切是如何运作的。我尝试输入一个console.log，但我的repl.it 失败了......

最后：

我在网上浏览了大量的极小极大资源，所以我希望有人能提供帮助——他们似乎都掩盖了这一点。我看过：

https://www.freecodecamp.org/news/how-to-make-your-tic-tac-toe-game-unbeatable-by-using-the-minimax-algorithm-9d690bad4b37/

https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/

https://youtu.be/trKjYdBAsyQ

https://youtu.be/ovr2sTYhb1I

https://learnersbucket.com/tutorials/js-projects/tic-tac-toe-game-in-javascript-with-bot/

https://steveafrost.com/articles/discovering-the-minimax-algorithm/

谢谢！

标签： javascriptarraysrecursiontic-tac-toeminimax

解决方案

让我们从你的最后一个问题开始。

既然是回合制游戏，那电脑在代码中的哪个位置“玩”对方以获得终值呢？

不是，不在此代码中。此函数有一个目的，即使用极小极大算法选择最佳移动。它通过操纵棋盘对象、设置值并重置它们、找到位置的分数来实现。其他代码必须处理 IO。所以重要的是要记住，这段代码只是整个井字游戏系统的一部分。

这种理解可能有助于澄清其他一些问题。

是否可以说在有可用点的棋盘中[4, 5, 6]，newBoard[availSpots[0]]是4，因此第一个移动对象的索引属性为 4？

虽然您可以这样想，但此代码中没有任何内容来描述板的表示方式。因此，虽然它可能是正方形1- 9，但不一定是。它们可能是a1, a2, a3, b1, b2, b3, c1, c2, c3. 或者可能有另一种表示。我们所知道的是，板子有一些我们可以引用的属性[]（数字、字符串，甚至可能是符号），这availSpots是这些值的数组。显然，它代表了可用的那些。

代码的新部分是newBoard[availSpots[i]] = player——这是否意味着玩家的图标被标记了newBoard[4]？

这意味着棋盘的内部数据结构现在可以识别具有给定单元格的玩家。同样，此代码仅用于选择最佳移动。但它对图标或板的可见表示一无所知。并注意，板子的这种状态是暂时的；对棋盘的操纵只是为了帮助计算最佳棋步。其他代码实际上会将其计算的移动应用到正在进行的棋盘上。

之后，有一条if else语句.score为对象添加属性move。

但后来我明白newBoard[availSpots[i]] = move.index了，这与我们之前所做的相反——这是为什么呢？

它正在测试棋盘，逐个可用棋步，以找到最好的棋盘。它通过移动、计算结果分数然后重置该移动来尝试不同的移动来做到这一点。在计算走法时，我们可能会递归调用minmax，然后它会按顺序尝试其走法，这可能会延伸到九层深，棋盘上的每个单元格一层。

因此，如果当前板看起来像

X O O
4 5 6
X O X

我们会得到以下分析：

         max    min    max
X O O
4 5 6
X O X
  |     X O O
  +-->  X 5 6  (score 10)
  |     X O X
  |
  |     X O O
  +-->  4 X 6  (score 10)
  |     X O X
  |
  |     X O O
  +-->  4 5 X
        X O X
          |    X O O
          +--> O 5 X
          |    X O X
          |      |    X O O
          |      +--> O X O  (score 10)
          |           X O X
          |     
          +--> X O O
               4 O X  (score -10)
               X O X

我们尝试可用的move 4for X，发现它的得分为+10，然后重置4为默认值，这样我们就可以尝试5for X，得分也为10。我们再次重置5为默认值。然后我们尝试6. X为了得分，我们必须更深入，首先尝试4. O这需要我们更深入，我们5开始X。那是有价值+10的。我们重置它，重置并重4试5for O，它的得分为-10。在极小极大之后，我们可以发现 的值X O O / 4 5 X / X O X是-10，并且我们已经看到两者X O O / X 5 6 / X O X并且X O O / 4 X 6 / X O X得分为+10，所以我们会选择其中之一。（通过这个算法，第一个，但更有趣的算法可能会在同样好的移动中随机选择。）

我尝试输入一个console.log，但我的repl.it 失败了......

是因为编译器正在尝试数十种排列并且将它们全部记录下来会很丑吗？计算机要尝试多少步？

我们必须看看你做了什么来测试这个，但是不，这个游戏很简单，你不应该在这些计算中耗尽任何资源。游戏总数少于9!- 即362880- 总数。所以我猜你没有正确记录。

推荐阅读