Changes

Jump to: navigation, search

NegaScout

12,720 bytes added, 20:29, 29 April 2018
Created page with " '''Home * Search * NegaScout''' '''NegaScout''',<br/> an Alpha-Beta enhancement and improvement of Judea Pearl's Scout-algorithm <r..."

'''[[Main Page|Home]] * [[Search]] * NegaScout'''

'''NegaScout''',<br/>
an [[Alpha-Beta]] enhancement and improvement of [[Judea Pearl|Judea Pearl's]] [[Scout]]-algorithm <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>, introduced by [[Alexander Reinefeld]] in [[Timeline#1983|1983]] <ref>[[Alexander Reinefeld]] ('''1983'''). ''An Improvement to the Scout Tree-Search Algorithm.'' [[ICGA Journal#6_4|ICCA Journal, Vol. 6, No. 4]], [[hhttp://www.top-5000.nl/ps/An%20improvement%20to%20the%20scout%20tree%20search%20algorithm.pdf|pdf]]</ref>. The improvements rely on a [[Negamax]] framework and some [[Fail-Soft|fail-soft]] issues concerning the two last plies, which did not require any re-searches.

=NegaScout vs. PVS=
NegaScout works similar to [[Tony Marsland|Tony Marsland's]] and [[Murray Campbell|Murray Campbell's]] [[Principal Variation Search|PVS]] <ref>[[Tony Marsland]], [[Murray Campbell]] ('''1982'''). ''Parallel Search of Strongly Ordered Game Trees.'' ACM Comput. Surv. 14(4): 533-551, [http://www.cs.ualberta.ca/%7Etony/OldPapers/strong.pdf pdf]</ref>. NegaScout's [[Fail-Soft|fail-soft]] refinements always returns correct minimax scores at the two lowest levels, since it assumes that all [[Horizon Node|horizon nodes]] would have the same score for the (in that case redundant) re-search, which most programs can not guarantee due to possible [[Extensions|extensions]] <ref>[https://www.stmintz.com/ccc/index.php?id=54343 Re: negascout vs pvs] by [[Dave Gomboc]] from [[CCC]], June 04, 1999</ref> and possible [[Bound|bound]] dependency of [[Quiescence Search|quiescence search]] and [[Evaluation|evaluation]]. NegaScout just searches the first move with an open window, and then every move after that with a [[Null Window|zero window]], whether [[Alpha|alpha]] was already improved or not. Some PVS implementations wait until an alpha-improvement before using [[Null Window|zero window]] at [[Node Types#PV|PV-Nodes]] <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>.

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: rgb(214, 214, 214);">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, possibly due to [[Search Instability|search instability]].

While re-searching, NegaScout uses the narrower window of <span style="background-color: rgb(214, 214, 214);">{score, beta},</span> while other implementations dealing with search instability, re-search with <span style="background-color: rgb(214, 214, 214);">{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]] from [[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]]</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.

=Smallest uniform Tree=
Smallest uniform Tree showing Negascout's advantage over [[Alpha-Beta]] <ref>Smallest uniform Tree showing Negascout to Advatage, image from Reinefeld, A. ('''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>:

[[FILE:SmallestTree2.JPG|none|border|text-bottom|690px]]

=Pseudo C Code=
==Original==
by [[Alexander Reinefeld]] <ref>[http://sc.hlrn.de/reinefeld/Research/nsc.html NegaScout - A Minimax Algorithm faster than AlphaBeta]</ref>
<pre>
int NegaScout ( position p; int alpha, beta )
{ /* compute minimax value of position p */
int a, b, t, i;
if ( d == maxdepth )
return Evaluate(p); /* leaf node */
determine successors p_1,...,p_w of p;
a = alpha;
b = beta;
for ( i = 1; i <= w; i++ ) {
t = -NegaScout ( p_i, -b, -a );
if ( (t > a) && (t < beta) && (i > 1) && (d < maxdepth-1) )
a = -NegaScout ( p_i, -beta, -t ); /* re-search */
a = max( a, t );
if ( a >= beta )
return a; /* cut-off */
b = a + 1; /* set new null window */
}
return a;
}
</pre>
==Alternative==
Following implementation addresses the mentioned issues, wider window for re-searches:
<pre>
int NegaScout ( position p; int alpha, beta )
{ /* compute minimax value of position p */
int b, t, i;
if ( d == maxdepth )
return quiesce(p, alpha, beta); /* leaf node */
determine successors p_1,...,p_w of p;
b = beta;
for ( i = 1; i <= w; i++ ) {
t = -NegaScout ( p_i, -b, -alpha );
if ( (t > a) && (t < beta) && (i > 1) )
t = -NegaScout ( p_i, -beta, -alpha ); /* re-search */
alpha = max( alpha, t );
if ( alpha >= beta )
return alpha; /* cut-off */
b = alpha + 1; /* set new null window */
}
return alpha;
}
</pre>

=See also=
* [[Alpha-Beta]]
* [[Enhanced Forward Pruning]]
* [[Iterative Deepening]]
* [[Move Ordering]]
* [[MTD(f)]]
* [[Null Window]]
* [[Principal Variation Search]]
* [[PVS and aspiration]]
* [[Scout]]

=Publications=
* [[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]
* [[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]
* [[Agata Muszycka-Jones|Agata Muszycka]], [[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
* [[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]
* [[Hung-Jui Chang]], [[Meng-Tsung Tsai]], [[Tsan-sheng Hsu]] ('''2011'''). ''Game Tree Search with Adaptive Resolution''. [[Advances in Computer Games 13]], [https://www.conftool.net/acg13/index.php/Chang-Game_Tree_Search_with_Adaptive_Resolution-145.pdf?page=downloadPaper&filename=Chang-Game_Tree_Search_with_Adaptive_Resolution-145.pdf&form_id=145&form_version=final pdf]

=Forum Posts=
* [http://groups.google.com/group/gnu.chess/browse_frm/thread/d40d873b8355b6f3 nega-scout in gnuchess] by [[Bruce Moreland]], [[GNU Chess#NewsGroup|gnu.chess]], June 16, 1994
* [https://www.stmintz.com/ccc/index.php?id=20868 Re: Zero-width Window Null Move Search] by [[Guido Schimmels]], [[CCC]], June 18, 1998 » [[Principal Variation Search]]
* [https://www.stmintz.com/ccc/index.php?id=54341 negascout vs pvs] by vitor, [[CCC]], June 04, 1999
* [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]], [[Principal Variation Search]]
* [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=379100 negascout and PVS?] by [[Peter Aloysius Harjanto|Peter Alloysius]], [[CCC]], July 26, 2004
* [http://www.talkchess.com/forum/viewtopic.php?t=24883 when to try zero window search] by Andrew Short, [[CCC]], November 14, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=60719 PVS/NegaScout: Actual benefits] by Vincent Tang, [[CCC]], July 06, 2016

=External Links=
* [https://en.wikipedia.org/wiki/Negascout NegaScout from Wikipedia]
* [http://sc.hlrn.de/reinefeld/Research/nsc.html NegaScout - A Minimax Algorithm faster than AlphaBeta] by [[Alexander Reinefeld]]

=References=
<references />

'''[[Search|Up one level]]'''

Navigation menu