Grey Matters: Blog: The Secrets of Nim (Dice Nim 2)

The Secrets of Nim (Dice Nim 2)

Published on Sunday, July 03, 2011 in fun, Martin Gardner, math, nim

NIM is WIN upside down! (NOTE: Check out the other posts in The Secrets of Nim series.)

We're going to continue the discussion of the game 31 from the previous post, so make sure you've read that post first!

Just so we have them handy in this post, we'll go over the winning strategies for 31 once again:

Ask yourself: “Can I rotate the die so as to get to a running total with a digital root of 4 (4, 13, 22, or 31)?” If so, do it! If not...

...Ask yourself, “Could I rotate the die to a 3 or a 4, so as to get to a running total with a digital root of 1, 5, or 9 (1, 5, 9, 10, 14, 18, 19, 23, 27, or 28)?” If so, do it! If not...

...rotate the die to a 2 or a 5, so as to obtain a running total with a digital root of 8 (8, 17, or 26). Assuming the other player hasn't purposely or accidentally made a good move, this one will still be possible.

When charted out against every number from 4 to 31, here's how the strategies appear:

Running Total	Digital Root	Reached via...	Running Total	Digital Root	Reached via...
4	4	Any Number	18	9	3 or 4
5	5	3 or 4	19	1	3 or 4
6	6	Avoid	20	2	Avoid
7	7	Avoid	21	3	Avoid
8	8	2 or 5	22	4	Any Number
9	9	3 or 4	23	5	3 or 4
10	1	3 or 4	24	6	Avoid
11	2	Avoid	25	7	Avoid
12	3	Avoid	26	8	2 or 5
13	4	Any Number	27	9	3 or 4
14	5	3 or 4	28	1	3 or 4
15	6	Avoid	29	2	Avoid
16	7	Avoid	30	3	Avoid
17	8	2 or 5	31	4	Any Number

The “Running Total” and “Digital Root” columns should be understandable, assuming you read my previous post. The “Reached via...” column lists the only numbers you should use in attaining the corresponding running total.

Other Totals?

What if someone suggests playing with a total other than 31? First, you could simply get lucky and they could choose a total whose digital root is also 4, such as 40, 49, 58, or so on. In that case, the strategy doesn't change at all (except for possibly more primary key numbers).

On the other hand, you may be up against, say, a Douglas Adams fan who is bound and determined to play to 42 (whose digital root is 6). Well, you could analyze the game for all of the digital roots from 1 to 9, and memorize 9 distinct strategies (and I could probably teach you how ;), but there's an easier way.

Once the goal total is chosen, look for the next number after that whose digital root is 4. In our 42 example, the next number above that with a digital root of 4 is 49 (49 → 4 + 9 = 13 → 1 + 3 = 4). The important thing to take note of here is how far above the target number this is. In our 42 example, we'd subtract 49 - 42 to get 7. 7 is the number you want to remember. We'll refer to this as your “adjustment number”.

From here, whenever you're considering your strategy, you simply take the actual running total, and mentally add your adjustment number before considering any strategies. In effect, you're secretly playing to another number with a digital root of 4, but the other player is unaware of this.

Let's try our sample game which being played to 42, in which you go first against another player. You work out, as above, that the next “4” number is 49, and do 49 - 42 to get 7. Since you're moving first and the running total is effectively 0, you think to yourself “0 + 7 = 7”, giving you a “secret running total” of 7. Obviously, choosing 6 here is the best best, as it gives you the total of 13, so you set start with 6. The real running total is 6, even though your secret running total says otherwise.

Say the other player rotates the die a quarter turn to 2 (Real running total: 6 + 2 = 8). Before you move, you mental add 7 to the real running total, giving you a secret running total of 15. Let's see, you can't get to 22 from 15, so how about adding 3 to get to 18 (digital root=9)! You rotate to the 3, so the real running total is now 11 (8 + 3 = 11).

The game continues on in this manner, with you adding your secret adjustment number to the real running total each time. If you played the original version of 31 enough to be familiar with the strategy, then you only need to get used to adding the adjustment number to the real running total each time, and you'll consistently win!

It's probably a good idea to keep the real running total on a piece of paper. Not only will this give you something to glance at when adding your adjustment number on your move, but it also minimizes and settles any disputes about the score.

