Search Instability
Search Instability,
a search phenomenon in alpha-beta and enhancements, where re-searches, most often with different windows leave contradicting results, for instance with aspiration windows at the root, an unexpected fail-low after a fail-high or vice versa. Beside other things, it may caused by graph history interaction or path-dependency in conjunction with the transposition table, as well as alpha-beta window dependencies of pruning decisions, like null move pruning, futility pruning, and history heuristic to decide about LMR.
Contents
Pragmatism
Some programmers abandon aspiration windows [2] , while others don't immediately return from a PV-nodes in case of sufficient exact hits from transposition table [3].
Quotes
In his Programming Topics, Bruce Moreland elaborates on Search Instability [4] :
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
- Astronomy
- Graph History Interaction
- Path-Dependency
- Principal Variation Search
- Transposition Table
- Window
Forum Posts
1994 ...
- Alpha-beta inconsistencies by Chua Kong Sian, rec.games.chess, February 19, 1994
- Search inconsistency by Bruce Moreland, rgcc, December 17, 1998
- Question: Fail High then Low at Root by William Bryant, CCC, December 28, 1999 » Fail-High, Fail-Low, Root
2000 ...
- Fail highs..which subsequently fail low by Tom King, CCC, August 27, 2000 » Fail-High, Fail-Low
- Search Inconsistencies by mjlef, Winboard Forum, June 23, 2006
2010 ...
- Fail-High / Fail-Low in mate situations... by Steve Maughan, CCC, August 24, 2013
- Fail low after fail high by J. Wesley Cleveland, CCC, April 04, 2015 » Fail-Low, Fail-High
- Ordering of Root moves and search instability ! by Mahmoud Uthman, CCC, October 26, 2015 » Move Ordering
- Shifting alpha/beta on hash hit by Martin Fierz, CCC, April 14, 2016 » Transposition Table
External Links
- Search Instability from Bruce Moreland's Programming Topics
- Aspiration Windows from Bruce Moreland's Programming Topics
- Instability from Wikipedia
References
- ↑ This is a mosaic image, one of the largest ever taken by NASA/ESA's Hubble Space Telescope of the Crab Nebula, a six-light-year-wide expanding remnant of a star's supernova explosion. Japanese and Chinese astronomers recorded this violent event nearly 1,000 years ago in 1054, as did, almost certainly, Native Americans. Rayleigh–Taylor instability from Wikipedia, HubbleSite - NewsCenter - A Giant Hubble Mosaic of the Crab Nebula (12/01/2005) - Release Images, December 01, 2005
- ↑ Re: PVS by Vincent Diepeveen, CCC, March 12, 2009
- ↑ Re: Transposition table pruning by Joona Kiiski, CCC, November 25, 2009
- ↑ Search Instability from Bruce Moreland's Programming Topics
