Difference between revisions of "Window"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * Alpha-Beta * Window''' border|right|thumb|Arched Window of wall painting showing [[Arts#Dali|Dalí <ref>Ar...") |
GerdIsenberg (talk | contribs) |
||
| Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Window''' | '''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Window''' | ||
| − | [[FILE:Fenster-Dalí.JPG|border|right|thumb|Arched Window of wall painting showing [[ | + | [[FILE:Fenster-Dalí.JPG|border|right|thumb|Arched Window of wall painting showing [[:Category:Salvador Dalí|Dalí]] <ref>Arched Window of a [https://commons.wikimedia.org/wiki/File:Fenster-Dal%C3%AD.JPG wall painting showing] [[:Category:Salvador Dalí|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]]. | 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]]. | ||
| Line 40: | Line 40: | ||
'''[[Alpha-Beta|Up one level]]''' | '''[[Alpha-Beta|Up one level]]''' | ||
| + | [[Category:Salvador Dalí]] | ||
Latest revision as of 19:38, 22 September 2018
Home * Search * Alpha-Beta * Window
A Window in the context of Alpha-Beta search (Alpha-Beta window) is the open interval between the lower bound Alpha and the upper bound Beta.
(α,β) = ]α,β[ = { x ∈ ℤ | α < x < β}
Only values inside this interval, that is excluding Alpha and Beta, are exact scores. Thus, with 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 PVS aka NegaScout, and MTD(f), with integers (α, α+1) or (β-1, β), can therefor only provide a bound, either failing-high with a lower bound or failing-low with an upper bound.
Minimax Wall
Robert Hyatt in a CCC reply to Bruce Moreland, January 1998 [2]:
If the window is above the true value, so that you will 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 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.
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) 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
Forum Posts
- Alpha-Beta window in transposition tables? by Marty Bochane, rgcc, October 25, 1996 » Transposition Table [3]
- Negative alpha/beta windows: Are they useful? by Thomas Dybdahl Ahle, CCC, March 06, 2015
External Links
- Interval (mathematics) from Wikipedia
- Window (disambiguation) from Wikipedia
- Window from Wikipedia
- Launch window from Wikipedia
- Window (computing) from Wikipedia » GUI
- Register window from Wikipedia
- Window function from Wikipedia
- Window (short story) from Wikipedia
References
- ↑ Arched Window of a wall painting showing Salvador Dalí, Lima, Peru, 2005 by Tabea Huth, Wikimedia Commons
- ↑ Re: New(?) search idea by Robert Hyatt, CCC, January 22, 1998
- ↑ Re. Fail low after fail high by Marcel van Kervinck, CCC, April 05, 2015 » Fail-Low , Fail-High
