Nim Part 5

Recently I was chatting with a friend about how I had generalized the game of Nim. I was very proud of the fact that I had solved the game no matter how large the pile was and no matter how many stones each player could remove. I thought I had generalized all I could. Then he asked me “what if you had more players?”

The thought had never occurred to me, but instantly I knew it would be interesting. Here is why:

Suppose you 3 players, Alice, Bob, and Charlie. Each player can remove 1 or 2 stones. Now consider what happens when Alice is facing a pile of 4 stones:

Capture4

As you can see, no matter what happens, Alice cannot win. However, the choice that Alice makes will determine whether Bob or Charlie wins. The above diagram proves that no matter how you change around the game, once you have more than 2 players, there is no guaranteed winning strategy. There might be a strategy that increases your chance of winning, but you cannot find a foolproof plan, like we could with 2 players.

As I began to explore the game with 3 players, I realized that I needed to add in some additional rules. My analysis would not make sense if one player just decided to be silly and only took 1 stone every turn. Further, if one player intentionally lost every game, it would make analysis impossible. I decided that none of the players would work together. Any partnership would be useless in the end because only one player can take the last stone. In a future post I may consider what would happen if the players collaborated on a slightly different version of Nim.

Here is what I found in picture form:

nim3

 

The picture is a diagram of the optimal strategy when playing with 3 people. The number represents the number of stones you are currently facing. The arrows indicate which move you should make. For example, if you are facing a pile of 35, you should take 2 stones and leave your opponent with 33 stones. Some numbers have an option. For example, if you are facing 6 stones, you can remove either 1 or 2 stones. Either choice gives you the same chance of winning.

The colours represent the pattern I found. Every time you reduce the pile by 5 stones the recommend strategy repeats. You can see how both 33 and 28 can remove 1 or 2 stones. Hence, if you were facing 528 stones, you should remove either 1 or 2 stones. I found this very beautiful.

Here are some interesting things to note.

  • If you are facing 5 stones you should remove 1 stone and leave the next person with 4. This makes sense because now they (like Alice above) are guaranteed to lose
  • If you have 7 stones you should remove 2 stones. However, there is no move that leads to 7 stones. Thus, unless the game starts with 7 stones, no player will ever face a pile with 7 stones
  • The pattern is initially chaotic and does not begin to repeat consistently until the red section with 13 stones

While the above picture details what move each player should make, it does not describe his or her chances of winning. Below is a table that gives the percent chance of winning, depending on the size of the pile:

Capture5

As you can see, the chance of winning repeats every 5 stones, just like the strategy repeats every 5 moves.

In conclusion, Nim gets complicated and beautiful with 3 players.

Math notes

For those of you curious as to how I created the above graphic, here is a rundown of my method. First, I assumed that each player was completely rational and would make the best decision possible. I defined the best decision as the move that would maximize the number of paths to victory. Second, if either move had an equal percentage of paths that would lead to victory, either move could be chosen.

The algorithm started with the base graph 3 → 2. It then considered the case with 4 stones and determined that the moves 4 → 3 and 4 → 2 were valid moves. The algorithm continued to build up the graph, adding the next number of possible stones at each step.

I realized that by the time I had 48 stones, there were already 26,244 possible paths. A quick graph revealed that the number of possible paths increased exponentially.

Capture6

If we wanted to determine the optimal strategy for 1,000 stones, we would need to search:

y = 0.5851 e^{0.2158 \times 1000} = 0.5851 e^{215.8} = 3.0 \times 10^{93} paths

This is more than the atoms in the known universe! Thankfully, I noticed a pattern in the strategy and so I could determine the chance of winning and the recommended strategy without brute forcing the solution on my computer and waiting for eternity.

Advertisements

1 Comment

Filed under Uncategorized

One response to “Nim Part 5

  1. Pingback: Nim Part 6 | the Math behind the Magic

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s