An upper/lower lower/upper kind of question

[FMonkman]

Here's a source of confusion, and looking round the web (at some quite learned-seeming papers too) I get the impression I'm not the only one suffering from it. It starts with the fact that, while Alpha (to take one example) is a Lower Bound, a fail-low or alpha cutoff is an *upper bound* type of cutoff (in other words, an upper bound to the Lower Bound, and of course the converse).

Take the following two pseudocode extracts from Aske Plaat's admirable summary:

[1]
function MTDF(root : node_type; f : integer; d : integer) : integer;

g := f;
upperbound := +INFINITY; ////////////////////// NB1
lowerbound := -INFINITY;

repeat
if g == lowerbound then beta := g + 1 else beta := g;
g := AlphaBetaWithMemory(root, beta - 1, beta, d);
if g < beta then upperbound := g else lowerbound := g;
until lowerbound >= upperbound;
return g;

[2]
function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) : integer;

if retrieve(n) == OK then /* Transposition table lookup */
if n.lowerbound >= beta then return n.lowerbound;
if n.upperbound <= alpha then return n.upperbound;
alpha := max(alpha, n.lowerbound);
beta := min(beta, n.upperbound);
if d == 0 then g := evaluate(n); /* leaf node */
else if n == MAXNODE then
g := -INFINITY; a := alpha; /* save original alpha value */
c := firstchild(n);
while (g < beta) and (c != NOCHILD) do
g := max(g, AlphaBetaWithMemory(c, a, beta, d - 1));
a := max(a, g);
c := nextbrother(c);
else /* n is a MINNODE */
g := +INFINITY; b := beta; /* save original beta value */
c := firstchild(n);
while (g > alpha) and (c != NOCHILD) do
g := min(g, AlphaBetaWithMemory(c, alpha, b, d - 1));
b := min(b, g);
c := nextbrother(c);
/* Traditional transposition table storing of bounds */
/* Fail low result implies an upper bound */ ///////////////////////// NB2
if g <= alpha then n.upperbound := g; store n.upperbound;
/* Found an accurate minimax value - will not occur if called with zero window */
if g > alpha and g < beta then
n.lowerbound := g; n.upperbound := g; store n.lowerbound, n.upperbound;
/* Fail high result implies a lower bound */
if g >= beta then n.lowerbound := g; store n.lowerbound;
return g;

Clearly, 'upperbound' and 'lowerbound' are being used with different meanings in the two functions. The MT driver refers to upperbound as, literally an Upper Bound, while the AlphaBetaWithMemory function clearly states "Fail low result implies an upper bound", and implements accordingly. All of which (given the caveat above) is fine, until we look at lines 5ff of the latter code block:

alpha := max(alpha, n.lowerbound);
beta := min(beta, n.upperbound);

Hasn't he totally confused the issue here by reverting to the opposite meanings of upper and lower *as used in the driver*? Or am I the one totally confused?? )

I've mailed AP, but with no reply so far... anyone else who can shed light here, do please!

Francis

[hgm]

I never saw anything confusing in this. A score obtained from a fail-low search is an upperbound to the true score, and stored under that name in the hash table. In the driver routine the variable 'upperbound' is also an upperbound to the true score.

I guess it is just a matter of realizing what is an upper-bound to what.

[FMonkman]

Thanks for the minimalist answer

However, fails to address a) my point about possible (and extant - see below) confusion between bounds to windows and bounds to scores, and b) why would anyone want to max alpha with a previously-stored hashentry of type *lowerbound* (ie specifically derived from a value >= beta)?

from Aske Plaat's ABWM function:

ln.5 alpha := max(alpha, n.lowerbound);
ln.29 if g >= beta then n.lowerbound := g; store n.lowerbound;

as an example of a) [randomly gleaned from web, possibly derived from above, although this author is using ht val to set bounds only]

