Lessons taught; Lessons learnt

(This post is featured in the 3rd Maths Teachers At Play Carnival. Check it out!)

A while back, I wrote an introduction to the game of Nim. If you can’t remember the rules, then go remind yourself!

After talking about one-pile and two-pile Nim (both fairly easy to analyse), I moved on to three-pile Nim. The first example I gave was a starting position with three piles: 1 counter in one, 2 counters in the second, and 3 counters in the third. I then said:

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).

One way to investigate this is to find all possible moves from the starting position, then all possible moves from those, and so on. If we do that, we can use something like Graphviz to visualise the possible ways the game can progress:

Here, every circle is a game position, so ‘11′ represents two piles, each with one counter. Positions are connected if moving from one to the other is a valid move.

Notice that this view of the game makes no assumptions about whether the people playing it are playing to win. For example, if you were in position ‘2′, then you can move to ‘1′, but it’s a crazy move, as by doing so you have thrown the game — your opponent will move to ‘0′, and win.

 You might think that the transitive reduction would be a good start (this removes any ’short cuts’: edges a -> c if there are edges from a ->b and b -> c). The transitive reduction of the game network looks like this:

This is actually a worse view of the game than the original one, though! It still includes lots of ‘bad plays’, like 3 -> 2 or 13 -> 12, while removing ‘good plays’ like 3 -> 0.

What we really want, then, is to remove from our network all moves which would never be followed by someone playing to win.. In particular, if we can move into a position which will make the opponent lose, then we only need to keep that move, and ignore all the others.

If we strip away all these ‘bad plays’ from the above, then we get:

There are several things to notice in this new visualisation of the game:

First, note that some of the positions (like ‘3′)  have disappeared from our new network. This is because we can never reach them from our starting position, as long as the second player is playing sensibly.

Second, note that we have kept every possible move from ‘123′ (and the other losing positions, like ‘22′), but only have one move from all the winning positions. The reason for this is quite simple: to demonstrate that something is a winning position, all we have to show is that we can move from it into a losing position; to show something is a losing position, we have to show that every position you can get to from it is a winning position.

We can formalise this into a definition of winning and losing positions that can be used to investigate many games. Watch out for a future post on this topic!

Related Posts (automatically generated)

1. Winning and losing at Nim
2. Nim: The limits of visualisation
3. The Joy of Hex