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 min ( a , b ) = − max ( − b , − a ) {\displaystyle \min(a,b)=-\max(-b,-a)} 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 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 selects 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 operates 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 is about to play from a given node. The negamax search objective is to find the node score value for the player who is playing at the root node. The pseudocode below shows the negamax base algorithm, with a configurable limit for the maximum search depth:
function negamax(node, depth, color) is if depth = 0 or node is a terminal node then return color × the heuristic value of node value := −∞ for each child of node do value := max(value, −negamax(child, depth − 1, −color)) return value
(* Initial call for Player A's root node *) negamax(rootNode, depth, 1)
(* Initial call for Player B's root node *) negamax(rootNode, depth, −1)
The root node inherits its score from one of its immediate child nodes. The child node that ultimately sets the root node's best score also represents the best move to play. Although the negamax function shown only returns the node's best score, practical negamax implementations will retain and return both best move and best score for the root node. Only the node's best score is essential with non-root nodes. And a node's best move isn't necessary to retain nor return for non-root nodes. 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. The heuristic value is not necessarily the same as a node's return value due to value negation by negamax and the color parameter. The negamax node's return value is a heuristic score from the point of view of the node's current player. Negamax scores match minimax scores for nodes where player A is about to play, and where player A is the maximizing player in the minimax equivalent. Negamax always searches for the maximum value for all its nodes. Hence for player B nodes, the minimax score is a negation of its negamax score. Player B is the minimizing player in the minimax equivalent.
Negamax variant with no color parameter Negamax can be implemented without the color parameter. In this case, the heuristic evaluation function must return values from the point of view of the node's current player rather than an absolute score. For example, the heuristic evaluation function in chess should return a positive value if the current node's player is black and black is winning.
function negamax(node, depth) is if depth = 0 or node is a terminal node then return evaluatePosition() // From current player's perspective value := −∞ for each child of node do value := max(value, −negamax(child, depth − 1)) return value
// Example picking best move in a chess game using negamax function above function think(boardState) is allMoves := generateLegalMoves(boardState) bestMove := null bestEvaluation := -∞
for each move in allMoves board.apply(move) evaluateMove := -negamax(boardState, depth=3) board.undo(move) if evaluateMove > bestEvaluation bestMove := move bestEvaluation := evaluateMove
return bestMove
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:
function negamax(node, depth, α, β, color) is if depth = 0 or node is a terminal node then return color × the heuristic value of node
childNodes := generateMoves(node) childNodes := orderMoves(childNodes) value := −∞ foreach child in childNodes do value := max(value, −negamax(child, depth − 1, −β, −α, −color)) α := max(α, value) if α ≥ β then break (* cut-off *) return value
(* Initial call for Player A's root node *) negamax(rootNode, depth, −∞, +∞, 1)
… excerpt ends here. Continue reading the full article.
