# Principal variation search

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Principal_variation_search
> Markdown URL: https://mediated.wiki/source/Principal_variation_search.md
> Source: https://en.wikipedia.org/wiki/Principal_variation_search
> Source revision: 1292169707
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Enhancement of Alpha–Beta game tree search

**Principal variation search** (sometimes equated with the practically identical **NegaScout**) is a [negamax](/source/Negamax) algorithm that can be faster than [alpha–beta pruning](/source/Alpha%E2%80%93beta_pruning). Like alpha–beta pruning, NegaScout is a directional search algorithm for computing the [minimax](/source/Minimax) value of a node in a [tree](/source/Tree_(data_structure)). 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](/source/Variation_(game_tree)). 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](/source/Alexander_Reinefeld) invented NegaScout several decades after the invention of alpha–beta pruning. He gives a proof of correctness of NegaScout in his book.[1]

Another search algorithm called [SSS*](/source/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.[2] 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)](/source/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](/source/Judea_Pearl) in 1980, which was the first algorithm to outperform alpha–beta and to be proven asymptotically optimal.[3][4] 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,[5] in a parallel alpha–beta algorithm,[6] and on the last subtree of a search tree root node.[7]

## 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](/source/Variation_(game_tree)) (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. [8] [9]

## 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](/source/Killer_heuristic)

## References

