The Game Tree for Sim - Traveling to St Ives

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.

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.

There are, in fact, 12 possible sequences to reach this game state (6 ways to draw the blue triangle, 2 ways to draw the two red lines, 6×2 = 12).  We can prune the duplicate board, and have the node that represents the previous move draw an edge to the already-existing board.

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 shows the same portion of the tree, but with the two paths pointing at the same node.

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.

Anybody You Know?

In the last post--when I mentioned counting the number of games in Sim--I failed to take into account any tie games.  In fact, the question can be asked, can there be any tie games?  Can we draw fifteen lines between the six vertices, and end up without any major triangles all in the same color?

To explore this possibility, I'd like to tell a little story that came to me in a dream (well, no it didn't, but it sounds better that way):

  I was invited to a gathering by my friend Alicia.  It was supposed to be a “game night,” so we were told to bring a game to play with the others.  When I arrived, Alicia was the only one there.
  “Hey there, Alicia, what game did you bring?”  I asked.  “Decided to go with an oldie,” she said, “Chutes and Ladders.”  “Classic,” I commented.
  “How about you, Karl B?  What game did you bring?” she asked. 
  “Well, it’s a new one I’ve created called Friends and Strangers,” I replied. “I’m hoping to try it out tonight.  But it depends on how many people show up.  You can play it with three or more, but you need three people who are all mutual friends or mutual strangers.”
  “Mutual strangers?” she asked, puzzled.
  Just then, another friend of mine showed up, Caroline.  “How’s it going, Karl B?  Is this where the game night is?”
  “Yes, do you know Alicia?” I said, introducing the two ladies.  Having never met before, they exchanged pleasantries.
  “How many folks do you expect tonight?” asked Caroline.
  “I really don’t know,” replied Alicia.  “I just put the announcement on the bulletin board.  It could be a really random collection of people.  Can we play your game, Karl B, with just the three of us?”
  “Not really,” I said.  “It requires three people who really know each other, or three people who know nothing about each other.  Since you and Caroline are ‘strangers,’ but I know you both, we don’t yet qualify.”
  “Weird game,” commented Caroline, munching on some celery from the food table. “I have Apples to Apples™, but that is better with more people, too.”
  “Do you always speak with little superscripts?” asked Alicia.
  At this point a new face arrived, someone I had never met before.  It turned out that his name was Daniel, and he was a friend of Caroline’s, but a new acquaintance to Alicia.
  “So can we play your game, yet, Karl B.?” asked Alicia.  “We’ve got three people who don’t know each other: I don’t know Caroline, you don’t know Daniel, and Daniel doesn’t know me.”
  Daniel thought this was an odd question, so after explaining my game’s requirements, I replied, “No, I’m afraid it still won’t work.  That’s what I meant by mutual strangers. It needs to be a three-way arrangement, or a three-way estrangement, so to speak.”  “Cute play on words,” commented Caroline.  Daniel just chewed on some chips and salsa.
  I decided to draw a diagram.  “See, before Daniel came, we had three people, so I’ll draw three labels, A, B, and C.  I’ll draw two blue lines to show that I know Alicia and Caroline, and a red one to show Caroline and Alicia are new to each other.”

 Figure 3-1

  Alicia took the pens from me.  “I get it.  Now that Daniel is here, we add a label ‘D’, and draw a blue line to his friend Caroline, and two red ones to you me as strangers.” 

 Figure 3-2

  At this point, Daniel finally spoke up.  “Okay, so to play your game, we would need triangles between three of the people, uh, I mean labels. And those triangles must be all red or all blue, right?  I mean, there's a red triangle internally here, but it falls short of the labels.”
  “Yes, that’s one one way to look at it,” I replied.
  “So,” asked Daniel, “how many people have to be at a party in order to assure that you can play your game?”
  “Um, I don’t know, really,” I admitted.  “I’ve always just foisted this on my family, and we’re all friends…”
  “Not my family,” interjected Caroline.
  “…so I was kind of hoping for three people tonight who were mutual strangers so we could test out that aspect of the game.  I've never thought of a ‘minimum’ number.”
  Daniel considered the diagram further. “Well, if no one else shows up, I’ve got Ticket to Ride™ which is fine with four people.” “More superscripts,” Alicia muttered.
  “Oh, I do hope someone else shows up,” I said.  “If someone comes who knows two of the four of us, we’ll be able to play one way or the other…I think.”
  “I’m not so sure,” murmured Daniel.
  At that point, Alicia jumped up excitedly.  “We’re about to find out!  Here comes my friend Ethan!” as one more person entered the room.  Poor guy, he was immediately assaulted with questions about who he knew in the room and who he didn’t.  After all the introductions, it turned out he was good friends to Alicia and Daniel, but Caroline and I were strangers.
  “Great!” I said.  “We should be good, now.”
  “I don’t think so, Karl B,” said Caroline ominously, studying the diagram.  She grabbed the pens and drew four more lines.

