Null Window
Home * Dictionary * Null Window
A Null Window, also called Zero Window, Scout Window or Narrow Window, is a way to reduce the search space in alpha-beta like search algorithms, to perform a boolean test, whether a move produces a worse or better score than a passed value. Null window searches are the base of Scout, NegaScout or Principal Variation Search, and MTD(f).
History
Null windows were first described by Judea Pearl, when introducing his Scout algorithm in April 1980 [1]. Independently, null window searches were further elaborated by John Philip Fishburn in the SIGART Bulletin, Issue 72, July 1980 [2], who was already trying to get this published starting in August 1979. Fishburn was somewhat disappointed in the speedup (or lack thereof) that he measured on checkers lookahead trees. However when he went to work at Bell Labs in 1981, Ken Thompson told him that he had read the SIGART paper, and had sped up Belle by 1.5x with null windows [3].
Applications
Null window searches are performed in
- MTD(f)
- Multi-Cut to prove no singularity
- NegaC*
- NegaScout
- Null Move Pruning to prove a null move fails high
- Principal Variation Search
- ProbCut for the reduced search
- Scout
- SSS* and Dual* as MT
A null window search can never return an exact score with alpha < score < beta and therefor a principal variation, but either an upper bound with score < beta (score <= alpha) or a lower bound with score >= beta (score > alpha).
With integers a null-window is defined as alpha == beta - 1.
See Also
Forum Posts
- Zero-width Window Null Move Search by Dezhi Zhao, CCC, June 15, 1998
- when to try zero window search by Andrew Short, CCC, November 14, 2008
- Zero window TT entry by Vlad Stamate, CCC, March 05, 2010 » Transposition Table
External Links
References
- ↑ Judea Pearl (1980). Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. pdf
- ↑ John Philip Fishburn (1980). An optimization of alpha-beta search, SIGART Bulletin, Issue 72
- ↑ John Philip Fishburn, personal communication
