Tag: combinatorial game theory

We are in the framework of games with perfect information. [add]

As a guiding example we consider the game of Nim, or to be more precise 3-Nim. We have three heaps of objects (say coins) and two players. On each turn, a player has to remove a positive number of coins from one heap. If a player is not able to move (that is, there is no coin left), that player loses and the other one wins.

There are two things to notice here. On one hand, the formulation given here is not equivalent to saying that the last one to pick is the winner, since we want to be able to consider the case . On the other hand, there are several variants of Nim, including one where the one left with the last coin is the one who loses.

As already hinted in the previous paragraph, there is a nice representation of each turn of the game, as a vector in . Also, notice that each move decreases the sum of the components, so we know that the game ends, and we also know that one of the two has to lose (and one has to win, no ties are possible).

Question: is it possible, given the initial state , to determine if a player has a winning strategy and, in case, which is this strategy?

We can start with some examples: is clearly a losing state for the player about to take its turn. Similarly, (as well as rearrangements: states are always equivalent under permutations) and in general for is a winning state for the player about to move. Notice moreover that with the player cannot lose, even if they wanted, whereas with with the player has to play well not to lose. But we assume that both players are rational and play their best strategy. Moving on, is clearly losing for the player about to move, as is any state with , while il winning for the player about to move, as is .

Proceeding by examples, we cannot really find a general strategy, so let’s try a different approach. In particular, since each move can be on a single heap/coordinate, we can consider the 3-heap game as a combination of three different games, each with a single pile. This opens up an interesting perspective but requires us to formally state what we mean by “combination” of multiple games. Given two games and , their sum is a game in which at each turn the player can decide whether to move in the game or in the game . In particular, we can see the 3-Nim as a sum of three 1-Nims, each corresponding to a column.

In order to harness what we have defined (that is, an operation), we want to associate to every (Nim) game a number, called nimber. We proceed in the following way. The Nim game has nimber 0. Given a game, we list all the possible moves (each of these provides a different game, with less coins) and we list all the corresponding nimber; the nimber of the game we started with is the smallest nimber not in the list.

If we consider only games of 1-Nim, nimbers are quite boring: they are just the number of coins in the heap. However, things start to be interesting when we move to -Nims with . Take for example the 2-Nim game . There is only one move possible (up to the choice of the heap): remove one coin and be left with the game . This game is the same as the game , so it has nimber equal to 1. Hence the nimber of , that is the smallest nimber not on the list, is 0.

How is this related to the sum of Nim games? Well, we can see that the nimber of the Nim sum of two games as the Nim sum of the nimbers of the two games. For example: . Also, as seen earlier, . We can construct the table of the Nim sum of nimbers:

	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	0	3	2	5	4	7	6
2	2	3	0	1	6	7	4	5
3	3	2	1	0	7	6	5	4
4	4	5	6	7	0	1	2	3
5	5	4	7	6	1	0	3	2
6	6	7	4	5	2	3	0	1
7	7	6	5	4	3	2	1	0

How do we fill this table? Since is the nimber of the 2-Nim , we can use the definition, and look at all possible moves in that game. What are these moves? We can reduce the number of coins in one of the two heaps (but not both), so we are moving either up along the column or left along the row. The nimber we have to write at the intersection of the row labelled and column labelled is the smallest that does not show up neither in the leftmost cells of the -th row nor in the first cells from above in the -th column.

This operation might look familiar: it can be written in a different way as the logical XOR of the nimbers written in binary. For example .

Notice that we have defined the operation for two games, but since the sum of two games has a nimber and can be considered equivalent to the 1-Nim with that nimber, we can go on and sum an additional game, and so on. We can also check that the operation is commutative and associative.

Now we can finally go back to the problem we had: which player has a winning strategy? We can now state the answer as a theorem.

Theorem: A Nim game is losing for the first player if and only if its nimber is 0.

To prove this result, we can go through two lemmas.

Lemma: If the nimber of a Nim game is 0 before a move, any legal move will result in a Nim game with nimber greater than 0.

Remember that any move takes us either left or up from where we are. We can be in a 0 only if there are no zeros left or up, because of the way we defined the nim sum.

Lemma: If the nimber of a Nim game is greater than 0 before a move, there exists always a move that will result in a Nim game with nimber 0.

This is specular to the previous one: if we were not able to put a 0 in the intersection of row and column, it means that there is at least a zero, either up or left.

The two lemmas give us not only the theorem, but they also tell us the winning strategy (if possible): always end your move on a 0, so that the other player has no winning move.

As a nice aside, we can also define a product between nimbers, the Nim product . The Nim product of two nimbers is the smallest nimber that is not in the list

   

The construction of the table of for the nimbers smaller than 8 is a nice exercise.