Aspiration windows are a way to reduce the 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), and use a window around this as the alpha-beta 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.
Some programs, such as Crafty, also use a gradual widening on re-searches. For instance, if the window is, in pawns:
and the search fails high, the next search would be
It's important to note that the bound that didn't fail is unchanged. In a basic alpha-beta without search instability, one could have done the next search on
instead. However, a fully fledged search is typically full of 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 (PVS) causes some additional complications.
Table of Contents
Gradual Widening
Some programs, such as Crafty, also use a gradual widening on re-searches. For instance, if the window is, in pawns:and the search fails high, the next search would be
It's important to note that the bound that didn't fail is unchanged. In a basic alpha-beta without search instability, one could have done the next search on
instead. However, a fully fledged search is typically full of 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 (PVS) causes some additional complications.See also
Publications
Forum Posts
1995 ...
2000 ...
2005 ...
2010 ...
2015 ...
- Parallel aspiration windows by Giuseppe Cannella, CCC, July 29, 2015
- Restarting iterative deepening by Harm Geert Muller, CCC, December 09, 2015 » Fail-Low, Iterative Deepening
2016- Dynamic aspiration window by Sergei S. Markoff, CCC, May 26, 2016
- Aspiration Windows on the root search -- Determining margin by Andrew Grant, CCC, June 08, 2016
- Iterative Deepening Question by David Cimbalista, CCC, July 23, 2016 » Iterative Deepening
- Aspiration window with TT question by sandermvdb, OpenChess Forum, August 01, 2016 » Transposition Table
2016External Links
References
What links here?
Up one level