Help me understand the game of Nim

The Game Room
1

Nim.

The game goes like this: create any number of piles of objects with any number of objects in each pile. You could have a pile of 3 red objects, a second pile of four blue objects, and a third pile of five green objects, for example. (I’ve color-coded the objects to make the game easier to understand).

On your turn, remove any number of objects, with two rules: you must remove at least one object, and all the objects you remove must be from the same pile.

If you remove the last object, you win.

The game is solved. Convert the number of objects in each pile into a binary number. Count the total number of 1’s in each place across all piles (in the sample piles above, there’s a 11 pile, a 100 pile, and a 101 pile, leading to two 1’s in the fours place, one 1 in the two’s place, and two 1s in the one’s place). If there are an even number of 1s in each place, then it’s a “winning position,” with “winning position” defined as “if you end your turn like this and play right, you’re guaranteed to win.” If there are an odd number of 1s in any place, it’s a losing position, with “losing position” defined as “if you end your turn like this, your opponent has a chance to win.”

The most basic winning position is two piles with 1 in each pile. Converted to binary, there are two 1s in the one’s place, which is an even number. If you end your turn with this position, then your opponent must take 1 cube (since they’re in two different piles), and you can then take the other cube and win.

I understand that it’s solved, and I understand how to determine whether any position is a winning position or a losing position.

What I don’t get is why. Why base 2 instead of base 3? Why must it be in pairs?

I feel like I’m on the verge of understanding it, but I don’t quite get it. If someone can explain it narratively to me–that is, without using fancy symbology, but rather laying it out in layman’s terms–I’d be very grateful.

2

Hmm, Nim really is the X game I played in elementary school. We sort of proved the binary trick is a winning strategy in this thread.

Basically, the binary trick allows you to define a winning position and a losing position.
You want to make a move that leaves you with a winning position.
There is always a legal move to convert a losing position to a winning position.
There is never a legal move to convert a winning position to another winning position.

3

Right, and I get all that. When the IMHO thread died out, I figured I’d post the mathematical/logical question here in GQ where it might get some more traction :). (I definitely appreciate all y’all did for me in that thread, btw).

My question is why, in defining a winning position and a losing position, you’d use binary, and specifically why you’d look for pairs of 1s in each place value in order to find the winning positions.

4

Because its a two player game and there are two main states: “Winning State” and “Losing State.”
You can probably prove the solution with induction.

5

Here’s one way to think about what you’re doing; maybe it’ll help. Don’t think about a move as “taking away pieces”; think about it as doing choosing a number M and a row, and replacing the value in that row with the bitwise XOR of M and its current value.

[If you don’t know what the XOR is, this is just the operation you’re doing to determine whether a position is winning. You write the numbers in binary and add the number of 1s in each position, modulo 2. The important property of the XOR is that it’s like addition: commutative and associative.]

The method you use to determine whether a position is winning or not is to take the XOR of the numbers of pieces in each row: so if there are three rows, with (a,b,c) pieces, then you compute P = a XOR b XOR c; a move is a winning move if the result P is 0. (P stands for “parity.”) So a move which replaces, say, b with b XOR M, takes a position from P = a XOR b XOR c to P’ = a XOR (b XOR M) XOR c = P XOR M.

In particular, since you have to take at least one piece in each move, M can’t be zero. So if you start at P=0 then P’ must be nonzero. Now if P’ is nonzero then you can just choose M=P’ to make the next value P’’=0 again. Hence I just choose, at each move, the same number M that my opponent used in his previous move.

[There’s a complication: we aren’t allowed to choose M arbitrarily. Since we’re actually taking away pieces, the rules also require that the resulting number (b XOR M, in the example move above) must be smaller than the initial number b. However, if you make sure that you choose a row which has a 1 bit in the same place as the highest 1 bit of M then the XOR will always be smaller, and such a row must exist, so you can always do this.]
… That may sound like gibberish, depending on your background. Maybe an example will help. Start with the traditional starting state (a,b,c)=(3,4,5); in binary that’s (11,100,101). The parity is P=11 XOR 100 XOR 101=10, so I want to take M=10 as well. I look for a row with a 1 in the 10s place; that’s row 1, with a=11. I compute a XOR M = 11 XOR 10 = 1, so I want to leave 1 piece in row 1; hence I take away two of them, leaving the state (1,100,101) with parity 0.

6

I’m not trying to be a jerk, but what I’m asking for is an explanation that doesn’t use terms like XOR or modulo. I’ve already read such explanations on the Wikipedia page, and while I can just barely follow them, I can’t grasp them.

I’m looking for something like this:

I’ve spent the last week teaching the game to very smart third-graders, and I want to explain to them tomorrow why the winning strategy works. I can’t do that if I’m using XOR and modulo; I’d like to find an explanation that I can give using terms like “doubles,” “equal,” “non-equal,” and “piles.”

They have studied binary, so I can talk to them about 1s in various positions. But anything more complex than that is not going to work.

7

We use base 2 because it works. If you’d like, we can go through the proof that it works, but given that it does work, what more needs to be said?

8

Moved to the Game Room.

Colibri
General Questions Moderator

9

Actually, a simple way to prove that it works: You start with the basic “If there are two piles of one each at the end of your turn, you will win”. So that’s a winning position. Then, you say that any position where you can force your way into a winning position is itself a winning position. Now you’ve got a whole big set of winning positions. Then it’s just a matter of figuring out what they have in common, so you can recognize the winning positions.

To show this to your class: Show them the one-and-one winning position, and ask the students for their move. They’ll quickly agree that they can’t win. Then show them a position one move further back, and ask them for a move, and no matter what they pick, show them that you can make a move that will turn it into the one-and-one position. Continue for a few moves. Once you’ve established that you can always win the examples you’re showing them, then describe your method for always winning. And once you’ve taught them the method, then show them why it works.

10

Yeah, and that’s what I did today: I showed them the binary breakdown for every winning position for a 3-4-5 game. It’s that last step–why it works–that I’m having trouble with. Why is 1-4-5 going to be a winning condition, when 1-3-4 is not? (I mean, with this particular example, I can show that 1-3-4 can be reduced to 1-2-3, but in general, why do the piles with an even number of 1s in each place value end up being winning conditions?)

11

I would just say that an even number of 1s in each place is stable. You can show that from that condition you can always get back to it no matter what your opponent plays. And as long as you get back to it you will eventually end up with two even piles. And from there it should be obvious you can’t lose.

An odd number of 1s in each place is always one move away from an even number, which as shown is a stable winning position.

12

I’m not sure which parts of the arguments presented so far are too hard; can you be more specific? What steps in the description below are too hard, or incomplete, or insufficiently intuitive? If it’s a problem with terminology (XOR, modulo, parity, …) there’s probably a more friendly term that could be used.

The first step is to talk about two categories of positions: “winning” and “losing” positions. The important property of these positions is that any move from a winning position gives a losing position, and for any losing position there is at least one move to a winning position (or to just win). You can define these classes of positions for any two-person alternating-move game; the only difficult game-specific part is in deciding which positions are of which type.

Of course in most real games this part is very difficult. Nim is an exception in having a simple rule which categorizes all positions.

In Nim you can define the “zero-parity” (“all-1s-even”) and “nonzero-parity” (“not-all-1s-even”) position, as you describe, by counting 1s in each position in the binary form for each row count. It is not hard to see that any move from a zero-parity state gives a nonzero-parity state and that there is a move from any nonzero-parity state to a zero-parity state.

Notice the similarity between the zero-parity/nonzero-parity positions and the winning/losing position definitions. This isn’t yet done, though, because we haven’t talked about what happens at the end. In Nim, you win if you take the last piece; this is a move from a nonzero-parity position to a zero-parity position. So this means that in fact the zero-parity positions are winning positions. It is also easy to see that the game must eventually end, since the number of pieces remaining decreases with each move.

So as long as the board is in a nonzero-parity state just before I move, I can force it into a zero-parity state, and then my opponent has no choice but to make it nonzero-parity. Since the game win state has zero parity, this will let me win.

13

:That right there is what I’m looking for, I think. Once we get to a set of pairs, whatever one player removes ruins the “set of pairs” approach, so whatever they remove, I can remove a similar thing from somewhere else. If they look at a pile of 6 and remove 3, then the 4-and-2 becomes a 2-and-1, so in essence they changed a 4 to a 1, so I need to find another 4 and change it to a 1.

14

You’re almost there. 1-4-5 is a winning condition because it can be reduced to a winning position. If you move into an even-parity position, then you’ll be able to move into an even-parity position the next move, too, and the one after that, and so on, until the game ends. And your opponent will never be able to move into such a position. And the game will end eventually with someone winning, and the last move is a move into an even-parity position, which you’re doing but your opponent isn’t, and therefore the winner will be you.

15

It might be easier to consider the following variant on Nim first:

The game is played on a rectangular grid filled with on/off switches, in some configuration.

On any player’s turn, they A) must flip some switch from on to off, and B) may also flip any additional switches they like, so long as they are to the right of the switch from part A.

If any player is unable to make a move (because all the switches have been turned off), they lose.

A common strategy in “Whoever can’t move loses” games is to try something like “Well, I’ll just duplicate what the other guy does”.

