Negamax
Encyclopedia
Negamax search is a slightly variant formulation of minimax
search that relies on the zero-sum property of a two-player game
.
This algorithm heavily 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.
Pseudocode
for depth-limited negamax search with alpha-beta pruning:
function negamax(node, depth, α, β, color)
if node is a terminal node or depth = 0
return color * the heuristic value of node
else
foreach child of node
α := max(α, -negamax(child, depth-1, -β, -α, -color))
{the following if statement constitutes alpha-beta pruning}
if α≥β
break
return α
When called, the arguments α and β should be set to the lowest and highest values possible for any node and color should be set to 1.
(* Initial call *)
negamax(origin, depth, -inf, +inf, 1)
What can be confusing for beginners is how the heuristic value of the current node is calculated. In this implementation, the value is always calculated from the point of view of the player running the algorithm because of the color parameter. This is the same behavior as the normal minimax
algorithm. If this parameter was not present, the evaluation function would need to return a score for the current player, i.e. the min or max player.
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
search that relies on the zero-sum property of a two-player game
Two-player game
A two-player game is a game played by just two players. This is distinct from a solitaire game which is played by only one player, or a multiplayer game played by more than two players. Two unofficial but logical ways of grouping and categorizing games could be by Type and by what it is Based In,...
.
This algorithm heavily relies on the fact that max(a, b) = -min(-a, -b) to simplify the implementation of the minimax
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
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
Negascout
NegaScout or Principal Variation Search is a negamax algorithm that can be faster than alpha-beta pruning. Like alpha-beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree...
, an algorithm to compute the minimax or negamax value quickly by clever use of alpha-beta pruning
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
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.
Pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
for depth-limited negamax search with alpha-beta pruning:
function negamax(node, depth, α, β, color)
if node is a terminal node or depth = 0
return color * the heuristic value of node
else
foreach child of node
α := max(α, -negamax(child, depth-1, -β, -α, -color))
{the following if statement constitutes alpha-beta pruning}
if α≥β
break
return α
When called, the arguments α and β should be set to the lowest and highest values possible for any node and color should be set to 1.
(* Initial call *)
negamax(origin, depth, -inf, +inf, 1)
What can be confusing for beginners is how the heuristic value of the current node is calculated. In this implementation, the value is always calculated from the point of view of the player running the algorithm because of the color parameter. This is the same behavior as the normal minimax
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
algorithm. If this parameter was not present, the evaluation function would need to return a score for the current player, i.e. the min or max player.