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
editReferences
editSources
edit- 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.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |