Here is a perfect strategy for Nim, to be discussed in lecture on about September 27.
Contents of this web page:
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 history 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.)
Well, that's obvious, because "I" was a computer. It's less obvious in person. 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.
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 two players alternate turns. 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 this "21" game until you can always win against the computer.
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. That is, at the end of your turn, if the number of sticks is 0, 4, 8, 12, 16, or 20, and you play perfectly for the rest of the game too, then you're going to win.
Before reading further, please experiment with the above strategy, and prove to yourself that it works.
We define the "kernel" of a game to be a set of game states which includes all winning states and which has the property 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.
That is to say, 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. If we additionally have a bound on the duration of the game (in the game 21, since each move takes at least one stick, the duration is at most 21 turns), then eventually I will move it to a kernel state which is a winning state, i.e. I will win.
Obviously, many games do not have a "kernel" in this sense. Games which do have a kernel are, in a sense, trivial.
The kernel of the 21 game = { 0, 4, 8, 12, 16, 20 }
So, 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.
To experiment with this further, you can play the game from the middle, manually editing the URL as desired so as to start from any game position you want to experiment with. (In the URL of the form "http://course.dgp.toronto.edu/cgi-bin/21?20", the "21" is the program name; then there's a question mark as separator; then there's the number of sticks remaining in the pile when it's the computer's move.)
The easiest way to express the set of winning states for the game of Nim involves the logical "exclusive or" operator, which can be summarized in the following table, using 0 for "false" and 1 for "true":
| a | b | a XOR b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
This is equal to the "parity" of the operands: add together the operands and see whether the result is even or odd. If the result is even, i.e. we have an even number of ones, then the result of the XOR is zero. If the result is odd, i.e. we have an odd number of ones, then the result of the XOR is 1. So the oddness of the result is equal to the oddness of the sum; we're just checking odd versus even here. That's the "exclusive or" (XOR) operator.
We can perform the "exclusive or" operation on multi-bit numbers (numbers in base two with more than one digit) by doing it "bitwise": each corresponding bit is xored, in parallel.
Call the set of all game states which xor to zero "G" (for "goal").
In the following proofs we will use these basic facts about the bitwise xor operator, written here as "^":
Theorem 1: If the game state is in G, any valid move necessarily takes it out
of G.
Proof: The move involves changing the value of one of the piles. Since the
xor of all of the piles was formerly zero, it is now 0^oldvalue^newvalue =
oldvalue^newvalue, which isn't zero because oldvalue != newvalue (else it's
not a valid move).
Theorem 2: If the game state is not in G, there exists a valid move which yields a game state which is in G.
Proof:
Compute a valid winning move as follows.
Xor together all the pile
values to get a value we call "b".
Since the game state is not in G, we know that b != 0
(that's the definition of G).
Now find a pile number i such that
gamestate[i] ^ b < gamestate[i].
The move is to replace gamestate[i] with
gamestate[i]^b, i.e. take (gamestate[i] - (gamestate[i]^b)) sticks.
This yields a big xor of zero, so we're in G.
It remains to be proved that such a pile ("i") exists.
Look at the binary digits
in b, and consider the column position of the leftmost 1 (call it the ith
digit, i.e. the value 2**i).
There must be a
game pile which has a 1 in position i (since the xor is bitwise -- this 1
must have come from somewhere).
If you xor b with that pile, you necessarily
get a lesser value: All the digits to the left of i will remain unchanged
(since they are zero in b); the i digit will change from 1 to 0; and digits to
the right of i may or may not change.
Since the most-significant digit which
changes is digit #i, and it changes from a 1 to a 0, the overall number has
decreased, so this is a valid move.
Theorem 3: The game has a finite upper bound on its duration.
Proof: Since each move takes at least one stick, the maximum number of moves
in the game is the sum of the initial numbers of sticks in each pile.
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 it's described quite differently.
If the result of this big xor is zero when it's our move, then the user is on the winning track and we can't make a winning move. However, the user will hopefully make a mistake later so our goal is to prolong the game as much as possible. Thus in this case we take one stick from any suitable pile. (This need not be random; any algorithm yielding a legal move of one stick is acceptable.)
If the result of the xor is non-zero, then we want to make a move which makes the xor of all of the piles in the new game state be zero. This is a winning move, and if we continue to follow this strategy we are guaranteed to win.
Call this big xor result "b". For each pile, consider changing it to gamestate[i]^b. E.g. if a pile has three sticks, which is 00011 in binary, and the big xor is 01001, then we'll flip both of those two bits to get 01010. This will change the overall xor to be all zeroes and thus it will be a winning move.
However, if we make the move implied by the previous paragraph, then our opponent will accuse us of cheating! That move involves changing a pile containing three sticks to a pile containing ten sticks. That's not a legal move.
So what we have to do is:
After computing the big xor,
we have to go through all of the piles a second time,
and for each pile "i", we check whether changing
the value from gamestate[i] to (gamestate[i] ^ b) would be a legal move.
It's a legal move iff
it results in a decrease in the number of sticks.
Note that the move is not (gamestate[i] ^ b), but rather, taking
(gamestate[i] - (gamestate[i] ^ b)) sticks from pile i.
If you understand the algorithm, you should be able to play against the computer at http://course.dgp.toronto.edu/cgi-bin/nim and always win, except when by random chance it gives you a winning state in the first place, and except for when you make a mistake in your calculations (in which case you can use your web browser's "back" button!).
Important note: There are no special cases. The above algorithm correctly deals with the case of only two piles being left, only one pile left, etc.