Negamax

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (December 2009)

Negamax search is a slightly variant formulation of minimax search that relies on the zero-sum property of a two-player game.

An animated pedagogical example showing the plain negamax algorithm (that is, without alpha-beta pruning). The person performing the game tree search is considered to be the one that has to move first from the current state of the game (player in this case)

An animated pedagogical example showing the negamax algorithm with alpha-beta pruning. The person performing the game tree search is considered to be the one that has to move first from the current state of the game (player in this case)

By definition 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 computation can be used to value all 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, which is a modern variation of alpha-beta pruning discovered in the 1980s, alpha-beta pruning itself being a more advanced form of minimax or negamax.

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 α≥β
                return α
        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)