ABSTRACT
This chapter looks at the minimax family of algorithms, the most popular board game artificial intelligence (AI) techniques. It discusses a different family of algorithms that has proven to be superior in many applications: the memory-enhanced test driver (MTD) algorithms. Both minimax and MTD are tree-search algorithms: they require a special tree representation of the game. The chapter shows why commercial turn-based strategy games are often too complex to take advantage of this AI. There are many more games that treat each player’s turn as a separate move, and this is the terminology normally used in turn-based strategy games. Game theory is a mathematical discipline concerned with the study of abstracted, idealized games. Game theory classifies games according to the number of players, the kinds of goal those players have, and the information each player has about the game. Many of the algorithms and techniques for turn-based AI assume that there is perfect information.
