25,161
edits
Changes
Created page with "'''Home * Search * Principal Variation Search''' FILE:Cage-variations-iii-14-small.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/File:Cage-var..."
'''[[Main Page|Home]] * [[Search]] * Principal Variation Search'''
[[FILE:Cage-variations-iii-14-small.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/File:Cage-variations-iii-14-small.jpg|[[Arts#Cage|John Cage]] - Variations III, No. 14 <ref>[https://en.wikipedia.org/wiki/File:Cage-variations-iii-14-small.jpg Variations III, No. 14], a 1992 print by [[Arts#Cage|John Cage]] from a series of 57, [https://en.wikipedia.org/wiki/John_Cage John Cage from Wikipedia] [https://en.wikipedia.org/wiki/Fair_use Fair use]</ref> ]]
'''Principal Variation Search (PVS)''',<br/>
an enhancement to [[Alpha-Beta]], based on [[Null Window|null- or zero window]] searches of none [[Node Types#PV|PV-nodes]], to prove a move is worse or not than an already safe score from the [[Principal Variation|principal variation]].
=The Idea=
In most of the [[Node|nodes]] we need just a [[Bound|bound]], proving that a move is unacceptable for us or for the opponent, and not the [[Exact Score|exact score]]. This is needed only in so-called [[Principal Variation|principal variation]] - a sequence of moves acceptable for both players (i.e. not causing a [[Beta-Cutoff|beta-cutoff]] anywhere in the path) which is expected to propagate down to the [[Root|root]]. If a lower-depth search has already established such a sequence, finding a series of moves whose value is greater than [[Alpha|alpha]] but lower than [[Beta|beta]] throughout the entire branch, the chances are that deviating from it will do us no good. So in a [[Node Types#PV|PV-node]] only the first move (the one which is deemed best by the previous iteration of an [[Iterative Deepening|iterative deepening]] framework) is searched in the full window in order to establish the expected node value.
When we already have a [[PV-Move|PV-move]] (defined as the move that raised alpha in a PV-node) we assume we are going to stick with it. To confirm our belief, a [[Null Window|null- or zero window]] search centered around alpha is conducted to test if a new move can be better. If so, with respect to the null window but not with respect to the full window, we have to do a re-search with the full normal window. Since null window searches are cheaper, with a good [[Move Ordering|move ordering]] we expect to save about 10% of a search effort.
[[Bruce Moreland|Bruce Moreland's]] PVS implementation waits until a move is found that improves alpha, and then searches every move after that with a zero window around alpha <ref>[http://web.archive.org/web/20040427015506/brucemo.com/compchess/programming/pvs.htm Principal Variation Search] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics]</ref> . The alpha improvement usually occurs at the first move, and always at the [[Leftmost Node|leftmost nodes]] (assuming from left to right traversal) with a most open alpha-beta window of +-oo. In re-searches or with [[Principal Variation Search#PVSandAspiration|aspiration-windows]] the first moves may rarely not improve alpha. As pointed out by [[Edmund Moshammer]], [[Gian-Carlo Pascutto]], [[Robert Hyatt]] and [[Vincent Diepeveen]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=26974 PVS] by [[Edmund Moshammer]], [[CCC]], March 12, 2009</ref> , it is recommend to only search the first move with an open window, and then every other move after that with a zero window. A further improvement (similar to that known from the [[NegaScout]] algorithm) is possible. Since there is not much to be gained in the last two plies of the normal search, one might disable PVS there, but programs respond differently to that change.
=History=
PVS was introduced by [[Tony Marsland]] and [[Murray Campbell]] in 1982 <ref>[[Tony Marsland]], [[Murray Campbell]] ('''1982'''). ''Parallel Search of Strongly Ordered Game Trees.'' [[ACM#Surveys|ACM Computing Surveys]], Vol. 14, No. 4, [http://www.cs.ualberta.ca/%7Etony/OldPapers/strong.pdf pdf reprint]</ref> as nomination of [[Raphael Finkel|Finkel's]] and [[John Philip Fishburn|Fishburn's]] routine '''Palphabeta''' <ref>[[Raphael Finkel]], [[John Philip Fishburn]] ('''1980'''). ''Parallel Alpha-Beta Search on Arachne.'' [[IEEE]] International Conference on Parallel Processing, pp. 235-243.</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=354016 Re: Fruit - Question for Fabien] by [[Fabien Letouzey]], [[CCC]], March 11, 2004</ref> , in Fishburn's [[Timeline#1981|1981]] thesis <ref>[[John Philip Fishburn]] ('''1981'''). ''Analysis of Speedup in Distributed Algorithms''. Ph.D. Thesis, [https://en.wikipedia.org/wiki/University_of_Wisconsin-Madison University of Wisconsin-Madison], [http://www.cs.wisc.edu/techreports/1981/TR431.pdf pdf], ''Calphabeta'' at page 167</ref> called '''Calphabeta''', which in turn is similar to [[Judea Pearl|Judea Pearl's]] [[Scout]] <ref>[[Judea Pearl]] ('''1980'''). ''Asymptotic Properties of Minimax Trees and Game-Searching Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 14, No. 2</ref> <ref>[[Judea Pearl]] ('''1980'''). ''Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties''. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. [http://ftp.cs.ucla.edu/pub/stat_ser/scout.pdf pdf]</ref> :
An interesting implementation of the alpha-beta algorithm treats the first variation in a special way. The method was originally called '''Palphabeta''' [FISH80] and then renamed '''Calphabeta''' [FISH81], but will be referred to here as principal variation search or PVS for short.
Despite the publications, PVS was already used in 1978, as mentioned by [[Robert Hyatt]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=254906&t=26974 Re: PVS] by [[Robert Hyatt]] from [[CCC]], March 12, 2009</ref> :
I first used PVS in 1978, quite by accident. Murray Campbell and I were discussing this idea at the [[ACM 1978|ACM event]] in Washington, DC. We were running on a Univac, and I suggested that we dial up my local Vax box and make the changes and see how it works. It looked pretty good, with the only odd thing being fail highs on very minor score changes, which was OK. The next round, our Univac developed a memory problem and I switched back to the vax and had a few exciting moments when we came out with a Nxf7!! sort of output, only to see the score rise by 2 or 3 millipawns. Even in 1978 we just searched the first move with normal alpha/beta and then went into the null-window search, just as the code exactly does in [[Crafty]]...
[[John Philip Fishburn]] in a note, September 2010:
I was thinking about what goes wrong if you start the entire search with a too-narrow window. If the beta value is too low, then one of the children of the [[Root|root]] might [[Fail-High|fail high]], and you wouldn't know the proper windows to give to the subsequent children of the root. Wait a minute... what if there aren't any subsequent children, i.e. what if the child that failed high was the last child of the root? Then you don't care about the subsequent windows, and in fact you've just proved that the last child is the best move. So when you're on the last child of the root, go all the way by bringing beta down to alpha+1. I was trying to get this published starting in Aug. 1979, and it finally appeared as "An optimization of alpha-beta search" in [[ACM#SIG|SIGART]] bulletin Issue 72 (July 1980) <ref>[[John Philip Fishburn]] ('''1980'''). ''An optimization of alpha-beta search'', SIGART Bulletin, Issue 72</ref> . After that came various generalizations where the null window is used generally in the search, also the [[Fail-Soft|fail-soft]] algorithm. I was somewhat disappointed in the speedup (or lack thereof) that I measured on [[Checkers|checkers]] lookahead trees. However when I went to work at [[Bell Laboratories|Bell Labs]] in 1981, [[Ken Thompson]] told me that he had read the SIGART paper, and had sped up [[Belle]] by 1.5x with [[Null Window|null windows]].
and subsequently some details about [[Belle|Belle's]] PVS-implementation ...
The PVS algorithm in Belle did not do a second search at the root until a '''second''' fail high occurred. I don’t know whether or not this idea appears in the literature or not. I would hope it does, but I haven’t been following the literature for about 25 years. In other words, Belle is cleverly going for broke: it knows it’s got a high failure, which is the best move so far, but as long as it doesn’t get a second high failure, the first high failure remains the best move, and it can still avoid doing any more full searches.
=PVS and NegaScout=
Most PVS implementations are similar to [[Alexander Reinefeld|Reinefeld's]] [[NegaScout]] <ref>[http://sc.hlrn.de/reinefeld/Research/nsc.html NegaScout - A Minimax Algorithm faster than AlphaBeta]</ref> <ref>[[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]], [http://www.top-5000.nl/ps/An%20improvement%20to%20the%20scout%20tree%20search%20algorithm.pdf pdf]</ref> , and are used by most todays chess programs. It is based on the accuracy of the [[Move Ordering|move ordering]]. Typically, modern chess programs find [[Fail-High|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|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 (<span style="background-color: #d6d6d6;">b = a + 1</span>), 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|search instability]]. While re-searching, it uses the narrow window of <span style="background-color: #d6d6d6;">{score, beta},</span> while other implementations dealing with search instability, re-search with <span style="background-color: #d6d6d6;">{alpha, beta}</span>. Practically, due to [[Quiescence Search]], and [[Fail-Soft|fail-soft]] implementations of PVS, the two algorithms are essentially equivalent to each other - they expand the same [[Search Tree|search tree]] <ref>[[Yngvi Björnsson]] ('''2002'''). ''Selective Depth-First Game-Tree Search.'' '''Ph.D. thesis''', [[University of Alberta]]</ref> <ref>[[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' Accepted for publication. [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]</ref> .
==Guido Schimmels==
[[Guido Schimmels]] in a [[CCC]] post on the difference of PVS vs. NegaScout <ref>[https://www.stmintz.com/ccc/index.php?id=20868 Re: Zero-width Window Null Move Search] by [[Guido Schimmels]], [[CCC]], June 18, 1998</ref> :
The difference is how they handle re-searches: PVS passes alpha/beta while NegaScout passes the value returned by the null window search instead of alpha. But then you can get a fail-low on the research due to search anonomalies. If that happens NegaScout returns the value from the first search. That means you will have a crippled PV. Then there is a refinement Reinefeld suggests which is to ommit the re-search at the last two plies (depth > 1) - but that won't work in a real program because of search extensions. NegaScout is slightly an ivory tower variant of PVS (IMHO).
'''PVS''':
<pre>
value = PVS(-(alpha+1),-alpha)
if(value > alpha && value < beta) {
value = PVS(-beta,-alpha);
}
</pre>
'''NegaScout''':
<pre>
value = NegaScout(-(alpha+1),-alpha)
if(value > alpha && value < beta && depth > 1) {
value2 = NegaScout(-beta,-value)
value = max(value,value2);
}
</pre>
==Yngvi Björnsson==
Quote by [[Yngvi Björnsson]] from [[CCC]], January 05, 2000 <ref>[https://www.stmintz.com/ccc/index.php?id=86134 Re: PVS and NegaScout] by [[Yngvi Björnsson]], [[CCC]], January 05, 2000</ref> :
Search-wise PVS and Negascout are identical (except the deep-cutoffs on the PV you mention), they are just formulated differently. In Negascout the same routine is used for searching both the PV and the rest of the tree, whereas PVS is typically formulated as two routines: PVS (for searching the PV) and NWS (for the null-window searches). Negascout and PVS were developed about the same time in the early '80 (82-83), but independently. I guess, that's part of the reason we know them by different names. Personally, I've always found the PVS/NWS formulation the most intuative, it's easier to understand what's really going on.
==Dennis Breuker==
Quote by [[Dennis Breuker]] from [[CCC]], July 28, 2004 <ref>[https://www.stmintz.com/ccc/index.php?id=379441 Negascout == PVS (with references)] by [[Dennis Breuker]], [[CCC]], July 28, 2004</ref> :
Q: What's the different between negascout and PVS ? They look like the same algorithm to me.
They are identical, see note 15 on page 22 of my thesis <ref>[[Dennis Breuker|Dennis M. Breuker]] ('''1998'''). ''[http://www.dennisbreuker.nl/thesis/index.html Ph.D. thesis: Memory versus Search in Games]''</ref> :We note that the version of principal-variation search as mentioned by Marsland (1986) <ref>[[Tony Marsland]] ('''1986'''). ''A Review of Game-Tree Pruning.'' [[ICGA Journal#9_1|ICCA Journal, Vol. 9, No. 1]], [http://www.cs.ualberta.ca/%7Etony/OldPapers/1986review.pdf pdf]</ref> is identical to the version of negascout as mentioned by Reinefeld (1989) <ref>[http://sc.hlrn.de/reinefeld/Research/nsc.html NegaScout - A Minimax Algorithm faster than AlphaBeta]</ref> . We use the 1989 reference instead of 1983 <ref>[[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]], [http://www.top-5000.nl/ps/An%20improvement%20to%20the%20scout%20tree%20search%20algorithm.pdf pdf]</ref> , which was the first source of this algorithm, since the algorithm described in Reinefeld (1983) contains minor errors.Dennis
=Pseudo Code=
This demonstrates PVS in a [[Fail-Hard|fail-hard]] framework, where alpha and beta are hard bounds of the returned score.
<pre>
int pvSearch( int alpha, int beta, int depth ) {
if( depth == 0 ) return quiesce( alpha, beta );
bool bSearchPv = true;
for ( all moves) {
make
if ( bSearchPv ) {
score = -pvSearch(-beta, -alpha, depth - 1);
} else {
score = -pvSearch(-alpha-1, -alpha, depth - 1);
if ( score > alpha ) // in fail-soft ... && score < beta ) is common
score = -pvSearch(-beta, -alpha, depth - 1); // re-search
}
unmake
if( score >= beta )
return beta; // fail-hard beta-cutoff
if( score > alpha ) {
alpha = score; // alpha acts like max in MiniMax
bSearchPv = false; // *1)
}
}
return alpha; // fail-hard
}
</pre>
1) it is recommend to set bSearchPv outside the score > alpha condition.
<span id="ZWS"></span>
=PVS + ZWS=
Often, programmers split PVS inside a pure [[Node Types#PV|PV-node]] search and a separate and a more compact [[Scout|scout search]] with [[Null Window|null windows]].
<pre>
int pvSearch( int alpha, int beta, int depth ) {
if( depth == 0 ) return quiesce(alpha, beta);
bool bSearchPv = true;
for ( all moves) {
make
if ( bSearchPv ) {
score = -pvSearch(-beta, -alpha, depth - 1);
} else {
score = -zwSearch(-alpha, depth - 1);
if ( score > alpha ) // in fail-soft ... && score < beta ) is common
score = -pvSearch(-beta, -alpha, depth - 1); // re-search
}
unmake
if( score >= beta )
return beta; // fail-hard beta-cutoff
if( score > alpha ) {
alpha = score; // alpha acts like max in MiniMax
bSearchPv = false; // *1)
}
}
return alpha;
}
// fail-hard zero window search, returns either beta-1 or beta
int zwSearch(int beta, int depth ) {
// alpha == beta - 1
// this is either a cut- or all-node
if( depth == 0 ) return quiesce(beta-1, beta);
for ( all moves) {
make
score = -zwSearch(1-beta, depth - 1);
unmake
if( score >= beta )
return beta; // fail-hard beta-cutoff
}
return beta-1; // fail-hard, return alpha
}
</pre>
1) it is recommend to set bSearchPv outside the score > alpha condition.
<span id="PVSandAspiration"></span>
=PVS and Aspiration=
When implementing PVS together with the [[Aspiration Windows|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").
* [[PVS and aspiration]]
A state of the art [[Fail-Soft|fail-soft]] PVS implementation, called without aspiration, was posted by [[Vincent Diepeveen]] inside the mentioned [[CCC]] thread <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=255191&t=26974 Re: PVS] by [[Vincent Diepeveen]], [[CCC]], March 14, 2009</ref> :
<pre>
Call from root:
rootscore = PVS(-infinite, infinite, depthleft);
int PVS(alfa,beta,depthleft) {
if( depthleft <= 0 ) return qsearch(alfa, beta);
// using fail soft with negamax:
make first move
bestscore = -PVS(-beta, -alfa, depthleft-1);
unmake first move
if( bestscore > alfa ) {
if( bestscore >= beta )
return bestscore;
alfa = bestscore;
}
for( all remaining moves ) {
make move
score = -PVS(-alfa-1, -alfa, depthleft-1); // alphaBeta or zwSearch
if( score > alfa && score < beta ) {
// research with window [alfa;beta]
score = -PVS(-beta, -alfa, depthleft-1);
if( score > alfa )
alfa = score;
}
unmake move
if( score > bestscore ) {
if( score >= beta )
return score;
bestscore = score;
}
}
return bestscore;
}
</pre>
=See also=
* [[Alpha-Beta]]
* [[CPW-Engine_search]]
* [[Enhanced Forward Pruning]]
* [[Iterative Deepening]]
* [[Move Ordering]]
* [[MTD(f)]]
* [[NegaScout]]
* [[Null Window]]
* [[PVS and aspiration]]
* [[Scout]]
=Publications=
==1980 ...==
* [[Judea Pearl]] ('''1980'''). ''Asymptotic Properties of Minimax Trees and Game-Searching Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 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. [http://ftp.cs.ucla.edu/pub/stat_ser/scout.pdf 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''. [[ACM#SIG|SIGART Bulletin]], Issue 72
* [[John Philip Fishburn]] ('''1981'''). ''Analysis of Speedup in Distributed Algorithms''. Ph.D. Thesis, [https://en.wikipedia.org/wiki/University_of_Wisconsin-Madison University of Wisconsin-Madison], [http://www.cs.wisc.edu/techreports/1981/TR431.pdf pdf], ''Calphabeta'' at page 167
* [[Tony Marsland]], [[Murray Campbell]] ('''1982'''). ''Parallel Search of Strongly Ordered Game Trees.'' [[ACM#Surveys|ACM Computing Surveys]], Vol. 14, No. 4, [http://www.cs.ualberta.ca/%7Etony/OldPapers/strong.pdf pdf]
* [[Murray Campbell]], [[Tony Marsland]] ('''1983'''). ''A Comparison of Minimax Tree Search Algorithms''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 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, [http://dli.iiit.ac.in/ijcai/IJCAI-83-VOL-2/PDF/040.pdf pdf]
* [[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]], [http://sc.hlrn.de/reinefeld/bib/83icca.pdf pdf]
==1985 ...==
* [[Agata Muszycka-Jones]], [[Rajjan Shinghal]] ('''1985'''). ''An empirical comparison of pruning strategies in game trees''. [[IEEE#SMC|IEEE Transactions on Systems, Man, and Cybernetics]], Vol. 15, No. 3
* [[Tony Marsland]] ('''1986'''). ''A Review of Game-Tree Pruning.'' [[ICGA Journal#9_1|ICCA Journal, Vol. 9, No. 1]], [http://www.cs.ualberta.ca/%7Etony/OldPapers/1986review.pdf pdf]
* [[Alexander Reinefeld]], [[Tony Marsland]] ('''1987'''). ''A Quantitative Analysis of Minimal Window Search.'' [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai87.html IJCAI-87], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/ijcai87.pdf pdf]
==2000 ...==
* [[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]] and [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' Accepted for publication. [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf] (with PVS modifications)
=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/3ffa1d89d13f9e86 Trick Marsland] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 15, 1996
* [https://www.stmintz.com/ccc/index.php?id=20868 Re: Zero-width Window Null Move Search] by [[Guido Schimmels]], [[CCC]], June 18, 1998 » [[NegaScout]]
* [https://www.stmintz.com/ccc/index.php?id=45482 Fail-soft with PVS?] by [[Will Singleton]], [[CCC]], March 09, 1999 » [[Fail-Soft]]
* [https://www.stmintz.com/ccc/index.php?id=54343 Re: negascout vs pvs] by [[Dave Gomboc]], [[CCC]], June 04, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=86122 PVS and NegaScout] by [[Gian-Carlo Pascutto]], [[CCC]], January 05, 2000
* [https://www.stmintz.com/ccc/index.php?id=102792 A Question on simple Alpha-Beta versus PVS/Negascout] by [[Andrei Fortuna]], [[CCC]], March 21, 2000 » [[Alpha-Beta]], [[NegaScout]]
* [https://www.stmintz.com/ccc/index.php?id=140872 What is Negascout and why is MWS PVS?] by [[Severi Salminen]], [[CCC]], November 24, 2000
* [https://www.stmintz.com/ccc/index.php?id=156886 Please explain the difference between PVS and NegaScout] by [[Severi Salminen]], [[CCC]], March 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=342287 QSearch() as PVS() ?] by [[Matthias Gemuh]], [[CCC]], January 14, 2004
* [https://www.stmintz.com/ccc/index.php?id=354012 Fruit - Question for Fabien] by [[Dan Honeycutt]], [[CCC]], March 11, 2004 » [[Fruit]], [[Node Types]], [[Transposition Table]], [[Principal variation]]
: [https://www.stmintz.com/ccc/index.php?id=354016 Re: Fruit - Question for Fabien] by [[Fabien Letouzey]], [[CCC]], March 11, 2004
* [https://www.stmintz.com/ccc/index.php?id=373537 Q. Aspiration, PVS, Fail-Soft] by [[David B. Weller]], [[CCC]], July 02, 2004
* [https://www.stmintz.com/ccc/index.php?id=379100 negascout and PVS?] by [[Peter Aloysius Harjanto|Peter Alloysius]], [[CCC]], July 26, 2004 » [[NegaScout]]
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6558 Slight enhancement to PVS] by [[Pradu Kannan]], [[Computer Chess Forums|Winboard Programming Forum]], June 10, 2007
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6665 Search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007 » [[Fail Soft]]
* [http://www.talkchess.com/forum/viewtopic.php?t=24883 when to try zero window search], [[CCC]], November 14, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=26974 PVS] by [[Edmund Moshammer]], [[CCC]], March 12, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=254906&t=26974 Re: PVS] by [[Robert Hyatt]], [[CCC]], March 12, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=255191&t=26974 Re: PVS] by [[Vincent Diepeveen]], [[CCC]], March 14, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=28266 No PVS at low depths?] by [[Mark Lefler]], [[CCC]], June 05, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=29681 A way to improve PVS] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], September 07, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=356836&t=35022 The strengths and weaknesses of PVS] by [[Edmund Moshammer]], [[CCC]], June 18, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38413 Memory-PV-Search] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46499 PV Search and Transposition Table] by [[Cheney Nattress]], [[CCC]], December 20, 2012
* [http://www.open-chess.org/viewtopic.php?f=5&t=2208 principle variation search] by nak3c, [[Computer Chess Forums|OpenChess Forum]], January 09, 2013
* [http://www.open-chess.org/viewtopic.php?f=5&t=2218 Implementing pvs] by [[Christian Daley|CDaley11]], [[Computer Chess Forums|OpenChess Forum]], January 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=53626 Improvement from PVS] by [[Matthew Lai]], [[CCC]], September 09, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53972 Your experience with PVS + Aspiration window] by [[Fabio Gobbato]], [[CCC]], October 07, 2014 » [[Aspiration Windows]], [[PVS and aspiration]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55709 Question on standard implementation of PVS+NWS] by Rob Williamson, [[CCC]], March 19, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=60719 PVS/NegaScout: Actual benefits] by Vincent Tang, [[CCC]], July 06, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62913 bound type in PVS ?] by [[Mahmoud Uthman]], [[CCC]], January 23, 2017 » [[Bound]], [[Exact Score]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=3084 LMR and PVS] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], February 10, 2017 » [[Late Move Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65490 PVS & Embla] by [[Folkert van Heusden]], [[CCC]], October 19, 2017 » [[Embla]]
=External Links=
* [http://web.archive.org/web/20070809015901/www.seanet.com/~brucemo/topics/pvs.htm Principal Variation Search] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]
* [https://en.wikipedia.org/wiki/Negascout NegaScout or Principal Variation Search from Wikipedia]
=Video Tutorial=
* A summary description of PVS and how it works by [[Jonathan Warkentin]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=1YdBLgmoV_E|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
[[FILE:Cage-variations-iii-14-small.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/File:Cage-variations-iii-14-small.jpg|[[Arts#Cage|John Cage]] - Variations III, No. 14 <ref>[https://en.wikipedia.org/wiki/File:Cage-variations-iii-14-small.jpg Variations III, No. 14], a 1992 print by [[Arts#Cage|John Cage]] from a series of 57, [https://en.wikipedia.org/wiki/John_Cage John Cage from Wikipedia] [https://en.wikipedia.org/wiki/Fair_use Fair use]</ref> ]]
'''Principal Variation Search (PVS)''',<br/>
an enhancement to [[Alpha-Beta]], based on [[Null Window|null- or zero window]] searches of none [[Node Types#PV|PV-nodes]], to prove a move is worse or not than an already safe score from the [[Principal Variation|principal variation]].
=The Idea=
In most of the [[Node|nodes]] we need just a [[Bound|bound]], proving that a move is unacceptable for us or for the opponent, and not the [[Exact Score|exact score]]. This is needed only in so-called [[Principal Variation|principal variation]] - a sequence of moves acceptable for both players (i.e. not causing a [[Beta-Cutoff|beta-cutoff]] anywhere in the path) which is expected to propagate down to the [[Root|root]]. If a lower-depth search has already established such a sequence, finding a series of moves whose value is greater than [[Alpha|alpha]] but lower than [[Beta|beta]] throughout the entire branch, the chances are that deviating from it will do us no good. So in a [[Node Types#PV|PV-node]] only the first move (the one which is deemed best by the previous iteration of an [[Iterative Deepening|iterative deepening]] framework) is searched in the full window in order to establish the expected node value.
When we already have a [[PV-Move|PV-move]] (defined as the move that raised alpha in a PV-node) we assume we are going to stick with it. To confirm our belief, a [[Null Window|null- or zero window]] search centered around alpha is conducted to test if a new move can be better. If so, with respect to the null window but not with respect to the full window, we have to do a re-search with the full normal window. Since null window searches are cheaper, with a good [[Move Ordering|move ordering]] we expect to save about 10% of a search effort.
[[Bruce Moreland|Bruce Moreland's]] PVS implementation waits until a move is found that improves alpha, and then searches every move after that with a zero window around alpha <ref>[http://web.archive.org/web/20040427015506/brucemo.com/compchess/programming/pvs.htm Principal Variation Search] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics]</ref> . The alpha improvement usually occurs at the first move, and always at the [[Leftmost Node|leftmost nodes]] (assuming from left to right traversal) with a most open alpha-beta window of +-oo. In re-searches or with [[Principal Variation Search#PVSandAspiration|aspiration-windows]] the first moves may rarely not improve alpha. As pointed out by [[Edmund Moshammer]], [[Gian-Carlo Pascutto]], [[Robert Hyatt]] and [[Vincent Diepeveen]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=26974 PVS] by [[Edmund Moshammer]], [[CCC]], March 12, 2009</ref> , it is recommend to only search the first move with an open window, and then every other move after that with a zero window. A further improvement (similar to that known from the [[NegaScout]] algorithm) is possible. Since there is not much to be gained in the last two plies of the normal search, one might disable PVS there, but programs respond differently to that change.
=History=
PVS was introduced by [[Tony Marsland]] and [[Murray Campbell]] in 1982 <ref>[[Tony Marsland]], [[Murray Campbell]] ('''1982'''). ''Parallel Search of Strongly Ordered Game Trees.'' [[ACM#Surveys|ACM Computing Surveys]], Vol. 14, No. 4, [http://www.cs.ualberta.ca/%7Etony/OldPapers/strong.pdf pdf reprint]</ref> as nomination of [[Raphael Finkel|Finkel's]] and [[John Philip Fishburn|Fishburn's]] routine '''Palphabeta''' <ref>[[Raphael Finkel]], [[John Philip Fishburn]] ('''1980'''). ''Parallel Alpha-Beta Search on Arachne.'' [[IEEE]] International Conference on Parallel Processing, pp. 235-243.</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=354016 Re: Fruit - Question for Fabien] by [[Fabien Letouzey]], [[CCC]], March 11, 2004</ref> , in Fishburn's [[Timeline#1981|1981]] thesis <ref>[[John Philip Fishburn]] ('''1981'''). ''Analysis of Speedup in Distributed Algorithms''. Ph.D. Thesis, [https://en.wikipedia.org/wiki/University_of_Wisconsin-Madison University of Wisconsin-Madison], [http://www.cs.wisc.edu/techreports/1981/TR431.pdf pdf], ''Calphabeta'' at page 167</ref> called '''Calphabeta''', which in turn is similar to [[Judea Pearl|Judea Pearl's]] [[Scout]] <ref>[[Judea Pearl]] ('''1980'''). ''Asymptotic Properties of Minimax Trees and Game-Searching Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 14, No. 2</ref> <ref>[[Judea Pearl]] ('''1980'''). ''Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties''. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. [http://ftp.cs.ucla.edu/pub/stat_ser/scout.pdf pdf]</ref> :
An interesting implementation of the alpha-beta algorithm treats the first variation in a special way. The method was originally called '''Palphabeta''' [FISH80] and then renamed '''Calphabeta''' [FISH81], but will be referred to here as principal variation search or PVS for short.
Despite the publications, PVS was already used in 1978, as mentioned by [[Robert Hyatt]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=254906&t=26974 Re: PVS] by [[Robert Hyatt]] from [[CCC]], March 12, 2009</ref> :
I first used PVS in 1978, quite by accident. Murray Campbell and I were discussing this idea at the [[ACM 1978|ACM event]] in Washington, DC. We were running on a Univac, and I suggested that we dial up my local Vax box and make the changes and see how it works. It looked pretty good, with the only odd thing being fail highs on very minor score changes, which was OK. The next round, our Univac developed a memory problem and I switched back to the vax and had a few exciting moments when we came out with a Nxf7!! sort of output, only to see the score rise by 2 or 3 millipawns. Even in 1978 we just searched the first move with normal alpha/beta and then went into the null-window search, just as the code exactly does in [[Crafty]]...
[[John Philip Fishburn]] in a note, September 2010:
I was thinking about what goes wrong if you start the entire search with a too-narrow window. If the beta value is too low, then one of the children of the [[Root|root]] might [[Fail-High|fail high]], and you wouldn't know the proper windows to give to the subsequent children of the root. Wait a minute... what if there aren't any subsequent children, i.e. what if the child that failed high was the last child of the root? Then you don't care about the subsequent windows, and in fact you've just proved that the last child is the best move. So when you're on the last child of the root, go all the way by bringing beta down to alpha+1. I was trying to get this published starting in Aug. 1979, and it finally appeared as "An optimization of alpha-beta search" in [[ACM#SIG|SIGART]] bulletin Issue 72 (July 1980) <ref>[[John Philip Fishburn]] ('''1980'''). ''An optimization of alpha-beta search'', SIGART Bulletin, Issue 72</ref> . After that came various generalizations where the null window is used generally in the search, also the [[Fail-Soft|fail-soft]] algorithm. I was somewhat disappointed in the speedup (or lack thereof) that I measured on [[Checkers|checkers]] lookahead trees. However when I went to work at [[Bell Laboratories|Bell Labs]] in 1981, [[Ken Thompson]] told me that he had read the SIGART paper, and had sped up [[Belle]] by 1.5x with [[Null Window|null windows]].
and subsequently some details about [[Belle|Belle's]] PVS-implementation ...
The PVS algorithm in Belle did not do a second search at the root until a '''second''' fail high occurred. I don’t know whether or not this idea appears in the literature or not. I would hope it does, but I haven’t been following the literature for about 25 years. In other words, Belle is cleverly going for broke: it knows it’s got a high failure, which is the best move so far, but as long as it doesn’t get a second high failure, the first high failure remains the best move, and it can still avoid doing any more full searches.
=PVS and NegaScout=
Most PVS implementations are similar to [[Alexander Reinefeld|Reinefeld's]] [[NegaScout]] <ref>[http://sc.hlrn.de/reinefeld/Research/nsc.html NegaScout - A Minimax Algorithm faster than AlphaBeta]</ref> <ref>[[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]], [http://www.top-5000.nl/ps/An%20improvement%20to%20the%20scout%20tree%20search%20algorithm.pdf pdf]</ref> , and are used by most todays chess programs. It is based on the accuracy of the [[Move Ordering|move ordering]]. Typically, modern chess programs find [[Fail-High|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|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 (<span style="background-color: #d6d6d6;">b = a + 1</span>), 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|search instability]]. While re-searching, it uses the narrow window of <span style="background-color: #d6d6d6;">{score, beta},</span> while other implementations dealing with search instability, re-search with <span style="background-color: #d6d6d6;">{alpha, beta}</span>. Practically, due to [[Quiescence Search]], and [[Fail-Soft|fail-soft]] implementations of PVS, the two algorithms are essentially equivalent to each other - they expand the same [[Search Tree|search tree]] <ref>[[Yngvi Björnsson]] ('''2002'''). ''Selective Depth-First Game-Tree Search.'' '''Ph.D. thesis''', [[University of Alberta]]</ref> <ref>[[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' Accepted for publication. [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]</ref> .
==Guido Schimmels==
[[Guido Schimmels]] in a [[CCC]] post on the difference of PVS vs. NegaScout <ref>[https://www.stmintz.com/ccc/index.php?id=20868 Re: Zero-width Window Null Move Search] by [[Guido Schimmels]], [[CCC]], June 18, 1998</ref> :
The difference is how they handle re-searches: PVS passes alpha/beta while NegaScout passes the value returned by the null window search instead of alpha. But then you can get a fail-low on the research due to search anonomalies. If that happens NegaScout returns the value from the first search. That means you will have a crippled PV. Then there is a refinement Reinefeld suggests which is to ommit the re-search at the last two plies (depth > 1) - but that won't work in a real program because of search extensions. NegaScout is slightly an ivory tower variant of PVS (IMHO).
'''PVS''':
<pre>
value = PVS(-(alpha+1),-alpha)
if(value > alpha && value < beta) {
value = PVS(-beta,-alpha);
}
</pre>
'''NegaScout''':
<pre>
value = NegaScout(-(alpha+1),-alpha)
if(value > alpha && value < beta && depth > 1) {
value2 = NegaScout(-beta,-value)
value = max(value,value2);
}
</pre>
==Yngvi Björnsson==
Quote by [[Yngvi Björnsson]] from [[CCC]], January 05, 2000 <ref>[https://www.stmintz.com/ccc/index.php?id=86134 Re: PVS and NegaScout] by [[Yngvi Björnsson]], [[CCC]], January 05, 2000</ref> :
Search-wise PVS and Negascout are identical (except the deep-cutoffs on the PV you mention), they are just formulated differently. In Negascout the same routine is used for searching both the PV and the rest of the tree, whereas PVS is typically formulated as two routines: PVS (for searching the PV) and NWS (for the null-window searches). Negascout and PVS were developed about the same time in the early '80 (82-83), but independently. I guess, that's part of the reason we know them by different names. Personally, I've always found the PVS/NWS formulation the most intuative, it's easier to understand what's really going on.
==Dennis Breuker==
Quote by [[Dennis Breuker]] from [[CCC]], July 28, 2004 <ref>[https://www.stmintz.com/ccc/index.php?id=379441 Negascout == PVS (with references)] by [[Dennis Breuker]], [[CCC]], July 28, 2004</ref> :
Q: What's the different between negascout and PVS ? They look like the same algorithm to me.
They are identical, see note 15 on page 22 of my thesis <ref>[[Dennis Breuker|Dennis M. Breuker]] ('''1998'''). ''[http://www.dennisbreuker.nl/thesis/index.html Ph.D. thesis: Memory versus Search in Games]''</ref> :We note that the version of principal-variation search as mentioned by Marsland (1986) <ref>[[Tony Marsland]] ('''1986'''). ''A Review of Game-Tree Pruning.'' [[ICGA Journal#9_1|ICCA Journal, Vol. 9, No. 1]], [http://www.cs.ualberta.ca/%7Etony/OldPapers/1986review.pdf pdf]</ref> is identical to the version of negascout as mentioned by Reinefeld (1989) <ref>[http://sc.hlrn.de/reinefeld/Research/nsc.html NegaScout - A Minimax Algorithm faster than AlphaBeta]</ref> . We use the 1989 reference instead of 1983 <ref>[[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]], [http://www.top-5000.nl/ps/An%20improvement%20to%20the%20scout%20tree%20search%20algorithm.pdf pdf]</ref> , which was the first source of this algorithm, since the algorithm described in Reinefeld (1983) contains minor errors.Dennis
=Pseudo Code=
This demonstrates PVS in a [[Fail-Hard|fail-hard]] framework, where alpha and beta are hard bounds of the returned score.
<pre>
int pvSearch( int alpha, int beta, int depth ) {
if( depth == 0 ) return quiesce( alpha, beta );
bool bSearchPv = true;
for ( all moves) {
make
if ( bSearchPv ) {
score = -pvSearch(-beta, -alpha, depth - 1);
} else {
score = -pvSearch(-alpha-1, -alpha, depth - 1);
if ( score > alpha ) // in fail-soft ... && score < beta ) is common
score = -pvSearch(-beta, -alpha, depth - 1); // re-search
}
unmake
if( score >= beta )
return beta; // fail-hard beta-cutoff
if( score > alpha ) {
alpha = score; // alpha acts like max in MiniMax
bSearchPv = false; // *1)
}
}
return alpha; // fail-hard
}
</pre>
1) it is recommend to set bSearchPv outside the score > alpha condition.
<span id="ZWS"></span>
=PVS + ZWS=
Often, programmers split PVS inside a pure [[Node Types#PV|PV-node]] search and a separate and a more compact [[Scout|scout search]] with [[Null Window|null windows]].
<pre>
int pvSearch( int alpha, int beta, int depth ) {
if( depth == 0 ) return quiesce(alpha, beta);
bool bSearchPv = true;
for ( all moves) {
make
if ( bSearchPv ) {
score = -pvSearch(-beta, -alpha, depth - 1);
} else {
score = -zwSearch(-alpha, depth - 1);
if ( score > alpha ) // in fail-soft ... && score < beta ) is common
score = -pvSearch(-beta, -alpha, depth - 1); // re-search
}
unmake
if( score >= beta )
return beta; // fail-hard beta-cutoff
if( score > alpha ) {
alpha = score; // alpha acts like max in MiniMax
bSearchPv = false; // *1)
}
}
return alpha;
}
// fail-hard zero window search, returns either beta-1 or beta
int zwSearch(int beta, int depth ) {
// alpha == beta - 1
// this is either a cut- or all-node
if( depth == 0 ) return quiesce(beta-1, beta);
for ( all moves) {
make
score = -zwSearch(1-beta, depth - 1);
unmake
if( score >= beta )
return beta; // fail-hard beta-cutoff
}
return beta-1; // fail-hard, return alpha
}
</pre>
1) it is recommend to set bSearchPv outside the score > alpha condition.
<span id="PVSandAspiration"></span>
=PVS and Aspiration=
When implementing PVS together with the [[Aspiration Windows|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").
* [[PVS and aspiration]]
A state of the art [[Fail-Soft|fail-soft]] PVS implementation, called without aspiration, was posted by [[Vincent Diepeveen]] inside the mentioned [[CCC]] thread <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=255191&t=26974 Re: PVS] by [[Vincent Diepeveen]], [[CCC]], March 14, 2009</ref> :
<pre>
Call from root:
rootscore = PVS(-infinite, infinite, depthleft);
int PVS(alfa,beta,depthleft) {
if( depthleft <= 0 ) return qsearch(alfa, beta);
// using fail soft with negamax:
make first move
bestscore = -PVS(-beta, -alfa, depthleft-1);
unmake first move
if( bestscore > alfa ) {
if( bestscore >= beta )
return bestscore;
alfa = bestscore;
}
for( all remaining moves ) {
make move
score = -PVS(-alfa-1, -alfa, depthleft-1); // alphaBeta or zwSearch
if( score > alfa && score < beta ) {
// research with window [alfa;beta]
score = -PVS(-beta, -alfa, depthleft-1);
if( score > alfa )
alfa = score;
}
unmake move
if( score > bestscore ) {
if( score >= beta )
return score;
bestscore = score;
}
}
return bestscore;
}
</pre>
=See also=
* [[Alpha-Beta]]
* [[CPW-Engine_search]]
* [[Enhanced Forward Pruning]]
* [[Iterative Deepening]]
* [[Move Ordering]]
* [[MTD(f)]]
* [[NegaScout]]
* [[Null Window]]
* [[PVS and aspiration]]
* [[Scout]]
=Publications=
==1980 ...==
* [[Judea Pearl]] ('''1980'''). ''Asymptotic Properties of Minimax Trees and Game-Searching Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 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. [http://ftp.cs.ucla.edu/pub/stat_ser/scout.pdf 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''. [[ACM#SIG|SIGART Bulletin]], Issue 72
* [[John Philip Fishburn]] ('''1981'''). ''Analysis of Speedup in Distributed Algorithms''. Ph.D. Thesis, [https://en.wikipedia.org/wiki/University_of_Wisconsin-Madison University of Wisconsin-Madison], [http://www.cs.wisc.edu/techreports/1981/TR431.pdf pdf], ''Calphabeta'' at page 167
* [[Tony Marsland]], [[Murray Campbell]] ('''1982'''). ''Parallel Search of Strongly Ordered Game Trees.'' [[ACM#Surveys|ACM Computing Surveys]], Vol. 14, No. 4, [http://www.cs.ualberta.ca/%7Etony/OldPapers/strong.pdf pdf]
* [[Murray Campbell]], [[Tony Marsland]] ('''1983'''). ''A Comparison of Minimax Tree Search Algorithms''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 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, [http://dli.iiit.ac.in/ijcai/IJCAI-83-VOL-2/PDF/040.pdf pdf]
* [[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]], [http://sc.hlrn.de/reinefeld/bib/83icca.pdf pdf]
==1985 ...==
* [[Agata Muszycka-Jones]], [[Rajjan Shinghal]] ('''1985'''). ''An empirical comparison of pruning strategies in game trees''. [[IEEE#SMC|IEEE Transactions on Systems, Man, and Cybernetics]], Vol. 15, No. 3
* [[Tony Marsland]] ('''1986'''). ''A Review of Game-Tree Pruning.'' [[ICGA Journal#9_1|ICCA Journal, Vol. 9, No. 1]], [http://www.cs.ualberta.ca/%7Etony/OldPapers/1986review.pdf pdf]
* [[Alexander Reinefeld]], [[Tony Marsland]] ('''1987'''). ''A Quantitative Analysis of Minimal Window Search.'' [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai87.html IJCAI-87], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/ijcai87.pdf pdf]
==2000 ...==
* [[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]] and [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' Accepted for publication. [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf] (with PVS modifications)
=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/3ffa1d89d13f9e86 Trick Marsland] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], February 15, 1996
* [https://www.stmintz.com/ccc/index.php?id=20868 Re: Zero-width Window Null Move Search] by [[Guido Schimmels]], [[CCC]], June 18, 1998 » [[NegaScout]]
* [https://www.stmintz.com/ccc/index.php?id=45482 Fail-soft with PVS?] by [[Will Singleton]], [[CCC]], March 09, 1999 » [[Fail-Soft]]
* [https://www.stmintz.com/ccc/index.php?id=54343 Re: negascout vs pvs] by [[Dave Gomboc]], [[CCC]], June 04, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=86122 PVS and NegaScout] by [[Gian-Carlo Pascutto]], [[CCC]], January 05, 2000
* [https://www.stmintz.com/ccc/index.php?id=102792 A Question on simple Alpha-Beta versus PVS/Negascout] by [[Andrei Fortuna]], [[CCC]], March 21, 2000 » [[Alpha-Beta]], [[NegaScout]]
* [https://www.stmintz.com/ccc/index.php?id=140872 What is Negascout and why is MWS PVS?] by [[Severi Salminen]], [[CCC]], November 24, 2000
* [https://www.stmintz.com/ccc/index.php?id=156886 Please explain the difference between PVS and NegaScout] by [[Severi Salminen]], [[CCC]], March 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=342287 QSearch() as PVS() ?] by [[Matthias Gemuh]], [[CCC]], January 14, 2004
* [https://www.stmintz.com/ccc/index.php?id=354012 Fruit - Question for Fabien] by [[Dan Honeycutt]], [[CCC]], March 11, 2004 » [[Fruit]], [[Node Types]], [[Transposition Table]], [[Principal variation]]
: [https://www.stmintz.com/ccc/index.php?id=354016 Re: Fruit - Question for Fabien] by [[Fabien Letouzey]], [[CCC]], March 11, 2004
* [https://www.stmintz.com/ccc/index.php?id=373537 Q. Aspiration, PVS, Fail-Soft] by [[David B. Weller]], [[CCC]], July 02, 2004
* [https://www.stmintz.com/ccc/index.php?id=379100 negascout and PVS?] by [[Peter Aloysius Harjanto|Peter Alloysius]], [[CCC]], July 26, 2004 » [[NegaScout]]
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6558 Slight enhancement to PVS] by [[Pradu Kannan]], [[Computer Chess Forums|Winboard Programming Forum]], June 10, 2007
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6665 Search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007 » [[Fail Soft]]
* [http://www.talkchess.com/forum/viewtopic.php?t=24883 when to try zero window search], [[CCC]], November 14, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=26974 PVS] by [[Edmund Moshammer]], [[CCC]], March 12, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=254906&t=26974 Re: PVS] by [[Robert Hyatt]], [[CCC]], March 12, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=255191&t=26974 Re: PVS] by [[Vincent Diepeveen]], [[CCC]], March 14, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=28266 No PVS at low depths?] by [[Mark Lefler]], [[CCC]], June 05, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=29681 A way to improve PVS] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], September 07, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=356836&t=35022 The strengths and weaknesses of PVS] by [[Edmund Moshammer]], [[CCC]], June 18, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38413 Memory-PV-Search] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46499 PV Search and Transposition Table] by [[Cheney Nattress]], [[CCC]], December 20, 2012
* [http://www.open-chess.org/viewtopic.php?f=5&t=2208 principle variation search] by nak3c, [[Computer Chess Forums|OpenChess Forum]], January 09, 2013
* [http://www.open-chess.org/viewtopic.php?f=5&t=2218 Implementing pvs] by [[Christian Daley|CDaley11]], [[Computer Chess Forums|OpenChess Forum]], January 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=53626 Improvement from PVS] by [[Matthew Lai]], [[CCC]], September 09, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53972 Your experience with PVS + Aspiration window] by [[Fabio Gobbato]], [[CCC]], October 07, 2014 » [[Aspiration Windows]], [[PVS and aspiration]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55709 Question on standard implementation of PVS+NWS] by Rob Williamson, [[CCC]], March 19, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=60719 PVS/NegaScout: Actual benefits] by Vincent Tang, [[CCC]], July 06, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62913 bound type in PVS ?] by [[Mahmoud Uthman]], [[CCC]], January 23, 2017 » [[Bound]], [[Exact Score]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=3084 LMR and PVS] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], February 10, 2017 » [[Late Move Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65490 PVS & Embla] by [[Folkert van Heusden]], [[CCC]], October 19, 2017 » [[Embla]]
=External Links=
* [http://web.archive.org/web/20070809015901/www.seanet.com/~brucemo/topics/pvs.htm Principal Variation Search] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]
* [https://en.wikipedia.org/wiki/Negascout NegaScout or Principal Variation Search from Wikipedia]
=Video Tutorial=
* A summary description of PVS and how it works by [[Jonathan Warkentin]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=1YdBLgmoV_E|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
