Winning and losing at Nim
(Update: this post is featured in the 38th Carnival of Mathematics. Check it out!)
Right, I need six volunteers from the audience.
If no one stands up, I will pick people.
…
Last summer I attended TSM, a three-day conference (and excellent networking opportunity!) based at Oundle School near Peterborough. TSM is designed to develop enthusiasm for the use of technologies such as interactive whiteboards, Autograph, dynamic geometry, Excel, etc. in maths teachers.
On the last of the conference day they held a Delegates Forum, where we could tell other delegates about any interesting resources we knew about, or talk about anything we had picked up in the various sessions.
I gave a brief talk demonstrating some of the software I’d learnt how to use that week. It was also an introduction to the wonderful game of Nim.
In the end I did get volunteers, so I didn’t have to pick people from the audience. Here we can see them being used to demonstrate a simple position in the game:
As well as having some fun using people as counters, I ended the talk by showing a very pretty visualisation, generated in Autograph, of the positions which are guaranteed losses if your opponent is playing properly.
Continue reading to find out how to play Nim, and to see what the losing positions in 3-pile Nim look like.
[The two pictures above are taken from this photo slideshow of TSM 2007.]
The Rules
Nim is a very simple strategy game — just about the simplest one you could imagine — and yet it has hidden depths.
The version of Nim we will be playing has the following rules:
We have some counters, which have been split into piles,
and two players, who take it in turns to remove counters from the piles.A move consists of taking as many counters as you like from one pile.
To win, take the last counter.
That’s all there is to it! Note that there is a very popular variation of this, where you lose if you take the last counter, but we’re not going to play that here.
One-Pile Nim
The best way to figure out how to play Nim is to try some simple cases first, and there are few simpler cases than when all the counters are in one pile. As there are unlikely to be six people hunched around a computer reading this willing to move on demand, I’ll demonstrate with counters instead.
So, imagine the game starts with two counters, in one pile:
What are the options for the person going first? You can either take one counter, leaving the pile looking like this:
Or you can take both counters, leaving the pile looking like this:
(you’ve taken all the counters, so there’s nothing left). In the latter case, you’ve won immediately, as you took the last counter (alternatively, the second player loses, as they can’t pick up any counters). This is obviously the best of the two options.
What about if there were more counters in the pile at the start of the game? Six, for example:
Now the player going first has many more options, but the sensible one is still to take all the counters, leaving the other player no options.
This holds no matter how many counters there are in the pile at the start of the game. So, we have a general rule for one-pile Nim:
The first player can always win one-pile Nim, and the winning move is to take all the counters.
Two-Pile Nim
Now we are one-pile experts, let’s try a game with two piles. The simplest position is to have one counter in each pile:
Is it best to go first or second in this game? In other words, is this a winning or a losing position?
The first player only has one option — to remove one of the counters from one of the piles, leaving a lone pile with one counter. The second player takes this, and wins. So this is a losing position.
Next let’s try:
If the first player takes the single counter pile, then the second player can remove both counters in the other pile, and win. If the first player takes both counters from the other pile, then the second player can remove the single counter left, and win. However, if the first player takes just one counter from the two-counter pile, we will be left with the situation we just considered, which we know is a losing position. So that’s what the first player should do!
Notice that we didn’t need to remember why the position with two one-counter piles was losing, just that it was. This suggests a key strategy we should use in games like this: we should always try to move in to a losing position. So the key to winning is knowing how to lose!
Two-pile Nim makes an interesting, accessible investigation for secondary maths students. By experimenting, and keeping thorough records, it is fairly easy to form the following conjecture:
All positions with equal numbers of counters in both piles are losing positions, and all others are winning positions.
So this, for example, is a winning position:
You might want to see if you agree with this conjecture, and, if so, whether you can find a convincing argument for it.
Three-Pile Nim
Two-pile Nim pales after a while, so the next logical step is to think about positions with three piles, like the following:
It’s worth experimenting with this position for yourself. You should find that it is impossible for the first player to win from this position, as long as the second player always plays well (i.e., they should always pick their best move).
Again, it is useful to find a convincing argument for this. One way to frame the argument is to show that, whatever move the first person makes, the second person can move into a position which is a losing one (using the criterion for losing positions given above in the two-pile section).
As with the two-pile game, the key with three-pile Nim is knowing what the losing positions are.
Finding the Losing Positions
While the 1, 2, 3 position is still simple enough to consider in detail, it would be very tedious to go through every possible move in a case like this one:
Rather surprisingly, however, there is a very simple way to check whether a given position in three-pile Nim is a losing position. Even more surprisingly, this involves seeing whether the number of counters in one pile is the XOR of the numbers of counters in the other two piles. Explaining why this is true is quite difficult, but it involves assigning a value (called a nimber) to every possible position, and then investigating the arithmetic of nimbers.
For the moment, let us use the result without worrying about the detail. 5 XOR 2 is 7, not 4, so the position above is a winning position. The move we should make is one that will turn this into a losing position. We obviously can’t add three counters to the third pile… so let’s look at the first and third piles: 5 XOR 4 is 1. This means that the position with 5, 4, and 1 counters in the three piles (in any order) is a losing position. So a winning move for the next player (and, actually, the only winning move in this case) is to reduce the second pile to a single counter.
If this seems a little obscure, don’t worry. There are quite a few sites out there which seek to explain how to play three-pile Nim in more detail than I have… as ever, Google is your friend!
Visualising the Losing Positions
I thought it would be interesting to get a visual representation of the losing positions in 3-pile Nim. As there are three piles, and each pile contains an integer number of counters, we can represent each position as a point in three dimensional space.
Our first task is to generate a list of all the losing positions. I wrote an Excel spreadsheet to do this for me, using (gasp!) the in-built Visual Basic: generating-losing-nim-values.xls. Choose your maximum value (I used 63 in the visualisation below), and click the button to generate all the possible losing positions with up to your chosen number of counters in each pile.
Once we have the list of losing position coordinates, we can import the list into Autograph, and plot it, using Autograph’s 3D mode. The initial view doesn’t look that promising,
but that’s because Autograph doesn’t automatically rescale to fit all the data on the screen. Once we change the scale for a minimum of 0 and a maximum of 64 on each axis, we are faced with this:
Now that’s unexpected! To get a better view, let’s remove the axes, and rotate around slightly:
It appears that the losing positions in Nim with three piles form a three-dimensional Sierpinsky gasket… certainly not something I was expecting when I first started playing around with the game!
Further Directions
This was as far as I reached in my talk at TSM, but there are a number of directions to go in to investigate further:
- It would be nice to understand why the losing positions are calculated as they are.
- What about four-pile Nim?
- What about if we restrict the maximum number of counters we can take from a pile?
- What if we allow players to take counters from more than one pile?
- What if we allow players to split or join piles?
- What about if we allow the two players to do different things (for example, player one has to take an odd number of counters, and player two an even number)?
- More generally, Nim is only one example of a whole class of finite, impartial, two-player games (a particularly nice one to play involves placing dominoes on the squares of a chessboard). Does Nim give us any hints about how to play these games?
Amazingly, it was shown back in the 1930s by Sprague and Grundy that every impartial two-player game is, in some sense, equivalent to a particular position in Nim… so if you understand how to play Nim properly, and you know how to translate games into Nim positions, then you can play every game in this class perfectly!
The name for this area of mathematics is combinatorial game theory. Answers, comments, and many (many!) digressions and generalisations on these topics are contained in one of my favourite (if mind-bending) books, Winning Ways by Berlekamp, Conway, and Guy.
One questions which isn’t covered in that book is this: we now what what XOR looks like. What about the other binary operations, like AND and OR?
Related Posts (automatically generated)
Tags: Autograph, Excel, games, Maths, Nim, TSM
August 6th, 2008 at 1:53 pm
“Explaining why this is true is quite difficult”
Scribling in your margins, Jon?
August 6th, 2008 at 2:10 pm
I didn’t want to give a complete course on combinatorial game theory in this post, I just wanted to show the pretty picture I made :).
But it’s true that it’s hard to find a simple explanation of why nim-addition is equivalent to finding the bitwise xor of two numbers… at least, hard to find an explanation which doesn’t require a high level of mathematical maturity. I’d love to find an explanation which is suitable for the average A-level student… but these days few students know about binary numbers and binary arithmetic, so that would have to introduced first. Oh for the days of New Math when all students knew about binary before percentages!
August 12th, 2008 at 2:49 am
[...] — you should go and check it out! Of particular interest to me was Jon Ingram’s post on winning and losing at Nim. Nim is a very simple game, but there are a lot of really interesting results associated with it, [...]
February 20th, 2009 at 1:01 pm
[...] while back, I wrote an introduction to the game of Nim. If you can’t remember the rules, then go remind [...]
April 22nd, 2009 at 6:54 am
I have written about the theory of impartial games, and Nim in particular, on my blog, http://sputsoft.com/?p=58.