25,161
edits
Changes
Created page with "'''Home * Dictionary * Null Window''' A '''Null Window''', also called '''Zero Window''', '''Scout Window''' or '''Narrow Window''', is a way to reduce the..."
'''[[Main Page|Home]] * [[Dictionary]] * Null Window'''
A '''Null Window''', also called '''Zero Window''', '''Scout Window''' or '''Narrow Window''', is a way to reduce the [[Search Space|search space]] in [[Alpha-Beta|alpha-beta]] like [[Search|search]] algorithms, to perform a boolean test, whether a [[Moves|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 <ref>[[Judea Pearl]] ('''1980'''). ''Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties''. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. [http://ftp.cs.ucla.edu/pub/stat_ser/scout.pdf pdf]</ref>. Independently, null window searches were further elaborated by [[John Philip Fishburn]] in the [[ACM#SIG|SIGART]] Bulletin, Issue 72, July 1980 <ref>[[John Philip Fishburn]] ('''1980'''). ''An optimization of alpha-beta search'', SIGART Bulletin, Issue 72</ref>, 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|checkers]] lookahead trees. However when he went to work at [[Bell Laboratories|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 <ref>[[John Philip Fishburn]], personal communication</ref>.
=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 [[Fail-High|fails high]]
* [[Principal Variation Search]]
* [[ProbCut]] for the reduced search
* [[Scout]]
* [[SSS* and Dual*#SSStarandDualStarAsMT|SSS* and Dual* as MT]]
A null window search can never return an [[Exact Score|exact score]] with <span style="background-color: rgb(224, 224, 224)">[[Alpha|alpha]] < score < [[Beta|beta]]</span> and therefor a [[Principal Variation|principal variation]], but either an [[Upper Bound|upper bound]] with <span style="background-color: rgb(224, 224, 224)">score < beta</span> (<span style="background-color: rgb(240, 224, 224)">score <= alpha</span>) or a [[Lower Bound|lower bound]] with <span style="background-color: rgb(224, 224, 224)">score >= beta</span> (<span style="background-color: rgb(240, 224, 224)">score > alpha</span>).
With integers a null-window is defined as <span style="background-color: rgb(224, 224, 224)">alpha == beta - 1</span>.
=See Also=
* [[Alpha-Beta]]
* [[Aspiration Windows]]
* [[Window]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=20596 Zero-width Window Null Move Search] by [[Dezhi Zhao]], [[CCC]], June 15, 1998
* [http://www.talkchess.com/forum/viewtopic.php?t=24883 when to try zero window search] by [[Andrew Short]], [[CCC]], November 14, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=33084 Zero window TT entry] by [[Vlad Stamate]], [[CCC]], March 05, 2010 ยป [[Transposition Table]]
=External Links=
* [https://en.wikipedia.org/wiki/Negascout Negascout from Wikipedia]
=References=
<references />
'''[[Dictionary|Up one level]]'''
A '''Null Window''', also called '''Zero Window''', '''Scout Window''' or '''Narrow Window''', is a way to reduce the [[Search Space|search space]] in [[Alpha-Beta|alpha-beta]] like [[Search|search]] algorithms, to perform a boolean test, whether a [[Moves|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 <ref>[[Judea Pearl]] ('''1980'''). ''Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties''. Proceedings of the First Annual National Conference on Artificial Intelligence. Stanford. [http://ftp.cs.ucla.edu/pub/stat_ser/scout.pdf pdf]</ref>. Independently, null window searches were further elaborated by [[John Philip Fishburn]] in the [[ACM#SIG|SIGART]] Bulletin, Issue 72, July 1980 <ref>[[John Philip Fishburn]] ('''1980'''). ''An optimization of alpha-beta search'', SIGART Bulletin, Issue 72</ref>, 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|checkers]] lookahead trees. However when he went to work at [[Bell Laboratories|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 <ref>[[John Philip Fishburn]], personal communication</ref>.
=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 [[Fail-High|fails high]]
* [[Principal Variation Search]]
* [[ProbCut]] for the reduced search
* [[Scout]]
* [[SSS* and Dual*#SSStarandDualStarAsMT|SSS* and Dual* as MT]]
A null window search can never return an [[Exact Score|exact score]] with <span style="background-color: rgb(224, 224, 224)">[[Alpha|alpha]] < score < [[Beta|beta]]</span> and therefor a [[Principal Variation|principal variation]], but either an [[Upper Bound|upper bound]] with <span style="background-color: rgb(224, 224, 224)">score < beta</span> (<span style="background-color: rgb(240, 224, 224)">score <= alpha</span>) or a [[Lower Bound|lower bound]] with <span style="background-color: rgb(224, 224, 224)">score >= beta</span> (<span style="background-color: rgb(240, 224, 224)">score > alpha</span>).
With integers a null-window is defined as <span style="background-color: rgb(224, 224, 224)">alpha == beta - 1</span>.
=See Also=
* [[Alpha-Beta]]
* [[Aspiration Windows]]
* [[Window]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=20596 Zero-width Window Null Move Search] by [[Dezhi Zhao]], [[CCC]], June 15, 1998
* [http://www.talkchess.com/forum/viewtopic.php?t=24883 when to try zero window search] by [[Andrew Short]], [[CCC]], November 14, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=33084 Zero window TT entry] by [[Vlad Stamate]], [[CCC]], March 05, 2010 ยป [[Transposition Table]]
=External Links=
* [https://en.wikipedia.org/wiki/Negascout Negascout from Wikipedia]
=References=
<references />
'''[[Dictionary|Up one level]]'''
