pseudo code that adds transposition table functions to negamax with alpha/beta pruning is given as follows: 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 (* Initial call for Player A's root node *) negamax(rootNode, depth, −∞, +∞, 1) Alpha/beta pruning and maximum search depth constraints in negamax can result in partial, inexact, and entirely skipped evaluation of nodes in a game tree. This complicates adding transposition table optimizations for negamax. It is insufficient to track only the node's value in the table, because value may not be the node's true value. The code therefore must preserve and restore the relationship of value with alpha/beta parameters and the search depth for each transposition table entry. Transposition tables are typically lossy and will omit or overwrite previous values of certain game tree nodes in its tables. This is necessary since the number of nodes negamax visits often far exceeds the transposition table size. Lost or omitted table entries are non-critical and will not affect the negamax result. However, lost entries may require negamax to re-compute certain game tree node values more frequently, thus affecting performance. References External links Negamax at the Chess Programming Wiki A C99 implementation of the Negamax algorithm for the Tic-Tac-Toe game Game artificial intelligence Optimization algorithms and methods Articles with example pseudocode