1

## The Secrets of Nim (Chocolate Nim)

Published on Sunday, February 13, 2011 in , , , , ,

()

In this post, you'll learn the sweetest and most tempting version of Nim ever: Chocolate Nim! If you've ever eaten a Hershey's Milk Chocolate Bar by breaking it along the lines, you've been practicing for this.

### Rules

Before we dive into the strategy for Chocolate Nim, we need to establish the rules of play. If you've played Nim before, these rules will be easily understood. If you haven't played Nim before, you'll want to check out the other Nim posts before trying this version out.
• There are two players.
• The players must alternate taking turns.
• The game is played using any chocolate or candy bar whose surface can be broken along existing lines, such as a Hershey's Milk Chocolate Bar.
• A turn consists of either breaking off 1 or more rows or 1 or more columns and eating them, or eating the remaining portion of the bar.
• Neither player may break off a row AND a column on the same turn.
With these rules in mind, you'll quickly find that you can't play standard Nim, in which the person who eats the last piece is the winner. If you did, the winning strategy would be to simply eat the entire bar on the first move!

So, the chocolate version is always a Misère Nim game, in which the person who eats the last piece is the loser. Now, in previous versions of Nim, pretty much any object could wind up being the last one in play. To make Chocolate Nim an analyzable, and therefore winnable, game, one square needs to be specified as the piece to avoid. This gives us the final rules:
• Before the play proceed, 1 individual segment of chocolate must be specified as the “losing segment”.
• The person who eats the losing segment is, of course, the loser of the game.
Just for fun, you could suggest imagining that the losing segment is the poison segment, or the segment made of bitter chocolate.

### Strategy

A standard Hershey's Milk Chocolate Bar has 3 rows and 4 columns, which is just large enough to make the game interesting, depending on which segment is chosen as the losing segment.

To start, you'll need to understand how to analyze multi-pile Nim. Make sure you've read and understood Part 2 of this Nim Series, as well as my post on visualizing multi-pile Nim.

To covert a given game of Chocolate Nim into a more familiar game of multi-pile Nim, all you have to do is count the number of columns to the LEFT of the losing segment (not including the losing segment itself), the number of columns to the RIGHT of the losing segment (again, not including the losing segment itself), the number of rows ABOVE the losing segment (yet again, not including the losing segment itself), and the number of rows BELOW the losing segment (still yet again, not including the losing segment itself). Each of these numbers is considered as a separate pile in multi-pile Nim.

Even though it's always a Misère Nim game (last person to remove an object loses), Chocolate Nim is actually equivalent to a game of multi-pile Nim in which the last person to remove an object wins (in other words, standard multi-pile Nim). Why is this?

The losing segment in is effectively a single item in its own special pile that nobody is allowed to touch until all the other piles have been removed. By being the last person to pick up a pile outside of that "special pile", you're forcing the other person to take the last item from that special pile.

I'll explain both of these concepts in more detail, with help from the illustration below.

The corner pieces, labeled A, are the easiest to explain. Any corner piece has 3 columns to one side, and 2 rows either above or below it. This translates into a two-pile game of standard multi-pile Nim, with a pile of 3 objects and a pile of 2 objects.

If you've played standard multi-pile Nim before, this is ridiculously easy. You play first, and always leave your opponent with 2 piles of equal size, and you'll always be able to take the last piece!

In Chocolate Nim with a regular Hershey Milk Chocolate Bar, this translates into always leaving the same number of columns next to the losing corner piece as you do rows above (or below) that corner piece. In this way, you'll always be able to leave the losing segment for your opponent.

How about those pieces marked B? Either one of those have 1 row above them, 1 row below them, and 3 columns to the side. In standard multi-pile Nim, this is like playing with rows of 1, 1, and 3 objects. You play first, remove the pile of 3, and you can't lose after that. Obviously, the Chocolate Nim version of this simply involves playing first, and breaking off the 3 columns to one side of the losing segment. This version also means you get to eat all but 2 squares of the chocolate bar!

Each of the segments marked C have 1 column to one side, 2 columns to the opposite side, and 2 rows above it (or below it). At this point, you're probably already ahead of me. This translates into piles of 1, 2, and 2 objects. If you go first, remove the pile containing 1 object, and mirror the other player from that point on, you'll always win. Naturally, in Chocolate Nim, this simply means breaking off the single-column to the side of the losing segment, and leaving the same number of rows and columns for the other player from that point on.

Finally, we get to the segments in the center, marked D. Can you work out the equivalent game and solution on your own at this point? Don't worry, I won't leave you hanging.

Each center segment has 1 row above it, 1 row below it, 1 column to one side, and 2 columns to the other side. This time, we're playing a 4-pile game of standard multi-pile Nim, with piles of 1, 1, 1 and 2 objects. You should now be able to see why, in Chocolate Nim, all you have to do is play first, reduce the surrounding chocolate to 1 column to the left, 1 column to the right, 1 column above, and 1 column below. From there, you mirror the other player and you can't lose.

In all the above cases specific to the 3-row and 4-column Hershey Milk Chocolate Bar, you must always go first to assure your win. A good way to present this is to state that the other person gets to choose the losing segment, and that you get to choose who will go first. In the case we've taught above, you always go first.

### Larger Chocolate Bars

Now that you understand how to win with a standard Hershey Milk Chocolate Bar, you can also analyze larger chocolate bars. For example, what if you wanted to play with a M&S Organic Fairtrade Milk Chocolate With Rose bar, which has 4 rows and 6 columns?

Start by explaining the rules to the other person, and mention that they'll chooses the losing segment, and then (and ONLY then!) you'll choose who gets to go first.

If you've practiced the strategies taught in both Part 2 of this Nim Series and the visualizing multi-pile Nim post, you should be able to work out whether it's to your advantage to go first at this point.

You could also use the Multi-Pile Nim Strategy Calculator and/or the Multi-Pile Nim Next Move Calculator, making sure that the piles are appropriately set, and that the Player who makes removes the last object is the: setting is set to Winner. This could also be a good way to practice.

If you know ahead of time that you're always going to be using a particular size bar, it would be worth your time to create a map of the bar and the appropriate strategies, as we did with the A, B, C, and D segments above.

### Exceptions

You should be aware of similar problems which seems the same, but in which the strategies taught here don't apply.

The strategy above works well for candy bars broken into rectangular segments, regardless of the numbers of row and columns. However, if a candy bar were broken up into triangular segments, such as this, then the approach taught above will not work. That link does detail another strategy, however.

Even more tricky is the similar game Chomp. In Chomp, you work down to the poisoned segment (always in a corner), but you're working with both rows and columns, which nullifies the previous strategies. The strategies for Chomp are very different.

### Closing Thoughts

Just for fun what about trying single pile Nim, standard or Misère, with a Toblerone bar? You could work the strategy out here.

Did you try this out? I'd love to hear any stories and thoughts you have on this game in the comments!

### 1 Response to The Secrets of Nim (Chocolate Nim)

8:27 PM

Great Game. Playing with Chocolate.