BFMAX (Node, Alpha, Beta)
FOR each Child[i] of Node
M[i] := Evaluation(Child[i] >
IF M[i] > Beta return M[i]
SORT Child[i] and M[i] in decreasing order
IF only one child, M[2] := -infinity
WHILE Alpha <= M[i] <= Beta
M[l] := BFMIN(Child[l],max(Alpha,M[2]),Beta)
insert Child[l] and M[l] in sorted order
return M[l]
BFMIN (Node, Alpha, Beta)
FOR each Child[i] of Node
M[i] := Evaluation(Child[i])
IF M[i] < Alpha return M[i]
SORT Child[i] and M[i] in increasing order
IF only one child, M[2] := infinity
WHILE Alpha <= MCI] <= Beta
MC[1] := BFMAX(Child[l],Alpha,min(Beta,M[2]))
insert Child[l] and M[l] in sorted order
return M[l]
BFnega(Node, Alpha,Beta)
FOR each Child[i] of Node
M[i] := Evaluation(Child[i] >
IF M[i] > Beta return M[i]
SORT Child[i] and M[i] in decreasing order
IF only one child, M[2] := -infinity
WHILE Alpha <= M[i] <= Beta
M[l] := -BFMIN(Child[l],-Beta, -(max(Alpha,M[2])))
insert Child[l] and M[l] in sorted order
return M[l]
// iterative version in pseudo code
depth = 1;
alpha[0] = -INF;
beta[0] = INF;
node = root;
n = node.children; // children is -1 when unexplored
while(n > 0) {
// select best child and score
score = -INF
for each node.child as child {
tmp = -child.score
if (tmp > score) {
score = tmp;
best = child;
}
}
node.score = score;
// check beta
if ( score > beta[depth-1]) {
// go back in tree
node = node.parent;
depth--;
}
else {
// get second best score
score = -INF
for each node.child as child {
if (child == best)
continue;
tmp = -child.score
if (tmp > score) {
score = tmp;
}
}
// set alpha
alpha[depth] = -beta[depth-1];
// set beta
beta[depth] = (score > alpha[depth-1])? -score : -alpha[depth-1];
depth++;
node = best;
}
n = node.children;
}
Not sure, but I could imagine that you restart the parent node search from scratch after a beta cutoff since you don't remember which children were already processed.
I also do not understand your pre-loop initialization. Your comment "children is -1 when unexplored" would prevent the "while(n>0)" loop from even starting, since -1 is not >0 ?? So it would mean that the root node is not "unexplored" in the beginning.
I guess you also need something like childIndex[depth] running within the range [0 .. node.children - 1] for each depth. Within the loop you might further need to distinguish between "processing after depth++" (enter a new subtree) and "processing after depth--" (select next sibling of parent).
Sven Schüle wrote:Not sure, but I could imagine that you restart the parent node search from scratch after a beta cutoff since you don't remember which children were already processed.
It seems that is the inherent overhead of the algorithm, and it should not cause any hanging in a loop. So maybe there is something else around ...
I currently wonder how you realize the sorting that was present in the recursive version.
Sven Schüle wrote:Not sure, but I could imagine that you restart the parent node search from scratch after a beta cutoff since you don't remember which children were already processed.
It seems that is the inherent overhead of the algorithm, and it should not cause any hanging in a loop. So maybe there is something else around ...
I currently wonder how you realize the sorting that was present in the recursive version.
Sven
Even the recursive version does not always terminate. If your Evaluation() never returns a value outside of the Alpha/Beta window given at the root node then it will loop forever. I quickly implemented your BFnega() function above to check this. It is possible that the iterative version suffers from the same problem.
Btw, the way how scores are checked against Alpha/Beta looks dubious, already in the original document. A score is inside the window if it is > Alpha and < Beta, the authors used some >=/<= that appears to be wrong. But that is more a minor issue compared to the "termination" problem.
The algorithm also does not mention how to stop at a maximum depth.