Aspiration window

An aspiration window is a heuristic used in pair with alpha-beta pruning in order to reduce search time for combinatorial games by supplying a window (or range) around an estimated score guess. Use of an aspiration window allows alpha-beta search to compete in the terms of efficiency against other pruning algorithms.[1]

Alpha-beta pruning achieves its performance by using cutoffs from its original range. Aspiration windows take advantage of this by supplying a smaller initial window, which increases the amount of cutoffs and therefore efficiency.[2][example needed]

However, due to search instability, the score may not always be in the window range. This may lead to a costly re-search that can penalize performance.[2] Despite this, popular engines such as Stockfish still use aspiration windows.[3]

The guess that aspiration windows use is usually supplied by the last iteration of iterative deepening.[4]

See also

References

  1. ^ Shams, Kaindl & Horacek 1991, p. 192.
  2. ^ a b Bruce Moreland's Programming Topics: Aspiration Windows
  3. ^ Stockfish source code - direct aspiration window mention
  4. ^ Computer Chess Programming Theory: Aspiration Windows

Sources

  • Shams, Reza; Kaindl, Hermann; Horacek, Helmut (August 1991). "Using aspiration windows for minimax algorithms" (PDF). IJCAI'91: Proceedings of the 12th International Joint Conference on Artificial Intelligence. 1: 192–197.


Stub icon

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.