Algorithms in a Nutshell

(^176) | Chapter 7: Path Finding in AI
From a programming perspective, the heart of the path-finding algorithm for a
game tree is an implementation of the IEvaluation interface shown in
Example 7-1.
Given a node representing the current game state, the algorithm computes the
best move forplayerassuming thatopponentwill play a perfect game in return.
Later we will investigate how MINIMAX,NEGMAX, and ALPHABETAcan be used
to search game trees.
Search Trees
The 8-puzzle is formed using a three-by-three grid containing eight square tiles
numbered 1 to 8 and an empty space that contains no tile. A tile adjacent (either
horizontally or vertically) to the empty space can be moved by sliding it into the
empty space. The aim is to start from a shuffled initial state and move tiles to
achieve the goal state, as shown in Figure 7-3. There are no competing players
taking alternate turns for these problems, but the behavior is quite similar to game
trees. There is an initial state (the top node in the search tree), and a sequence of
moves transforms the board state until a goal state is reached (labeled “GOAL”).
The eight-move solution in Figure 7-3 is recorded as the bold path from the initial
node to the goal node.
We use the termsearch treeto refer to the tree representing the set of interme-
diate board states as the path-finding algorithm progresses. The computed
structure is a tree because the algorithm ensures that it does not visit a board state
twice. The algorithm decides the order of board states to visit as it attempts to
reach the goal.
Often, the search tree rapidly explodes to contain (potentially) millions of states.
The algorithms in this chapter describe how to efficiently search through these
trees more rapidly than using a blind search. To describe the inherent complexity
of the problem, we introduce DEPTH-FIRST SEARCH and BREADTH-FIRST
SEARCHas two potential approaches to path-finding algorithms. We then present
the powerful A*SEARCHalgorithm for finding a minimal-cost solution (under
certain conditions). We’ll now briefly summarize the core concepts, illustrated in
Figure 7-4, that will be used when discussing search tree algorithms.
TheINodeinterface abstracts the essential concepts needed to conduct searches
over a board state. This interface groups together code for:
Generating valid moves
validMoves( ) returns a list of available moves for a board state.
Evaluating the board state
score(int)associates an integer score with the board state, representing the
result of an evaluation function;score( )returns the evaluation result previ-
ously associated with the board state.
Example 7-1. Common interface for game tree path finding
public interface IEvaluation {
IGameMove bestMove(IGameState state, IPlayer player, IPlayer opponent);
}
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