Transpositional tables with alpha beta pruning

Question

I'm trying to implement the alpha beta pruning with transpositional tables, I found the pseudocode of the algorithm in wikipedia: https://en.wikipedia.org/wiki/Negamax#cite_note-Breuker-1 However I belive that this psudocode is wrong, I think that alphaOrig is useless and instead of:

if bestValue ≤ alphaOrig
        ttEntry.Flag := UPPERBOUND

It should be:

if bestValue ≤ α
        ttEntry.Flag := UPPERBOUND

Can anyone confirm if I'm right or explain to me why I'm wrong, thanks!

Here the pseudocode:

function negamax(node, depth, α, β, color)

alphaOrig := α

// Transposition Table Lookup; node is the lookup key for ttEntry
ttEntry := TranspositionTableLookup( node )
if ttEntry is valid and ttEntry.depth ≥ depth
    if ttEntry.Flag = EXACT
        return ttEntry.Value
    else if ttEntry.Flag = LOWERBOUND
        α := max( α, ttEntry.Value)
    else if ttEntry.Flag = UPPERBOUND
        β := min( β, ttEntry.Value)
    endif
    if α ≥ β
        return ttEntry.Value
endif

if depth = 0 or node is a terminal node
    return color * the heuristic value of node

bestValue := -∞
childNodes := GenerateMoves(node)
childNodes := OrderMoves(childNodes)
foreach child in childNodes
    v := -negamax(child, depth - 1, -β, -α, -color)
    bestValue := max( bestValue, v )
    α := max( α, v )
    if α ≥ β
        break

// Transposition Table Store; node is the lookup key for ttEntry
ttEntry.Value := bestValue
if bestValue ≤ alphaOrig
    ttEntry.Flag := UPPERBOUND
else if bestValue ≥ β
    ttEntry.Flag := LOWERBOUND
else
    ttEntry.Flag := EXACT
endif
ttEntry.depth := depth 
TranspositionTableStore( node, ttEntry )

return bestValue

Warfold

Answer 1

There are different implementations for alpha beta pruning with transposition tables available. For example the one from Marsland: A REVIEW OF GAME-TREE PRUNING, Breuker: Memory versus Search in Games and Carolus: Alpha-Beta with Sibling Prediction Pruning in Chess

For my answer I will quote a snippet of the Talk:Negamax page:

Marsland transposition table logic is equivalent when alphaOrig in Breuker stores α after the transposition table lookup (rather than before). But consider the following case during a negamax function call:

• transposition table lookup updates α because it's a "lower bound" (Breuker: alphaOrig < α Marsland: alphaOrig = α)
• the move evaluation returns the same as unchanged α for bestValue (score)
• update the node's transposition table entry with the same bestValue (score)

In Breuker's logic, the node's transposition table entry will update with "exact" flag (since alphaOrig < bestValue < β). In Marsland, the update will have "upper bound" flag (since score ≤ α). Optimally, the flag for the score should be "exact" rather than alternating between upper and lower bound. So I think Breuker's version is better? In Carolus, there's no alphaOrig and no equivalent. alpha updates during move evaluation. In this case, after move evaluation, best can never be greater than alpha, and setting "exact" flag for the transposition table entry is impossible.

There are even more discussion about this on the talk page of the Negamax article.

Isodiametric