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)
 
Search Nedrilad ::




Custom Search