Principal variation search (sometimes equated with the practically identical NegaScout) is a
negamax
Negamax search is a variant form of minimax search that relies on the Zero-sum (Game theory), zero-sum property of a two-player game.
This algorithm relies on the fact that to simplify the implementation of the minimax algorithm. More precisely, ...
algorithm that can be faster than
alpha–beta pruning
Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the Minimax#Minimax algorithm with alternate moves, minimax algorithm in its game tree, search tree. It is an adversarial search algorith ...
. Like alpha–beta pruning, NegaScout is a directional search algorithm for computing the
minimax
Minimax (sometimes Minmax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for ''minimizing'' the possible loss function, loss for a Worst-case scenari ...
value of a node in a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
. 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 node 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.
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
SSS* can theoretically result in fewer nodes searched. However, its original formulation has practical issues (in particular, it relies heavily on an OPEN list for storage) and nowadays most chess engines still use a form of NegaScout in their search. Most chess engines use a transposition table in which the relevant part of the search tree is stored. This part of the tree has the same size as SSS*'s OPEN list would have. A reformulation called MT-SSS* allowed it to be implemented as a series of null window calls to Alpha–Beta (or NegaScout) that use a transposition table, and direct comparisons using game playing programs could be made. It did not outperform NegaScout in practice. Yet another search algorithm, which does tend to do better than NegaScout in practice, is the best-first algorithm called
MTD(f), although neither algorithm dominates the other. There are trees in which NegaScout searches fewer nodes than SSS* or MTD(f) and vice versa.
NegaScout takes after SCOUT, invented by
Judea Pearl
Judea Pearl (; born September 4, 1936) is an Israeli-American computer scientist and philosopher, best known for championing the probabilistic approach to artificial intelligence and the development of Bayesian networks (see the article on belie ...
in 1980, which was the first algorithm to outperform alpha–beta and to be proven asymptotically optimal. Null windows, with β=α+1 in a negamax setting, were invented independently by J.P. Fishburn and used in an algorithm similar to SCOUT in an appendix to his Ph.D. thesis, in a parallel alpha–beta algorithm, and on the last subtree of a search tree root node.
The idea
Most of the moves are not acceptable for both players, so we do not need to fully search every node to get the exact score. The exact score is only needed for nodes in the
principal variation (an optimal sequence of moves for both players), where it will propagate up to the root. In iterative deepening search, the previous iteration has already established a candidate for such a sequence, which is also commonly called the principal variation. For any non-leaf in this principal variation, its children are reordered such that the next node from this principal variation is the first child. All other children are assumed to result in a worse or equal score for the current player (this assumption follows from the assumption that the current PV candidate is an actual PV). To test this, we search the first move with a full window to establish an upper bound on the score of the other children, for which we conduct a zero window search to test if a move can be better. Since a zero window search is much cheaper due to the higher frequency of beta cut-offs, this can save a lot of effort. If we find that a move can raise alpha, our assumption has been disproven for this move and we do a re-search with the full window to get the exact score.
[Murray Campbell, Tony Marsland (1983). A Comparison of Minimax Tree Search Algorithms. Artificial Intelligence, vol. 20, no. 4, pp. 347–367. ISSN 0004-3702.]
Pseudocode
function pvs(node, depth, α, β, color) is
if depth = 0 or node is a terminal node then
return color × the heuristic value of node
for each child of node do
if child is first child then
score := −pvs(child, depth − 1, −β, −α, −color)
else
score := −pvs(child, depth − 1, −α − 1, −α, −color) ''(* search with a null window *)''
if α < score < β then
score := −pvs(child, depth − 1, −β, −α, −color) ''(* if it failed high, do a full re-search *)''
α := max(α, score)
if α ≥ β then
break ''(* beta cut-off *)''
return α
See also
*
Killer heuristic
References
External links
Computer Chess Programming Theory
Game artificial intelligence
Articles with example pseudocode
Combinatorial game theory
{{Game theory