The multi-player version of minimax displays game-tree pathology

摘要

It is widely believed that by searching deeper in the game tree, the decision-maker is more likely to make a better decision. Dana Nau and others have discovered pathology theorems that show the opposite: searching deeper in the game tree causes the quality of the ultimate decision to become worse, not better. The models for these theorems assume that the search procedure is minimax and the games are two-player zero-sum. This report extends Nau's pathology theorem to multi-player game trees searched with maxn, the multi-player version of minimax. Thus two-player zero-sum game trees and multi-player game trees are shown to have an important feature in common.