I don't get why flags for table entries are used as they are. Consider e.g. the pseudocode for Negamax with alpha-beta pruning and transposition tables and concentrate on the TT parts.
(* Transposition Table Lookup; node is the lookup key for ttEntry *)
ttEntry := transpositionTableLookup(node)
if ttEntry is valid and ttEntry.depth ≥ depth then
if ttEntry.flag = EXACT then
return ttEntry.value
else if ttEntry.flag = LOWERBOUND then
α := max(α, ttEntry.value)
else if ttEntry.flag = UPPERBOUND then
β := min(β, ttEntry.value)
if α ≥ β then
return ttEntry.value
That's OK. If entry contains the lower bound of the exact value we try to shrink the window from the left, etc.
(* Transposition Table Store; node is the lookup key for ttEntry *)
ttEntry.value := value
if value ≤ alphaOrig then
ttEntry.flag := UPPERBOUND
else if value ≥ β then
ttEntry.flag := LOWERBOUND
else
ttEntry.flag := EXACT
ttEntry.depth := depth
transpositionTableStore(node, ttEntry)
And this part I don't understand. Why we set UPPERBOUND flag if value was too small? value is on the left side of the search window -- it's smaller than the known lower bound -- alpha. So it seems that value should be a LOWERBOUND.
I'm certainly wrong with that logic, as it seen from my tests and the fact that everyone using that version. But I don't get why.
On the second thought, the question is trivial :)
Indeed, if the child node value was too good to cause a beta-cutoff (value ≥ β), it means that parent node has move that is at lest good as value, but maybe there are some even better move. So the value is the LOWERBOUND for the exact node value.
value ≤ alphaOrig means that all moves was worse than alphaOrig. That means that value is the UPPERBOUND of consequences of all moves.
Lower and Upper are bounds of the value of the current node, not the root one, as I somehow implied.