int NegaMax(Position P, int depth, int alpha, int beta) {
if(depth<=0) {
return QuiescenceSearch(P, alpha, beta); // For some games, simply return the static evaluation here
}

// Look this position up in the hash table
HashEntry hash_entry;
bool hash_hit=query_hash(b.hash_key(), &hash_entry);
if(hash_hit && hash_entry.depth>=depth){
switch(hash_entry.score_type){
case lower_bound:
if(alpha<hash_entry.score)
alpha=hash_entry.score;
break;
case upper_bound:
if(beta>hash_entry.score)
beta=hash_entry.score;
break;
case exact_score:
return hash_entry.score;
}
if(alpha>=beta)
return hash_entry.score;
}

// ... continue search normally

}

Actually, Wikispace pinpoints the problem without too much fuss

Alpha is an Lower Bound of a score for this node.
A Lower Bound is returned from an Alpha-Beta like search, if it fails high [NB beta cutoff].

[Bo Persson]

Thanks for the minimalist answer

However, fails to address a) my point about possible (and extant - see below) confusion between bounds to windows and bounds to scores, and b) why would anyone want to max alpha with a previously-stored hashentry of type *lowerbound* (ie specifically derived from a value >= beta)?

from Aske Plaat's ABWM function:

ln.5 alpha := max(alpha, n.lowerbound);

Why not?

If alpha is less than a known lower bound, it obviously is too low - let's raise it!

[FMonkman]

Got it

The code problem only arises when you store two values in the ht (as should Plaat, because he's retrieving two). The real problem is that although both may be accessed (which we must assume since there's no way of foretelling the alpha and beta values current next time the ht is read, so we can't predict for sure that either cutoff will necessarily have happened), no lowerbound is being written in the case of an upperbound cutoff and vice versa, in Plaat's code as it stands. So in the event of a beta cutoff, n.upperbound should be written as, say +WIN etc. Does that seem right?

if g <= alpha then n.upperbound := g; store n.upperbound; // must store a lowerbound -WIN
/* Found an accurate minimax value - will not occur if called with zero window */
if g > alpha and g < beta then
n.lowerbound := g; n.upperbound := g; store n.lowerbound, n.upperbound;
/* Fail high result implies a lower bound */
if g >= beta then n.lowerbound := g; store n.lowerbound; // store n.upperbound +WIN

All of which presumably implies there's no point storing two values in ht...?

[bob]

Here's a source of confusion, and looking round the web (at some quite learned-seeming papers too) I get the impression I'm not the only one suffering from it. It starts with the fact that, while Alpha (to take one example) is a Lower Bound, a fail-low or alpha cutoff is an *upper bound* type of cutoff (in other words, an upper bound to the Lower Bound, and of course the converse).

Take the following two pseudocode extracts from Aske Plaat's admirable summary:

[1]
function MTDF(root : node_type; f : integer; d : integer) : integer;

g := f;
upperbound := +INFINITY; ////////////////////// NB1
lowerbound := -INFINITY;

repeat
if g == lowerbound then beta := g + 1 else beta := g;
g := AlphaBetaWithMemory(root, beta - 1, beta, d);
if g < beta then upperbound := g else lowerbound := g;
until lowerbound >= upperbound;
return g;

[2]
function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) : integer;

if retrieve(n) == OK then /* Transposition table lookup */
if n.lowerbound >= beta then return n.lowerbound;
if n.upperbound <= alpha then return n.upperbound;
alpha := max(alpha, n.lowerbound);
beta := min(beta, n.upperbound);
if d == 0 then g := evaluate(n); /* leaf node */
else if n == MAXNODE then
g := -INFINITY; a := alpha; /* save original alpha value */
c := firstchild(n);
while (g < beta) and (c != NOCHILD) do
g := max(g, AlphaBetaWithMemory(c, a, beta, d - 1));
a := max(a, g);
c := nextbrother(c);
else /* n is a MINNODE */
g := +INFINITY; b := beta; /* save original beta value */
c := firstchild(n);
while (g > alpha) and (c != NOCHILD) do
g := min(g, AlphaBetaWithMemory(c, alpha, b, d - 1));
b := min(b, g);
c := nextbrother(c);
/* Traditional transposition table storing of bounds */
/* Fail low result implies an upper bound */ ///////////////////////// NB2
if g <= alpha then n.upperbound := g; store n.upperbound;
/* Found an accurate minimax value - will not occur if called with zero window */
if g > alpha and g < beta then
n.lowerbound := g; n.upperbound := g; store n.lowerbound, n.upperbound;
/* Fail high result implies a lower bound */
if g >= beta then n.lowerbound := g; store n.lowerbound;
return g;

