Algorithms in a Nutshell
172 Chapter 7. Path Finding in AI............................................................................................... ...
Overview | 173 Path Finding in AI Game Trees The game of tic-tac-toe is played on a three-by-three board where players take turn ...
(^174) | Chapter 7: Path Finding in AI The game tree represents the full set of potential game states that result from sequences ...
Overview | 175 Path Finding in AI summarize the core concepts of game tree algorithms, which are illustrated in Figure 7-2. TheI ...
(^176) | Chapter 7: Path Finding in AI From a programming perspective, the heart of the path-finding algorithm for a game tree i ...
Overview | 177 Path Finding in AI Managing the board state copy( )returns an identical copy of the board state (except for the o ...
(^178) | Chapter 7: Path Finding in AI Managing optional board state data storedData(Object o)associates the given object with t ...
Overview | 179 Path Finding in AI (a) neither piece has yet moved, (b) the intervening two squares are empty and not currently a ...
(^180) | Chapter 7: Path Finding in AI Select the order and number of allowed moves to be applied When considering available mov ...
Depth-First Search | 181 Path Finding in AI Assumptions We assume that the problems all have game states that can be represented ...
(^182) | Chapter 7: Path Finding in AI Output Return a sequence of moves that represents a path from the initial state to the go ...
Depth-First Search | 183 Path Finding in AI Solution DEPTH-FIRSTSEARCHstoresthesetofopen(i.e.,yettobevisited)boardstatesin a sta ...
(^184) | Chapter 7: Path Finding in AI Each board state stores a reference, called aDepthTransition, that records (a) the move t ...
Depth-First Search | 185 Path Finding in AI The implementation in Example 7-3 must be careful to store theclosedset using a stru ...
(^186) | Chapter 7: Path Finding in AI open.remove( ) Remove the “next” board state to evaluate closed.insert(INode state) Add b ...
Depth-First Search | 187 Path Finding in AI Table 7-1. Size of search tree (open + closed) for three initial positions Depth bou ...
(^188) | Chapter 7: Path Finding in AI Given the size of the search trees in Figure 7-7, one wonders about the quality of the so ...
Depth-First Search | 189 Path Finding in AI which is inspected in the 25thlevel. This board is only three moves away from the so ...
(^190) | Chapter 7: Path Finding in AI Interestingly, given the initial board state N1, an unbounded DEPTH-FIRST SEARCHwill actu ...
Breadth-First Search | 191 Path Finding in AI compute the set of successor board states given the valid moves. If the goal state ...
«
5
6
7
8
9
10
11
12
13
14
»
Free download pdf