(NOTE: Check out the other posts in The Secrets of Nim series.)

Back in my Secrets of Nim Wrap-up post, I briefly mentioned this Spiked Math cartoon. The stick figure (presumably visiting from XKCD) is challenged to a game of multi-pile standard Nim, and after just looking at the piles, he concludes that he's lost.

Being able to just look at a multi-pile Nim game like that would be amazing wouldn't it? Sure, you could always use the Nim Strategy Calculator, but is it really possible to look at an unfamiliar multi-pile Nim game and analyze it in your head? Surprisingly, the answer is yes!

Refresher

Before we move ahead, let's make sure we're on the same page. All the Nim terminology I'll be using is defined in Part 1 of this series.

You should understand standard multi-pile Nim, and the similarities and differences between that and multi-pile Misère Nim.

Pay special attention to the fact that multi-pile Misère Nim really only differs in the endgame. You should also know the moves by heart that will win multi-pile Nim, standard and Misère.

Finally, you'll need to know your powers of 2 up to 16: 1, 2, 4, 8, and 16. Sure, you could go on beyond these to 32, 64, 128, and so on, but very few Nim games will have rows of 32 or more objects.

Once you've mastered the strategies I'm about to describe, the best way to present this is to have the other person choose the number of piles used, and how many objects will be used. You then stipulate that you will decide who goes first.

Who Goes First?

When faced with an unfamiliar layout, you first need to determine who should go first. Let's use a layout of 4, 6, and 7 objects as an example.

WYou start by determining the largest power of 2 involved. What's the largest power of 2 that we'll use here? 4, 6, and 7 are all less than 8, so the largest power we'll need to look at is 4. OK, so what do we do with the 4 we've decided to use?

What we're going to be doing is looking for pairs of each power of 2, in a process that will be described shortly, starting with the largest and then working with each power down to 1. In our above example, this means we'll be looking for pairs of 4s, pairs of 2s, and then pairs of 1s.

Ask yourself: How many rows have at least 4 objects in them? In our 4, 6, and 7 example, all three do! In other words, we have a pair of 4s, and an extra 4, as depicted below:

XXXX
XXXXxx
XXXXxxx

Anytime you have even a single unpaired power of 2, as we do in this case, you'll want to go first. If you examine all the powers of 2, and everything is paired up, you'll want the other person to go first. In this case, remember that you have a 4 (that unpaired 4).

However, for later use, you're going to want to analyze any and all upaired groups. For the next round, we need to mentally remove all those groups of 4 (effectivly ignoring the first 4 cards in each row), leaving just a group of 2 and 3:

xx
xxx

After 4, we now have to deal with 2. With piles of 2 and 3, both have 2 objects in them:

XX
XXx

The 2s are paired, so we don't have to think about 2s. Don't forget that unpaired 4 from earlier, though.

For the next round, we mentally remove those 2s, and that leaves us with a single pile of 1, which is unpaired. So, from a pile of 4, 6, and 7, we've narrowed down that we have an unpaired 4 and an unpaired 1.

As mentioned before, when you have 1 or more unpaired powers of 2 in the layout, you should decide to go first.

In the cartoon linked above, there were piles of 3, 5, and 6, and the player was told that he had to go first. Analyzed the same way, we see that there's a pair of 4s:

xxx
XXXXx
XXXXxx

Leaving us with 3, 1, and 2 objects, and looking at 2s, we have a pair of 2s, as well:

XXx
x
XX

Removing those obviously leaves us with a pair of 1s. So, every power of 2 we examined was paired up. That means there's no good move for the first player in this game, and the first player will lose, assuming all other moves are played perfectly.

What's My First Move?

Going back to our example game of 4, 6, and 7, we found ourself left with an unpaired 4 and an unpaired 1. How do we use this to determine our first move?

The rule of thumb here is to remove enough items from the largest unpaired number (4 in our example) that all the other numbers (just 1 in our example) will be paired up.

For our example case, where we wound up with an unpaired 4 and an unpaired 1, we're going to pair up that 1 by trimming the 4 down. In other words, we're going to remove 3. But from which pile?

The removal of 3 we've determined should be done from the smallest pile where such a move is possible. In our piles of 4, 6, 7, this means the pile of 4. Removing 3 leaves us with piles of 1, 6, and 7 for the other player.

All this sounds complicated, but it's really just a way of applying the equals pairs and mirroring approach you learned in the earlier multi-pile Nim columns.

Do you have to keep analyzing powers of 2 to play the game? Not really. If you know the strategies taught earlier for piles of 3, 5, 7, once you get all the piles down to numbers equal to or less than those, you can start playing those safe moves from memory.

If you can memorize winning moves for larger games, perhaps using the Nim Strategy Calculator, then you'll have a larger set of practiced memorized moves, and can handle even larger games automatically!

What if you're given four piles, consisting of 13, 5, 1, and 9 objects? Do you think you could properly analyze it? Here's a video titled Classic Nim Game - Powers of Two, in which two high school girls analyze exactly this game. The video can be downloaded and watched offline if you don't have Flash installed.

Master this, and you can play Nim like a mathematical genius!
––––––––––––––––––––––––––––
Answer to Halloween Candy Puzzle: