Quiescence Search
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.
Contents
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
- Bobby's Strategic Quiescence Search
- CPW-Engine_quiescence
- Don Beal's Generalized Quiescence Search
- Crossovers
- Delta Pruning
- Horizon Effect
- Horizon Node
- MVV-LVA
- Quiescent Node
- Search Explosion
- Static Exchange Evaluation
- Swap-off algorithm - SOMA
- Swap-off by Helmut Richter
- Vice Video on Quiescence
- Zzzzzz' Quiescence Search
Publications
1975
- Larry Harris (1975) The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play. IJCAI 1975 Tbilisi, Georgia: 334-339. reprinted (1988) in Computer Chess Compendium
1980 ...
- Hermann Kaindl (1982). Dynamic Control of the Quiescence Search in Computer Chess. Cybernetics and Systems Research (ed. R. Trappl), pp. 973-977. North-Holland, Amsterdam.
- Hermann Kaindl (1982). Quiescence Search in Computer Chess. SIGART Newsletter, 80, pp. 124-131. Reprinted (1983) in Computer-Game-Playing: Theory and Practice, pp. 39-52. Ellis Horwood Ltd., Chichester.
- Don Beal (1984). Mating Sequences in the Quiescence Search. ICCA Journal, Vol. 7, No. 3
- Prakash Bettadapur (1986). Experiments in Chess Capture Search, M.Sc. Thesis, Department of Computing Science, University of Alberta.
- Prakash Bettadapur (1986). Influence of Ordering on Capture Search. ICCA Journal, Vol. 9, No. 4
- Prakash Bettadapur, Tony Marsland (1988). Accuracy and Savings in Depth-Limited Capture Search. In International Journal of Man-Machine Studies, 29 (5) pp. 497-502
- Don Beal (1989). Experiments with the Null Move. Advances in Computer Chess 5, a revised version is published (1990) under the title A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702, edited version in (1999). The Nature of MINIMAX Search. Ph.D. thesis, IKAT, ISBN 90-62-16-6348. Chapter 10, pp. 101-116 » Null Move
- Günther Schrüfer (1989). A Strategic Quiescence Search. ICCA Journal, Vol. 12, No. 1 » Bobby's Strategic Quiescence Search
1990 ...
- Don Beal (1990). A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702
- Sören Walter Perrey (1991). Mathematische Methoden der Künstlichen Intelligenz: Zur Quiescence-Suche in Spielbäumen. Diplom thesis, Sonderforschungsbereich 343, E91-006, University of Bielefeld (German) [2]
- Michael Gherrity, Paul Kube (1993). Quiescent Search is Beneficial. Technical Report CS93-289, University of California, San Diego
- Don Beal (1999). The Nature of MINIMAX Search. Ph.D. thesis, IKAT, ISBN 90-62-16-6348
2000 ...
- Jeff Rollason (2000). SUPER-SOMA - Solving Tactical Exchanges in Shogi without Tree Searching. Lecture Notes In Computer Science, Vol. 2063, CG 2000, Word preprint [3]
- Jeff Rollason (2006). Looking for Alternatives to Quiescence Search. AI Factory, Autumn 2006
- Don Beal (2006). Review of a nullmove-quiescence search mechanism from 1986. File:Alg1986review.txt (Draft) [4]
- Maarten Schadd, Mark Winands (2009). Quiescence Search for Stratego. In BNAIC 2009, pdf
Forum Posts
1994 ...
- Efficient quiescence by Hans Bogaards, rec.games.chess, January 19, 1994
- Computer Chess: swap down evaluators vs capture search by Jon Dart, rgc, October 24, 1994 » Swap-off algorithm - SOMA
- Re: Computer Chess: swap down evaluators vs capture search by Deniz Yuret, rgc, October 26, 1994
- quiescence search problems by Matt Craighead, rgcc, August 01, 1995
- Re: Quiescence search problems by David Blackman, rgcc, August 3, 1995 » Integrated Bounds and Values
- quiescent vs non-quiescent node counting by Robert Hyatt, rgcc, July 01, 1996
- Deep Quiesence Searching by Steve Dicks, rgcc, February 22, 1997
- quiescence search by Andrew Tridgell, rgcc, April 16, 1997 » Check, Crafty
- Limiting the QSearch by John Scalo, CCC, December, 30, 1997
- Quiescence vs swapoff by Peter Fendrich, CCC, April 15, 1998
- SEE for forward pruning in Q. Search by Tom King, CCC, August 04, 1999 » SEE
- SEE for forward pruning in the Q. search - I'm confused! by Tom King, CCC, August 11, 1999
2000 ...
- What is the q-search? by Leonid, CCC, January 07, 2000
- Qsearch problems...(about sorting and SEE) by Severi Salminen, CCC, November 26, 2000 » Static Exchange Evaluation
2001
- Bonus points for side to move in qsearch? by Leen Ammeraal, CCC, January 06, 2001 » Tempo
- About limiting Qsearch, again... by Severi Salminen, CCC, December 29, 2001
- About qsearch... by Severi Salminen, CCC, December 27, 2001
- Qsearch survey by Severi Salminen, CCC, December 30, 2001
2002
- Checks in the Qsearch by Scott Gasch, CCC, June 28, 2002 » Check
- A question about quiescence search by Nagendra Singh Tomar, CCC, October 19, 2002
- Quiescence Explosion by David Rasmussen, CCC, November 26, 2002
- Quiescent Explosion by macaroni, CCC, June 26, 2003
- Regarding Qsearch with Fractional ply extensions by Federico Corigliano, CCC, August 11, 2003 » Depth - Fractional Plies
- real job of the qSearch? find quiet vs stop horizon effect by Scott Farrell, CCC, August 28, 2003
- quiescence by Noah Roberts, rgcc, September 20, 2003
2004
- QSearch() as PVS() ? by Matthias Gemuh, CCC, January 14, 2004
- Rebel's long checks concept in QS by milix, CCC, January 23, 2004 » Rebel, Check
- quiesce node explosion by Mike Siler, CCC, January 24, 2004
- Qsearch Checks by Tor Lattimore, CCC, August 29, 2004 » Check
- Checks in QSearch by Dan Honeycutt, Winboard Programming Forum, November 23, 2004
2005 ...
- quiescence search / horizon question by Andrew Shapira, CCC, August 26, 2005
- How to Best Limit Checks in the Quiescence ? by Stuart Cracraft, CCC, August 20, 2007 » Check, Checks in Quiescence Search
- Quiescence Search Explosions by Mike Leany, CCC, April 18, 2008
- checks in q-search by Robert Hyatt, CCC, September 02, 2008
- Limiting Quiescent Search Depth by John Merlino, CCC, May 20, 2009
- Null move in quiescence search idea from Don Beal, 1986 by Eelco de Groot, CCC, Aug 17, 2009 » Null Move Pruning, Don Beal
- Threat information from evaluation to inform q-search by Gary, CCC, September 15, 2009
- Only recaptures in qsearch? by John Merlino, CCC, November 21, 2009
2010 ...
- Avoiding qsearch explosion by Marco Costalba, CCC, January 29, 2010
- Problems when implementing checks in qsearch by Luca Hemmerich, CCC, February 03, 2010
- Standpat and check by Vlad Stamate, CCC, February 06, 2010 » Standing Pat, Check
- This is totally weird ... Don't understand at all by Gregory Strong, CCC, November 13, 2010
2012
- checks in quies by Larry Kaufman, CCC, March 22, 2012
- stand pat or side to move bonus by Larry Kaufman, CCC, March 22, 2012
- Some thoughts on QS by Harm Geert Muller, CCC, July 19, 2012
- QSearch, checks and the lack of progress... by Mincho Georgiev, CCC, July 27, 2012
- Quiescence - Check Evaluation and Depth Control by Cheney Nattress, CCC, November 10, 2012
2013
- Quiescent search, and side to move is in check by Louis Zulli, CCC, February 08, 2013
- Transposition table usage in quiescent search? by Jerry Donald, CCC, March 01, 2013 » Transposition Table
- Pruning in QS by Harm Geert Muller, CCC, March 06, 2013 » Pruning
- QS investigation by Ed Schröder, CCC, March 07, 2013
- qsearch question by nak3c, OpenChess Forum, August 19, 2013
- about qs by Daniel Anulliero, CCC, September 11, 2013
2014
- Positional quiesence by Harm Geert Muller, CCC, April 12, 2014
- Transposition table in Q-search by Alex Ferguson, CCC, December 26, 2014 » Transposition Table
2015 ...
- Detail evaluation within quiescence search by Reinhard Scharnagl, CCC, February 22, 2015
- hanging piece at starting quiescence search - how to handle? by Reinhard Scharnagl, CCC, February 22, 2015 » Hanging Piece
- Search algorithm in it's simplest forum by Mahmoud Uthman, CCC, February 25, 2015 » Alpha-Beta
- Check-extension in QS by Harm Geert Muller, CCC, April 03, 2015 » Check
- quiescence search (best practices) by thevinenator, OpenChess Forum, July 02, 2015
- Null Move in Quiescent search by Laurie Tunnicliffe, CCC, December 09, 2015 » Null Move Pruning, Search Pathology
2016
- Checks in qsearch - must-have or optional? by Martin Fierz, CCC, March 15, 2016 » Check, Checks in Quiescence Search
- Hashing in Qsearch? by Martin Fierz, CCC, April 03, 2016 » Transposition Table
- Quiescence node explosion by sandermvdb, OpenChess Forum, June 01, 2016 » Search Explosion
- Starting with quiescence search by Luis Babboni, CCC, July 28, 2016
- Quiescence Search Performance by David Cimbalista, CCC, July 28, 2016
- Removing Q-search by Matthew Lai, CCC, September 02, 2016
- Searching using slow eval with tactical verification by Matthew Lai, CCC, September 06, 2016
- Collecting PVs of Qsearch ? by Mahmoud Uthman, CCC, October 22, 2016 » Principal Variation, Triangular PV-Table
2017
- capturing PV in QSearch by thevinenator, OpenChess Forum, January 20, 2017 » Principal Variation, Triangular PV-Table
- Ridiculous QSearch Depth by Jonathan Rosenthal, CCC, March 03, 2017 » Depth
- Q search explosion by Colin Jenkins, CCC, March 30, 2017 » Search Explosion
- Probe EGT in quiescence? by Nguyen Pham, CCC, May 20, 2017 » Endgame Tablebases, Xiangqi
- Is expensive eval required for QS? by Alexandru Mosoi, CCC, July 21, 2017 » Lazy Evaluation
External Links
- Quiescence search from Wikipedia
- Quiescence from Wikipedia
- Quiescence Search from Bruce Moreland's Programming Topics
- Quiescent Search in REBEL from Ed Schröder's Programmer Stuff
- Pim Jacobs, Ruud Jacobs, Ruud Brink, Wim Overgaauw, Dom Um Romão, Astrud Gilberto - Meditation, It Might as Well Be Spring, Telephone Song, Only Trust Your Heart, Corcovado (Quiet Nights of Quiet Stars), The Girl From Ipanema; from Dzjes Zien à la Bossa Nova, NCRV 1965, YouTube Video
References
- ↑ Quiescence by Karen Schuman from Artist Karen Schuman’s Personal Mythology Reviewed by Anna Poplawska
- ↑ Ingo Althöfer (1991). Mathematische Methoden der Künstlichen Intelligenz: Zur Quiescence-Suche in Spielbäumen. Review, ICCA Journal, Vol. 14, No. 2
- ↑ Jeff Rollason (2006). Looking for Alternatives to Quiescence Search. AI Factory, Autumn 2006
- ↑ courtesy of Don Beal and Carey Bloodworth, Re: Antique chess programs by Carey, CCC, December 16, 2015