algorithm - 如何显示Alpha Beta Pruning算法结果？

Question

更新

更新 1

我试过 this (第 2 行):我在 alphabeta 函数中添加了更改节点颜色作为第一条指令。我得到 this result :

绿色节点是访问过的节点。看起来，算法会正确地抛出节点，对吧？但是如何在节点中输出正确的值——我也需要这样做？子值的最小值，子值的最大值(不包括修剪的分支)。

更新 2

我试图将 alpha 和 beta 输出到树节点，但没有得到正确的结果。 This是代码(添加了第 18 和 31 行)。 This是代码的结果:

关于 this图片我展示了奇怪的地方:

第一个箭头:为什么 7 和 6 中的最小值是 5？第二个箭头:为什么 4、3 和 2 的最大值是 5？奇怪的。这就是我认为它现在可以正常工作的原因。

老问题

曾几何时，我在这里提出了类似的问题。就像:“为什么我会收到这个错误？”。让我们回滚并创建新的。本题为:“Alpha Beta Pruning 算法结果如何显示？”

我在维基上找到了这个算法的伪代码。可以查到here .

我的实现如下(它是在 JavaScript 上实现的，但我不认为要回答这个问题你必须了解 JS 或 Java 或 C++ 等)。问题是如何在图(树结构)上输出该算法的结果？一开始我有这个树结构:

注意: 我有树结构(一些链接的节点)，我将在其上使用 alpha beta 修剪算法，我还有另一个树结构(用于显示结果，我们称之为“图表”)。我用来显示图形的树节点与我用来查找算法结果的节点相连。

因此，alpha beta 剪枝算法的代码如下。您能否说明我必须输出什么以及输出到哪里才能正确显示算法的过程/结果？

我的假设是输出 alpha 和 beta，但我认为这是错误的。我试过了，但没用。

我想显示修剪并用正确的值填充树中的所有节点。

这是我使用 alpha beta 剪枝实现的 minimax:

function alphabeta(node, depth, alpha, beta, isMax, g) {
    if((depth == 0) || (node.isTerminal == true)) {
        return node.value;
    }
    if(isMax) {
        console.log('maximizing');
        for (var i in node.children) {
            var child = node.children[i];
            console.log(child);
            alpha = Math.max(alpha, alphabeta(child, depth-1, alpha, beta, false, g));
            if(beta <= alpha) {
                console.log('beta '+beta+' alpha '+alpha);
                break;
            }
        }

        return alpha;
    } else {
        console.log('minimizing');
        for (var i in node.children) {
            console.log('1 child');
            var child = node.children[i];
            console.log(child);
            beta = Math.min(beta, alphabeta(child, depth-1, alpha, beta, true, g));
            if (beta <= alpha) {
                console.log('beta '+beta+' alpha '+alpha);
                break;
            }
        }

        return beta;
    }
}

Answer 1

为什么不只存储实际访问过的节点，并将这些节点标记为红色。然后您将看到与整棵树相比哪些节点得到了评估。例如

在评论中进行了长时间的讨论后，我想我现在可以阐明这一点。当 alpha beta 围绕树运行时，它具有三个值，当在给定节点上运行时，它具有从其父节点传递给它的 alpha 和 beta，然后它具有迄今为止找到的最佳值.如果它在 alpha-beta 窗口之外找到一个值，它会立即修剪，因为它知道这个节点不是最佳移动，而不管它的值如何。因此，对于某些节点，alpha beta 永远无法计算出节点的“真实值”。

因此，当您被要求显示 alpha beta 的“结果”时，我错误地认为您指的是 alpha-beta 窗口，因为“真实值”永远不会被评估。

您需要编写单独的代码来打印“真实节点值”。我认为 minimax 算法会为您做到这一点。

此外，在手动比较时请注意，如果您使用的是一组“节点”，则列表迭代器不能保证以可预测的顺序返回节点，因此如果在节点内部您使用的是集合而不是列表，您可能会发现很难手动跟进。列表迭代器按插入顺序返回。集合迭代器没有可预测的迭代器。