Put a collection of small objects (stones, beans, Popsicle sticks, etc) in a pile. Let two people take turns removing one, two or three of the objects. Can you predict which person will take the last object? My seven year old knows who will.
The game is called Nim and there are plenty of variations of it. In some variations the objects are divided into piles and you cannot remove objects from more than one pile while in other multi-pile variations you can remove from multiple piles as long as you remove the same number from each pile. In some variations there is a set maximum number of objects you can remove while in other variations the maximum number is double whatever was taken by the previous player.
The game can be played verbally as in the Modular Games book by Eugene W. Madison, where players alternate counting up to a pre-determined number, or they can be played with physical objects. There is even a variation of the game, Wythoff’s Nim, that is played on a chess board with only a single queen being moved by two players in turn as they attempt to be the one to place the queen in a predetermined corner of the board.
Of course the pile of tiles isn’t always going to be a multiple of the control number. In the picture to the left there are 23 tiles. In this case the first player can remove three pieces so that the pile now has a multiple of 4 and the second player will now lose. You can think of that first turn as a sort of “pre-turn” and the game the second player is in effect starting the game as first player in a zero game.
The Nim games fit into the category of impartial games, because we are both withdrawing pieces from the same pile. Unlike chess or checkers there is no set of “your pieces” vs “my pieces.”
They also belong to the category of perfect-information games because there are no hidden surprises. Of course you can choose to add surprises back in. Eugene W. Madison suggests playing the game with cards (players taking turns selecting how many cards to collect in order to be the one who collects the last card) but with the addition of a “joker’s rule” that allows whomever draws the joker to take a second turn, thus upsetting the patterns. One variation my children and I played we taped a few little symbols to the back of the math-tiles we were using, one allowing a player a second turn, one forcing a player to pick up an additional two tiles and one deleting all the remaining tiles of that particular color (in that game we used math tiles of four different colors mixed together). No one knew who would draw the special tiles or how far through the game they would be, so it brought back in an element of chance.
I wanted to find a way to illustrate how a game moves and how I think of two turns as being one round so I started doodling in my notebook. I came up with a system of triangles to represent the turns, and eventually copied it onto the computer. The numbers in the triangles represent the number of tokens taken that turn and the arrows point out how many tokens are left in the pile between turns. The illustration to the left is a sort of alternative version of what I was trying to explain in this post.
Now for the footnote. I obtained a copy of Eugene W. Madison’s book from the publisher as a review copy and did a review on Amazon as they asked. In no way did receiving a free book oblige me to go to the effort of writing this post, but in honor of having received it free I will point out that you can buy the book if you feel so inclined. Quite frankly, the book isn’t one I would recommend unless a person is already into game theory and/or is looking for an investment opportunity. It feels like part of it probably came from whatever documents he needed to create in order to patent his computer and board game. But the book got me curious about what Combinatorial game theory is, and I borrowed from my local library the book On Numbers and Games. It has more than just the one game and appears to be a classic in the field of Combinatorial game theory. That said, I had to follow the suggestion in the intro and start reading at chapter seven because I honestly couldn’t understand the first half of the book. Even starting where I did I found myself looking up quite a few things online. Thankfully there are a few easy-ish articles, such as this one on Hackenbush.