Home * Search * Search Instability
external image 300px-Crab_Nebula.jpg

Search Instability is 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.
Rayleigh–Taylor instability in the Crab Nebula [1]

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


External Links


References

  1. ^ Rayleigh–Taylor instability from Wikipedia,
  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

What links here?


Up one Level