0

## Nim Strategy Calculator

Published on Sunday, August 22, 2010 in , , ,

()

I've received plenty of positive comments on my recent Secrets of Nim posts. Jim Wilder, of jimwilder.com, sent me a private message saying, "looked at your blog on NIM... excellent stuff there". James Grime (also known as singingbanana), gave me a great compliment on his twitter account. Even the gambling-specialists over at the Magic Cafe had many good things to say about my Nim series.

It's one thing to understand the math behind the various versions of Nim. Wouldn't it be nice if there were a quicker way to determine the best strategies for Nim?

Now there is! Today, I'm introducing my Nim Strategy Calculator! It's available as a permanent page, accessible from the Mental Gym's Workout page under Tools.

The Nim Strategy Calculator is actually 3 calculators in 1. The first is the strategy calculator for single-pile Nim, the second is for multi-pile Nim, and the final one is merely for determining the next move in the middle of a multi-pile Nim game (all these terms are defined in Part 1 of my Secrets of Nim post). You choose between them using the tabs at the top.

I've tried to make them easy to use and straightforward by asking for all the information in an interview-type format. Once you enter all the relevant information in a section, you simply click the Calculate button at the bottom of the section, and the strategy will be given to you in plain English.

Here are more details on each section:

### Single-Pile Nim Strategy Calculator

Being the simplest form of Nim, you only need to provide 4 pieces of information for single-pile Nim:

The first question, which is the same with all 3 calculators, is whether the person who moves last is the winner or the loser.

The next question is how many objects are used. While single-pile Nim is usually played down to 0, such as the game in Episode 8 of Scam School, there are games where you start at 0, and try and go up to a maximum amount, like in episode 80 of Scam School. This is why this is asked as the “maximum” or “limit”.

This is also why the third question asks whether the game is played down to 0 or up to the limit. Lastly, the final question asks about the range of the amount of objects that can be used per turn.

As an example, let's try using the calculator to analyze the match game from Scam School's 8th episode. The player who makes the last move is the loser, they're using 17 objects, playing down to 0, and up to 3 objects are allowed per turn, so the data would be entered as follows:

Click the Calculate Nim Strategy button below all the data, and you get this response in the box:
The rules for this particular version of the game of Nim are as follows:
* There are two players.
* The players alternate taking turns.
* The game starts out with 17 objects.
* On a given player's turn, they must remove anywhere from 1 to 3 objects.
* Neither player is allowed to remove 0 objects.
* The last person to make a move is the loser.

The Scam: Although seemingly fair, you can rig this game in your favor.

For this particular version of Nim, the other person should go first. This will ensure that you can always leave certain key numbers of objects on each turn that will guarantee your win.

The key numbers of objects you need to leave on each turn, in order to safely win the game, are as follows:

13
9
5
1 (of course)

Tips:

* You don't have to hit every key number. Just make sure you get to one of the above key numbers before the goal is reached, and you'll always be able to win the game from there.

* If it's decided that you must go first, and your opponent isn't wise to the ways of Nim, it's still possible for you to win. Only play small amounts of objects on your turns, until you get an opportunity to reach a key number.

* Instead of playing single-pile Nim with physical objects, you can often just state the numbers verbally, or even use a calculator.
This data can be copied to a text editor or word processor, where you can save the information for later. Note that various tips are given, and they are often different for particular settings.

Whenever you get a response, always read it carefully! Besides the particular goal numbers, it also mentions whether you or the other person should go first, and what to do if that's not possible. I've tried to make the tips as useful as possible, as well.

Try entering the data yourself for Scam School episode 80: The person who makes the last move is the winner, the limit is 31, the game is played up to the limit, and the number of objects used per turn is from 1 to 6. When you click the Calculate Nim Strategy button, note that the advice here is exactly the same advice (for the first round, anyway), as in the video (assuming you entered the information correctly)! There are even some extra tips that aren't given in the video.

### Multi-Pile Nim Strategy Calculator

