Null Window

From Chessprogramming wiki
Jump to: navigation, search

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

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

External Links

References

  1. 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
  2. John Philip Fishburn (1980). An optimization of alpha-beta search, SIGART Bulletin, Issue 72
  3. John Philip Fishburn, personal communication

Up one level