25,161
edits
Changes
Created page with "'''Home * Search * Instability''' FILE:Crab Nebula.jpg|border|right|thumb|[https://en.wikipedia.org/wiki/Rayleigh%E2%80%93Taylor_instability Rayleigh–Ta..."
'''[[Main Page|Home]] * [[Search]] * Instability'''
[[FILE:Crab Nebula.jpg|border|right|thumb|[https://en.wikipedia.org/wiki/Rayleigh%E2%80%93Taylor_instability Rayleigh–Taylor instability] in the [https://en.wikipedia.org/wiki/Crab_Nebula Crab Nebula] <ref>[https://en.wikipedia.org/wiki/File:Crab_Nebula.jpg This] is a [https://en.wikipedia.org/wiki/Photographic_mosaic mosaic image], one of the largest ever taken by [https://en.wikipedia.org/wiki/NASA NASA]/[https://en.wikipedia.org/wiki/European_Space_Agency ESA's] [https://en.wikipedia.org/wiki/Hubble_Space_Telescope Hubble Space Telescope] of the [https://en.wikipedia.org/wiki/Crab_Nebula Crab Nebula], a six-light-year-wide expanding remnant of a star's [https://en.wikipedia.org/wiki/Supernova supernova explosion]. Japanese and Chinese astronomers recorded this violent event nearly 1,000 years ago in 1054, as did, almost certainly, Native Americans. [https://en.wikipedia.org/wiki/Rayleigh%E2%80%93Taylor_instability Rayleigh–Taylor instability from Wikipedia], [http://hubblesite.org/newscenter/archive/releases/2005/37/image/a/ HubbleSite - NewsCenter - A Giant Hubble Mosaic of the Crab Nebula (12/01/2005) - Release Images], December 01, 2005</ref> ]]
'''Search Instability''',<br/>
a search phenomenon in [[Alpha-Beta|alpha-beta]] and enhancements, where re-searches, most often with different [[Window|windows]] leave contradicting results, for instance with [[Aspiration Windows|aspiration windows]] at the [[Root|root]], an unexpected [[Fail-Low|fail-low]] after a [[Fail-High|fail-high]] or vice versa. Beside other things, it may caused by [[Graph History Interaction|graph history interaction]] or [[Path-Dependency|path-dependency]] in conjunction with the [[Transposition Table|transposition table]], as well as alpha-beta window dependencies of [[Pruning|pruning]] decisions, like [[Null Move Pruning|null move pruning]], [[Futility Pruning|futility pruning]], and [[History Heuristic|history heuristic]] to decide about [[Late Move Reductions|LMR]].
=Pragmatism=
Some programmers abandon aspiration windows <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=254862 Re: PVS] by [[Vincent Diepeveen]], [[CCC]], March 12, 2009</ref> , while others don't immediately return from a [[Node Types#PV|PV-nodes]] in case of sufficient [[Exact Score|exact]] hits from transposition table <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=305236&t=30788 Re: Transposition table pruning] by [[Joona Kiiski]], [[CCC]], November 25, 2009</ref>.
=Quotes=
In his ''Programming Topics'', [[Bruce Moreland]] elaborates on Search Instability <ref>[http://web.archive.org/web/20070704214238/www.seanet.com/%7Ebrucemo/topics/instability.htm Search Instability] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]</ref> :
Search instability is something that happens when you try to write a program that is strong, as opposed to one that is perfect. There are many causes of instability, and I will discuss how various search enhancements can lead to instability, when I discuss those enhancements. A few other search techniques must take into account the possibility of instability.
An unstable search is one that returns results that don't make any sense. You have an alpha-beta window of (5, 25) and fail high. So you re-search with (24, INFINITY) and fail low. This shouldn't happen, because the fail-high indicated very clearly that the score should be 25 or better. How can you fail low?
Fact is, a lot of the things that make a chess program fast or strong do sleazy things that result in searches returning slightly different values when called with different windows, and if you aren't expecting the values you get, you can crash or have a bug that might make your program play a dumb move.
Some chess programmers can't handle the idea of search instability, and they are willing to let very good search techniques go in order to avoid it, or in order to think that they are avoiding it.
I wish it was possible to get rid of it completely, but as long as certain very basic techniques are used, it will be a problem. I think that the solution is to defend against crashes and bad behavior, then try to put it out of your mind.
=See also=
* [[Alpha-Beta]]
* [[Aspiration Windows]]
* [[Various Classifications#Astronomy|Astronomy]]
* [[Graph History Interaction]]
* [[Path-Dependency]]
* [[Principal Variation Search]]
* [[Transposition Table]]
* [[Window]]
=Forum Posts=
==1994 ...==
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/b5f847cde3d26fd6 Alpha-beta inconsistencies] by [[Chua Kong Sian]], [[Computer Chess Forums|rec.games.chess]], February 19, 1994
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/2f916d80413c656f Search inconsistency] by [[Bruce Moreland]], [[Computer Chess Forums|rgcc]], December 17, 1998
* [https://www.stmintz.com/ccc/index.php?id=84651 Question: Fail High then Low at Root] by [[William Bryant]], [[CCC]], December 28, 1999 » [[Fail-High]], [[Fail-Low]], [[Root]]
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=126878 Fail highs..which subsequently fail low] by [[Tom King]], [[CCC]], August 27, 2000 » [[Fail-High]], [[Fail-Low]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5072 Search Inconsistencies] by [[Mark Lefler|mjlef]], [[Computer Chess Forums|Winboard Forum]], June 23, 2006
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=49081 Fail-High / Fail-Low in mate situations...] by [[Steve Maughan]], [[CCC]], August 24, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=55889 Fail low after fail high] by [[J. Wesley Cleveland]], [[CCC]], April 04, 2015 » [[Fail-Low]], [[Fail-High]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58055 Ordering of Root moves and search instability !] by [[Mahmoud Uthman]], [[CCC]], October 26, 2015 » [[Move Ordering]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59856 Shifting alpha/beta on hash hit] by [[Martin Fierz]], [[CCC]], April 14, 2016 » [[Transposition Table]]
=External Links=
* [http://web.archive.org/web/20070704214238/www.seanet.com/%7Ebrucemo/topics/instability.htm Search Instability] 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/20070705134903/www.seanet.com/%7Ebrucemo/topics/aspiration.htm Aspiration Windows] 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/Instability Instability from Wikipedia]
=References=
<references />
'''[[Search|Up one Level]]'''
[[FILE:Crab Nebula.jpg|border|right|thumb|[https://en.wikipedia.org/wiki/Rayleigh%E2%80%93Taylor_instability Rayleigh–Taylor instability] in the [https://en.wikipedia.org/wiki/Crab_Nebula Crab Nebula] <ref>[https://en.wikipedia.org/wiki/File:Crab_Nebula.jpg This] is a [https://en.wikipedia.org/wiki/Photographic_mosaic mosaic image], one of the largest ever taken by [https://en.wikipedia.org/wiki/NASA NASA]/[https://en.wikipedia.org/wiki/European_Space_Agency ESA's] [https://en.wikipedia.org/wiki/Hubble_Space_Telescope Hubble Space Telescope] of the [https://en.wikipedia.org/wiki/Crab_Nebula Crab Nebula], a six-light-year-wide expanding remnant of a star's [https://en.wikipedia.org/wiki/Supernova supernova explosion]. Japanese and Chinese astronomers recorded this violent event nearly 1,000 years ago in 1054, as did, almost certainly, Native Americans. [https://en.wikipedia.org/wiki/Rayleigh%E2%80%93Taylor_instability Rayleigh–Taylor instability from Wikipedia], [http://hubblesite.org/newscenter/archive/releases/2005/37/image/a/ HubbleSite - NewsCenter - A Giant Hubble Mosaic of the Crab Nebula (12/01/2005) - Release Images], December 01, 2005</ref> ]]
'''Search Instability''',<br/>
a search phenomenon in [[Alpha-Beta|alpha-beta]] and enhancements, where re-searches, most often with different [[Window|windows]] leave contradicting results, for instance with [[Aspiration Windows|aspiration windows]] at the [[Root|root]], an unexpected [[Fail-Low|fail-low]] after a [[Fail-High|fail-high]] or vice versa. Beside other things, it may caused by [[Graph History Interaction|graph history interaction]] or [[Path-Dependency|path-dependency]] in conjunction with the [[Transposition Table|transposition table]], as well as alpha-beta window dependencies of [[Pruning|pruning]] decisions, like [[Null Move Pruning|null move pruning]], [[Futility Pruning|futility pruning]], and [[History Heuristic|history heuristic]] to decide about [[Late Move Reductions|LMR]].
=Pragmatism=
Some programmers abandon aspiration windows <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=254862 Re: PVS] by [[Vincent Diepeveen]], [[CCC]], March 12, 2009</ref> , while others don't immediately return from a [[Node Types#PV|PV-nodes]] in case of sufficient [[Exact Score|exact]] hits from transposition table <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=305236&t=30788 Re: Transposition table pruning] by [[Joona Kiiski]], [[CCC]], November 25, 2009</ref>.
=Quotes=
In his ''Programming Topics'', [[Bruce Moreland]] elaborates on Search Instability <ref>[http://web.archive.org/web/20070704214238/www.seanet.com/%7Ebrucemo/topics/instability.htm Search Instability] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]</ref> :
Search instability is something that happens when you try to write a program that is strong, as opposed to one that is perfect. There are many causes of instability, and I will discuss how various search enhancements can lead to instability, when I discuss those enhancements. A few other search techniques must take into account the possibility of instability.
An unstable search is one that returns results that don't make any sense. You have an alpha-beta window of (5, 25) and fail high. So you re-search with (24, INFINITY) and fail low. This shouldn't happen, because the fail-high indicated very clearly that the score should be 25 or better. How can you fail low?
Fact is, a lot of the things that make a chess program fast or strong do sleazy things that result in searches returning slightly different values when called with different windows, and if you aren't expecting the values you get, you can crash or have a bug that might make your program play a dumb move.
Some chess programmers can't handle the idea of search instability, and they are willing to let very good search techniques go in order to avoid it, or in order to think that they are avoiding it.
I wish it was possible to get rid of it completely, but as long as certain very basic techniques are used, it will be a problem. I think that the solution is to defend against crashes and bad behavior, then try to put it out of your mind.
=See also=
* [[Alpha-Beta]]
* [[Aspiration Windows]]
* [[Various Classifications#Astronomy|Astronomy]]
* [[Graph History Interaction]]
* [[Path-Dependency]]
* [[Principal Variation Search]]
* [[Transposition Table]]
* [[Window]]
=Forum Posts=
==1994 ...==
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/b5f847cde3d26fd6 Alpha-beta inconsistencies] by [[Chua Kong Sian]], [[Computer Chess Forums|rec.games.chess]], February 19, 1994
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/2f916d80413c656f Search inconsistency] by [[Bruce Moreland]], [[Computer Chess Forums|rgcc]], December 17, 1998
* [https://www.stmintz.com/ccc/index.php?id=84651 Question: Fail High then Low at Root] by [[William Bryant]], [[CCC]], December 28, 1999 » [[Fail-High]], [[Fail-Low]], [[Root]]
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=126878 Fail highs..which subsequently fail low] by [[Tom King]], [[CCC]], August 27, 2000 » [[Fail-High]], [[Fail-Low]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5072 Search Inconsistencies] by [[Mark Lefler|mjlef]], [[Computer Chess Forums|Winboard Forum]], June 23, 2006
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=49081 Fail-High / Fail-Low in mate situations...] by [[Steve Maughan]], [[CCC]], August 24, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=55889 Fail low after fail high] by [[J. Wesley Cleveland]], [[CCC]], April 04, 2015 » [[Fail-Low]], [[Fail-High]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58055 Ordering of Root moves and search instability !] by [[Mahmoud Uthman]], [[CCC]], October 26, 2015 » [[Move Ordering]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59856 Shifting alpha/beta on hash hit] by [[Martin Fierz]], [[CCC]], April 14, 2016 » [[Transposition Table]]
=External Links=
* [http://web.archive.org/web/20070704214238/www.seanet.com/%7Ebrucemo/topics/instability.htm Search Instability] 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/20070705134903/www.seanet.com/%7Ebrucemo/topics/aspiration.htm Aspiration Windows] 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/Instability Instability from Wikipedia]
=References=
<references />
'''[[Search|Up one Level]]'''
