Algorithms in a Nutshell

Minimax | 209

Path Finding

in AI

Assumptions

Evaluating the game state is complex, and one must resort to heuristic evalua-

tions to determine the better game state. Indeed, developing accurate evaluation

functions for games such as chess, checkers, or reversi (also known as Othello) is

the greatest challenge in designing intelligent programs. We assume these evalua-

tion functions are available.

Context

MINIMAXrequires no additional bookkeeping other than the individual game

state. One need only define ascore(state, player)method that evaluates the

game state from the perspective of a given player, where a negative number repre-

sents a weak game state for the player and a positive number represents a strong

game state.

The size of the game tree is determined by the number of available moves at each

game state. Assume there arebmoves valid at the initial game state and that each

move takes away a potential move from the opponent. If the ply depth isd, the

total number of game states checked is

whereb! is the factorial ofb. To give an example of the scale involved, whenb=10

andd=6, the total number of game states that must be evaluated is 187,300.

MINIMAXdepends on the accuracy of the state evaluation function,score(state,

player). During the recursive invocation within MINIMAX, this evaluation func-

tion must be consistently applied to use theoriginal playerfor whom a move is

being calculated; it must not be invoked with alternating player and opponent, or

the minimum and maximum recursive evaluations will not coordinate their

efforts.

Solution

The helper classMoveEvaluationpairs together anIMoveand theintevaluation to

be associated with that move. MINIMAXexplores to a fixed ply depth, or when a

game state has no valid moves for a player. The Java code in Example 7-6 returns

the best move for a player in a given game state.

Example 7-6. Minimax Java implementation

public class MinimaxEvaluation implements IEvaluation {

IGameState state; /** State to be modified during search. */

int ply; /** Ply depth. How far to continue search. */

IPlayer original; /** Evaluate all states from this perspective. */

public MinimaxEvaluation (int ply) {

this.ply = ply;

}

b!

()bi–!

------------------

i= 1

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