Negamax

From Wikipedia, the free encyclopedia

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

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 adversary search engines are coded using some form of negamax search.

Pseudocode for depth-limited negamax search with alpha-beta pruning:

function negamax(node, depth, α, β)
    if node is a terminal node or depth = 0
        return the heuristic value of node
    else
        foreach child of node
            α := max(α, -negamax(child, depth-1, -β, -α))
            {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.