algorithm - 为什么这个修剪是由我的程序完成的？

Question

我创建了在图形上执行 alpha beta 算法的程序。

(图片可点击放大)

我有这张图:

算法结果:

这张图片显示了问题区域:

为什么要修剪这两个节点？组的第一个节点是 5，前面顶点的父节点是 2，所以我们比较 5 和 2。5 不小于 2，但程序进行了截断。为什么？只有当节点值小于 2 时它才必须这样做，但在我们的例子中不是这样。

我是否误解了 alpha-beta 修剪理论中的某些内容，所以我比较了错误的值？还是我的认识有问题？之前所有其他分支都运行良好，那么为什么问题只出现在这里？另一方面，请看这张图片:

程序必须剪枝，剪枝已经完成。当第一个子顶点为 5 或 1 时，为什么要剪枝？

---

我的 alpha beta 函数(on GitHub):

function alphabeta_blank(node, depth, alpha, beta, isMax, g) {
    g.nodes[node.name].shape.items['0'].attr('fill', 'green');

    if((depth == 0) || (node.isTerminal == true)) {
        return node.value;
    }
    if(isMax) {
        for (var i in node.children) {
            var child = node.children[i];
            alpha = Math.max(alpha, alphabeta_blank(child, depth-1, alpha, beta, false, g));
            if(beta <= alpha) {
                break;
            }
        }
        return alpha;
    } else {
        for (var i in node.children) {
            var child = node.children[i];
            beta = Math.min(beta, alphabeta_blank(child, depth-1, alpha, beta, true, g));
            if (beta <= alpha) {
                break;
            }
        }
        return beta;
    }
}

这个函数是the pseudocode on Wikipedia的翻译到 JavaScript。

注意:如果你打开完整的源代码，你会注意到我在这里展示了 alpha_beta_blank 函数——这个函数是维基百科伪代码的翻译。事实上，我在我的程序中使用了另一个函数，但都没有正常工作，如上所述。

关于调试。你可以看看this function (带有所有调试语句的原始函数)并看到我正在打印调试消息。调试跟踪的这部分属于问题顶点:

minimizing (min312)
getting value from terminal node node31 (value is 5)
beta value is set to 5
alpha cut-off (5<=5), others children of max31 wouldn't be visited
min312 — minimum of childs of min312 is 5
min312 — childs of node min312: [5]
returning beta, minimal node is 5, node min312 value is set as 5
going back to node max31

带有名称的部分图表(以便您可以理解日志):

             max31
            /       \
      min311         min312
     ........     /    |     \
                 /     |      \
child:          5      4       5

Full repository on GitHub .

Answer 1

通过探索第一个子树(从根开始)，我们发现我们一定会得到 5 的结果，所以当我们转到那个“麻烦”的节点并获得 5 的值时，我们可以修剪，因为没有办法min 节点将取更高的值，当然我们不想尝试获得更低的值，因为我们总是可以转到第一个子树并获得 5 的结果(同样适用于你的其他示例，当它为 1 时，因为5 优于 1)。尽管如果它是 6，那么它就不会修剪。

那个地方的 alpha 值不是 2，而是 5，因为它是从第一个子树作为保证的最大值结转而来的。所以这就是为什么你的书面比较 2<5不正确，应该是 5<=5这是真的。