javascriptchessalpha-beta-pruning

How to implement transposition tables with alpha beta pruning


I'm trying to make an implementation of transposition tables in my negamax. But first I want to understand all of the ideas in the pseudo code:

` function negamax(node, depth, α, β, color) is alphaOrig := α

(* 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

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

childNodes := generateMoves(node)
childNodes := orderMoves(childNodes)
value := −∞
for each child in childNodes do
    value := max(value, −negamax(child, depth − 1, −β, −α, −color))
    α := max(α, value)
    if α ≥ β then
        break

(* 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)

return value

But one thing I want to know is what is the flags? Like EXACT, UPPERBOUND, and LOWERBOUND?


Solution

  • In a Negamax search with alpha beta you typically start with an infinite window (alpha=-inf, beta=inf). Then during search this window is narrowed due to the cut offs, which leads to either raising alpha, or lowering beta.

    The flags indicate which type of node you have found. If you found a node within your search window (alpha < score < beta) this means you have an EXACT node. Lower bound means that score >= beta, and upper bound that the score <= alpha.

    You can read more about it here, which is also a good page for finding all you need for chess programming.