The Multi-Pile Nim Strategy Calculator looks a little different than the single-pile version:

The first question, as before, determines whether standard or Misère Nim is being played.

The next question is a pull-down menu that lets you select from 3 to 9 piles. When you change this number, a number of boxes equal to your choice will appear below it. These boxes allow you to specify how many objects are in the individual piles.

One of the most basic versions of multi-pile nim is taught in episode 37 of Scam School. In this version, the person who removes the last object loses, there are 3 piles, and the piles consist of 3, 5, and 7 objects respectively. The data would be entered like this:

When you click the Calculate Nim Strategy button here, you might be surprised to find more safe positions than are listed in the Scam School video. In this particular case, the new moves are simply those that are 1 object different from the opening layout.

Just for fun, try using the Multi-Pile Nim Strategy Calculator to determine the best strategy for the Last Year in Marienbad version (it's Misère Nim), or to find out why the XKCD character in this comic reacts the way he does.

### Next Move?

Originally, I tried using the Multi-Pile Nim Strategy Calculator to play against online versions of Nim, such as Pearls Before Swine or Nim Master (Flash required for both). Unfortunately, I often found that the number of piles and/or the number of objects involved often made it too difficult to search through the list of safe positions quickly and effectively.

To solve that problem, I added the “Next Move?” calculator. It works pretty much the same as the Multi-Pile Nim Strategy Calculator, with just one added feature: A checkbox you mark if the arrangement in question is the first move. Many computer versions of Nim let you decide who goes first, so this will give you an appropriate recommendation. Here's how the “Next Move?” calculator appears:

As an example, I'll start a game of Pearls Before Swine, in which the last person to remove an object is always the loser. I see 3 piles, consisting of 3, 6, and 8 object as the opening layout. I enter this into the “Next Move?” calculator as follows:

Since this calculator is only concerned with looking 1 move ahead, the reponses are much briefer. The response I get from the above entry, after clicking the Calculate Next Move button was this:
Here are the plays you can make on this turn, in order to insure a win at the end:

3, 6, 5 (8-object pile: Remove 3)
Note that it gives you the layout numerically, but also tells you in plain language how many are removed, and from which pile.

Continuing to play this same game, I make the recommended move, and am now left with 3 piles of 3, 6, and 4 (after the other player's move). Updating this to reflect the new information (including the fact that this isn't the opening move), I get this response:
Here are the plays you can make on this turn, in order to insure a win at the end:

2, 6, 4 (3-object pile: Remove 1)
Needless to say, after a few more moves, I won this particular game.

### Uses

There are quite a few nice things about using these calculators.

First, if you want to understand how the strategy changes as the rules change, you can get a quick understanding here. If you have a favorite layout of, say, multi-pile Nim, and people after a few games are asking things like, “What if I go first?” or “What if we make the person who takes the last match a winner?”, you can be ready for such eventualities.

Working with the calculators can make the entire Secrets of Nim series easier to follow and understand.

Also, these calculators can help you learn a particular strategy by heart, as well. In multi-pile Nim, the same safe positions are safe in any game (with certain exceptions for Misère Nim and multiple 1-object piles). Using the “Next Move?” calculator frequently in the beginning will often make these moves very familiar.

Finally, you can use these calculators to create custom Nim variations (and learn to play them correctly). For example, what if you have a friend whose 37th birthday is coming up, and he has 4 kids. You could challenge him to a game of single-pile Nim that starts with 37 objects, where you're allowed to take up to 4 objects per turn. In this particular case, I suggest making it a Misère Nim, because the winning strategy can quickly become obvious (Why? Run it through the calculator and see for yourself).

Alternatively, what if his 4 kids are ages 4, 8, 10 and 14, respectively? You could play a game of multi-pile Nim against him, starting with piles of 4, 8, 10 and 14, and already know the best plays.

I hope you enjoy the Nim Strategy Calculator, and find it useful! If you do find it useful, please take the time to click on the ads on this page, or the calculator page.