Conspiracy numbers for min-max search (Q1102218)

This paper presents a new procedure for growing min-max game trees. In large games, such as chess, decisions must be based on incomplete search trees. This procedure is based on a new measure of the accuracy of the root value of an incomplete tree, denoted as ``conspiracy number''. The conspiracy numbers measure the number of leaf nodes whose value must change in order to change the minimax root value by a given amount. Trees are grown in such a way that maximizes the conspiracy required to change the root value. This is a heuristic procedure which, intuitively, gradually rules out ``bad'' moves near the root of the tree and thus reduces the branching factor at the root position.