Difference between revisions of "Quiescence Search"

From Chessprogramming wiki
Jump to: navigation, search
(4 intermediate revisions by the same user not shown)
Line 168: Line 168:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64030 Probe EGT in quiescence?] by [[Pham Hong Nguyen|Nguyen Pham]], [[CCC]], May 20, 2017 » [[Endgame Tablebases]], [[Chinese Chess|Xiangqi]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64030 Probe EGT in quiescence?] by [[Pham Hong Nguyen|Nguyen Pham]], [[CCC]], May 20, 2017 » [[Endgame Tablebases]], [[Chinese Chess|Xiangqi]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64674 Is expensive eval required for QS?] by [[Alexandru Mosoi]], [[CCC]], July 21, 2017 » [[Lazy Evaluation]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64674 Is expensive eval required for QS?] by [[Alexandru Mosoi]], [[CCC]], July 21, 2017 » [[Lazy Evaluation]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=64940 Cutoffs in Quiescence Search] by jfern2011, [[CCC]], August 20, 2017 » [[Beta-Cutoff]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=65903 TT in Qsearch] by [[Laurie Tunnicliffe]], [[CCC]], December 05, 2017 » [[Transposition Table]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=65903 TT in Qsearch] by [[Laurie Tunnicliffe]], [[CCC]], December 05, 2017 » [[Transposition Table]]
 
'''2019'''
 
'''2019'''
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69629 Playing transposition table moves in the Quiescence search] by [[Andrew Grant]], [[CCC]], January 17, 2019 » [[Transposition Table]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69629 Playing transposition table moves in the Quiescence search] by [[Andrew Grant]], [[CCC]], January 17, 2019 » [[Transposition Table]]
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74170 Tactical search] by [[Alvaro Cardoso]], [[CCC]], June 13, 2020 » [[Tactics]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75059 Qsearch() variant] by [[Michael Sherwin|Mike Sherwin]], [[CCC]], September 09, 2020
  
 
=External Links=  
 
=External Links=  
Line 177: Line 181:
 