Clearly, 'upperbound' and 'lowerbound' are being used with different meanings in the two functions. The MT driver refers to upperbound as, literally an Upper Bound, while the AlphaBetaWithMemory function clearly states "Fail low result implies an upper bound", and implements accordingly. All of which (given the caveat above) is fine, until we look at lines 5ff of the latter code block:

alpha := max(alpha, n.lowerbound);
beta := min(beta, n.upperbound);

Hasn't he totally confused the issue here by reverting to the opposite meanings of upper and lower *as used in the driver*? Or am I the one totally confused?? )

I've mailed AP, but with no reply so far... anyone else who can shed light here, do please!

Francis

If you think about it for a minute, this is a logical way of doing things. When you get an alpha cutoff, you know that the score is guaranteed to be <= alpha, but you don't know how low it really is. All you know is that alpha is the "upper bound" on the score but that it is most likely lower.

When you get a beta cutoff, you know that the score is >= beta, So in the same sense, beta is a lower bound on the score that is probably even higher.

It has always seemed quite normal, once you think about it. But it can be confusing when you first encounter the discussion with no explanation...

[FMonkman]

Hi Bob - and just when I thought I'd worked it out!

Actually, in the meantime I arrived at the following:

With a beta cutoff, the code terminates (and with it my thinking about what really happens). I'd always thought that a beta cutoff (if one continued searching the node) would reset *beta*, but I see that's nonsense - it's alpha which now goes above beta, so 'lower bound' is consistent. Of course this implies beta is also to be reset, and in the case of code (like Plaat's) which stores two values to hash (setting lower == upper to indicate exact) a 'new beta' would probably need to be set +WIN, in order to avoid masking, say, a new search with a win in 10 ply looking for better.

Apologies, 'alpha cutoff' is probably a misnomer (although I guess it becomes a beta ditto at the caller's ply), since it implies fail low after all moves searched. But conceptually, the inverse of the above works - it's beta which is now lower than alpha.

For the record, all this recent 'self-debugging' process started when I found that a PV hash 'loss in 10 ply' for the opponent was being masked out by the even-more-terrible alpha == -WIN, derived directly from 'root beta' - if there is such a thing - set blissfully to ultimate optimism

case upper_bound:
if(hashtable[stm][hk].eval <= alpha) // no way
return (hashtable[stm][hk].eval);

[hgm]

if g <= alpha then n.upperbound := g; store n.upperbound; // must store a lowerbound -WIN
/* Found an accurate minimax value - will not occur if called with zero window */
if g > alpha and g < beta then
n.lowerbound := g; n.upperbound := g; store n.lowerbound, n.upperbound;
/* Fail high result implies a lower bound */
if g >= beta then n.lowerbound := g; store n.lowerbound; // store n.upperbound +WIN

All of which presumably implies there's no point storing two values in ht...?

In MTD(f) there is very much point in storing, and keeping two values in the hash table. So in case of a beta cutoff you only get info on the lower-bound, and you should not touch the upper bound. Just leave it at the value it had from a previous search. It might be needed again in the next search.

The whole idea of MTD(f) is to perform bisection on the score range to zero in on the true score. And if your current null-window is below the score of a certain node (so it fails high), the next search the window might very well be above it, because the root score was also above the null-window, so we are raising it. In fact we might raise it so much that not only the true score, but even a previous upper bound is below the new null-window, so that the stored upper bound would be enough to cause a fail low without search.

The Plaat algorithm says "alphaBetaWithMemory", but relaxing the not-updated bound like you propose actually destroys that memory.

[bob]

Hi Bob - and just when I thought I'd worked it out!

Actually, in the meantime I arrived at the following:

With a beta cutoff, the code terminates (and with it my thinking about what really happens). I'd always thought that a beta cutoff (if one continued searching the node) would reset *beta*, but I see that's nonsense - it's alpha which now goes above beta, so 'lower bound' is consistent. Of course this implies beta is also to be reset, and in the case of code (like Plaat's) which stores two values to hash (setting lower == upper to indicate exact) a 'new beta' would probably need to be set +WIN, in order to avoid masking, say, a new search with a win in 10 ply looking for better.

