Conspiracy numbers for min-max search

摘要

A new procedure is presented for growing min-max game trees. In large games, such as chess, decisions must be based on incomplete search trees. The new tree-growth procedure is based on “conspiracy numbers” as a measure of the accuracy of the root minimax value of an incomplete tree. 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 a way that maximizes the conspiracy required to change the root value. The trees grown by this procedure are often deep and narrow. However, if all static values in a game are the same, this new procedure reduces to d-ply search with α-β pruning. Unlike B∗ search, nonuniform growth is achieved without any modification of the static-board evaluator.