I.3: Introduction to Nim

Nim is the most famous Simple game. Variants of it have been played for centuries and it is perhaps the first significantly interesting example of a solved game (Charles L. Bouton found out which positions were P-positions, and what winning moves would be for every N-position back in 1901, although he did not use these terms.).

In Nim, there are some piles of objects, and on your turn, you may remove any number (at least one) of objects from a single pile. Sometimes people call this game Nim even under misère play, but we will take Nim to have normal play (and hence a Simple game) where you lose when there are no objects for you to take on your turn.

Let’s analyze some small Nim positions to see how they should be played/which ones are P-positions and which ones are N-positions. I’ll list pile sizes in rectangular brackets.

[] (the position with no piles) or [0] (the position with one “pile” of size zero) is a P-position. If you’re faced with this at some point, you’ve already lost to the person who moved Previously, as per normal-play rules.

The single-pile positions [1],[2],[3],[4],… are all N-positions. If you’re Next to move, and faced with one of these, take the whole pile. You’ll leave your opponent with [] and they’ll lose.

Consider a two-pile position where the piles are equal, like [1,1], or [2,2], etc. In this case, you’re in trouble; it’s kind of like Kayles. Whatever moves you make in one pile can be mirrored by your opponent, so these are P-positions.

For a two-pile position where the piles are unequal, like [1,2], or [5,789]. You’re in good shape, because you can make the piles equal. Once you do, your opponent has just been handed a losing situation (because you’ll then go on to mirror their moves). Thus, these are N-positions.

Before considering bigger situations in Nim, I want to point out some more general facts about Simple games. The P-positions are the ones where you can only move to an N-position. Why? First assume you’re in a P-position. If you could move to another P-position, then by definition you could give you opponent a position where they had no winning strategy, but if you could do that, then doing so would win you the game! Therefore, you can’t possibly move to another P-position. Conversely, if all moves are to N-positions, then you’re forced to give your opponent the win, so you must be in a P-position. More pithily: If you’re losing a Simple game, all moves are bad, and if all moves are bad, you’re losing.

The contrapositive to the above statement is If you can move to a P-position, you must be in an N-position., so you don’t have to check full strategies if you have some table of what types of positions things are. Relatedly, From an N-position, the winning moves are the moves to P-positions. If you have control of the game, you have to make moves that don’t yield control to your opponent if you want to ensure you win.

Now let’s look at some three-pile positions in Nim. It doesn’t take too much work to see that positions where 2 pile sizes are repeated (like [2,5,5] or [4,4,4] or [1,1,7]…) are N-positions; in such a case, just take a pile that leaves two equal piles so it becomes a P-position.

What about the smallest three-pile position that’s not like that: [1,2,3]? If you kill a whole pile, you leave two unequal piles, so that you’ve handed your opponent an N-position. If you don’t kill a whole pile, you leave a pair of equal piles plus a third pile, which we just said was an N-position too! Since you can only move to N-positions, you must be in a P-position.

You can keep expanding this table by brute force: since [1,2,4],[1,3,4],[2,3,4],[1,2,5],… can be turned into [1,2,3], they must all be N-positions, etc. One would hope that there’s some pattern, some relatively quick way to just look at a three-pile Nim position and figure out whether it’s an N-position or a P-position. If we had such a method, then you could 1. test if you’re in an N-position, and if you are, 2. test all of the positions you can get to in one move to see which one(s) is/are P-position(s), so you know which is the winning move.

However, I’ll tell you right now: It’s really hard to come up with a method that works for all three pile positions on your own (but if you somehow do, you’ll probably be able to figure out how to handle all Nim positions, not just three-pile ones).

I know many of you have seen this before, but if you haven’t, try and play some three pile (or more!) Nim/make some tables to see if you can notice any patterns. Even if you don’t get a complete rule, maybe you can get some interesting general results. For instance, here’s one: if all three pile sizes are odd, it’s an N position!

Advertisements

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