Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Minimal Window Search

Aliases: Null Window Search

Keywords: games

Categories: 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.



Add Comment

No comments.