algorithm - minimax 静态树是如何构建的？

Question

考虑到我正在从头开始构建井字游戏，我目前正在尝试使用 minimax 算法，这样我就可以让计算机作为玩家 1，而我自己作为玩家 2。我想我理解 minimax 算法(作为某种形式的深度第一次搜索)。

我的问题是，minimax 算法所作用的树最初是如何生成的？我看到的所有示例都已经在终端节点中用一些数值制作了树。

例如:

       max
  / \  
       min
 /\ /\
7 2 1 5 

我看过这个更简单的树版本，以及如何选择到终端节点中值为 1 的节点的路径。我们如何首先获得 7、2、1 和 5？让我们在井字游戏中说..我的好奇心在这里徘徊。

Answer 1

您似乎在问两个问题。我将首先解决第二个问题。您问我们如何首先获取终端节点中的值。这取决于我们正在处理的游戏类型。对于 tic-tac-toe，所有叶节点将等于 -1、0 或 1。-1 表示输，0 表示平局，1 表示赢。必须评估每个节点以查看它是否是终端节点(即游戏是否结束)，如果是，则为其分配适当的值。您经常在搜索树中看到其他值的原因是因为在更复杂的游戏中，无法评估整棵树，因此应用启发式评估函数，通常包含广泛的值。但对于井字游戏来说，这是无关紧要的。

您首先还问过极小极大树是如何制作的。使用递归生成标准的极小极大树。为 tictactoe 简化的伪代码如下所示

function minimax(depth,maximizingPlayer)
      if(node is terminal)
            return value;
      if (maximizingPlayer)
            bestValue  = -infinity;
            for each possible legal move 
                  makeMove(move)
                  value = minimax(depth-1,false);
                  bestValue = max(bestValue,value);
                  unmakeMove(move);
            return bestValue
      else // minimizing player
            bestValue  = infinity;
            for each possible legal move 
                  makeMove(move)
                  value = minimax(depth-1,true);
                  bestValue = min(bestValue,value);
                  unmakeMove(move);
            return bestValue