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.