mathbabe

Yesterday I gave a “Prime Time” talk here at HCSSiM, which is an hour long talk to the entire program. I talked about the game of Nim.

Nim is an old game (that’s the kind of in-depth historical information you’re gonna get from me) where you have a certain number of piles and each pile has a certain number of stones in it. There are two players and you take turns removing as many stones from any one pile as you want. The last person to remove a stone wins. Or, to anticipate my confusion later on, the person who gives back an empty game to their opponent wins.

You can play Nim online here with 3 or more piles and where the stones are matchsticks.

A bunch of the kids had never played so I got them to come to the board to play 2- and 3-pile Nim. Eventually it was  discovered that, as long as you start out with uneven piles with 2-pile Nim, you have a winning strategy by making them even. But it wasn’t clear how to win with 3-pile Nim, so we put that question in our back pocket for later.

I then changed it up a bit and put a rook on a chessboard, and said the point was to land on the top left corner, and you could only go up and to the left. They quickly realized it was just two-pile Nim again and the winning strategy was to get the rook on the diagonal. Then I switched it up further and made it be a queen, not a rook, and allowed the piece to move up, left, and diagonally up and left. This was harder.

We then decided that, when you have a game like Nim which is two-player, and the players share the same pieces (so not chess) and moves, and when the game gets smaller every time someone makes a move, then every position can be considered either “winning” or “losing”, by growing the game up from smaller games. If you can only get to winning positions, then you’re at a losing position. If there’s an option to get to a losing position, then you’re at a winning position. A consequence of this way of thinking of things is that a “game” can be described by the options you have when given a chance to play (along with the rules that define the options).

We then discussed adding two games A and B, which just means you get to play from either A or B but not both. We decided that 2-pile Nim is already of the form A + A, where A is 1-pile Nim. And furthermore, 1-pile Nim is pretty dumb – the winning strategy is always to just take away all the stones. But in spite of this, 5 stones is not the same as 6 stones for 1-pile Nim, since you can get to 5 stones from 6 but not vice versa.

Then I defined A ~ B if for all other (impartial) games H, A + H always has the same winner as B + H. It’s easy to see ~ is an equivalence relation, and that G + G is always winning (again, by mimicking your opponent’s moves). It’s also pretty easy to see that if A is winning, then A + G ~ G for all G.

But it’s a bad definition of ~ in that it seems to take an infinite amount of work to decide if A ~ B, since you’d have to check something for all possible H. We decided to improve this by proving that G ~ G’ if and only if G + G’ is winning. It is pretty easy to do this.

Then it was time for action, namely to prove the Sprague-Grundy Theorem which states that:

Every impartial game G has G ~ [N] for some N, where [N] denotes 1-pile Nim with N stones.

We prove this by showing recursively on the size of the game that N above (also called the “Nimber” of the position) is just the “mex” function, which is the minimum excluded non-negative integer. In other words, we designate the winning position as having N = 0, and then we grow the game up from there. If a given position can get to a “0” position, then its Nimber is at least 0 – in fact it’s the minimum number that it can’t reach in one move.

In particular, if you are at a position with Nim number non-zero, you can get to a zero position (i.e. a winning position), as well as any smaller Nim position, and if you are at a position with Nim number zero, you can only get to non-zero positions. This is similar to the losing-winning dichotomy except slightly more nuanced.

We then drew a Nimber addition table, which is the same as the chessboard problem with a rook. We used this to reduce 3-pile Nim to 2-pile Nim and worked out a winning strategy for the 3-pile Nim game (2, 5, 3).

Next we drew a Nimber table for the queen on a chessboard problem. We decided we knew how to play that game plus a 3-pile Nim game.

I was running out of time by this time but I ended with showing them a fast way to find the Nimber of the sum of a bunch of games whose Nimbers you already know, namely the bitwise XOR function. I didn’t have time to prove it (it’s not hard to see with induction on the number of games you’re adding up) but it’s easy to see this recovers our “mimicking” strategy with two games.