Game Development Reference

In-Depth Information

Our approximation yields a google (a one with 100 zeroes after it). Recall from

Chapter 6 that numbers this large will lead to execution times that compare

unfavorably with the estimated time until the heat decay death of the universe.

Math note: 100 = 10 * 10 = 10
2
. So with two 10s multiplied together in every

100, we get 100
50
= (10
2
)
50
=10
100

Maybe some more heuristics will help. Any serious
Twixt
play exploits three-

move combinations called setups. Not only are the setups good moves, players

certainly expect the AI to use them. So if the AI wants to see the opponent's

response to its next three moves, the AI needs to look ahead six moves total

instead of 50. If we again approximate the numbers between 484 and 479 as all

being larger than 100 and multiply everything, we get a trillion (a one followed by

12 zeroes). The actual number is over 12,000 trillion. This number is still

hopeless, but far better than a google.

484 * 483 * 482 * 481 * 480 * 479 = 12,461,242,792,078,080

100 * 100 * 100 * 100 * 100 * 100 = 100
6
=10
12
(smaller, easier to compute)

Maybe we can prune. Because we are assuming that the play is based on setups, let

us look at the complexity of the setups. The collection of basic setups goes in our

book of moves. Once the first peg is placed, assume the best future moves are

based on setups starting with that peg. Let us examine the four setups given in the

original rules for
Twixt
. These setups, diagrammed in Figure 7.2, are known as

''Beam'' (4-0), ''Tilt'' (3-3), ''Coign'' (3-1), and ''Mesh'' (2-0). (There are other

setups, including four-move and five-move setups, but these are the basic ones

from the original rules.) The white pegs show the first and second moves, and the

black pegs show the two possible third moves. Either third move links to both the

first and second moves (known as double linking). The setups shown are for

white, which wants to connect the top and bottom rows of the board.

After the first peg is placed, there are two possible follow-up moves that start a

Beam (one toward the top of the board and one toward the bottom), four follow-

up moves each to start a Tilt or Coign, and two for a Mesh. That is a total of 12

likely follow-up moves for the side that placed the first peg, which is far fewer

than 482. If the opposition attacks the setup ineffectually, there will be exactly

one move available to complete the setup. If the opposition does not attack the

setup at all, there is no need to waste a move by completing the setup using either

of the two available third moves, and the AI should look for the next setup that

connects to this one.