如何显示Alpha Beta剪枝算法的结果?

8

更新

更新 1

我尝试了这个(第二行):我在alphabeta函数中添加了更改节点颜色的第一条指令。我得到了这个结果

结果

绿色节点是访问过的节点。看起来算法正在正确地遍历节点,对吗?但是如何输出节点中的正确值——我也需要做到这一点吗?子节点值的最小值、子节点值的最大值(不包括剪枝的分支)。

更新 2

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

输出

这个图像上,我展示了一些奇怪的地方:

输出错误

第一个箭头:为什么7和6的最小值是5?第二个箭头:为什么4、3和2的最大值是5?奇怪。这就是为什么我认为它现在不正确的原因。

旧问题

曾经我在这里创建过类似的问题。它是这样的:“为什么我会得到这个错误?”让我们回滚并创建新的问题。这个问题将是:“如何显示Alpha Beta剪枝算法的结果?”

我在维基百科上找到了该算法的伪代码。可以在这里找到。

我的实现如下(它是JavaScript的,但我认为回答这个问题不需要您知道JS或Java或C++等)。问题是如何在图表(树形结构)上输出此算法的结果?一开始我有这个树形结构:

任务,我的结构

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

因此,下面是alpha beta修剪算法的代码。请问您能否澄清我需要在哪里输出才能正确地显示算法的过程/结果?

我的假设是输出alpha和beta,但我认为这是错误的。我尝试了一下,但它并不起作用。

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

这是我的minimax和alpha beta修剪的实现:

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;
    }
}

你想要展示什么?你想要像图片中那样的树形结构,还是只需要记录信息以便跟踪树形结构?你需要节点上的标签来验证代码是否正确运行吗? - Nathan S.
@NathanS 是的,我希望任务中树上的空白节点被填充。此外,我想展示修剪,例如通过颜色。 - Sharikov Vladislav
这个问题的问题在于它看起来不像是一个需要解决的技术问题,而更像是你想让别人为你完成的一些工作。如果有明确的技术障碍,请具体说明是什么。 - Denys Séguret
1个回答

5
为什么不只存储实际访问过的节点,并将这些节点标为红色。然后,您将看到与整个树相比哪些节点被评估了。例如:
在评论中长时间讨论后,我现在可以解释一下。随着αβ遍历树,它有三个值,当在给定节点上操作时,它具有从其父节点传递给它的α和β,然后它具有迄今为止找到的最佳值。如果它发现一个超出α-β窗口的值,它立即剪枝,因为它知道该节点不是最优移动,无论其值如何。因此,对于某些节点,αβ永远不会计算出节点的“真实值”。
因此,在被要求显示αβ的“结果”时,我错误地认为你指的是α-β窗口,因为“真实值”未必被计算出来。
您需要编写单独的代码以打印“真实节点值”。我认为minimax算法会为您完成此操作。
此外,请注意手动比较时,如果您使用节点“集”,则列表迭代器不能保证以可预测的顺序返回节点,因此,如果在节点内部您使用的是集合而不是列表,则可能难以手动跟踪。列表迭代器按插入顺序返回。集合迭代器没有可预测的顺序。

我试过了。我应该在哪里改变节点的颜色?我尝试了这个(第二行):我将更改节点颜色作为alphabeta函数中的第一条指令添加。我得到了这个结果:绿色节点是访问过的节点。看起来,算法正在正确地遍历节点,对吗?但如何输出节点中的正确值——我也需要这样做吗?子节点值的最小值、子节点值的最大值(不包括被剪枝的分支)。 - Sharikov Vladislav
我试图将alpha和beta输出到树节点中,但没有得到正确的结果。这是代码(添加了第18行和第31行)。这是代码的结果。在这张图片中,我展示了一些奇怪的地方。第一个箭头:为什么7和6的最小值是5?第二个箭头:为什么4、3和2的最大值是5?很奇怪。这就是为什么我认为它现在还没有正确工作。 - Sharikov Vladislav
是的,这很奇怪。首先检查(1)您是否使用足够的深度调用算法以达到树的最终层级?调用代码应该是例如alphabeta(root,1000,-1000,+1000,true,g)您的代码看起来正确,但您已经正确地识别出了荒谬的结果。或者,您可能由于某种原因没有输出每个节点?制作一个结果,其中打印(alpha,beta),并根据调用的if语句不同的颜色。 - phil_20686
我认为是的,我使用正确的深度进行调用。我现在使用深度为五,但是像你建议的那样,稍后我会尝试使用1000。此外,我将尝试使用不同颜色对不同节点进行着色,但稍后在晚上进行,但我认为新的彩色图像很难理解,因为这个函数是递归的,颜色有时会被覆盖(这只是我的猜测,我想我已经尝试过了,只有第一个(左侧)节点变成了绿色)。无论如何,我会再次尝试。谢谢。 - Sharikov Vladislav
你可能认为alpha beta算法和minimax算法很相似,但实际上它们并不一样。这个算法的关键在于它不必计算节点的值,因此如果它找到了任何一个超出alpha beta窗口的子节点,整个分支都会被剪枝。你输出的是alpha和beta的值,而这个窗口内的节点是不会被剪枝的,但这与节点的值并不相同。 - phil_20686
显示剩余18条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接