1. **[^](#cite_ref-1)** A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlin (1989), [ISBN](/source/ISBN_(identifier)) [3-540-50742-6](https://en.wikipedia.org/wiki/Special:BookSources/3-540-50742-6)

1. **[^](#cite_ref-2)** Plaat, Aske; Jonathan Schaeffer; Wim Pijls; Arie de Bruin (November 1996). ["Best-first Fixed-depth Minimax Algorithms"](https://doi.org/10.1016%2F0004-3702%2895%2900126-3). *Artificial Intelligence*. **87** (1–2): 255–293. [doi](/source/Doi_(identifier)):[10.1016/0004-3702(95)00126-3](https://doi.org/10.1016%2F0004-3702%2895%2900126-3).

1. **[^](#cite_ref-3)** Pearl, J., "SCOUT: A Simple Game-Searching Algorithm With Proven Optimal Properties,"*Proceedings of the First Annual National Conference on Artificial Intelligence,* Stanford University, August 18–21, 1980, pp. 143–145.

1. **[^](#cite_ref-4)** Pearl, J., "Asymptotic Properties of Minimax Trees and Game-Searching Procedures," *Artificial Intelligence,* vol. 14, no. 2, pp. 113–138, September 1980.

1. **[^](#cite_ref-5)** Fishburn, J.P., "Analysis of Speedup in Distributed Algorithms", UMI Research Press [ISBN](/source/ISBN_(identifier)) [0-8357-1527-2](https://en.wikipedia.org/wiki/Special:BookSources/0-8357-1527-2), 1981, 1984.

1. **[^](#cite_ref-6)** Fishburn, J.P., Finkel, R.A., and Lawless, S.A., "Parallel Alpha–Beta Search on Arachne" *Proceedings 1980 Int. Conf. Parallel Processing,* IEEE, August 26–29, 1980, pp. 235–243.

1. **[^](#cite_ref-7)** Fishburn, J.P., "An Optimization of Alpha–Beta Search" *ACM SIGART Bulletin*, issue 72, July 1980, pp. 29–31.

1. **[^](#cite_ref-8)** Judea Pearl (1980). Asymptotic Properties of Minimax Trees and Game-Searching Procedures. Artificial Intelligence, vol. 14, no. 2

1. **[^](#cite_ref-9)** Murray Campbell, Tony Marsland (1983). A Comparison of Minimax Tree Search Algorithms. Artificial Intelligence, vol. 20, no. 4, pp. 347–367. ISSN 0004-3702.

## External links

- [Computer Chess Programming Theory](http://frayn.net/beowulf/theory.html#pvsearch)

- [Strategy Game Programming](http://fierz.ch/strategy2.htm#pvs)

v t e Game theory Glossary Game theorists Games Traditional game theory Definitions Asynchrony Bayesian regret Best response Bounded rationality Cheap talk Coalition Complete contract Complete information Complete mixing Conjectural variation Contingent cooperator Coopetition Cooperative game theory Dynamic inconsistency Escalation of commitment Farsightedness Game semantics Hierarchy of beliefs Imperfect information Incomplete information Information set Move by nature Mutual knowledge Non-cooperative game theory Non-credible threat Outcome Perfect information Perfect recall Ply Preference Rationality Sequential game Simultaneous action selection Spite Strategic complements Strategic dominance Strategic form Strategic interaction Strategic move Strategy Subgame Succinct game Topological game Tragedy of the commons Uncorrelated asymmetry Win–win game Zero-sum game Equilibrium concepts Backward induction Bayes correlated equilibrium Bayesian efficiency Bayesian game Bayesian Nash equilibrium Berge equilibrium Bertrand–Edgeworth model Coalition-proof Nash equilibrium Core Correlated equilibrium Cursed equilibrium Edgeworth price cycle Epsilon-equilibrium Gibbs equilibrium Incomplete contracts Inequity aversion Individual rationality Iterated elimination of dominated strategies Markov perfect equilibrium Mertens-stable equilibrium Nash equilibrium Open-loop model Pareto efficiency Payoff dominance Perfect Bayesian equilibrium Price of anarchy Program equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Rational agent Rationalizable strategy Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfect equilibrium Trembling hand equilibrium Strategies Appeasement Bid shading Cheap talk Collusion Commitment device De-escalation Deterrence Escalation Fictitious play Focal point Grim trigger Hobbesian trap Markov strategy Max-dominated strategy Mixed strategy Pure strategy Tit for tat Win–stay, lose–switch Games All-pay auction Battle of the sexes Nash bargaining game Bertrand competition Blotto game Centipede game Coordination game Cournot competition Deadlock Dictator game Trust game Diner's dilemma Dollar auction El Farol Bar problem Electronic mail game Gift-exchange game Guess 2/3 of the average Keynesian beauty contest Kuhn poker Lewis signaling game Matching pennies Obligationes Optional prisoner's dilemma Pirate game Prisoner's dilemma Public goods game Rendezvous problem Rock paper scissors Stackelberg competition Stag hunt Traveler's dilemma Ultimatum game Volunteer's dilemma War of attrition Theorems Arrow's impossibility theorem Aumann's agreement theorem Brouwer fixed-point theorem Competitive altruism Folk theorem Gibbard–Satterthwaite theorem Gibbs lemma Glicksberg's theorem Kakutani fixed-point theorem Kuhn's theorem One-shot deviation principle Prim–Read theory Rational ignorance Rational irrationality Sperner's lemma Zermelo's theorem Subfields Algorithmic game theory Behavioral game theory Behavioral strategy Compositional game theory Confrontation analysis Contract theory Drama theory Graphical game theory Heresthetic Mean-field game theory Negotiation theory Quantum game theory Social software Key people Albert W. Tucker Alvin E. Roth Amos Tversky Antoine Augustin Cournot Ariel Rubinstein David Gale David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Herbert Scarf Hervé Moulin Jean Tirole Jean-François Mertens Jennifer Tour Chayes Ken Binmore Kenneth Arrow Leonid Hurwicz Lloyd Shapley Martin Shubik Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert Axelrod Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey Combinatorial game theory Core concepts Combinatorial explosion Determinacy Disjunctive sum First-player and second-player win Game complexity Game tree Impartial game Misère Partisan game Solved game Sprague–Grundy theorem Strategy-stealing argument Zugzwang Games Chess Chomp Clobber Cram Domineering Hackenbush Nim Notakto Subtract a square Sylver coinage Toads and Frogs Mathematical tools Mex Nimber On Numbers and Games Star Surreal number Winning Ways for Your Mathematical Plays Search algorithms Alpha–beta pruning Expectiminimax Minimax Monte Carlo tree search Negamax Paranoid algorithm Principal variation search Key people Claude Shannon John Conway John von Neumann Evolutionary game theory Core concepts Bishop–Cannings theorem Evolution and the Theory of Games Evolutionarily stable set Evolutionarily stable state Evolutionarily stable strategy Replicator equation Risk dominance Stochastically stable equilibrium Weak evolutionarily stable strategy Games Chicken Stag hunt Applications Cultural group selection Fisher's principle Mobbing Terminal investment hypothesis Key people John Maynard Smith George R. Price William Donald Hamilton Robert Axelrod Mechanism design Core concepts Algorithmic mechanism design Bayesian-optimal mechanism Incentive compatibility Market design Myerson ironing Monotonicity Participation constraint Revelation principle Strategyproofness Vickrey–Clarke–Groves mechanism Virtual valuation Theorems Myerson–Satterthwaite theorem Revenue equivalence Border's theorem Applications Digital goods auction Knapsack auction Truthful cake-cutting Other topics Bertrand paradox Chainstore paradox Computational complexity of games Helly metric Multi-agent system PPAD-complete Mathematics portal Game theory WikiProject Game theory

---
Adapted from the Wikipedia article [Principal variation search](https://en.wikipedia.org/wiki/Principal_variation_search) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Principal_variation_search?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.