Combinatorial Game Theory with Early Elementary School Aged Children

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.

I presented my seven year old son with the game using the rules mentioned in Eugene Madison's book, but using square math-tiles laid out as an array instead of just saying the numbers. My son noticed quickly connected the game with the Chess nim game which he had played previously, and started to look for "sweet spots." The most obvious sweet spot is to have the opponent have to choose from a pile of pieces just one over the maximum allowed to be taken in a turn. But how do you get the pile to there? If that's your goal you can look for the sweet spot immediately before that one - again just one over the maximum number allowed to be taken.

Over two days I helped encourage him to see that his opponent and his turn as a set, the total result of which he could control (he could, if he choose, see to it that those two turns added together equaled the maximum number of tiles permitted plus one). Mentally or physically arrange the pile of objects into multiples of that control number. In the picture to the left, the maximum number of tiles to be removed at a time is three and so the control number is four. Each turn the first player can take one, two or three tiles, and the second player will take the complementary number so that a total of four tiles is removed. The first player will eventually be faced with four tiles and no way to either take the last tile or leave more than three tiles for the next player to take. The first player will lose. In Combinatorial Game Theory a game where, when both players know what they are doing, the first player loses are called zero games. 

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 loose. 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 join their review team or 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.