Nim Strategy

Game theory has a lot of uses; it's not just for playing games. But today we're going to use it to play games.

Rules of Nim

"Nim" is a two-player game played with sticks. The sticks are divided into piles. The players alternate turns. On each player's turn they may remove any number of sticks from one of the piles, up to the number of sticks remaining in that pile; but they can only take from a single pile on a given turn.

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

How did I win that game? I followed an algorithm.

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

To illustrate the basic theoretical idea behind the Nim strategy, let's first look at a game called "21". There are 21 sticks in just one pile. The rules are: You can take one, two, or three sticks on your turn. Whoever takes the last stick (i.e. all of the remaining sticks at that point) wins.

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)

Then, go through each column and take the "parity" -- a 0 if there are an even number of 1s, or a 1 if there are an odd number of 1s. This is known as a "bitwise xor", and is also equivalent to adding each column mod 2, and many other descriptions. It is the "^" operator in C.

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.

0100  (4)
thus we've moved into the kernel. So that's what the computer would do.

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.

[back to problem session 3] [list of problem session notes] [main course page]