Apologies, 'alpha cutoff' is probably a misnomer (although I guess it becomes a beta ditto at the caller's ply), since it implies fail low after all moves searched. But conceptually, the inverse of the above works - it's beta which is now lower than alpha.

For the record, all this recent 'self-debugging' process started when I found that a PV hash 'loss in 10 ply' for the opponent was being masked out by the even-more-terrible alpha == -WIN, derived directly from 'root beta' - if there is such a thing - set blissfully to ultimate optimism

case upper_bound:
if(hashtable[stm][hk].eval <= alpha) // no way
return (hashtable[stm][hk].eval);

Before hashing had been explained anywhere, back in the middle 70's when I added it to (at the time) Blitz, I used the opposite nomenclature as well. Because when I failed low I stored the entry as "lower bound". Meaning that this position failed on a lower bound. Others came along and used the current nomenclature instead, and when we had discussions about hashing, we had real confusion since we were using different terminology. After thinking about it for a while, I decided to "change" myself because although either terminology is usable, a common one is better for discussion.

Didn't take long for the "switch" to stick, and the terminology now doesn't bother me at all and since we can have discussions and understand each other, things are even better. There are several terms that get mis-used or abused, and therefore lead to arguments that are not really arguments when you understand the context of _both_ sides. But things like BF and EBF are important in many discussions and they are _not_ interchangable. So I am for a common vocabulary, which is why I didn't like the idea of "threads" or "processes" or "cores" to tell a program how many CPUs it should use. Some use threads. Some use processors. Some use CPUs. So far, nobody has used "cores". But if you jump into a discussion on parallel issues, threads or processes don't cause confusion since they are describing the same concept, but different methodologies...

Hope that helps. Sometimes it is better to use an existing term that you might not like (at first) in order to be able to communicate with others without massive confusion.

[FMonkman]

if g <= alpha then n.upperbound := g; store n.upperbound; // must store a lowerbound -WIN
/* Found an accurate minimax value - will not occur if called with zero window */
if g > alpha and g < beta then
n.lowerbound := g; n.upperbound := g; store n.lowerbound, n.upperbound;
/* Fail high result implies a lower bound */
if g >= beta then n.lowerbound := g; store n.lowerbound; // store n.upperbound +WIN

All of which presumably implies there's no point storing two values in ht...?

In MTD(f) there is very much point in storing, and keeping two values in the hash table. So in case of a beta cutoff you only get info on the lower-bound, and you should not touch the upper bound. Just leave it at the value it had from a previous search. It might be needed again in the next search.

The whole idea of MTD(f) is to perform bisection on the score range to zero in on the true score. And if your current null-window is below the score of a certain node (so it fails high), the next search the window might very well be above it, because the root score was also above the null-window, so we are raising it. In fact we might raise it so much that not only the true score, but even a previous upper bound is below the new null-window, so that the stored upper bound would be enough to cause a fail low without search.

The Plaat algorithm says "alphaBetaWithMemory", but relaxing the not-updated bound like you propose actually destroys that memory.

Thanks, interesting and useful. But the entries still have to be initialized, since otherwise one might be used with a spurious value, no?

alpha := max(alpha, n.lowerbound);
beta := min(beta, n.upperbound);

Let's say we call initially with firstguess == 0. Then say, we find +1 so fail high and store lb accordingly. But next search with a higher value window, we don't fail so we set bounds as above. Now, we're min'ing (sorry) beta with an unknown value..? Ah, of course, works okay with a null window which always fails one way or t'other - but presumably if one wanted to use ABWM with a wider window (I was assuming it would work generically) then the init. becomes important..?