we know recursively achieve the same value.  When we complete the maximizer's loop in the algorithm, it follows that Sans will be a set of positions from which the maximizer can indeed achieve the value vans. Thus the maximizer can also achieve that value from any position in R ( p, Sans ). It follows that the overall set of positions known to have the value vans is given by R(p, Sans) N C(p, Sall), intersecting the two conditions of this paragraph. This is what is done in the second daggered step in the algorithm.

口

## 2.4 Zero-Window Variations

The effectiveness of partition search depends crucially on the size of the sets maintained in the transposition table. If the sets are large, many positions will be evaluated by lookup.

If the sets are small, partition search collapses to conventional a- β pruning.

An examination of Algorithm 2.3.3 suggests that the points in the algorithm at which the sets are reduced the most are those marked with a double dagger in the description, where an intersection is required because we need to ensure both that the player can make a move equivalent to his best one and that there are no other options. The effectiveness of the method would be improved if this possibility were removed.

To see how to do this, suppose for a moment that the evaluation function always returned 0 or 1, as opposed to intermediate values. Now if the maximizer is on play and the value vnew = 1, a prune will be generated because there can be no better value found for the maximizer. If all of the vnew are 0, then vans = 0 and we can avoid the troublesome intersection. The maximizer loses and there is no "best" move that we have to worry about making.

In reality, the restriction to values of 0 or 1 is unrealistic. Some games, such as bridge, allow more than two outcomes, while others cannot be analyzed to termination and need to rely on evaluation functions that return approximate values for internal nodes. We can deal with these situations using a technique known as zero-window search (originally called scout search (Pearl, 1980)). To evaluate a specific position, one first estimates the value to be e and then determines whether the actual value is above or below e by treating any value v > e as a win for the maximizer and any value v ≤ e as a win for the minimizer. The results of this calculation can then be used to refine the guess, and the process is repeated. If no initial estimate is available, a binary search can be used to find the value to within any desired tolerance.

Zero-window search is effective because little time is wasted on iterations where the estimate is wildly inaccurate; there will typically be many lines showing that a new estimate is needed. Most of the time is spent on the last iteration or two, developing tight bounds on the position being considered. There is an analog in conventional α-β pruning, where the bounds typically get tight quickly and the bulk of the analysis deals with a situation where the value of the original position is known to lie in a fairly narrow range.

In zero-window sear, a node always evaluates to 0 or 1, since either v > e or v < e.

This allows a straightforward modification to Algorithm 2.3.3 that avoids the troublesome cases mentioned earlier.