As an introduction to a mathematical game, and how you
can use a little bit of math to form a description of the game that
allows you to determine the optimal strategy, I'm going to talk a bit about Nim.
Nim is a simple two-player turn-taking game. The idea is you've got a collection of piles of rocks. The standard
terminology calls each pile a heap. Each turn, a player can take any number of rocks from any single heap.
In classic Nim, whoever takes the last rock loses. But we're going to start with an easier to analyze variant, where
whoever takes the last rock wins.
Let's look at an example game. We've got two players, which we'll
call Adam and Bill. We've got 5 piles of rocks, which have 6, 2, 3, 7, and 3
rocks each. Adam goes first.
| Player | Move | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 6 | 2 | 3 | 7 | 3 | ||
| Adam | 3 from 4 | 6 | 2 | 3 | 4 | 3 |
| Bill | 1 from 5 | 6 | 2 | 3 | 4 | 2 |
| Adam | 2 from 5 | 6 | 2 | 3 | 4 | 0 |
| Bill | 2 from 2 | 6 | 0 | 3 | 4 | 0 |
| Adam | 3 from 1 | 3 | 0 | 3 | 4 | 0 |
| Bill | 4 from 4 | 3 | 0 | 3 | 0 | 0 |
| Adam | 2 from 1 | 1 | 0 | 3 | 0 | 0 |
| Bill | 2 from 3 | 1 | 0 | 1 | 0 | 0 |
| Adam | 1 from 3 | 1 | 0 | 0 | 0 | 0 |
| Bill | 1 from 1 | 0 | 0 | 9 | 0 | 0 |
So Bill wins.
Now, mathematically, what can we say about the game of Nim?
Nim has some really interesting properties. It's a sort of canonical game: there are a wide class of games that are all ultimately reduceable to equivalent games of Nim. Better, if both players are perfect, Nim is completely deterministic: you can tell which player will win before the game even starts.
The easiest way to understand what the optimal strategy is, and to see why the winner is predetermined, is to look at nimbers. Nimbers are an alternative construction of a field of numbers which capture the basic behavior of Nim. Using nimbers, you can add up the number of rocks in the heaps in a way that tells you what the key properties of the heaps are. It's called the Nim-sum. For computer scientists, the nim-sum is easy: it's the bitwise exclusive or of the number of rocks in each heap. For non-CS folk, I'll
describe it in more detail below.
The idea is that you always want to make the nim-sum be zero. The first player whose move makes the nim-sum be zero is guaranteed to win. Why?
The key to Nim is understanding the way how the nim-sum works, and what
that means. So let's look in a bit more detail at the nim-sum. What it does is
decompose each number into a sum of powers of two. Then any time there's two
copies of a single number, they can be canceled with one another. For example,
let's look at 11+19. 11 = 1 + 2 + 8; 19 = 1 + 2 + 16. So nim-summed together,
we get 1+2+8+1+2+16. There are two 1s, so we cancel them; and there are two
2s, so we cancel them, leaving us with 8+16. So the nim-sum of 11+19 is
24.
The main property of the nim-sum is that it describes cancellation. If the
nim-sum of the heaps is zero before your move, then if you can make a move taking N rocks from a heap, then that means that there must be some
way that I can also take N rocks from a heap. Because each time
you make a move, removing rocks from a heap, the new nim-sum must include a move where I can remove the same number of rocks; if there weren't,
then the nim-sum wouldn't have been 0.
Look at an example. If the nim-sum is 0, and you take 11 stones, the new nim-sum is going to be 11. If it weren't, then the nim-sum before your move
wouldn't have been zero.
So no matter what you do, I've got a move left that makes the nim-sum be zero. So I'm going to win.
Let's go back and look at our example game again, but we'll add a column for the nim-sum of the heaps.
| Player | Move | 1 | 2 | 3 | 4 | 5 | Nim-Sum |
|---|---|---|---|---|---|---|---|
| 6 | 2 | 3 | 7 | 3 | 3 | ||
| Adam | 3 from 4 | 6 | 2 | 3 | 4 | 3 | 0 |
| Bill | 1 from 5 | 6 | 2 | 3 | 4 | 2 | 1 |
| Adam | 2 from 5 | 6 | 2 | 3 | 4 | 0 | 3 |
| Bill | 2 from 2 | 6 | 0 | 3 | 4 | 0 | 1 |
| Adam | 3 from 1 | 3 | 0 | 3 | 4 | 0 | 4 |
| Bill | 4 from 4 | 3 | 0 | 3 | 0 | 0 | 0 |
| Adam | 2 from 1 | 1 | 0 | 3 | 0 | 0 | 2 |
| Bill | 2 from 3 | 1 | 0 | 1 | 0 | 0 | 0 |
| Adam | 1 from 3 | 1 | 0 | 0 | 0 | 0 | 1 |
| Bill | 1 from 1 | 0 | 0 | 9 | 0 | 0 | 0 |
We can see that neither player played well at all. After his first move, Adam should have had the game locked up:
he made the nim-sum be zero. If he'd just kept it there, he'd have won. But he screwed it up. Then, on the 6th move,
Bill had a zero nim-sum - he could have guaranteed a win if he'd played properly. How should it have gone? If
we're playing to pick up the last rock, something like this:
| Player | Move | 1 | 2 | 3 | 4 | 5 | Nim-Sum |
|---|---|---|---|---|---|---|---|
| 6 | 2 | 3 | 7 | 3 | 3 | ||
| Adam | 3 from 4 | 6 | 2 | 3 | 4 | 3 | 0 |
| Bill | 1 from 5 | 6 | 2 | 3 | 4 | 2 | 1 |
| Adam | 1 from 3 | 6 | 2 | 2 | 4 | 2 | 0 |
| Bill | 2 from 2 | 6 | 0 | 2 | 4 | 2 | 2 |
| Adam | 2 from 5 | 6 | 0 | 2 | 4 | 0 | 0 |
| Bill | 4 from 4 | 3 | 0 | 2 | 0 | 0 | 1 |
| Adam | 1 from 1 | 2 | 0 | 2 | 0 | 0 | 0 |
| Bill | 2 from 3 | 2 | 0 | 0 | 0 | 0 | 1 |
| Adam | 2 from 1 | 0 | 0 | 0 | 0 | 0 | 0 |
Once Adam got a nim-sum of zero, he just cancels out every move that Bill makes until the game is over.
Now, let's pull a switch, and look at the classic form of Nim, where whoever takes the last rock
loses. Basically, you do the same thing: play for nim-sum of zero - up until you get
to the point where making your move will leave no heap with more than one stone. Then you make the move
that leaves an odd number of heaps with one stone each. So in the example game above, Adam would play the same way up to his last move. Then he'd only take one stone - leaving one heap with one stone, forcing Bill
to take last. That's a trivial example of the winning strategy. Let's look at a slightly more interesting one.
| Player | Move | 1 | 2 | 3 | 4 | Nim-Sum |
|---|---|---|---|---|---|---|
| 4 | 2 | 4 | 5 | 7 | ||
| Adam | 3 from 4 | 4 | 2 | 4 | 2 | 0 |
| Bill | 2 from 3 | 4 | 2 | 1 | 2 | 5 |
| Adam | 3 from 1 | 1 | 2 | 1 | 2 | 0 |
| Bill | 1 from 4 | 1 | 2 | 1 | 1 | 3 |
| Adam | 2 from 2 | 1 | 0 | 1 | 1 |
In the last move shown, if Adam had make the nim-sum zero, there would
have been an even number of single-rock heaps left. So instead, he takes 2 from heap two. And
that's pretty much it: there's nothing Bill can do. Once Adam got the nim-sum to zero, there
was nothing Bill could ever do.
So what about getting the nim-sum to zero? If the initial nim-sum is zero, then there is absolutely no way for
the first player to win unless the second player makes a mistake. If the initial nim-sum is not zero, then
the first player can always make it be zero in one move; and that means that the first player must win.
- Log in to post comments
Ah, this brings back memories! Other than the pile of matchboxes for playing tic-tac-toe, the first computer I was involved with was one I and a friend built in high school, 1964-1965. It played the first version of the game of NIM. Logic was a large number of BPO 3000 relay stacks, the FSM was implemented in 30 or so 32 position rotary wafers, and the PC was a stepping motor whose shaft connected the wafers. It won too. Unfortunately some jealous soul trashed it the night before show-and-tell. We never did find out who.
Looks like a typo with the 9 in heap 3 of the first game (and in subsequent copies of that table).
Sorry for the double comment. When analyzing the first game, you say, "Then, on the 6th move, Bill had a zero nim-sum - he could have guaranteed a win if he'd played properly." It looks like he did play according to the proper strategy and went on to win the game from that point. Maybe I'm confused about whether we're going by the last-stone-equals-win versus last-stone-equals-loss rules. This is the first time I've seen Nim so maybe (probably?) I'm confused.
It would be cool if you write about the game of Go (http://en.wikipedia.org/wiki/Go_(board_game)).
I think "take the last rock to win" is the standard winning condition, because "you lose if there is no move for you to make" is also the standard. So I think you got that bit backwards.
No, the standard approach for most of these types of games are "the person to take the last object loses".
One quibble:
That's actually not correct. A simple example can be seen by looking at two piles of 12 stones each; the nimsum of 12 and 12 is 0, but the nimsum of 12 and 1 is 13.
What is correct is this:
1) If you start with nim-sum 0, any possible move is going to leave you with a non-zero nim-sum, and
2) If you start with a non-zero nim-sum, there is a move that will get you down to a zero nim-sum. (Depending on configuration, there may be more than one, but there is always at least one)
Both these properties follow pretty easily from the facts that nim-sum is commutative and associative, and that the nimsum of a and b is 0 if and only if a equals b. (Well, I suppose that to prove 2, you also need to do some messing about with the binary representation to show that there must be some pile you can remove the appropriate things from)
Note that you can also treat nim as a specific case of a more general class of two-player games played by taking turns moving a token around on a directed acyclic graph, where you lose if you move the token to a sink node.
Your strategie seem suspicious to me, or there is something I haven't understood I what you explain. you said:
If the nim-sum of the heaps is zero before your move, then if you can make a move taking N rocks from a heap, then that means that there must be some way that I can also take N rocks from a heap.
Well, With four heap I could have
7 4 2 1
with a zero nim-sum. Then if I remove 7 from heap 1, nothing can be done to remove 7 form anyother heap, but removing 1 from the heap 2 make the nim-sum zero again.
In the same way, if we go from the same position, and remove 3 from heap 1, we have:
4 4 2 1
then the correct anwser is not to remove 3 from heap 2: it would lead to
4 1 2 1
with a nim-sum of 6, the correct awnser is to remove 1 from heap 3:
4 4 1 1
with an obvious nim-sum of 0
I still disagree with Mobyseven:
http://en.wikipedia.org/wiki/Nim
says pretty clearly that in "normal play" the person who makes the last move (takes the last object) wins, and most games of this type are played this way, although Nim itself is often played "misere" in which the person who makes the last move loses.
So MarkCC was right to say that Nim is usually played the other way around; I then attempted to "incorrect" him; but Mobyseven is also wrong to claim that most of these types of games are played misere. For most non-Nim games it's an unusual variant that's played this way.
Joshua:
When wikipedia uses the term "normal play", they're not saying that "normally, games are played this way". They're using a mathematical term: normal play is a game theoretic term; and you can see why it's called normal play in Nim: the normal play has a straightforward, consistent strategy all the way through the game; the misere play (that is, the standard Nim play) requires a strange strategy shift at the end.
-Mark
One more minor typo - in the third table, showing the optimal play heap 1 mysteriously changes from 6 stones to 3 stones about 6 moves in, causing causing Adam to move 1 stone instead of 4.
Anonymous, Mark said to cancel out the moves (keep the nimsum at zero), not to remove the same number. Your examples to help to illustrate the difference though.
If before your move, there are 15, 9, 6, stones (in binary 1111,1001,0110), which has nim-sum (15^9^6 == 0), and you take the 15, how can I makes nim-sum 0 again ?
Dooh, sorry, I my brain was not working. You could just take 3 out of the 9 to make it 6,6 and nim-sum is zero again :). I made the same mistake as anonymous.
Thanks for this. There's an online 1-player Nim game at gamedesign.jp. It is the math-normal version; the player wins upon taking the last object. Not knowing anything about nimbers, I had figured out that I should leave two stacks with equal numbers, but hadn't managed to generalize that to the entire multi-stack game. Just had to play opportunistically.
Of course, knowing the key has taken all the fun out of it (player always goes first on that version), but now I can beat hell out of my friends when we play with quarters. At least until they figure out that I'm hustling them.
I remember programming a simpler version of Nim on a Commodore PET back in high school. I was using the version published (IIRC) by Martin Gardner in Scientific American, with only one pile (and using toothpicks instead of rocks). It's interesting to see how the game generalizes!
Huh. How about that, eh? I had nearly always encountered the rules as 'misere' (though I never knew them as that) in these sorts of games.
Sorry about that!