Catalogue of Artificial Intelligence Techniques
Minimal Window Search
Aliases: Null Window Search
Author(s): Alexander Reinefeld
The use of minimal windows provides an improvement on the Alpha/Beta tree-searching algorithm. Minimal window search is based on the assumption that all subtrees are inferior to the best subtree searched thus far, until proven otherwise. Having searched the first branch with a full width alpha-beta window [alpha,beta], all remaining branches are searched with a minimal window [alpha,alpha+1], where alpha represents the best Minimax value found so far. If the value returned is indeed less than or equal to alpha, then the assumption was correct and the subtree is inferior. Otherwise, this subtree is superior and must be re-searched with a wider window to determine its exact minimax value. Two things work in favour of minimal window search: First, it is easier to prove a subtree inferior than to determine its exact minimax value (like alpha-beta does), and second, most of the tests would result in exempting the subtree from further evaluation. This cautious `testing-before-evaluating' strategy originally appeared in Pearl's Scout algorithm, and has subsequently been adapted to the negamax notation, giving the NegaScout, P-Alpha-Beta and PVS algorithms.
- Pearl, J., Heuristics: Intelligent Search Strategies for Computer
, Addison-Wesley, Reading, MA, 1984.