Home * Search * Alpha-Beta * Window
Fenster-Dalí.JPG

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.


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.
Arched Window of wall painting showing Dalí [1]

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


External Links


References

  1. ^ Arched Window of a wall painting showing Salvador Dalí, Lima, Peru, 2005 by Tabea Huth, Wikimedia Commons
  2. ^ Re: New(?) search idea by Robert Hyatt, CCC, January 22, 1998
  3. ^ Re. Fail low after fail high by Marcel van Kervinck, CCC, April 05, 2015 » Fail-Low, Fail-High

What links here?


Up one level