如何显示Alpha Beta修剪算法结果？

Question

更新

更新1

我试过这个(第2行):我添加了更改节点颜色作为alphabeta函数中的第一条指令.我得到了这个结果:

绿色节点是访问节点.看起来,算法正确地投掷节点,对吗？但是如何在节点中输出正确的值 - 我还需要这样做？最小子值,最大子值(不包括已修剪的分支).

更新2

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

在这张图片上我展示了奇怪的地方:

第一个箭头:为什么7和6的最小值是5？第二个箭头:为什么最多4,3和2是5？奇怪.这就是为什么我认为它现在正常工作.

老问题

曾几何时我在这里创建了类似的问题.这就像:"为什么我会收到这个错误？".让我们回滚并创建一个新的.这个问题将是:"如何显示Alpha Beta修剪算法结果？"

我在维基上找到了这个算法的伪代码.它可以在这里找到.

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

注意:我有树结构(一定数量的链接nodes),我将使用alpha beta修剪算法,我有另一个树结构(为了显示结果,我们称之为"图").我用来显示图形的树节点与节点连接,我用它来查找算法的结果.

因此,alpha beta修剪algroithm的代码如下.你能说清楚我必须输出的内容和位置,以正确显示算法的过程/结果吗？

我的假设是输出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 窗口，因为“真实值”永远不会被评估。

您需要编写单独的代码来打印“真实节点值”。我认为极小极大算法可以为你做到这一点。

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