25,161
edits
Changes
Created page with "'''Home * Search * Alpha-Beta * Aspiration Windows''' FILE:TheNon-EuclideanWindow.JPG|border|right|thumb|The Non-Euclidean Window <ref>[[Arts#GerhardH..."
'''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Aspiration Windows'''
[[FILE:TheNon-EuclideanWindow.JPG|border|right|thumb|The Non-Euclidean Window <ref>[[Arts#GerhardHoehme|Gerhard Hoehme]] - The Non-Euclidean Window (1964), mixed technique / wood on canvas, [[Arts#ArtMuseumBochum|Art Museum]], [https://en.wikipedia.org/wiki/Bochum Bochum], [https://en.wikipedia.org/wiki/North_Rhine-Westphalia North Rhine-Westphalia], [https://en.wikipedia.org/wiki/Germany Germany], part of [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]] of the [https://en.wikipedia.org/wiki/Ruhr Ruhr area], Photo by [[Gerd Isenberg]], October 30, 2016</ref> ]]
'''Aspiration windows''' are a way to reduce the [[Search Space|search space]] in an alpha-beta search. The technique is to use a guess of the expected value (usually from the last iteration in [[Iterative Deepening|iterative deepening]]), and use a [[Window|window]] around this as the alpha-beta [[Bound|bounds]]. Because the window is narrower, more beta cutoffs are achieved, and the search takes a shorter time. The drawback is that if the true score is outside this window, then a costly re-search must be made. Typical window sizes are 1/2 to 1/4 of a pawn on either side of the guess.
=Gradual Widening=
Some programs, such as [[Crafty]], also use a gradual widening on re-searches. For instance, if the window is, in pawns:
[g - 1/4, g + 1/4]
and the search fails high, the next search would be
[g - 1/4, g + 1]
It's important to note that the bound that didn't fail is unchanged. In a basic alpha-beta without [[Search Instability|search instability]], one could have done the next search on
[g + 1/4, g + 1]
instead. However, a fully fledged search is typically full of [[Search Instability|search instability]], and it will often happen that the above re-search will fail low! This is why it is best to only widen the bound that fails, and leave the other bound unchanged.
Modern engines, like [[Robbolito]] or [[Stockfish]], start with a rather small aspiration window, and increase the bound that fails in an exponential fashion.
=PVS and Aspiration=
Using aspiration windows together with the [[Principal Variation Search|principal variation search]] (PVS) causes some additional complications.
* [[PVS and Aspiration]]
=See also=
* [[Null Window]]
* [[Ronald de Man#ScoringRootMoves|Scoring Root Moves]]
* [[Search Instability]]
* [[Window]]
=Publications=
* [[Hermann Kaindl]], [[Reza Shams]], [[Helmut Horacek]] ('''1991'''). ''[http://portal.acm.org/citation.cfm?id=123034 Minimax Search Algorithms with and without Aspiration Windows].'' [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 13, No. 12
* [[Reza Shams]], [[Hermann Kaindl]], [[Helmut Horacek]] ('''1991'''). ''Using Aspiration Windows for Minimax Algorithms''. [[Conferences#IJCAI1991|IJCAI 1991]], [http://ijcai.org/Proceedings/91-1/Papers/031.pdf pdf]
=Forum Posts=
==1995 ...==
* [https://www.stmintz.com/ccc/index.php?id=24677 Question about aspiration window] by [[Werner Inmann]], [[CCC]], August 14, 1998
* [https://www.stmintz.com/ccc/index.php?id=34177 aspiration windows] by [[James Swafford|James Long]], [[CCC]], November 27, 1998
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/8ad0cbc2b137dbf3 Aspiration Rules...] by Chris Pile, [[Computer Chess Forums|rgcc]], February 5, 1999
* [https://www.stmintz.com/ccc/index.php?id=49314 Aspiration search] by [[James Robertson]], [[CCC]], April 20, 1999
* [https://www.stmintz.com/ccc/index.php?id=64553 Aspiration search] by [[Scott Gasch]], [[CCC]], August 13, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=208714 Aspiration window] by [[Bas Hamstra]], [[CCC]], January 20, 2002
* [https://www.stmintz.com/ccc/index.php?id=243640 Exact value of second best move in AlphaBeta with aspiration Window] by [[Martin Bauer]], [[CCC]], August 01, 2002
* [https://www.stmintz.com/ccc/index.php?id=273558 Aspiration search, PVS] by [[Russell Reagan]], [[CCC]], December 28, 2002
* [https://www.stmintz.com/ccc/index.php?id=283426 Unstable aspiration search] by [[Sune Fischer]], [[CCC]], February 10, 2003
* [https://www.stmintz.com/ccc/index.php?id=356170 Question about aspiration search] by [[Jaime Benito de Valle Ruiz]], [[CCC]], March 23, 2004
* [https://www.stmintz.com/ccc/index.php?id=356826 What is a common Aspiration window?] by [[Joachim Rang]], [[CCC]], March 26, 2004
* [https://www.stmintz.com/ccc/index.php?id=364869 aspiration search question] by [[Daniel Shawul]], [[CCC]], May 13, 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=381004 PVS and aspiration windows] by [[Tord Romstad]], [[CCC]], August 06, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=416677 Aspiration Window sizes] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], March 14, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=27040 Bounds for aspiration window re-search] by [[Sven Schüle]], [[CCC]], March 17, 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?t=33500 Apiration window] by [[Don Dailey]], [[CCC]], March 27, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=42224 A few general questions...] by [[Bill Henry]], [[CCC]], January 29, 2012 » [[Root]], [[Exact Score]]
* [http://www.talkchess.com/forum/viewtopic.php?t=42841 optimal aspiration window for stockfish question] by [[Uri Blass]], [[CCC]], March 12, 2012 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44464 Aspiration Windows: Rubbish!] by [[Matthew R. Brades]], [[CCC]], July 16, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46624 Aspiration window - effect? Issue with hashtables?!] by [[Jens Bæk Nielsen]], [[CCC]], December 28, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46837 Aspiration Windows] by [[Jerry Donald]], [[CCC]], January 11, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47996 Aspiration windows] by [[Marco Pampaloni]], [[CCC]], May 14, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=53972 Your experience with PVS + Aspiration window] by [[Fabio Gobbato]], [[CCC]], October 07, 2014 » [[Principal Variation Search]], [[PVS and aspiration]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54241 Solving a fail low situation at the root] by [[Alberto Sanjuan]], [[CCC]], November 03, 2014 » [[Fail-Low]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57113 Parallel aspiration windows] by [[Giuseppe Cannella]], [[CCC]], July 29, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58542 Restarting iterative deepening] by [[Harm Geert Muller]], [[CCC]], December 09, 2015 » [[Fail-Low]], [[Iterative Deepening]]
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=60285 Dynamic aspiration window] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], May 26, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60402 Aspiration Windows on the root search -- Determining margin] by [[Andrew Grant]], [[CCC]], June 08, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60916 Iterative Deepening Question] by [[David Cimbalista]], [[CCC]], July 23, 2016 » [[Iterative Deepening]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2995 Aspiration window with TT question] by [[Sander Maassen vd Brink|sandermvdb]], [[Computer Chess Forums|OpenChess Forum]], August 01, 2016 » [[Transposition Table]]
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=63706 Conceptual question on aspiration windows] by Jacob Wilkins, [[CCC]], April 09, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64321 (I)ID and PV dropout] by [[Harm Geert Muller]], [[CCC]], June 17, 2017 » [[Fail-Low]], [[Internal Iterative Deepening]], [[Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65589 Aspiration window problem] by [[Sander Maassen vd Brink]], [[CCC]], October 30, 2017
=External Links=
* [http://web.archive.org/web/20070705134903/www.seanet.com/%7Ebrucemo/topics/aspiration.htm Aspiration Windows] from [[Bruce Moreland|Bruce Moreland's]] [[Bruce Moreland#Topics|Programming Topics]]
* [https://en.wikipedia.org/wiki/Aspiration Aspiration from Wikipedia]
* [https://en.wiktionary.org/wiki/aspiration aspiration - Wiktionary]
* [https://en.wiktionary.org/wiki/aspire aspire - Wiktionary]
=References=
<references />
'''[[Alpha-Beta|Up one level]]'''
[[FILE:TheNon-EuclideanWindow.JPG|border|right|thumb|The Non-Euclidean Window <ref>[[Arts#GerhardHoehme|Gerhard Hoehme]] - The Non-Euclidean Window (1964), mixed technique / wood on canvas, [[Arts#ArtMuseumBochum|Art Museum]], [https://en.wikipedia.org/wiki/Bochum Bochum], [https://en.wikipedia.org/wiki/North_Rhine-Westphalia North Rhine-Westphalia], [https://en.wikipedia.org/wiki/Germany Germany], part of [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]] of the [https://en.wikipedia.org/wiki/Ruhr Ruhr area], Photo by [[Gerd Isenberg]], October 30, 2016</ref> ]]
'''Aspiration windows''' are a way to reduce the [[Search Space|search space]] in an alpha-beta search. The technique is to use a guess of the expected value (usually from the last iteration in [[Iterative Deepening|iterative deepening]]), and use a [[Window|window]] around this as the alpha-beta [[Bound|bounds]]. Because the window is narrower, more beta cutoffs are achieved, and the search takes a shorter time. The drawback is that if the true score is outside this window, then a costly re-search must be made. Typical window sizes are 1/2 to 1/4 of a pawn on either side of the guess.
=Gradual Widening=
Some programs, such as [[Crafty]], also use a gradual widening on re-searches. For instance, if the window is, in pawns:
[g - 1/4, g + 1/4]
and the search fails high, the next search would be
[g - 1/4, g + 1]
It's important to note that the bound that didn't fail is unchanged. In a basic alpha-beta without [[Search Instability|search instability]], one could have done the next search on
[g + 1/4, g + 1]
instead. However, a fully fledged search is typically full of [[Search Instability|search instability]], and it will often happen that the above re-search will fail low! This is why it is best to only widen the bound that fails, and leave the other bound unchanged.
Modern engines, like [[Robbolito]] or [[Stockfish]], start with a rather small aspiration window, and increase the bound that fails in an exponential fashion.
=PVS and Aspiration=
Using aspiration windows together with the [[Principal Variation Search|principal variation search]] (PVS) causes some additional complications.
* [[PVS and Aspiration]]
=See also=
* [[Null Window]]
* [[Ronald de Man#ScoringRootMoves|Scoring Root Moves]]
* [[Search Instability]]
* [[Window]]
=Publications=
* [[Hermann Kaindl]], [[Reza Shams]], [[Helmut Horacek]] ('''1991'''). ''[http://portal.acm.org/citation.cfm?id=123034 Minimax Search Algorithms with and without Aspiration Windows].'' [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 13, No. 12
* [[Reza Shams]], [[Hermann Kaindl]], [[Helmut Horacek]] ('''1991'''). ''Using Aspiration Windows for Minimax Algorithms''. [[Conferences#IJCAI1991|IJCAI 1991]], [http://ijcai.org/Proceedings/91-1/Papers/031.pdf pdf]
=Forum Posts=
==1995 ...==
* [https://www.stmintz.com/ccc/index.php?id=24677 Question about aspiration window] by [[Werner Inmann]], [[CCC]], August 14, 1998
* [https://www.stmintz.com/ccc/index.php?id=34177 aspiration windows] by [[James Swafford|James Long]], [[CCC]], November 27, 1998
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/8ad0cbc2b137dbf3 Aspiration Rules...] by Chris Pile, [[Computer Chess Forums|rgcc]], February 5, 1999
* [https://www.stmintz.com/ccc/index.php?id=49314 Aspiration search] by [[James Robertson]], [[CCC]], April 20, 1999
* [https://www.stmintz.com/ccc/index.php?id=64553 Aspiration search] by [[Scott Gasch]], [[CCC]], August 13, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=208714 Aspiration window] by [[Bas Hamstra]], [[CCC]], January 20, 2002
* [https://www.stmintz.com/ccc/index.php?id=243640 Exact value of second best move in AlphaBeta with aspiration Window] by [[Martin Bauer]], [[CCC]], August 01, 2002
* [https://www.stmintz.com/ccc/index.php?id=273558 Aspiration search, PVS] by [[Russell Reagan]], [[CCC]], December 28, 2002
* [https://www.stmintz.com/ccc/index.php?id=283426 Unstable aspiration search] by [[Sune Fischer]], [[CCC]], February 10, 2003
* [https://www.stmintz.com/ccc/index.php?id=356170 Question about aspiration search] by [[Jaime Benito de Valle Ruiz]], [[CCC]], March 23, 2004
* [https://www.stmintz.com/ccc/index.php?id=356826 What is a common Aspiration window?] by [[Joachim Rang]], [[CCC]], March 26, 2004
* [https://www.stmintz.com/ccc/index.php?id=364869 aspiration search question] by [[Daniel Shawul]], [[CCC]], May 13, 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=381004 PVS and aspiration windows] by [[Tord Romstad]], [[CCC]], August 06, 2004
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=416677 Aspiration Window sizes] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], March 14, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=27040 Bounds for aspiration window re-search] by [[Sven Schüle]], [[CCC]], March 17, 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?t=33500 Apiration window] by [[Don Dailey]], [[CCC]], March 27, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=42224 A few general questions...] by [[Bill Henry]], [[CCC]], January 29, 2012 » [[Root]], [[Exact Score]]
* [http://www.talkchess.com/forum/viewtopic.php?t=42841 optimal aspiration window for stockfish question] by [[Uri Blass]], [[CCC]], March 12, 2012 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44464 Aspiration Windows: Rubbish!] by [[Matthew R. Brades]], [[CCC]], July 16, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46624 Aspiration window - effect? Issue with hashtables?!] by [[Jens Bæk Nielsen]], [[CCC]], December 28, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46837 Aspiration Windows] by [[Jerry Donald]], [[CCC]], January 11, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47996 Aspiration windows] by [[Marco Pampaloni]], [[CCC]], May 14, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=53972 Your experience with PVS + Aspiration window] by [[Fabio Gobbato]], [[CCC]], October 07, 2014 » [[Principal Variation Search]], [[PVS and aspiration]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54241 Solving a fail low situation at the root] by [[Alberto Sanjuan]], [[CCC]], November 03, 2014 » [[Fail-Low]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57113 Parallel aspiration windows] by [[Giuseppe Cannella]], [[CCC]], July 29, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58542 Restarting iterative deepening] by [[Harm Geert Muller]], [[CCC]], December 09, 2015 » [[Fail-Low]], [[Iterative Deepening]]
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=60285 Dynamic aspiration window] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], May 26, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60402 Aspiration Windows on the root search -- Determining margin] by [[Andrew Grant]], [[CCC]], June 08, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60916 Iterative Deepening Question] by [[David Cimbalista]], [[CCC]], July 23, 2016 » [[Iterative Deepening]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2995 Aspiration window with TT question] by [[Sander Maassen vd Brink|sandermvdb]], [[Computer Chess Forums|OpenChess Forum]], August 01, 2016 » [[Transposition Table]]
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=63706 Conceptual question on aspiration windows] by Jacob Wilkins, [[CCC]], April 09, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64321 (I)ID and PV dropout] by [[Harm Geert Muller]], [[CCC]], June 17, 2017 » [[Fail-Low]], [[Internal Iterative Deepening]], [[Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65589 Aspiration window problem] by [[Sander Maassen vd Brink]], [[CCC]], October 30, 2017
=External Links=
* [http://web.archive.org/web/20070705134903/www.seanet.com/%7Ebrucemo/topics/aspiration.htm Aspiration Windows] from [[Bruce Moreland|Bruce Moreland's]] [[Bruce Moreland#Topics|Programming Topics]]
* [https://en.wikipedia.org/wiki/Aspiration Aspiration from Wikipedia]
* [https://en.wiktionary.org/wiki/aspiration aspiration - Wiktionary]
* [https://en.wiktionary.org/wiki/aspire aspire - Wiktionary]
=References=
<references />
'''[[Alpha-Beta|Up one level]]'''
