java - MiniMax 返回反向效用值

Question

我正在尝试打印出 Mini Max 的访问状态和效用。当值从终端状态返回到其根时，我遇到了问题，从而导致我访问的状态实用程序值中的 4 个不正确。我只是不知道是什么原因导致了这个错误。我很确定我的 Min 和 Max 方法是正确的。

Answer 1

在你的列表中选择第一个状态，你需要解释为什么 ooxxxo-xo 应该是 1。如果我按照我认为我应该阅读的方式重写它，状态读取作为:

oox
xxo
-xo

如果我们正确地应用 x 作为下一步，我们将得到正确的答案。所以，也许问题出在你的移动生成上。

看看这个，你有一个单一的静态数组来存储移动，但是当你进行递归调用时，你会一遍又一遍地覆盖这个移动。相反，您需要为每个递归调用移动的本地副本。因此，将 minChildren 和 maxChildren 的定义移动到 MinTurn 和 MaxTurn 中至少可以解决代码中的一个问题. (我没有验证过没有其他问题。)

明确地说，您的调用堆栈是这样的:

MaxTurn call
  Set maxChildren to legal moves // <--- A
  Call MinTurn recursively
    MinTurn call
      Set minChildren to legal moves
      Call MaxTurn recursively
        MaxTurn call
          Set maxChildren to legal moves // <--- B
          Call MinTurn recursively

当您到达标记为 B 的行时，您将覆盖在 A 行计算的 maxChildren。因此，当程序返回到 A 时，可用的移动将被覆盖，并且可能与之前预期的不同。

---

修复后，我相信您的新问题就出在您打印东西的方式上。如果您查看您的打印代码，您会记录当前的最大值，而不是 child 返回的值:

int maxValue = Setting.NEGATIVE_INFINITY;
maxChildren = generateMoves(state);
for (State aChildren : maxChildren) {
    maxValue = Math.max(maxValue, MinTurn(aChildren)); // <-- A
    nodes.add(aChildren.getState() + " " + maxValue); // <--B
}

因此，在标记为 B 的行中，您正在为目前看到的所有 child 打印 maxValue。如果你想看到 child 的值(value)，你不应该立即在行 A 中取最大值。而是存储结果并记录它。然后，取最大值。

你在这个状态下遇到了问题:

oox
xxo
-x-

这是从可能开始搜索的父状态打印的:

oox
xxo
---

第一步是把x放在左下角，赢得比赛，赋值1。当第二步走，导致x在中间的状态，maxValue仍然是1 来自上一步。

您的代码应如下所示:

int nextValue = MinTurn(aChildren)
maxValue = Math.max(maxValue, nextValue);
nodes.add(aChildren.getState() + " " + nextValue);