Information Technology Reference
In-Depth Information
Fig. 13.8. A (partial) game tree for tic-tac-
toe or noughts and crosses.
nodes , the points at which players can take actions, and branches , which represent
the possible moves at each node. In 1951, Dietrich Prinz wrote the first chess
program able to solve simple endgame problems. Prinz worked for Ferranti, a
British computer company marketing the Manchester Mark I machine, the first
commercially available general-purpose computer. Five years later, Stan Ulam
and a group at Los Alamos National Laboratory wrote a program that could play
a full game of chess, but only on a reduced board of 6 × 6 squares and no bish-
ops. It was not until 1957 that IBM programmer Alex Bernstein wrote the first
complete chess program for the IBM 704 computer, one of the last vacuum-tube
computers. The chess program took about eight minutes to make a move after
completing a search that could look about two moves ahead. Before we exam-
ine how a chess program works, let us look at a simpler problem, a computer
program for the game called tic-tac-toe or noughts and crosses.
We shall label the two players MAX, who makes the X moves, and MIN,
who makes the O moves. The total game tree consists of all the legal moves
from all the possible configurations of Xs and Os. MAX moves first, and from
the top node of the tree, MAX can make nine possible moves - a branching fac-
tor of nine (see Fig. 13.8 ). Then it is MIN's turn to make one of the eight remain-
ing moves. This alternation continues until either a line of Xs or Os is achieved
or all spaces on the board are filled. There are 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
nodes, or 362,880 nodes, in the tree. The game has a simple evaluation function
by which a player chooses the best move: +1 for a win for MAX, ½ for a draw,
and 0 for a win for MIN. A computer program can easily evaluate all possible
paths and positions leading to the final move of the game.
For the first move in chess, there are twenty possible moves, sixteen with
the eight pawns and four with the two knights. A typical game is around forty
moves, and for each position there is an average of thirty to thirty-five possible
moves to explore. Because the entire chess game tree would contain more than
10 40 nodes, an exhaustive search strategy looking at all the final positions is
not possible. Because we cannot get to the final positions, the evaluation func-
tion for chess is also much more complicated. For example, a chess evaluation
function usually has a weighted sum of the various factors that are thought to
Search WWH ::




Custom Search