グラフ上でアルファ ベータ アルゴリズムを実行するプログラムを作成しました。
(画像をクリックすると拡大版が表示されます)
私はこのグラフを持っています：
アルゴリズムの結果:
この画像は、問題のある領域を示しています。
これら 2 つのノードがプルーニングされたのはなぜですか? グループの最初のノードは 5、前の頂点の親ノードは 2 であるため、5 と 2 を比較します。5は 2 未満ではありませんが、プログラムはカットオフを行いました。なんで？ノード値が 2 より小さい場合にのみ実行する必要がありますが、この場合はそうではありません。
α-β プルーニング理論で何か誤解しているので、間違った値を比較していますか? それとも私の認識の問題ですか？以前は他のすべてのブランチが完全に機能していたのに、なぜここでのみ問題が発生するのでしょうか? 一方、こちらの画像をご覧ください。
プログラムは整理する必要があり、整理が完了します。最初の子頂点が 5 または 1 の場合、なぜ剪定が行われるのですか?
私のアルファベータ機能（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;
}
}
この関数は、Wikipedia の疑似コードを JavaScript に翻訳したものです。
注: 完全なソースを開くと、alpha_beta_blankここで関数を示したことに気付くでしょう。この関数は、Wikipedia の疑似コードを翻訳したものです。実際、プログラムで別の関数を使用していますが、上記のようにどちらも正しく機能していません。
デバッグについて。この関数(すべてのデバッグ ステートメントを含む元の関数) を見ると、デバッグ メッセージを出力していることがわかります。デバッグ トレースのこの部分は、問題の頂点に属しています。
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