Algorithms in a Nutshell

Overview | 179

Path Finding

in AI

(a) neither piece has yet moved, (b) the intervening two squares are empty and

not currently attacked by an enemy piece, and (c) the King is not currently in

check. Note that (b) and (c) can be computed directly from the board state and

therefore do not need to be stored; however, the game state must separately store

which King and Rook have moved.

The game state stores information about the game at each node in the search tree.

For games with exponentially large game trees, the state must be stored as

compactly as possible. If symmetries exist in the state, such as with Connect

Four®, Othello, or the 15-puzzle, then the search tree can be greatly reduced by

detecting and eliminating identical states that may simply be rotated or reflected.

More complex representations called bitboards have been used for chess,

checkers, or Othello to manage the incredibly large number of states with impres-

sive efficiency gains (Pepicelli, 2005).

Calculating available moves

At each game state, it must be possible to compute the available moves allowed to

the player making the move. The termbranching factorrefers to the total number

of moves that are allowed at any individual game state. For games such as tic-tac-

toe, the branching factor constantly decreases from its high of nine (at the start of

the game) as each mark is made. The original three-by-three Rubik’s cube has (on

average) a branching factor of 13.5 (Korf, 1985), whereas Connect Four has a

branching factor of 7 for most of the game. Checkers is more complicated because

of the rule that a player must capture a piece if that move is available. Based on

the analysis of a large number of checkers databases, the branching factor for

capture positions is 1.20, whereas for non-capture positions it is 7.94; Schaeffer

computes the average branching factor during a game to be 6.14 (Schaeffer,

2008). The game of Go has an initial branching factor of over 360 (Berlekamp and

Wolfe, 1997).

Many of the algorithms are sensitive to the order by which the available moves are

attempted. Indeed, if the branching factor for a game is high and the moves are

not properly ordered based upon some evaluative measure of success, then blindly

searching a game tree is unlikely to lead to a solution.

Using heuristic information

An algorithm that performs a blind search does not take any advantage of the

game state, but rather applies a fixed strategy. Adepth-firstblind search simply

iterates through all available moves, recursively applying each one until a solution

is found, backtracking to reverse bad decisions as it inexorably computes to the

finish. Abreadth-firstblind search methodically explores all possible solutions

withk moves before first attempting any solution withk+1 moves.

There are several ways to add intelligence to the search (Barr and Feigenbaum,

1981):

Select board state to expand rather than using a fixed decision

Instead of always imposing a depth-first or a breadth-first structure, a search

algorithm might alternate between these two strategies.

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