Algorithms in a Nutshell

Minimax | 211

Path Finding

in AI

Consequences

This algorithm can rapidly become overwhelmed by the sheer number of game

states generated during the recursive search. In chess, where the average number

of moves on a board is often considered to be 30 (Laramée, 2000), to look ahead

only five moves (i.e.,b=30,d=5) requires evaluating up to 25,137,931 board posi-

tions. This value is determined by the expression:

MINIMAXcan take advantage of symmetries in the game state (such as rotations

of the board or reflections) by caching past states viewed (and their respective

scores), but the savings are game-specific.

Analysis

Figure 7-17 contains a two-ply exploration of an initial tic-tac-toe game state for

player O using MINIMAX. The alternating levels ofMAXandMINshow how the

first move from the left—placing an O in the upper-left corner—is the only move

that averts an immediate loss. Note that all possible game states are expanded,

even when it becomes clear that the opponent X can secure a win if O makes a

poor move choice.

The depth of the game tree is fixed, and each potential game state in the ply-depth

sequence of moves is generated for evaluation. When there is a fixed numberbof

moves at each game state (or even when the number of available moves reduces

by one with each level), then the total number of game states searched in ad-ply

MINIMAX is on the order of O(bd), which demonstrates exponential growth.

Given the results of Figure 7-17, there must be some way to eliminate the explora-

tion of useless game states.MAXtries to maximize the evaluated game state

given a set of potential moves; as each move is evaluated,MAXcomputes a

maxValuethat determines the highest achievable score that playerMAXcan ensure.

Figure 7-16. IComparator interface abstracts MAX and MIN operators

b

i

i= 0

d

∑

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use