An aspiration window is a heuristic used in pair with
alpha-beta pruning Alphabeta or Alpha Beta may also refer to:
* Alphabeta, an Israeli musical group
* Alpha Beta, a former chain of Californian supermarkets
* The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters
* Alpha and beta anome ...
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.
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.
However, due to search
instability
In dynamical systems instability means that some of the outputs or internal states increase with time, without bounds. Not all systems that are not stable are unstable; systems can also be marginally stable or exhibit limit cycle behavior.
...
, the score may not always be in the window range. This may lead to a costly re-search that can penalize performance.
[Bruce Moreland's Programming Topics: Aspiration Windows](_blank)
/ref> Despite this, popular engines such as Stockfish
Stockfish is unsalted fish, especially cod, dried by cold air and wind on wooden racks (which are called "hjell" in Norway) on the foreshore. The drying of food is the world's oldest known preservation method, and dried fish has a storage li ...
still use aspiration windows.
The guess that aspiration windows use is usually supplied by the last iteration of iterative deepening
In computer science, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with incre ...
.Computer Chess Programming Theory: Aspiration Windows
/ref>
See also
* Principal variation search
References
Sources
*
Game artificial intelligence
{{Game theory