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