* [http://web.archive.org/web/20070813042640/www.seanet.com/~brucemo/topics/quiescent.htm Quiescence Search] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]
 
* [http://web.archive.org/web/20070813042640/www.seanet.com/~brucemo/topics/quiescent.htm Quiescence Search] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]
 
* [http://www.top-5000.nl/authors/rebel/chess840.htm#QS Quiescent Search in REBEL ] from [[Ed Schroder|Ed Schröder's]] [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Stuff]
 
* [http://www.top-5000.nl/authors/rebel/chess840.htm#QS Quiescent Search in REBEL ] from [[Ed Schroder|Ed Schröder's]] [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Stuff]
* [https://en.wikipedia.org/wiki/Pim_Jacobs Pim Jacobs], [http://nl.wikipedia.org/wiki/Ruud_Jacobs Ruud Jacobs], [http://nl.wikipedia.org/wiki/Ruud_Brink Ruud Brink], [https://en.wikipedia.org/wiki/Wim_Overgaauw Wim Overgaauw], [[:Category:Dom Um Romão|Dom Um Romão]], [[:Category:Astrud Gilberto|Astrud Gilberto]] - [https://en.wikipedia.org/wiki/Meditation_%28song%29 Meditation], [https://en.wikipedia.org/wiki/It_Might_as_Well_Be_Spring It Might as Well Be Spring], Telephone Song, [https://en.wikipedia.org/wiki/Only_Trust_Your_Heart Only Trust Your Heart], [https://en.wikipedia.org/wiki/Corcovado_%28song%29 Corcovado (Quiet Nights of Quiet Stars)], [https://en.wikipedia.org/wiki/The_Girl_from_Ipanema The Girl From Ipanema]; from [http://www.cultura.nl/genres/kunst/2014/brazili-.html Dzjes Zien à la Bossa Nova], [https://en.wikipedia.org/wiki/Nederlandse_Christelijke_Radio_Vereniging NCRV] 1965, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
+
* [https://en.wikipedia.org/wiki/Pim_Jacobs Pim Jacobs], [[:Category:Ruud Jacobs|Ruud Jacobs]], [http://nl.wikipedia.org/wiki/Ruud_Brink Ruud Brink], [https://en.wikipedia.org/wiki/Wim_Overgaauw Wim Overgaauw], [[:Category:Dom Um Romão|Dom Um Romão]], [[:Category:Astrud Gilberto|Astrud Gilberto]] - [https://en.wikipedia.org/wiki/Meditation_%28song%29 Meditation], [https://en.wikipedia.org/wiki/It_Might_as_Well_Be_Spring It Might as Well Be Spring], Telephone Song, [https://en.wikipedia.org/wiki/Only_Trust_Your_Heart Only Trust Your Heart], [https://en.wikipedia.org/wiki/Corcovado_%28song%29 Corcovado (Quiet Nights of Quiet Stars)], [https://en.wikipedia.org/wiki/The_Girl_from_Ipanema The Girl From Ipanema]; from [http://www.cultura.nl/genres/kunst/2014/brazili-.html Dzjes Zien à la Bossa Nova], [https://en.wikipedia.org/wiki/Nederlandse_Christelijke_Radio_Vereniging NCRV] 1965, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
: {{#evu:https://www.youtube.com/watch?v=9DCaxN6TfH4|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=9DCaxN6TfH4|alignment=left|valignment=top}}
  
Line 185: Line 189:
 
[[Category:Astrud Gilberto]]
 
[[Category:Astrud Gilberto]]
 
[[Category:Dom Um Romão]]
 
[[Category:Dom Um Romão]]
 +
[[Category:Ruud Jacobs]]
 
[[Category:Karen Schuman]]
 
[[Category:Karen Schuman]]

Revision as of 17:57, 25 December 2020

Home * Search * Quiescence

Karen Schuman - Quiescence [1]

Most chess programs, at the end of the main search perform a more limited quiescence search, containing fewer moves. The purpose of this search is to only evaluate "quiet" positions, or positions where there are no winning tactical moves to be made. This search is needed to avoid the horizon effect. Simply stopping your search when you reach the desired depth and then evaluate, is very dangerous. Consider the situation where the last move you consider is QxP. If you stop there and evaluate, you might think that you have won a pawn. But what if you were to search one move deeper and find that the next move is PxQ? You didn't win a pawn, you actually lost a queen. Hence the need to make sure that you are evaluating only quiescent (quiet) positions.

Limiting Quiescence

Despite the fact that quiescence searches are typically very short, about 50%-90% nodes are spent there, so it is worthwhile to apply some pruning there. Apart from not trying moves with the static exchange evaluation < 0, delta pruning can be used for that purpose.

Standing Pat

In order to allow the quiescence search to stabilize, we need to be able to stop searching without necessarily searching all available captures. In addition, we need a score to return in case there are no captures available to be played. This is done by a using the static evaluation as a "stand-pat" score (the term is taken from the game of poker, where it denotes playing one's hand without drawing more cards). At the beginning of quiescence, the position's evaluation is used to establish a lower bound on the score. This is theoretically sound because we can usually assume that there is at least one move that can either match or beat the lower bound. This is based on the Null Move Observation - it assumes that we are not in Zugzwang. If the lower bound from the stand pat score is already greater than or equal to beta, we can return the stand pat score (fail-soft) or beta (fail-hard) as a lower bound. Otherwise, the search continues, keeping the evaluated "stand-pat" score as an lower bound if it exceeds alpha, to see if any tactical moves can increase alpha.

Checks

Some programs search treat checks and check evasions specially in quiescence. The idea behind this is that if the side to move is in check, the position is not quiet, and there is a threat that needs to be resolved. In this case, all evasions to the check are searched. Stand pat is not allowed if we are in check, for two reasons. First, because we are not sure that there is a move that can match alpha--in many positions a check can mean a serious threat that cannot be resolved. Second, because we are searching every move in the position, rather than only captures. Standing pat assumes that even if we finish searching all moves, and none of them increase alpha, one of the non-tactical moves can most likely raise alpha. This is not valid if we search every move. The other case of treating checks specially is the checking moves themselves. Some programs, after searching all the captures in a position without finding a move to raise alpha, will generate non-capture moves that give check. This has to be limited somehow, however, because in most given positions there will be very many long and pointless checking sequences that do not amount to anything. Most programs achieve this limit by delta pruning checks, as well as limiting the generation of checks to the first X plies of quiescence.

Pseudo Code

int Quiesce( int alpha, int beta ) {
    int stand_pat = Evaluate();
    if( stand_pat >= beta )
        return beta;
    if( alpha < stand_pat )
        alpha = stand_pat;

    until( every_capture_has_been_examined )  {
        MakeCapture();
        score = -Quiesce( -beta, -alpha );
        TakeBackMove();

        if( score >= beta )
            return beta;
        if( score > alpha )
           alpha = score;
    }
    return alpha;
}

See also

Publications

1975

1980 ...

1990 ...

2000 ...

Forum Posts

1994 ...

Re: Computer Chess: swap down evaluators vs capture search by Deniz Yuret, rgc, October 26, 1994
Re: Quiescence search problems by David Blackman, rgcc, August 3, 1995 » Integrated Bounds and Values

2000 ...

2001

2002

2004

2005 ...

2010 ...

2012

2013

2014

2015 ...

2016

2017

2019

2020 ...

External Links

References

  1. Quiescence by Karen Schuman from Artist Karen Schuman’s Personal Mythology Reviewed by Anna Poplawska
  2. Ingo Althöfer (1991). Mathematische Methoden der Künstlichen Intelligenz: Zur Quiescence-Suche in Spielbäumen. Review, ICCA Journal, Vol. 14, No. 2
  3. Jeff Rollason (2006). Looking for Alternatives to Quiescence Search. AI Factory, Autumn 2006
  4. courtesy of Don Beal and Carey Bloodworth, Re: Antique chess programs by Carey, CCC, December 16, 2015

Up one level