Algorithms in a Nutshell

Overview | 175

Path Finding

in AI

summarize the core concepts of game tree algorithms, which are illustrated in

Figure 7-2.

TheIGameStateinterface abstracts the essential concepts needed to conduct

searches over a game state. It defines the interface for:

Interpreting the game state

isDraw( ) determines whether the game concludes with neither player

winning;isWin( ) determines whether the game is won.

Managing the game state

copy( )returns an identical copy of the game state so moves can be applied

without updating the original game state;equivalent(IGameState)deter-

mines whether two game state positions are equal.

TheIPlayerinterface abstracts the abilities of a player to manipulate the game

state:

Evaluating a board

eval(IGameState)returns an integer evaluating the game state from the

player’s perspective;score(IGameScore)sets the scoring computation the player

uses to evaluate a game state.

Generating valid moves

validMoves(IGameState)returns a collection of available moves given the

game state.

TheIGameMoveinterface defines how moves can manipulate the game state. The

move classes are problem-specific, and the search algorithm need not be aware of

their specific implementation.IGameScoredefines the interface for scoring compu-

tations. In this chapter, we use theBoardEvaluationscoring function for tic-tac-

toe, which was defined by Nil Nilsson (1971). Letnc(gs,p) be the number of rows,

columns, or diagonals on a tic-tac-toe game state,gs, in which playerpmay still

get three in a row. We then definescore(IGameState gs, IPlayer player) to be:

•+∞ ifplayer has won the game in game stategs

•–∞ if the opponent ofplayer has won the game in game stategs

• nc(gs,player)–nc(gs,opponent) if neither player has won the game in game
  stategs

Figure 7-2. Core concepts for game tree algorithms

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