Published in ACM Computing Surveys, Vol. 21, No. 2, June 1989
This article, which I wrote in 1986 to fulfill a degree requirement, surveys two branches of the AI literature concerned with two-player games. The first branch, game programming, is a heavily empirical subfield directed toward incremental improvements in state-of-the-art game programs, with a particular emphasis on computer chess.
The second branch, heuristic analysis, is a fairly theoretical subfield interested in formal analyses of heuristic search techniques employed by artificial intelligence systems, including the search strategies used in game-playing systems. Despite their overlapping interests, the fundamental results of these fields point in opposite directions. Game programmers have come to embrace a heuristic version of the minimax algorithm whose performance in chess programs has been outstanding. Every theoretical analysis of minimax, however, has concluded that its standard heuristic implementation should not work. This article reviews both bodies of literature, attempts to explain the source of disagreement between theory and practice, and points to qualitative implications of the theoretical results that should interest game programmers.
Recent Comments