Principal Variation SearchHistory
Home * Search * Principal Variation Search
John Cage - Variations III, No. 14 [1] Principal Variation Search (PVS),
an enhancement to Alpha-Beta, based on null- or zero window searches of none PV-nodes, to prove a move is worse or not than an already safe score from the principal variation.
History
PVS was introduced by Tony Marsland and Murray Campbell in 1982 [4] as nomination of Finkel’s and Fishburn’s routine Palphabeta [5] [6] , in Fishburn’s 1981 thesis [7] called Calphabeta, which in turn is similar to Judea Pearl’s Scout [8] [9] :
Despite the publications, PVS was already used in 1978, as mentioned by Robert Hyatt [10] :
John Philip Fishburn in a note, September 2010:
and subsequently some details about Belle’s PVS-implementation …
PVS and NegaScout
Most PVS implementations are similar to Reinefeld’s NegaScout [12] [13] , and are used by most todays chess programs. It is based on the accuracy of the move ordering. Typically, modern chess programs find fail-highs on the first move around 90% of the time. This observation can be used to narrow the window on searches of moves after the first, because there is a high probability that they will be lower than the score of the first move.
Reinefeld’s original implementation introduces one additional variable on the stack (only b, since after a = alpha, alpha is not needed any longer), for a slightly simpler control structure than PVS. It has therefor set a new null window at the end of the loop (b = a + 1), but has to consider the move count for the re-search condition though. His implementation trusts the null-window score, even if the re-search doesn’t confirm the alpha increase, eventually due to search instability. While re-searching, it uses the narrow window of {score, beta}, while other implementations dealing with search instability, re-search with {alpha, beta}. Practically, due to Quiescence Search, and fail-soft implementations of PVS, the two algorithms are essentially equivalent to each other - they expand the same search tree [14] [15] .
Guido Schimmels
Guido Schimmels in a CCC post on the difference of PVS vs. NegaScout [16] :
PVS:
NegaScout:
Yngvi Björnsson
Quote by Yngvi Björnsson from CCC, January 05, 2000 [17] :
Dennis Breuker
Quote by Dennis Breuker from CCC, July 28, 2004 [18] :
Pseudo Code
This demonstrates PVS in a fail-hard framework, where alpha and beta are hard bounds of the returned score.
- it is recommend to set bSearchPv outside the score > alpha condition.
PVS + ZWS
Often, programmers split PVS inside a pure PV-node search and a separate and a more compact scout search with null windows.
- it is recommend to set bSearchPv outside the score > alpha condition.
PVS and Aspiration
When implementing PVS together with the aspiration window, one must be aware that in this case also a normal window search might fail, leaving the program with no move and no PV. (Actually this is the reason why I wrote “When we already have a PV move” and not “searching later moves”).
A state of the art fail-soft PVS implementation, called without aspiration, was posted by Vincent Diepeveen inside the mentioned CCC thread [23] :
See also
- Alpha-Beta
- CPW-Engine_search
- Enhanced Forward Pruning
- Iterative Deepening
- Move Ordering
- MTD(f)
- NegaScout
- Null Window
- Principal Variation
- PVS and Aspiration
- Scout
Publications
1980 …
- Judea Pearl (1980). Asymptotic Properties of Minimax Trees and Game-Searching Procedures. Artificial Intelligence, Vol. 14, No. 2
- Judea Pearl (1980). Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. pdf
- Raphael Finkel, John Philip Fishburn (1980). Parallel Alpha-Beta Search on Arachne. IEEE International Conference on Parallel Processing
- John Philip Fishburn (1980). An optimization of alpha-beta search. SIGART Bulletin, Issue 72
- John Philip Fishburn (1981). Analysis of Speedup in Distributed Algorithms. Ph.D. Thesis, University of Wisconsin-Madison, pdf, Calphabeta at page 167
- Tony Marsland, Murray Campbell (1982). Parallel Search of Strongly Ordered Game Trees. ACM Computing Surveys, Vol. 14, No. 4, pdf
- Murray Campbell, Tony Marsland (1983). A Comparison of Minimax Tree Search Algorithms. Artificial Intelligence, Vol. 20, No. 4, pp. 347-367. ISSN 0004-3702.
- Tony Marsland (1983). Relative Efficiency of Alpha-beta Implementations. Procs. 8th Int. Joint Conf. on Art. Intell., pp. 763-766. Kaufman, Los Altos, pdf
- Alexander Reinefeld (1983). An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, Vol. 6, No. 4, pdf
1985 …
- Agata Muszycka-Jones, Rajjan Shinghal (1985). An empirical comparison of pruning strategies in game trees. IEEE Transactions on Systems, Man, and Cybernetics, Vol. 15, No. 3
- Tony Marsland (1986). A Review of Game-Tree Pruning. ICCA Journal, Vol. 9, No. 1, pdf
- Alexander Reinefeld, Tony Marsland (1987). A Quantitative Analysis of Minimal Window Search. IJCAI-87, pdf
2000 …
- Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. JCIS 2003
- Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2005). Enhanced Forward Pruning. Information Sciences, Vol. 175, No. 4, pdf preprint (with PVS modifications)
Forum Posts
1995 …
- Trick Marsland by Robert Hyatt, rgcc, February 15, 1996
- Re: Zero-width Window Null Move Search by Guido Schimmels, CCC, June 18, 1998 » NegaScout
- Fail-soft with PVS? by Will Singleton, CCC, March 09, 1999 » Fail-Soft
- Re: negascout vs pvs by Dave Gomboc, CCC, June 04, 1999
2000 …
- PVS and NegaScout by Gian-Carlo Pascutto, CCC, January 05, 2000
- A Question on simple Alpha-Beta versus PVS/Negascout by Andrei Fortuna, CCC, March 21, 2000 » Alpha-Beta, NegaScout
- What is Negascout and why is MWS PVS? by Severi Salminen, CCC, November 24, 2000
- Please explain the difference between PVS and NegaScout by Severi Salminen, CCC, March 02, 2001
- QSearch() as PVS() ? by Matthias Gemuh, CCC, January 14, 2004
- Fruit - Question for Fabien by Dan Honeycutt, CCC, March 11, 2004 » Fruit, Node Types, Transposition Table, Principal Variation
Re: Fruit - Question for Fabien by Fabien Letouzey, CCC, March 11, 2004
- Q. Aspiration, PVS, Fail-Soft by David B. Weller, CCC, July 02, 2004
- negascout and PVS? by Peter Alloysius, CCC, July 26, 2004 » NegaScout
2005 …
- Slight enhancement to PVS by Pradu Kannan, Winboard Programming Forum, June 10, 2007
- Search questions by Sven Schüle, Winboard Forum, July 17, 2007 » Fail-Soft
- Tuning PVS by Aleks Peshkov, CCC, September 27, 2007
- when to try zero window search, CCC, November 14, 2008
- PVS by Edmund Moshammer, CCC, March 12, 2009
- Re: PVS by Robert Hyatt, CCC, March 12, 2009
- Re: PVS by Vincent Diepeveen, CCC, March 14, 2009
- No PVS at low depths? by Mark Lefler, CCC, June 05, 2009
- A way to improve PVS by Sergei S. Markoff, CCC, September 07, 2009
2010 …
- The strengths and weaknesses of PVS by Edmund Moshammer, CCC, June 18, 2010
- Memory-PV-Search by Onno Garms, CCC, March 13, 2011 » Onno
- PV Search and Transposition Table by Cheney Nattress, CCC, December 20, 2012
- principle variation search by nak3c, OpenChess Forum, January 09, 2013
- Implementing pvs by CDaley11, OpenChess Forum, January 13, 2013
- Question about PVS and nodes type by Patrice Duhamel, CCC, May 28, 2013 » Node Types
- Improvement from PVS by Matthew Lai, CCC, September 09, 2014
- Your experience with PVS + Aspiration window by Fabio Gobbato, CCC, October 07, 2014 » Aspiration Windows, PVS and Aspiration
2015 …
- Question on standard implementation of PVS+NWS by Rob Williamson, CCC, March 19, 2015
- PVS/NegaScout: Actual benefits by Vincent Tang, CCC, July 06, 2016
- bound type in PVS ? by Mahmoud Uthman, CCC, January 23, 2017 » Bound, Exact Score
- LMR and PVS by thevinenator, OpenChess Forum, February 10, 2017 » Late Move Reductions
- PVS & Embla by Folkert van Heusden, CCC, October 19, 2017 » Embla
- out of time in PVS by Louis Mackenzie-Smith, CCC, December 13, 2018
2020 …
- Principal Variation Search vs. Transposition Table by Marcel Vanthoor, CCC, October 26, 2020 » Principal Variation
External Links
- Principal Variation Search from Bruce Moreland’s Programming Topics
- Lecture notes for February 2, 1999 Variants of Alpha-Beta Search by David Eppstein
- NegaScout or Principal Variation Search from Wikipedia
Video Tutorial
- A summary description of PVS and how it works by Jonathan Warkentin, YouTube Video
References
- ↑ Variations III, No. 14, a 1992 print by John Cage from a series of 57, John Cage from Wikipedia Fair use
- ↑ Principal Variation Search from Bruce Moreland’s Programming Topics
- ↑ PVS by Edmund Moshammer, CCC, March 12, 2009
- ↑ Tony Marsland, Murray Campbell (1982). Parallel Search of Strongly Ordered Game Trees. ACM Computing Surveys, Vol. 14, No. 4, pdf reprint
- ↑ Raphael Finkel, John Philip Fishburn (1980). Parallel Alpha-Beta Search on Arachne. IEEE International Conference on Parallel Processing, pp. 235-243.
- ↑ Re: Fruit - Question for Fabien by Fabien Letouzey, CCC, March 11, 2004
- ↑ John Philip Fishburn (1981). Analysis of Speedup in Distributed Algorithms. Ph.D. Thesis, University of Wisconsin-Madison, pdf, Calphabeta at page 167
- ↑ Judea Pearl (1980). Asymptotic Properties of Minimax Trees and Game-Searching Procedures. Artificial Intelligence, Vol. 14, No. 2
- ↑ Judea Pearl (1980). Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. pdf
- ↑ Re: PVS by Robert Hyatt from CCC, March 12, 2009
- ↑ John Philip Fishburn (1980). An optimization of alpha-beta search, SIGART Bulletin, Issue 72
- ↑ NegaScout - A Minimax Algorithm faster than AlphaBeta
- ↑ Alexander Reinefeld (1983). An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, Vol. 6, No. 4, pdf
- ↑ Yngvi Björnsson (2002). Selective Depth-First Game-Tree Search. Ph.D. thesis, University of Alberta
- ↑ Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. Accepted for publication. pdf
- ↑ Re: Zero-width Window Null Move Search by Guido Schimmels, CCC, June 18, 1998
- ↑ Re: PVS and NegaScout by Yngvi Björnsson, CCC, January 05, 2000
- ↑ Negascout == PVS (with references) by Dennis Breuker, CCC, July 28, 2004
- ↑ Dennis M. Breuker (1998). Ph.D. thesis: Memory versus Search in Games
- ↑ Tony Marsland (1986). A Review of Game-Tree Pruning. ICCA Journal, Vol. 9, No. 1, pdf
- ↑ NegaScout - A Minimax Algorithm faster than AlphaBeta
- ↑ Alexander Reinefeld (1983). An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, Vol. 6, No. 4, pdf
- ↑ Re: PVS by Vincent Diepeveen, CCC, March 14, 2009