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