Alas, in this game, no one could ever hope to exactly duplicate the move just made. The leftmost switch flipped from on to off could not be the leftmost switch flipped on the next turn.

However, one could try flipping the corresponding switches in a different row. This will work so long as there’s another row with an on switch in the same column as the leftmost on switch just flipped.

This brings us to the idea of considering whether the on switches in a column can be paired off. That is, the idea of considering whether all the columns have an even number of switches.

If every column has an even number of on switches, then any move you make will upset that balance.

On the other hand, once the balance is upset, it is easy to restore: find the leftmost column with an odd number of on switches. Find some on switch in that column. Flip it to off (fixing that column), and do whatever’s necessary in the rest of that row to fix the other columns.

Thus, any player who puts the board into balance knows their opponent will put it out of balance. And they can put it back in balance again and their opponent will have to put it out of balance again. And so on and so on till eventually the game ends. But since the game ends in a balanced state, the balancing player must be the one who makes the last move and wins.

Thus, we’ve completely figured out a winning strategy for this game.

Now, I said this game was a variant on Nim. But as you no doubt realize by now, I lied to you: this game is in fact exactly the same as Nim. Each row represents the size of a pile in binary notation, and the allowed moves are precisely to reduce the size of one pile on each turn.

16

So the pairing off arises because of the “I’m going to try to duplicate what my opponent does” cadence.

And why base 2? Well, we could set up a similar game representing piles with digits in any base, with the rule “On any move, you must lower a digit, and may change arbitrarily the digits on its right”, and keeping track of balance in the sense of whether all the columns have an even number of positive (i.e., lowerable) digits.

But only in base 2 do we have the guarantee that reducing a positive digit changes it from positive to zero, thus upsetting the balance on that column. So only from our base 2 representation do we have the guarantee that an opponent handed a balanced board will return an unbalanced board.

Alternatively, we could keep track of balance in the sense of whether the digits in each column add up to a multiple of the base. Then we have the guarantee that a balanced board turns unbalanced on the next move, but we no longer have the guarantee that an unbalanced column can be fixed by lowering a digit within it (as the deficit may be too large to be fixed by any one digit’s lowering; for example, consider a column with two 1s and nothing else, in base larger than 2).

In short, the reason we use base 2 is, as Chronos said, because it works. But the above may shed some light on that.

17

Wait–today I got it, I think.

It’s gotta be base 2, because each place value in base 2 is comprised of all the other place values added together, plus 1. This isn’t true of other place values.

So you’re in a situation with 1 or more place values with an odd number of 1s in it. Here’s what you do: you take the largest odd-1, and you break it down such that the remaining pieces pair with all the other odd-1s, and you subtract whatever’s left over.

Imagine a board with four piles: 1/2/4/16. You’ve got an odd 1 in the ones, twos, fours, and sixteens. So you break the 16 pile down such that you have a 1, a 2, and a 4, and you subtract the rest: you remove 9 from the 16 pile, leaving 7 behind. The 7 contains a pair for the 1, the 2, and the 4. 1/2/4/7, therefore, is a winning position.

If you analyze it in base 3, it’s much harder to see where the pairs are. The situation I described above in binary is 1/10/100/10000, and you rearrange it to become 1/10/100/111. In base 3, it’s 1/2/11/121, and you rearrange it to become 01/02/11/21. Much less clear.

I think I’ve got it now, even if that doesn’t make sense to anyone else!

18

That’s right!

There is also a general theory of games which works as follows: we can assign a value to any position in any game (of the sort we are discussing) by the recursive rule “The value associated to any position is the smallest ordinal number not associated to any position reachable from it in one move”. Then, in a suitable sense, any game is equivalent to the Nim game with a single pile whose size is the corresponding value.

In particular, the values of two-pile Nim games are shown in this table (which can be constructed by the aforementioned rule, which in this context states that each cell contains the smallest ordinal number not found anywhere directly above it or to its left). And any multi-pile Nim game can be reduced to an equivalent single-pile Nim game by repeatedly reducing two piles within it to one.

This table tells us everything there is to know about analyzing Nim games…

Except it also turns out there’s an easier way to describe the function just tabulated. And that’s via base 2 addition-without-carries (aka, bitwise XOR).

So bitwise XOR can be seen as not the fundamental phenomenon, but an emergent one, arising from our recursive rule for constructing the table.

But, alas, I don’t know any very nice proof for why the values of the table happen to match the values given by bitwise XOR, except by sterile inductions or rehashing of the arguments above on how to use bitwise XOR to yield a winning strategy for Nim. It would be nice if this last observation (that the recursive rule defining the table happens to create bitwise XOR) could be made cleaner somehow.

19

IBM Research has posted its latest puzzle.