25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Search]] * Quiescence'''
[[FILE:Quiescence.jpg|border|right|thumb|link=http://www.yogachicago.com/jan06/art.shtml|[[Arts#:Category:Karen Schuman|Karen Schuman]], - Quiescence <ref>Quiescence by [[Arts#:Category:Karen Schuman|Karen Schuman]] from [http://www.yogachicago.com/jan06/art.shtml Artist Karen Schuman’s Personal Mythology] Reviewed by [http://www.chicagoartcriticsassociation.org/B/poplawska.html Anna Poplawska]</ref> ]]
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 [[Evaluation|evaluate]] "quiet" [[Chess Position|positions]], or positions where there are no winning [[Tactical Moves|tactical moves]] to be made. This search is needed to avoid the [[Horizon Effect|horizon effect]]. Simply stopping your search when you reach the desired [[Depth|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.
<span id="StandPat"></span>
=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|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 [[Evaluation|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|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|fail-soft]]) or [[Beta|beta]] ([[Fail-Hard|fail-hard]]) as a [[Lower Bound|lower bound]]. Otherwise, the search continues, keeping the evaluated "stand-pat" score as an [[Lower Bound|lower bound]] if it exceeds [[Alpha|alpha]], to see if any [[Tactical movesMoves|tactical moves]] can increase [[Alpha|alpha]].
<span id="Checks"></span>
=Checks=
* [[Bobby#StrategicQuiescenceSearch|Bobby's Strategic Quiescence Search]]
* [[CPW-Engine_quiescence]]
* [[Horizon Effect#Crossovers|Crossovers]]
* [[Delta Pruning]]
* [[Null Move Pruning#NMQS|Generalized Quiescence Search]] by [[Don Beal]]
* [[Horizon Effect]]
* [[Horizon Node]]
* [[SOMA#Swapoff|Swap-off algorithm - SOMA]]
* [[Helmut Richter#Swapoff|Swap-off]] by [[Helmut Richter]]
* [[Excalibur Mirage#TacticalQuiescence|Tactical Quiescence Search]] in [[Excalibur Mirage]]
* [[Vice#Quiescence|Vice Video on Quiescence]]
* [[Zzzzzz#Quiescence|Zzzzzz' Quiescence Search]]
* [[Jeff Rollason]] ('''2000'''). ''SUPER-SOMA - Solving Tactical Exchanges in Shogi without Tree Searching''. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes In Computer Science], Vol. 2063, [[CG 2000]], [http://www.aifactory.co.uk/downloads/SUPER-SOMA.doc Word preprint] <ref>[[Jeff Rollason]] ('''2006'''). ''[http://www.aifactory.co.uk/newsletter/2006_03_quiescence_alts.htm Looking for Alternatives to Quiescence Search]''. [[AI Factory]], Autumn 2006</ref>
* [[Jeff Rollason]] ('''2006'''). ''[http://www.aifactory.co.uk/newsletter/2006_03_quiescence_alts.htm Looking for Alternatives to Quiescence Search]''. [[AI Factory]], Autumn 2006
* [[Don Beal]] ('''2006'''). ''[[File:alg1986review.txt|Review of a nullmove-quiescence search mechanism from 1986]]''. [[FILE:alg1986review.txt]] (Draft) <ref>courtesy of [[Don Beal]] and [[Carey Bloodworth]], [http://www.talkchess.com/forum/viewtopic.php?t=58603&start=13 Re: Antique chess programs] by [[Carey Bloodworth|Carey]], [[CCC]], December 16, 2015</ref>
* [[Maarten Schadd]], [[Mark Winands]] ('''2009'''). ''Quiescence Search for Stratego''. In BNAIC 2009, [http://www.personeel.unimaas.nl/Maarten-Schadd/Papers/2009StrategoBNAIC1.pdf pdf]
* [http://www.talkchess.com/forum/viewtopic.php?t=42971 checks in quies] by [[Larry Kaufman]], [[CCC]], March 22, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=42982 stand pat or side to move bonus] by [[Larry Kaufman]], [[CCC]], March 22, 2012
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=43769 TT question?] by [[Fermin Serrano]], [[CCC]], May 19, 2012 » [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44507 Some thoughts on QS] by [[Harm Geert Muller]], [[CCC]], July 19, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44599 QSearch, checks and the lack of progress...] by [[Mincho Georgiev]], [[CCC]], July 27, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=45942 Quiescence - Check Evaluation and Depth Control] by [[Cheney Nattress]], [[CCC]], November 10, 2012
'''2013'''
* [http://www.open-chess.org/viewtopic.php?f=5&t=2212 Quiescence Search and Checkmates] by [[Christian Daley|CDaley11]], [[Computer Chess Forums|OpenChess Forum]], January 11, 2013 » [[Checkmate]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47162 Quiescent search, and side to move is in check] by [[Louis Zulli]], [[CCC]], February 08, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47373 Transposition table usage in quiescent search?] by [[Jerry Donald]], [[CCC]], March 01, 2013 » [[Transposition Table]]
* [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/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]]
'''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]]
==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
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76706 Quiescence Search doesn't improve strength] by [[Thomas Jahn]], [[CCC]], February 25, 2021
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77286 For or against the transposition table probe in quiet search?] by [[Eugene Kotlov]], [[CCC]], May 11, 2021 » [[Transposition Table]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77380 Qsearch dynamic order besides MVV/LVA] by [[Aleks Peshkov]], [[CCC]], May 25, 2021 » [[Move Ordering]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77451 Futility Pruning and its Relation to Quiescence Search] by [[Jakob Progsch]], [[CCC]], June 06, 2021 » [[Futility Pruning]]
=External Links=
* [https://en.wikipedia.org/wiki/Quiescence_search Quiescence search from Wikipedia]
* [https://en.wikipedia.org/wiki/Quiescence Quiescence from Wikipedia]
* [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]([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])* [https://web.archive.org/web/20120331060714/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 JacobsWayback_Machine Wayback Machine], )* [httphttps://nlen.wikipedia.org/wiki/Ruud_Jacobs 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], [[Videos#DomUmRomao:Category:Dom Um Romão|Dom Um Romão]], [https[:Category://en.wikipedia.org/wiki/Astrud_Gilberto 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}}
<references />
'''[[Search|Up one level]]'''
[[Category:Astrud Gilberto]]
[[Category:Dom Um Romão]]
[[Category:Ruud Jacobs]]
[[Category:Karen Schuman]]
