25,161
edits
Changes
Created page with "'''Home * Search * Alpha-Beta * Window''' border|right|thumb|Arched Window of wall painting showing [[Arts#Dali|Dalí <ref>Ar..."
'''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Window'''
[[FILE:Fenster-Dalí.JPG|border|right|thumb|Arched Window of wall painting showing [[Arts#Dali|Dalí]] <ref>Arched Window of a [https://commons.wikimedia.org/wiki/File:Fenster-Dal%C3%AD.JPG wall painting showing] [[Arts#Dali|Salvador Dalí]], [https://en.wikipedia.org/wiki/Lima Lima], [https://en.wikipedia.org/wiki/Peru Peru], 2005 by Tabea Huth, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
A '''Window''' in the context of Alpha-Beta search (Alpha-Beta window) is the [https://en.wikipedia.org/wiki/Interval_%28mathematics%29#Terminology open interval] between the [[Lower Bound|lower bound]] [[Alpha]] and the [[Upper Bound|upper bound]] [[Beta]].
'''(α,β) = ]α,β[ = { x ∈ ℤ | α < x < β}'''
Only values inside this interval, that is excluding Alpha and Beta, are [[Exact Score|exact scores]]. Thus, with [https://en.wikipedia.org/wiki/Integer integers] at least a window of (x-1, x+1) is necessary to reveal one exact score x. A [[Null Window]] as used in the [[Scout]] part of [[Principal Variation Search|PVS]] aka [[NegaScout]], and [[MTD(f)]], with integers (α, α+1) or (β-1, β), can therefor only provide a [[Bound|bound]], either [[Fail-High|failing-high]] with a lower bound or [[Fail-Low|failing-low]] with an upper bound.
=<span id="MinimaxWall"></span>Minimax Wall=
[[Robert Hyatt]] in a [[CCC]] reply to [[Bruce Moreland]], January 1998 <ref> [https://www.stmintz.com/ccc/index.php?id=14539 Re: New(?) search idea] by [[Robert Hyatt]], [[CCC]], January 22, 1998</ref>:
If the window is above the true value, so that you will [[Fail-Low|fail low]], you get maximal efficiency. Here's the way to follow why. If every root move fails low, it can do so after searching only one move at ply 2, the one move necessary to 'refute' the root move. So you get a truly small tree. If the window is below the true value, so you [[Fail-High|fail high]] on every move at the root, to fail high at the root means *every* move at ply=2 must fail low. The tree is roughly W times larger in this case.
[[Jonathan Schaeffer|Schaeffer]] noticed this and referred to this as the "minimax wall", that point where the window just drops down over the real score so that you don't get the quick fail lows. I saw this when I played with [[MTD(f)|mtd(f)]] a few months ago, as it was faster when the window was too high. Fast enough that it is best to keep it up there rather than dropping below the real value and having to fail upward...
=See also=
* [[Aspiration Windows]]
* [[MTD(f)]]
* [[Null Window]]
* [[Odd-Even Effect]]
* [[Ronald de Man#ScoringRootMoves|Scoring Root Moves]]
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess.computer/p8GbiiLjp0o/81vZ3czsthIJ Alpha-Beta window in transposition tables?] by Marty Bochane, [[Computer Chess Forums|rgcc]], October 25, 1996 » [[Transposition Table]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55889&start=8 Re. Fail low after fail high] by [[Marcel van Kervinck]], [[CCC]], April 05, 2015 » [[Fail-Low ]], [[Fail-High]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=55577 Negative alpha/beta windows: Are they useful?] by [[Thomas Dybdahl Ahle]], [[CCC]], March 06, 2015
=External Links=
* [https://en.wikipedia.org/wiki/Interval_%28mathematics%29 Interval (mathematics) from Wikipedia]
* [https://en.wikipedia.org/wiki/Window_%28disambiguation%29 Window (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Window Window from Wikipedia]
* [https://en.wikipedia.org/wiki/Launch_window Launch window from Wikipedia]
* [https://en.wikipedia.org/wiki/Window_%28computing%29 Window (computing) from Wikipedia] » [[GUI]]
* [https://en.wikipedia.org/wiki/Register_window Register window from Wikipedia]
* [https://en.wikipedia.org/wiki/Window_function Window function from Wikipedia]
* [https://en.wikipedia.org/wiki/Window_%28short_story%29 Window (short story) from Wikipedia]
=References=
<references />
'''[[Alpha-Beta|Up one level]]'''
[[FILE:Fenster-Dalí.JPG|border|right|thumb|Arched Window of wall painting showing [[Arts#Dali|Dalí]] <ref>Arched Window of a [https://commons.wikimedia.org/wiki/File:Fenster-Dal%C3%AD.JPG wall painting showing] [[Arts#Dali|Salvador Dalí]], [https://en.wikipedia.org/wiki/Lima Lima], [https://en.wikipedia.org/wiki/Peru Peru], 2005 by Tabea Huth, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
A '''Window''' in the context of Alpha-Beta search (Alpha-Beta window) is the [https://en.wikipedia.org/wiki/Interval_%28mathematics%29#Terminology open interval] between the [[Lower Bound|lower bound]] [[Alpha]] and the [[Upper Bound|upper bound]] [[Beta]].
'''(α,β) = ]α,β[ = { x ∈ ℤ | α < x < β}'''
Only values inside this interval, that is excluding Alpha and Beta, are [[Exact Score|exact scores]]. Thus, with [https://en.wikipedia.org/wiki/Integer integers] at least a window of (x-1, x+1) is necessary to reveal one exact score x. A [[Null Window]] as used in the [[Scout]] part of [[Principal Variation Search|PVS]] aka [[NegaScout]], and [[MTD(f)]], with integers (α, α+1) or (β-1, β), can therefor only provide a [[Bound|bound]], either [[Fail-High|failing-high]] with a lower bound or [[Fail-Low|failing-low]] with an upper bound.
=<span id="MinimaxWall"></span>Minimax Wall=
[[Robert Hyatt]] in a [[CCC]] reply to [[Bruce Moreland]], January 1998 <ref> [https://www.stmintz.com/ccc/index.php?id=14539 Re: New(?) search idea] by [[Robert Hyatt]], [[CCC]], January 22, 1998</ref>:
If the window is above the true value, so that you will [[Fail-Low|fail low]], you get maximal efficiency. Here's the way to follow why. If every root move fails low, it can do so after searching only one move at ply 2, the one move necessary to 'refute' the root move. So you get a truly small tree. If the window is below the true value, so you [[Fail-High|fail high]] on every move at the root, to fail high at the root means *every* move at ply=2 must fail low. The tree is roughly W times larger in this case.
[[Jonathan Schaeffer|Schaeffer]] noticed this and referred to this as the "minimax wall", that point where the window just drops down over the real score so that you don't get the quick fail lows. I saw this when I played with [[MTD(f)|mtd(f)]] a few months ago, as it was faster when the window was too high. Fast enough that it is best to keep it up there rather than dropping below the real value and having to fail upward...
=See also=
* [[Aspiration Windows]]
* [[MTD(f)]]
* [[Null Window]]
* [[Odd-Even Effect]]
* [[Ronald de Man#ScoringRootMoves|Scoring Root Moves]]
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess.computer/p8GbiiLjp0o/81vZ3czsthIJ Alpha-Beta window in transposition tables?] by Marty Bochane, [[Computer Chess Forums|rgcc]], October 25, 1996 » [[Transposition Table]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55889&start=8 Re. Fail low after fail high] by [[Marcel van Kervinck]], [[CCC]], April 05, 2015 » [[Fail-Low ]], [[Fail-High]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=55577 Negative alpha/beta windows: Are they useful?] by [[Thomas Dybdahl Ahle]], [[CCC]], March 06, 2015
=External Links=
* [https://en.wikipedia.org/wiki/Interval_%28mathematics%29 Interval (mathematics) from Wikipedia]
* [https://en.wikipedia.org/wiki/Window_%28disambiguation%29 Window (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Window Window from Wikipedia]
* [https://en.wikipedia.org/wiki/Launch_window Launch window from Wikipedia]
* [https://en.wikipedia.org/wiki/Window_%28computing%29 Window (computing) from Wikipedia] » [[GUI]]
* [https://en.wikipedia.org/wiki/Register_window Register window from Wikipedia]
* [https://en.wikipedia.org/wiki/Window_function Window function from Wikipedia]
* [https://en.wikipedia.org/wiki/Window_%28short_story%29 Window (short story) from Wikipedia]
=References=
<references />
'''[[Alpha-Beta|Up one level]]'''
