As I was going to St. Ives, I met a man with seven wives
Every wife had seven sacks,
And every sack had seven cats,
And every cat had seven kits.
Kits, cats, sacks, and wives:
How many were going to St. Ives?
In another post, I touched briefly on whether the first or second player has an advantage when playing Sim. I then took a small detour to verify that one or the other must be the winner (there can be no tie games). So now I can return to figuring out which player can force a win, assuming that they know everything there is to know about the game. The tool I will use for this figuring is called a “game tree.”
A game tree is used to represent the different possible states of a game, and how to get to each state. In mathematical terms, it is a directed graph where each node represents a different state of the game, and the edges between the nodes represent a player's move from one state to another. Figure 4-1 shows the portion of the tree for first move for Sim. You'll probably have to click on it to make it big enough to decipher.
Figure 4-1
Player One moves from an empty board to one of fifteen possible boards, each with a single line on it. Each level down in the tree represents a new move (this game tree grows downward; if you are uncomfortable calling such a thing a "tree," it may help to turn yourself upside down when viewing the figures). The next level (Player Two's first move) produces a tree with fourteen new branches from each of the fifteen boards shown above; it is a ponderous image and I won't even try to display it here.
This kind of game tree would have an exceedingly large number of nodes. An upper bound for the total number of the nodes would include the one for the top, empty board; plus 15 at the next level; plus 15 × 14 at the next level; plus 15 × 14 × 13 at the next; until you get down to 15! nodes at the bottom level. This upper bound reminds me of the nursery rhyme about going to St. Ives shown at the beginning of this post. Except that instead of the traditional answer to the nursery rhyme (one: I am the only one going to St. Ives), we have a much bigger number:
1 + SUM(15! ÷ x! for x = 14,13,...,2,1) = 2,246,953,104,075
The equation above uses an trick with factorials: we get our series of 15 + 15×14 + 15×14×13 + ... by using (15! ÷ 14!) + (15! ÷ 13!) + (15! ÷ 12!) + ... which turns out to be the same thing.
Anyway, 2.2 trillion nodes is a lot to handle. If we could represent each game state as a single byte (which I don't think we can do), then such a game tree would use up 2.2 terabytes to store. Fortunately, there are ways to reduce the size of the game tree.
Anyway, 2.2 trillion nodes is a lot to handle. If we could represent each game state as a single byte (which I don't think we can do), then such a game tree would use up 2.2 terabytes to store. Fortunately, there are ways to reduce the size of the game tree.
Reduction 1: Some paths finish the game before move # 15
A game of Sim is finished as soon as one player completes a major triangle in all one color. Recall the game illustrated in Figure 4-2 (where Player One was obviously suicidal and wanted to lose quickly).
Figure 4-2
The portion of the game tree beyond this point can be pruned from the overall tree, saving (in this instance) 10 + 10×9 + 10×9×8 + ... + 10! nodes. This saves only 6,235,300 nodes, but hey, six million here, six million there, it adds up. Anywhere a loss is registered before all 15 lines are drawn is a candidate for pruning.
I mentioned before that there were 109,132,115,040 different games in the Sim universe. This isn't the same as the number of nodes in a game tree, but even if each game had 15 lines (which they don't), we're talking about 1.5 trillion instead of 2.2 trillion. It's a start.
Reduction 2: Some paths produce identical game boards
Looking at Figure 4-2 again, it is not possible to determine the sequence of play. Any of the following are possibilities (B indicates Blue for Player One, R indicates Red for Player 2)
- B1-2, R1-5, B2-3, R4-6, B1-3
- B1-3, R4-6, B1-2, R1-5, B2-3
- B1-2, R4-6, B1-3, R1-5, B2-3
- B2-3, R1-5, B1-3, R4-6, B1-2
- etc., etc.
As an example, Figure 4-3 below shows a portion of a game tree where drawing line 2-3 from one board or drawing line 1-3 from another board ends up with duplicate nodes within the tree.
Figure 4-3, duplicate nodes from different paths
Figure 4-4, consolidating the duplicate paths to point at the same node
By recognizing identical game boards, and directing the appropriate edge to only one instance of that game board, we reduce the size of the game tree significantly.
Reduction 3: Some game states are equivalent, even if they are not identical
This is actually a more general case of Reduction 2, and produces a profound reduction. Consider the following three game boards, shown in Figure 4-5.
Figure 4-5, game boards X, Y, and Z
It is easy to see that board Y can be rotated one "click" counter-clockwise and it becomes identical to board X. The only difference would be the labeling of the vertices, but since the labels are only present to help us humans, such a difference is immaterial.
Figure 4-6, board X & Y on either side, rotating the middle board matches up with each neighbor
A bit more difficult to see is the result of swapping vertices 1 and 4 in board Z, and suddenly that, too, is identical to board X. The labels (A and D) are again a little out of order, but still immaterial.
Figure 4-7, board X & Z on either side, swapping nodes A & D in the middle board matches neighbors
We will represent such a vertex swap by the following symbolism: m«»n means that vertex m has been swapped with vertex n. Thus, in Figure 4-7, the board on the right has 1«»4. We use numbers when swapping, always swapping the vertices at position 1,2,...,6. Normally, we would label the vertices with numbers; in these figures, though, it seemed like a good idea to show alphabetic labels with each vertex to illustrate where they travel to.
In fact, swapping is more general than the rotation that is illustrated in Figure 4-6. Board Y could also be "rotated" by the following sequence of swaps: 1«»2, 2«»3, 3«»4, 4«»5, and 5«»6. The node labeled "A" would move clockwise to position 2, then 3, then 4, then 5, and finally wind up at 6. Each of the other labels would shift counter-clockwise one position in the process.
If you can convert one game board into another one by a sequence of swaps, then those two boards are equivalent, at least as far as playing the game of Sim. Therefore, as in Reduction 2, by recognizing equivalent game boards, and directing the appropriate edge
to only one instance of that game board, we reduce the size of the game
tree even more.
Applying Reductions 1, 2, and 3 results in a manageable game tree.
We've used words like "significantly reduce" and "reduce even more". What is the overall result of applying these reductions? A game tree for Sim with only distinct game boards has 3,817 nodes. We've moved from a maximum of 2.2 trillion to just under 4 thousand. The first four levels of this game tree are shown in Figure 4-8.
Figure 4-8, the first four levels of the game tree for Sim
(displaying only distinct game boards)
For the sake of simplicity, I haven't provided all the information that would be included in a game tree. For instance, going from one level to another, it would be useful to know which lines drawn took you down which edge. At the second level, to go to the left, you could pick lines 1-3, 1-4, 1-5, 1-6, 2-3, 2-4, 2-5, or 2-6. All these game boards are equivalent to the board shown with lines 1-2 and 1-3, that is, where the two lines share a vertex. To go to the right, you could pick lines 3-4, 3-5, 3-6, 4-5, 4-6, or 5-6. All these game boards are equivalent to the board shown with lines 1-2 and 3-4, this is, where the two lines share no vertices. It's interesting to see which swaps are necessary to convert the board with the chosen line into the board represented in the tree.
The challenge to producing such a game tree, however, is in recognizing equivalent game boards. In other words, how does one discover the sequence of swaps that turns one board into another?
Addressing this challenge is the topic for the next post.