Analysis

The question you may have now is how the strategy was developed. Not surprisingly, it's tricky to analyze. Back in 2008, these chess players tried analyzing the original 31 game, but never got as far as stating the strategy as clearly as above. Note, however, that they quickly picked up on the importance of 4, 13, 22, and 31.

If you're really interested in seeing how the strategy develops, there is a fun project you can try for yourself that also meshes nicely with the principles in my recent Iteration, Feedback, and Change series. I'll describe the craft version below, but if you're into computer programming, you could read through the process below and write it as a program instead.

Craft Project/Computer Program

Back in 2008, I wrote about Hexapawn, a 2-player game on a 3 by 3 chessboard, played only with 3 black pawns and 3 white pawns. The game itself is short and easy to master. The major point of the game was that you could build a simple array with matchboxes and counters (beads, coins, colored candies, etc.) that could not only play against you, but learn to win the game! Here's the original description by Martin Gardner, detailing how the matchbox array is prepared and used. For those interested in doing a computer program version, here's a BASIC listing to inspire you, including a sample run.

You can adapt this matchbox project quite easily to 31. For the dice game version, you'll also need 22 matchboxes, and counters in 6 different colors. You should have 16 counters in each of the 6 colors, for a total of 96 counters. You'll need to decide which color represents which number. For example, you might decide that red=1, blue=2, green=3, orange=4, white=5, and black=6.

On 1 of the matchboxes, you're going to write “Move 1”. On 3 of the matchboxes, you're going to write “Move 3”. You'll also write “Move 5” on a different set of 3 matchboxes, and the same for “Move 7”, “Move 9”, “Move 11”, “Move 13”, and “Move 15”.

In the single “Move 1” box, you're going to place counters of all 6 colors. This represents the fact that the matchbox array, which will always go first, can start the game by choosing any of the 6 numbers on the dice.

On one of the “Move 3” boxes write “1 or 6 on top”, an only put in the counters with colors representing 2, 3, 4, and 5 in that box. Do the same for one of the “Move 5” boxes, one of the “Move 7” boxes, and so on. On another “Move 3” box, write “2 or 5 on top”, and only include the counters representing the numbers 1, 3, 4, and 6 in that box. Again, do the same for one of the “Move 5” boxes, one of the “Move 7” boxes, and so on. Finally, mark all the remaining empty boxes, write “3 or 4 on top”, and only include counters representing the numbers 1, 2, 5, and 6 in those boxes.

Note that there's only a single move 1 box, as any number can be chosen on the first move. Each of the other moves has 3 boxes, because there are 3 different possibilities on each of the remaining moves. From this starting point, play is similar to the Hexapawn game described above, except that the matchbox array always goes first.

Playing Against the Matchboxes

To start the game, pick up the game marked “Move 1” shake it, and draw out a color at random. Close the matchbox and set the chosen counter on top of the “Move 1” box, setting the die according to the color, and have that be the starting total. Next, you make move 2 by giving the die a quarter turn in any direction and adding that to the running total. Feel free to use the strategies you learned above to try and win.

After that, it's time for the computer to play move 3, so look at the die, note the number on the top, and pick up the corresponding “Move 3” box. For example, if you left a 5 on top when you made move 2, then you'd pick up the box marked “Move 3, 2 or 5 on top”, and choose a counter randomly from that box. Again, set the counter on top of the box from which you chose it, rotate the die as needed, add the amount to the running total, and continue the game until you or the matchbox wins.

Since the matchbox array is playing randomly, and you're playing with an effective strategy, you'll more than likely win this first game. Here comes the interesting part: If the matchbox array loses a game, punish it by permanently removing all the counters which are sitting on top of the boxes. If the matchbox array wins the game instead, reward it by placing each of the counters back into their corresponding boxes. Now, play the game again.

Playing Repeatedly

If you play the game against the matchbox array repeatedly, punishing it and rewarding as described above, you'll notice that the matchboxes get better and better at playing the game! Don't be surprised if the matchbox array eventually becomes unbeatable. Because you're employing the processes we talked about in the Iteration, Feedback, and Change series, you'll note that the remaining stones allow the game to “survive” more effectively in the context of the game.