Algorithms in a Nutshell

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

turns placing X and O marks on the board. The first player to place three of his

marks in a row wins; the game is a draw if no spaces remain and no player has

won. Any 10-year-old child knows that the player making the first move can never

lose, even against a player who makes no mistakes. A computer program that

plays tic-tac-toe can be written to deliver the same result based on artificial intelli-

gence (AI) algorithms developed forcombinatorial gamessuch as checkers and

chess (but not poker, which relies on chance). In a combinatorial game, there is an

initial game position, and each player makes alternating moves that update the

game state until some winning condition is achieved (or the game is drawn, with

no player winning).

In tic-tac-toe there are only 765 unique positions (ignoring reflections and rota-

tions of the board state) and a calculated 26,830 possible games that can be

played (Schaeffer, 2002). The first player can always force a win or a draw, and

quite often undergraduate computer science students are asked to write tic-tac-toe

programs in an AI class. One need only construct thegame tree, as shown

partially in Figure 7-1, and find a path from the current game state (represented as

the top node in this tree) to some future game state that ensures either a victory or

a draw for the player faced with the current game state.

A game tree is also known as an AND/OR tree since it is formed by two different

types of nodes. The game tree in Figure 7-1 is constructed for player O. The top

node is an OR node, since the goal is to select just one of the six available moves

in the middle tier. The middle-tier nodes are AND nodes, since the goal (from O’s

perspective) is to ensure that all countermoves by X (as shown as children nodes

in the bottom tier) will still lead to either a victory or a draw for O. The game tree

in Figure 7-1 is only partially expanded since there are actually 30 different game

states in the bottom tier. The top game state is particularly interesting because

neither X nor O has won by the bottom tier (i.e., after two moves). Intuitively, this

means that a tic-tac-toe program must look at least three moves ahead to deter-

mine how O should best respond in this circumstance.

Figure 7-1. Partial game tree given an initial tic-tac-toe game 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