Search Instability

From Chessprogramming wiki
Jump to: navigation, search

Home * 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.

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

Forum Posts

1994 ...

2000 ...

2010 ...

External Links

References

  1. 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
  2. Re: PVS by Vincent Diepeveen, CCC, March 12, 2009
  3. Re: Transposition table pruning by Joona Kiiski, CCC, November 25, 2009
  4. Search Instability from Bruce Moreland's Programming Topics

Up one Level