Negamax
Negamax search is a variant form of minimax search that relies on the zero-sum property of a two-player game.
This algorithm relies on the fact that max(a, b) = -min(-a, -b) to simplify the implementation of the minimax algorithm. More precisely, the value of a position to player A in such a game is the negation of the value to player B. Thus, the player on move looks for a move that maximizes the negation of the value of the position resulting from the move: this successor position must by definition have been valued by the opponent. The reasoning of the previous sentence works regardless of whether A or B is on move. This means that a single procedure can be used to value both positions. This is a coding simplification over minimax, which requires that A select the move with the maximum-valued successor while B selects the move with the minimum-valued successor.
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. Note that alpha-beta pruning is itself a way to compute the minimax or negamax value of a position quickly by avoiding the search of certain uninteresting positions.
Most adversarial search engines are coded using some form of negamax search.
NegaMax Base Algorithm
NegaMax searches operate on the same game trees as those used with the minimax search algorithm. Each node and root node in the tree are game states (such as game board configuration) of a two player game. Transitions to child nodes represent moves available to a player who's about to play from a given node.
The negamax search objective is to find the node score value, and hence the best move, for the player that's playing at the root node. The pseudocode below shows the negamax base algorithm,[1] with a configurable limit for the maximum search depth:
function negamax(node, depth, color)
if depth = 0 or node is a terminal node
return color * the heuristic value of node
bestValue := -∞
foreach child of node
val := -negamax(child, depth - 1, -color)
bestValue := max( bestValue, val )
return bestValue
Initial call for Player A's root node
rootNodeValue := negamax( rootNode, depth, 1)
Initial call for Player B's root node
rootNodeValue := -negamax( rootNode, depth, -1)
What can be confusing is how the heuristic value of the current node is calculated. In this implementation, this value is always calculated from the point of view of player A, whose color value is one. In other words, higher heuristic values always represent situations more favorable for player A. This is the same behavior as the normal minimax algorithm. Note this heuristic value is not necessarily the same as a node's return value, bestValue, due to value negation by negamax and the color parameter. The node's return value is from the point of view of the node's current player, who may be either the minimizing player B or maximizing player A in the minimax equivalent.
Variations in negamax implementations sometimes omit the color parameter. In this case, the heuristic evaluation function must return values from the point of view of the node's current player.
NegaMax with Alpha Beta Pruning
Algorithm optimizations for minimax are also equally applicable for Negamax. Alpha-beta pruning can decrease the number of nodes the negamax algorithm evaluates in a search tree in a manner similar with its use with the minimax algorithm.
The pseudocode for depth-limited negamax search with alpha-beta pruning follows:[1]
function negamax(node, depth, α, β, color)
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
val := -negamax(child, depth - 1, -β, -α, -color)
bestValue := max( bestValue, val )
α := max( α, val );
if α ≥ β
break
return bestValue
Initial call for Player A's root node
rootNodeValue := negamax( rootNode, depth, -∞, +∞, 1)
Initial call for Player B's root node
rootNodeValue := -negamax( rootNode, depth, -∞, +∞, -1)
When called, the arguments α and β should be set to the lowest and highest values possible.
This implementation includes optional move ordering prior to the foreach loop that evaluates child nodes. Move ordering[2] is an optimization for alpha beta pruning that attempts to guess the most probable child nodes that yield the node's score. The algorithm searches those child nodes first. The result of good guesses is earlier and more frequent alpha/beta cutoffs occur, thereby pruning additional game tree branches and remaining child nodes from the search tree.
NegaMax with Alpha Beta Pruning and Transposition Tables
Transposition tables selectively memorizes the values of nodes in the game tree. Transposition is a term reference that a given game board position can be reached in more than one way with differing game move sequences.
When negamax searches the game tree, and encounters the same node multiple times, a transposition table can return a previously computed value of the node, skipping potentially lengthy and duplicate re-computation of the node's value. 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:
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
val := -negamax(child, depth - 1, -β, -α, -color)
bestValue := max( bestValue, val )
α := max( α, val );
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
Initial call for Player A's root node
rootNodeValue := negamax( rootNode, depth, -∞, +∞, 1)
Initial call for Player B's root node
rootNodeValue := -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's insufficient to track only the node's bestValue in the table, because bestValue may not be the node's true value. The code therefore must preserve and restore the relationship of bestValue 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 game tree nodes often far exceed the table size. Lost or omitted table entries are non critical and won't affect the negamax result. However, lost entries may require negamax to re-compute certain game tree node values more frequently, thus affecting performance.
References
- George T. Heineman, Gary Pollice, and Stanley Selkow (2008). "Chapter 7:Path Finding in AI". Algorithms in a Nutshell. Oreilly Media. pp. 213–217. ISBN 978-0-596-51624-6.
- ↑ 1.0 1.1 Breuker, Dennis M. Memory versus Search in Games, Maastricht University, October 16, 1998
- ↑ Schaeffer, Jonathan The History Heuristic and Alpha-Beta Search Enhancements in Practice, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989