Why Minimax Works: An Alternative Explanation

Abstract

In game-playing programs relying on the minimax principle, deeper searches generally produce better evaluations. Theoretical analyses, however, suggest that in many cases minimaxing amplifies the noise introduced by the heuristic function used to evaluate the leaves of the game tree, leading to what is known as pathological behavior, where deeper searches produce worse evaluations. In most of the previous research, positions were evaluated as losses or wins. Dependence between the values of positions close to each other was identified as the property of realistic game trees that eliminates the pathology and explains why minimax is successful in practice. In this paper we present an alternative explanation that does not rely on value dependence. We show that if real numbers are used for position values, position values tend to be further apart at lower levels of the game tree, which leads to a larger proportion of more extreme positions, where error is less probable. Decreased probability of error in searches to greater depths is sufficient to eliminate the pathology and no additional properties of game trees are required. 1