Game Development Reference

In-Depth Information

around it has four possible moves. It can have fewer when near hounds or an

edge, but it can never have more. Each of the four hounds, when nothing is in

front of it and it is not next to an edge of the board, has two possible moves.

Setting up the math, we get four possible fox moves times eight possible hounds

moves for 32 combinations. We do this 28 times, yielding 32
28
. This is the

same as 2
140
. Very roughly speaking, this is 10
42
combinations to evaluate. If

somehow our 1GHz computer could do a billion of these per second, it would

take 10
33
seconds, which compares poorly to the age of the Earth, which is

around 10
17
seconds, and to the estimated time until the heat decay death of the

universe at 10
19
seconds. The polite word for this kind of problem is ''intract-

able,'' although it might not be the first thing AI programmers say when they run

the numbers. It should be very clear that heuristics are required to keep the

computational complexity of the game manageable. A brute-force look-ahead

approach will simply take too long.

It is worth noting that
Fox and Hounds
has only 32 possible combinations for a

single move and the following countermove. A move and countermove pair is

called a ''ply.''
Chess
starts out with 32 pieces, and most of them have two or more

possible moves to consider each turn. If the pieces were limited to just two possible

moves each (a number that is far too small), a single move for one side would

involve one of 16 pieces, times two possible moves, for 32 combinations. Not all of

the 16 pieces can always move, but half of the pieces have far more than the two

moves we limited them to, with eight being a more typical number. If 32 com-

binations is a reasonable estimate, then there are 32 possibilities for the white times

the 32 possibilities for black as a countermove for a product of 1,024 combinations

in each ply. This number might seem too large, but
Chess
starts out with exactly

20 possible opening moves followed by 20 opening response for 400 combinations

in the first ply. This is called the
branching factor
, and in games such as
Chess
(or

worse yet,
Go
), the branching factor is so high that simple look-ahead is quickly

overwhelmed. Heuristics and other measures have helped a great deal in the case of

Chess
, but they have achieved far more modest success with
Go
.

There are noteworthy comparisons to be made between the complexity of
Fox

and Hounds
and
Tic-Tac-Toe
.
Tic-Tac-Toe
is small enough that its factorial

growth never goes on long enough to overwhelm the situation. For small

numbers, factorial growth is well behaved.
Fox and Hounds
is more complex,

but unlike
Tic-Tac-Toe
, the complexity of the individual turns is fixed. If you

increased the number of turns for both games, by playing on a larger board, for

example, eventually
Tic-Tac-Toe
would show higher complexity as ever higher