Figure 3-3 

  I stared at the diagram.  No solid-color triangles between the labels.  I looked at the people.  No mutual friends between three of them, and no mutual strangers either (although we were fast becoming acquainted).  I was stuck.  People expressed sympathy for my plight.
  “Oh, well,” I said, appreciating their kind support.  “It probably isn’t a very good game, anyway.”
  “Looks like you’ll need at least six people to guarantee you can play,” mentioned Daniel.
  “That’s what we thought about five people,” I said.  “Maybe there’s a way to end up with six people who all know each other so mediocre-ly that there aren’t three friends or three strangers.”
  “Well, here comes Frank,” said Alicia, as the sixth member of the party strolled in.  “Perhaps he has a theory about this.”

He did have a theory.  That theory is now called Ramsey's theorem, named after Frank P. Ramsey, a British mathematician who lived from 1903 to 1930.  I love Wikipedia's description of the theory:

One of the theorems proved by Ramsey in his 1928 paper On a problem of formal logic now bears his name (Ramsey's theorem). While this theorem is the work Ramsey is probably best remembered for, he only proved it in passing, as a minor lemma along the way to his true goal in the paper...[1]

 Every article I remember about Sim invokes Ramsey's theorem to prove that Sim does not end in a tie.  Ramsey's theorem states, among other things, that any 6-vertex diagram drawn with two colors (such as a Sim game board) must have a monochromatic triangle between the vertices of one color or another. Therefore, Sim cannot have a tie game.  I suppose that this is appropriate, since it was Gustavus Simmons' research on Ramsey theory which led him to invent Sim.

I have the utmost respect for Ramsey and his theory, but this "proof" that there was no tie game has always seemed a little hollow to me. I would prefer something a little more accessible than just invoking a higher-math-type theorem.  My favorite explanation goes as follows:

Consider a completely filled-in game board of Sim.  Any given vertex has 5 lines drawn from it to the other vertices.  Therefore, there must be at least three of one color or the other (see Figure 3-4).

Figure 3-4. Three lines of one color drawn from one vertex

In a completely filled-in game board, lines 3-4, 3-5, and 4-5 must all be drawn.  It is easy to see that if any of them are draw with the same color (blue, in Figure 3-4), then a monochromatic triangle will be formed.  But, if all three of them are then "safely" colored the other color (red), then we still get a monochromatic triangle (red, in this case; see Figure 3-5).

Figure 3-5. A losing game results even if "closing lines" are drawn "safely."

So there you have it: a nice little proof that the Game of Sim will not end in a tie.  And, the successful conclusion of a lovely little game-night party.

Postscript:  The game Friends and Strangers is not a real game(although it is based on a real property[2]), and I'd be intrigued with anyone's attempt to devise one along the lines described in the dream.  I suppose that if there were ever such a game, the advanced version would require either four mutual friends or four mutual strangers.  Ramsey's theory states that you would have to have eighteen people to assure one group or the other[3].  Perhaps if you invited two baseball teams together...

[1] Wikipedia, Frank P. Ramsey, http://en.wikipedia.org/wiki/Frank_P._Ramsey, retrieved 15 Nov 2013.
[2] Wikipedia, Theorem on Friends and Strangers, http://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers, retrieved 15 Nov 2013.
[3]  Wikipedia, Ramsey's theorem, sub-topic Ramsey Numbers, http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers, retrieved 15 Nov 2013.

How Many Games?

A joke is told about mathematicians:  If you show a mathematician a pot of water on the kitchen table, and ask him to please boil the water, he will gladly place it on the stove and heat it up to boiling.  If you then, perhaps the next day, show him a pot of water on the kitchen counter, and ask him to please boil the water, he will then place the water on the table.  After all, reasons the mathematician, he has merely reduced the problem to one he has already solved.

I didn't say it was a funny joke. Still, I like it.  And it is vaguely related to the concept of recursion,which comes in handy for finding out the about the number of games possible in the Sim universe.

When Simmons first proposed Sim, he conjectured that the second player might have an advantage, since the first player can draw up to eight lines, while the second player can draw only seven.  Ignoring the first four lines--since it is impossible for a player to make a single-color triangle until he has drawn three lines--the first player has five chances to lose as opposed to the second player's four chances.  Simmons figured this is likely an advantage, as a player doesn't so much win in Sim as he avoids becoming the loser--the game ends when one player forms a triangle entirely of his color. Therefore, a winning strategy really involves "not losing."

To test Simmons' conjecture, we use a computer program to iterate through each of the different possible games, and then count which of them end after an odd or even number of lines, which corresponds to a loss for Player One or Player Two.

Lines Drawn     End Games
1 line:                 0
2 lines:                0
3 lines:                0
4 lines:                0
5 lines:           15,840
6 lines:          151,200
7 lines:        4,082,400
8 lines:       27,993,600
9 lines:      348,364,800
10 lines:   1,488,067,200
11 lines:   9,068,112,000
12 lines:  19,719,936,000
13 lines:  45,816,192,000
14 lines:  28,086,912,000
15 lines:   4,572,288,000

Table 2-1

 

Player One can lose with 5, 7, 9, 11, 13, or 15 lines, while Player Two can lose with 6, 8, 10, 12, or 14 lines. Apparently, Player One loses in 59,809,055,040 games, while Player Two loses in 49,323,060,000 games, which seems to confirm that Player Two has an advantage.  The total number of games in the Sim universe is 109,132,115,040.

It is interesting to me that there are some 15,000 games that end after five lines (the shortest game possible).  This could only happen if Player One was being completely contrary and trying to lose.

 

Figure 2-1

What if we somehow take out such premature losses, and only count those that are forced?

Let us try to refine the definition of Sim in the following way:  Players alternate drawing lines as before, except that completing a single-colored triangle is now an illegal move.  The last player to draw a line--to bring the game to the point where no more legal lines may be drawn--is declared the winner.  In this version, which I will call Sim+, the numbers turn out a little differently:

Lines Drawn     End Games
1 line:                 0
2 lines:                0
3 lines:                0
4 lines:                0
5 lines:                0
6 lines:                0
7 lines:                0
8 lines:                0
9 lines:           86,400
10 lines:      27,993,600
11 lines:     248,832,000
12 lines:   6,625,152,000
13 lines:  11,757,312,000
14 lines:   4,572,288,000
15 lines:               0

Table 2-2

This time, Player One wins with 9, 11, or 13 lines (no one can get to 15 lines--it would cause an illegal move) while Player Two wins with 10, 12, or 14 lines.  Doing the math, Player One wins 12,006,230,400 different games, while Player Two wins "only" 11,225,433,600 games (a total of 23,231,664,000--only 20% of the games in regular Sim).  So, maybe when the players actively avoid making the final triangle (or, as in Sim+, it is illegal to do so), then Player One has the advantage, or at least the game is a lot more evenly matched.  It's interesting to me that in both games, the maximum number of end games occurs at 13 lines.  For Sim+, this helps Player One's win totals tremendously; for regular Sim, it is a detriment.

As opposed to regular Sim, the first end game in Sim+ occurs at 9 lines, a win for Player One, since Player Two cannot avoid making a triangle.  What does this look like?  Here's an example (I think it has a nice symmetry):

  

Figure 2-2

In order to generate the numbers for the tables above, I initially wrote a simple recursive program (a "depth-first" search in computer terms).  However, it was taking a really long time. How long?  I'm glad you asked.  I recorded some numbers on the second table (the smaller of the two), and finally quit after the program had run for six and a quarter hours.  At that point, we were about 3.8% of the way through the process, which implies it would have taken just a few hours short of a week to finish the calculations.  I ended up calculating the tables a different way, which I hope to tell about in another entry.

Introduction - My Lab Notebook about Sim

When I was in high school, I came across an article in Scientific American[1] about a pen-and-pencil game called Sim.  It had been invented by a mathematician by the name of Gustavus Simmons[2] and was named after him.  I was intrigued at the time by its simplicity and thought that I would be able to devise a winning strategy.  In college I even wrote a couple of papers on the the game, and thought I had come up with a reasonably optimal way to ensure a win.

I was wrong.

This blog is a small experiment in writing down the things I have learned recently as, once again, I decided to investigate different aspects about the game.  You may think of this as a kind of lab notebook, which is bound to show wrong assumptions, meandering "rabbit-trails" where I go way off topic, and maybe the occasional insight into the game, game theory, or possibly programming.  I don't expect to have a whole lot of people following such a blog as this, but should anyone stumble across it, welcome!

As this is an introduction, it seems reasonable to present the basic Game of Sim.  You can grab a piece of paper, draw six dots in a hexagonal shape, bring in a partner to play against, and you are ready to go.

 

Figure 1-1

Figure 1-1 above shows the "empty" version of the board that I will use to show moves throughout this blog.  The "dots" are numbered for easy reference.

Things go very well if you have two different-colored pens or pencils--one for each player--but it works fine to alternate solid lines and dashed lines, too. The two players take turns drawing lines between the six dots (or vertices) of the hexagon with their color.

 

Figure 1-2

Figure 1-2 above shows a game in progress; the player with the blue pen went first and a total of seven lines have been drawn so far.  A "major" triangle is formed from three lines that connect the numbered vertices (interior triangles don't count).  For instance, there is one major triangle in Figure 1-2, between vertices 2-3-4.  It has two blue lines and one red line. The object of the game is to avoid creating a major triangle with only your colors.  The first player to create a monochromatic major triangle loses the game.  For instance, continuing the game above, the players might come to the following point (Figure 1-3), where the "blue" player is about the draw the last available line:

Figure 1-3

With only one line left, the blue player will be forced to create a major triangle of his own color.  In fact, in this case, with one line he will create two monochromatic major triangles, 1-2-4 and 1-4-6.

 

Figure 1-4

Sometimes we will highlight the losing major triangles so they are easier to see, as in Figure 1-5:

Figure 1-5

When I play this game, I keep thinking that there should be a winning strategy--simple enough for a person to master--that would allow a player to make the "best" moves.  That is, a strategy (a plan, an algorithm, a heuristic) that indicates the moves that would lead to a win, or at least stave off a loss as long as possible.

There is already quite a bit about this game on the internet, but I have not yet found a such a useful strategy.  One goal of this blog is to find this elusive strategy, but more compelling (to me, at least) is the chance to use this game to learn many new and interesting things.  You are most welcome to tag along as we wander down the road of discovery!

[1] Gardner, M. Mathematical Games, Scientific American, February (1973), pp. 108-112

[2] Simmons, Gustavus J. "The game of SIM," J. Recreational Mathematics, 2(2), 1969, pp. 66.