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.