Game Development Reference
In-Depth Information
to make the game easier for the AI to play and easier for the programmer to
understand. We will start with some design discussions before we get to the game
board that contains the squares.
A checkerboard is more than 64 graphical squares. People have no trouble seeing
that the squares of the same color are connected diagonally, but we will need to
program that knowledge for the benefit of the AI and the user interface code. Our
game only uses squares of one color, so if we do it right, we ignore squares of the
other color. As we look at connectivity, we see that the neighbors of any square
are also the set of moves that a fox can take from that square if there are no
hounds in the way. Continuing that thought leads us to the idea that the half of
the neighbors that are ''down'' as we see the board are potential moves for
hounds. The AI will be using this knowledge all of the time, so it is best if we
precompute it. While we are at it, moves up are handy to know as well (more on
that later). All of this makes us ask, ''How do we tell one square apart from
another?''
As shown in Figure 6.4, we will tell squares apart by numbering them (ignore the
buttons at the bottom for now). For us, the upper-left square is square 0.
Our board has four squares in each row, since we are ignoring the off-color
squares. The lower-right square will then be square 31. If you have a cheap
folding checkerboard, it may have similar numbers that differ by one. Num-
bering from 0 to 31 makes our code easier, even if we humans have a pesky habit
of starting out at 1.
The kind of design we are doing now is the first concrete step toward dealing with
knowledge representation. We know that the AI will need to make numerous
copies of the boards it considers, so we need to be aware of the performance
impact of those copies. There are three standard factors to consider: memory
space, computational speed, and programmer time.
The space consideration is worth at least a quick examination. Earlier, we saw
complexity numbers such as 1,024 combinations for the fox and 262,144 for the
hounds. While we might examine that many boards, we will never store them all
at the same time. The number of boards we have in memory at the same time is
related to how deep we are looking ahead. The most we look ahead is six moves
when the hounds are looking ahead. Since there is a fox move between each