Negamax

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)

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.

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.