Nim Strategy

Rules of Nim

The goal is to take the last stick. Whoever takes the last stick wins.

So the goal is to make the other person clear out all but one pile, so you can take all the sticks in that last pile. Etc.

Let's play a game starting from the game state 3, 5, 8. You can go first. Use your "back" button or "Go" menu or something like that to get back here after you play.

Choose how many sticks to take from which pile by clicking on one of the Xs. Your click takes the clicked stick and all sticks to its right.

 1. XXX      (3 sticks)
 2. XXXXX    (5 sticks)
 3. XXXXXXXX (8 sticks)

(If you like, you can also play a full game, but try the above first.)

Computer game playing and a strategy for Nim

That is more obvious given this presentation on the web page, as opposed to my usual personal demonstration. In fact, I can't be sure while I'm writing this that "I" did win above; but I think I probably did. I've always won against my classes when presenting this, even though I've selected an initial position which is actually to your advantage -- you could force a win starting from that position. But you probably didn't, because it's complex enough that it's far from obvious how to do it. It requires a little analysis to formulate the algorithm.

First, some background

play it

If you play it a few times, you will probably figure out the strategy. The strategy is to leave the count at a multiple of four after your turn. Before reading further, please experiment with the strategy, and prove to yourself that it works.

We define the "kernel" of a game to be a set of game states including all winning states and such that if the state of the game is in the kernel, it is not possible to make a move which keeps it in the kernel, whereas if the state is not in the kernel, it IS possible to make a move which gets it into the kernel.

In other words, if I'm playing with a winning strategy based on my observation that a particular set is the kernel for the game, then when it's your move the game will be in a kernel state. Your move will necessarily take it out of the kernel. My move will restore it to a kernel state because this is always possible from a non-kernel state, whereas your move will always take it out because if I present you with a kernel state, you cannot keep it in the kernel. And eventually, I will move it to a kernel state which is the winning state, i.e. I will win.

Obviously, many games do not have a kernel.

The kernel of 21 = { 0, 4, 8, 12, 16, 20 }

That is, if it is your move and it is in a kernel state, you're going to lose (unless I make a mistake). On the other hand, if it is not in a kernel state when it is your move, then you can force a win, by moving it into a kernel state, and then I'm forced to move out of a kernel state, and then you can move it back into a kernel state, and so on, and eventually we get to a winning state.

How could this always be possible? Because that's the definition of a kernel. Many games do not have a kernel; there doesn't exist a set with the above property. However, the 21 game and Nim each have a kernel set. So you can describe a winning strategy by describing the kernel.

For Nim, the kernel is most easily expressed in the following computational way. (And we can't express the game states as succinctly as we did in "21".)

Take all the piles' contents, and write them out in binary.
Example: Suppose the piles are 3, 7, 9
(it doesn't matter which pile is which, just the set of numbers, order unimportant)

0011
0111
1001

The resulting value is 1101, thus this state is not in the kernel.
The rule is: in the kernel === all zeroes in parity computation (bitwise xor)

Note that the winning state is all zeroes, so the parity computation yields all zeroes, thus it is in the kernel (as it must be, for that to be a correct kernel for the game).

Suppose here we take 5 from the largest pile.

0011
0111
0100  (4)
====
0000

Now, the player has to adjust one of those piles. I claim that no matter what they do, they will be flipping some zeroes and ones, in one pile (row) only; thus they will be turning some of the bottom line's zeroes into ones.

To justify this, note that only the exact pattern in each row represents that exact number in binary. Any other number has some of the ones and zeroes different -- or it would be the same number.

If they could take some from each of two rows, then they could turn a one to a zero and another one in the same column to a zero, thus keeping the parity computation at all zeroes. But you're only allowed to take from one pile at a time.

It's harder to see that you can always go from a non-kernel state (as we've defined the kernel) to a kernel one. Basically, you do an xor of the result into a pile which has a one in the column of the left-most column with a one in the result. That's not how a typical nim-playing program's computer strategy does it, but that's how you'd come up with a proof that there always must exist a move to bring it into the kernel.

Remember that we have those two aspects of the kernel: you can get into it from out of it, but you can't stay in it.

Also note that in a sense, this bitwise xor thing is arbitrary. It defines a set of game states (the ones where the result is all zeroes). Then you can analyze that set and see if it is in fact a kernel for the game. There may be other ways to describe this set which don't involve the same computations.

However, it is impossible for there to be more than one kernel for a game, so this set is THE kernel for Nim. Any other correct specification of Nim game-playing strategy will identify the same set as the kernel, even if the description reads quite differently.