我创建了在图表上执行 alpha beta 算法的程序。
(图片可点击查看大图)
我有这张图:
算法结果:
此图显示了问题区域:
为什么要修剪这两个节点?组的第一个节点是 5,前一个顶点的父节点是 2,所以我们比较 5 和 2。5 不小于 2,但是程序做了截断。为什么?只有当节点值小于 2 时,它才必须这样做,但在我们的情况下不是这样。
我是否误解了 alpha-beta 修剪理论中的某些内容,所以我在比较错误的值?还是我实现的问题?之前所有其他分支都运行良好,那么为什么问题只出现在这里?另一方面,看看这张图片:
程序必须修剪,修剪完成。当第一个子顶点为 5 或 1 时,为什么要修剪?
我的 alpha beta 函数(在 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;
}
}
这个函数是维基百科上的伪代码到 JavaScript 的翻译。
注意:如果你打开完整的源代码,你会注意到我在alpha_beta_blank
这里展示了这个函数——这个函数是维基百科伪代码的翻译。实际上,我在我的程序中使用了另一个函数,但都没有正常工作,如上所述。
关于调试。您可以查看此函数(带有所有调试语句的原始函数)并看到我正在打印调试消息。调试跟踪中的这部分属于问题顶点:
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