Game Development Reference

In-Depth Information

There are boards of other sizes in use. An 18
18-hole board is less intimidating

and easier for beginners as well as game AI. A quarter-size board, with 12 holes

per side, is good for demonstration purposes—the
Twixt
resources available on

the Web often make use of these smaller boards—but is too small to allow

interesting play to develop.

Complexity

We will start with brute-force look-ahead and then exploit the tools we have to

see if we can get the complexity of the game down to something that computers

can handle in reasonable amounts of time. As you might expect, the initial

computations show an impossibly complex game. The goal will be to get the

complexity down to something playable. To compute complexity, we will make

some simplifying approximations, all based on the idea of ''which is at least as big

as.'' If we multiply or add together simple numbers that are smaller than the

actual numbers, we will get a result that is smaller than the actual complexity.

Simple smaller numbers make for simpler computations. If our result using the

simple small numbers is too large to be practical, then we know that the larger,

actual result is likewise too large to be practical. Only when the approximation

suggests that an approach might be practical will we need to use actual numbers

to prove it. Approximations like these are often called ''back-of-the-envelope''

because they do not need a whole sheet of paper to compute them.

The na
¨
ve evaluation of
Twixt
's computational complexity yields enormous

numbers. If you could somehow fill every hole in the board, there would be 484!

combinations, which is so large it is not worth computing. It is time for our first

heuristic.

In a very long
Twixt
game, each side will make 25 moves for a total of 50 moves.

Are the numbers more tractable if the search depth is limited to 25 rounds of

move, counter-move? There are 484 starting moves. After taking 49 moves, we

have 434 possible 50
th
moves. The actual complexity can be computed by

multiplying the 50 different numbers from 484 to 434 together. If we approx-

imate the 50 numbers between 484 and 434 as all being at least as large as 100, we

will vastly underestimate the result, but we also get a much easier math problem.

484 * 483 * 482 ...* 436 * 435 * 434 = a very hard to compute number

100 * 100 * 100 ...* 100 * 100 * 100 = 100
50
=10
100
(smaller, easier to

compute)