beavers Who are Busy

When people first hear about combinatorial games, they are often a little bit intimidated by the name; combinatorics has been a source of trauma for numerous people in school, I’m sure. But despite their name, combinatorial games are actually easy to define and play.

A combinatorial game is a game defined by a sequence of board states such that:

• it is non-random (deterministic)
• everyone can see the whole board (perfect information)
• it is played by two players, who each have the same set of rules (symmetric)

Therefore, poker wouldn’t be a combinatorial game, meanwhile tic-tac-toe is one.

A slightly more interesting example of a combinatorial game than tic-tac-toe is a game called 2-pile nim. It is played like this:

Choose 2 different positive integers, take for example 2, and 5

At each turn the player will subtract any positive integer from either of the two numbers. 2->1 is a valid move, while 5->6 is not.

Play continues until 0,0

Depending on what version you play, there are two different conditions for winning; putting the board into the 0,0 state, or forcing the other player to put the board into the 0,0 state.

There is a really nice way that we can formulate a winning strategy for the game in both cases, and to find the both, we’ll first consider the case where the player who ends the game wins:

Think about if you received the board in the state, n,n.

No matter what you did, you would not be able to be the one to end the game, since once you take from one of the piles, there will be an imbalance.

Also, if you receive the board in an imbalanced state, you will always be able to balance it.

Since both balancing and imbalancing can continually be forced by one player, the first one who can receive the board in an imbalanced state should be able to win.

In other words, if the board is not of the form n,n, the first player will always win, and if it is, then the second player will win.

Now we can think about the case where the last person to pull the last numbers will lose.

If we consider the case where the board is of the form n,a when it is received, where n is above 1, and a is at most 1, we know that the receiving player will win. This is becase, in all cases, they are able to control the parity of the number of 1s on the board after their turn, which will always determine the game.

Therefore, players would like to receive the board that has only 1 pile with more than 1 in it. This is the same as just playing the previous version of Nim, where all the piles are 1 smaller than normal. Therefore the strategy reduces to that one, and we once again have a winning strategy for one of the players.

I’d encourage you to use these ideas to play Nim with some of your friends, who you might immediately lose for beating them mercilessly (not like that).