172Chapter 7. Path Finding in AI......................................................................................................................................................
7
Path Finding in AI
Overview
To solve a problem when there is no clear algorithm for computing a valid solu-
tion, we turn to path finding. In this chapter we will cover two related path-
finding approaches, one forgame treesand the other forsearch trees. These
approaches rely on a common structure, namely a state tree where the root node
represents the initial state and edges represent potential moves that transform the
state into a new state. The searches are challenging because the underlying struc-
ture is not computed in its entirety, due to the explosion of the number of states.
In a game of checkers, for example, there are roughly 5*10^20 different board
configurations (Schaeffer, 2007). Thus the trees over which the search proceeds
are constructed on demand as needed. The two path-finding approaches are char-
acterized as follows:
Game tree
Two players take alternating turns in making moves that modify the game
state from its initial state. There are potentially many states in which either
player can win the game. There also may be some states that are “draws,” in
which case no one wins. A path-finding algorithm maximizes the chances
that a player will win the game (or force a draw).
Search tree
A single agent is given a task to accomplish, starting from an initial board
state, with a series of allowed move types. In most cases, there is exactly one
goal state that is desired. A path-finding algorithm identifies the exact
sequence of moves that will transform the initial state into the goal state.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