A Cure for Pathological Behavior in Games that Use Minimax
  The traditional approach to choosing moves in game-playing programs is the
minimax procedure. The general belief underlying its use is that increasing
search depth improves play. Recent research has shown that given certain
simplifying assumptions about a game tree's structure, this belief is
erroneous: searching deeper decreases the probability of making a correct move.
This phenomenon is called game tree pathology. Among these simplifying
assumptions is uniform depth of win/loss (terminal) nodes, a condition which is
not true for most real games. Analytic studies in [10] have shown that if every
node in a pathological game tree is made terminal with probability exceeding a
certain threshold, the resulting tree is nonpathological. This paper considers
a new evaluation function which recognizes increasing densities of forced wins
at deeper levels in the tree. This property raises two points that strengthen
the hypothesis that uniform win depth causes pathology. First, it proves
mathematically that as search deepens, an evaluation function that does not
explicitly check for certain forced win patterns becomes decreasingly likely to
force wins. This failing predicts the pathological behavior of the original
evaluation function. Second, it shows empirically that despite recognizing
fewer mid-game wins than the theoretically predicted minimum, the new function
is nonpathological.
