Negamax

It should not be confused with negascout, an algorithm to compute the minimax or negamax value quickly by clever use of alpha–beta pruning discovered in the 1980s.

In this case, the heuristic evaluation function must return values from the point of view of the node's current player (Ex: In a chess game, if it is white's turn and white is winning, it should return a positive value.

The pseudocode for depth-limited negamax search with alpha–beta pruning follows:[1] Alpha (α) and beta (β) represent lower and upper bounds for child node values at a given tree depth.

Negamax sets the arguments α and β for the root node to the lowest and highest values possible.

This value is identical to the result the negamax base algorithm would return, without cut offs and without any α and β bounds.

Thus, a node value may be outside the initial α and β range bounds set with a negamax function call.

In contrast, fail-hard alpha–beta pruning always limits a node value in the range of α and β.

This implementation also shows optional move ordering prior to the foreach loop that evaluates child nodes.

Negamax performance improves particularly for game trees with many paths that lead to a given node in common.

The pseudo code that adds transposition table functions to negamax with alpha/beta pruning is given as follows:[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.

The code therefore must preserve and restore the relationship of value with alpha/beta parameters and the search depth for each transposition table entry.

This is necessary since the number of nodes negamax visits often far exceeds the transposition table size.

However, lost entries may require negamax to re-compute certain game tree node values more frequently, thus affecting performance.