AlphaBetaConspiracy Search

David McAllester and Deniz Yuret (2002)
( PS )

AlphaBetaConspiracy Search. ICGA Journal, Vol. 25, No. 2,
p. xxx.
Abstract:
We introduce a variant of alphabeta search in which each node is
associated with two depths rather than one. The purpose of alphabeta
search is to find strategies for each player that together establish a
value for the root position. A max strategy establishes a lower bound
and the min strategy establishes an upper bound. It has long been
observed that forced moves should be searched more deeply. Here we
make the observation that in the max strategy we are only concerned
with the forcedness of max moves and in the min strategy we are only
concerned with the forcedness of min moves. This leads to two
measures of depth  one for each strategy  and to a two depth variant
of alphabeta called ABC search. The two depth approach can be
formally derived from conspiracy theory and the structure of the ABC
procedure is justified by two theorems relating ABC search and
conspiracy numbers.