Negascout
Encyclopedia
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
. It dominates alpha-beta pruning in the sense that it will never examine a node that can be pruned by alpha-beta; however it relies on accurate move ordering to capitalize on this advantage.
NegaScout works best when there is a good move ordering. In practice, the move ordering is often determined by previous shallower searches. It produces more cutoffs than alpha-beta by assuming that the first explored node is the best. In other words, it supposes the first node is in the principal variation
. Then, it can check whether that is true by searching the remaining nodes with a null window (also known as a scout window; when alpha and beta are equal), which is faster than searching with the regular alpha-beta window. If the proof fails, then the first node was not in the principal variation, and the search continues as normal alpha-beta. Hence, NegaScout works best when the move ordering is good. With a random move ordering, NegaScout will take more time than regular alpha-beta; although it will not explore any nodes alpha-beta did not, it will have to re-search many nodes.
In chess
engines, NegaScout has typically given a 10 percent performance increase.
Alexander Reinefeld
invented NegaScout several decades after the invention of alpha-beta pruning. He gives a proof of correctness of NegaScout in his book.
Another search algorithm called MTD(f) can theoretically result in even fewer nodes searched. However it has practical issues (in particular, it relies heavily on the transposition table
) and nowadays most chess engines still use a form of NegaScout in their search. Yet another search algorithm which tends to do better than NegaScout in practice is the best-first algorithm called SSS*, although neither algorithm dominates the other. There are trees in which NegaScout searches fewer nodes than SSS* and vice-versa. However, note that SSS* is not a depth-first search and thus has larger memory requirements.
Pseudocode
function negascout(node, depth, α, β)
if node is a terminal node or depth = 0
return the heuristic value of node
b := β (* initial window is (-β, -α) *)
foreach child of node
score := -negascout (child, depth - 1, -b, -α)
if α < score < β and child is not first child (* check if null-window failed high *)
score := -negascout(child, depth - 1, -β, -α) (* full re-search *)
α := max(α, score)
if α ≥ β
return α (* Beta cut-off *)
b := α + 1 (* set new null window *)
return α
Negamax
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 = -min to simplify the implementation of the minimax algorithm. More precisely, the value of a position to player A in such...
algorithm that can be faster than 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...
. Like alpha-beta pruning, NegaScout is a directional search algorithm for computing 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...
value of a node in a tree
Tree
A tree is a perennial woody plant. It is most often defined as a woody plant that has many secondary branches supported clear of the ground on a single main stem or trunk with clear apical dominance. A minimum height specification at maturity is cited by some authors, varying from 3 m to...
. It dominates alpha-beta pruning in the sense that it will never examine a node that can be pruned by alpha-beta; however it relies on accurate move ordering to capitalize on this advantage.
NegaScout works best when there is a good move ordering. In practice, the move ordering is often determined by previous shallower searches. It produces more cutoffs than alpha-beta by assuming that the first explored node is the best. In other words, it supposes the first node is in the principal variation
Variation (game tree)
A Variation can refer to a specific sequence of successive moves in a turn-based game, often used to specify a hypothetical future state of a game that is being played. Although the term is most commonly used in the context of Chess analysis, it has been applied to other games...
. Then, it can check whether that is true by searching the remaining nodes with a null window (also known as a scout window; when alpha and beta are equal), which is faster than searching with the regular alpha-beta window. If the proof fails, then the first node was not in the principal variation, and the search continues as normal alpha-beta. Hence, NegaScout works best when the move ordering is good. With a random move ordering, NegaScout will take more time than regular alpha-beta; although it will not explore any nodes alpha-beta did not, it will have to re-search many nodes.
In chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
engines, NegaScout has typically given a 10 percent performance increase.
Alexander Reinefeld
Alexander Reinefeld
Alexander Reinefeld is the head of computer science at Zuse Institute Berlin. His contributions to the field include the NegaScout algorithm.-External links:*Alexander Reinefeld's ....
invented NegaScout several decades after the invention of alpha-beta pruning. He gives a proof of correctness of NegaScout in his book.
Another search algorithm called MTD(f) can theoretically result in even fewer nodes searched. However it has practical issues (in particular, it relies heavily on the transposition table
Transposition table
In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. Transposition tables are primarily useful in perfect information games, meaning the entire state of the game is known to all players at all times....
) and nowadays most chess engines still use a form of NegaScout in their search. Yet another search algorithm which tends to do better than NegaScout in practice is the best-first algorithm called SSS*, although neither algorithm dominates the other. There are trees in which NegaScout searches fewer nodes than SSS* and vice-versa. However, note that SSS* is not a depth-first search and thus has larger memory requirements.
PseudocodePseudocodeIn 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...
function negascout(node, depth, α, β)if node is a terminal node or depth = 0
return the heuristic value of node
b := β (* initial window is (-β, -α) *)
foreach child of node
score := -negascout (child, depth - 1, -b, -α)
if α < score < β and child is not first child (* check if null-window failed high *)
score := -negascout(child, depth - 1, -β, -α) (* full re-search *)
α := max(α, score)
if α ≥ β
return α (* Beta cut-off *)
b := α + 1 (* set new null window *)
return α