Algorithms in a Nutshell

Chapter 7. Path Finding in AI

Overview

To solve a problem when there is no clear algorithm for computing a valid solution, we turn to path finding. In this chapter we will cover two related path-finding approaches, one for game trees and the other for search 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 structure 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²⁰ 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 characterized 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 ...