NIM Games--Introductory Combinatorial Game Theory

First let us recall the two games which were introduced previously:

1. Squaring the Number : Two players alternately subtract positive square integers from n, until 0 is reached.
2. Nim Given some piles of stones, two players alternately remove stones from a single pile, until all the piles are empty.

Let us combine the concept of both games, so that we have Nim-Square : as in Nim, we start with some piles of stones. Two players A and B alternately remove a number of stones from any single pile, as long as the number of stones removed is a perfect square. A game of Nim-Square might proceed as follows:

(4,9,12)		(4,9,8)		(0,9,8)		(0,5,8)		(0,5,4)
(0,1,4)		(0,1,3)		(0,1,2)		(0,1,1)		(0,1,0)		(0,0,0)

So the second player wins. A thorough analysis of this game is more complex, so we will accomplish this step-by-step.



Sum of Two Games

Suppose G and H are any two games. We define the sum G + H to be the ‘combined game‘ of G and H. To put it explicitly, we place the two games side-by-side, and let players A and B begin. At each player‘s turn, he or she may choose a valid move from either G or H. A player is not compelled to choose from a particular game; nor does he have to follow his opponent. The player who is unable to make any move at all loses.

The follow diagram is an example of a sum between a game of Chinese Chess and a game of International Chess. Player A has made 3 moves on the left and 3 moves on the right, while Player B has made 5 moves on the left but 1 move on the right. However in this case, it is not clear how to determine the winner.


It is clear that the sum of two Nim games is yet another Nim game. For example, the sum of the Nim games (2,5,7) and (3,4,8) is precisely the game (2,3,4,5,7,8). Also, every Nim game can be broken down as a sum of Nim games with a single pile. For example, the Nim game (2,5,7) is the sum of the individual Nim games (2), (5) and (7). Similarly, Nim-Square is simply the sum of individual games of Squaring the Number.



Nimbers

Nimbers are simply ‘Nim values‘ which are assigned to a game configuration - these values are written as 0, *1, *2, *3 .... We shall first describe how to obtain the Nim values for the game Squaring the Number. First, the Nim value of n=0 is assigned 0, since it is a state in which neither player has a valid move.

0	1	2	3	4	5	6	7	8	9	10	11	12	13
0

We then recursively adopt the following rule for each n : find all the possible moves from n and pick the smallest Nim value which does not occur among all these possible moves. Hence, the Nim value of n=1 is assigned the Nim value of *1. To illustrate the above rule, let us suppose the Nim values of all n < 13 has already been obtained :

0	1	2	3	4	5	6	7	8	9	10	11	12	13
0	*1	0	*1	*2	0	*1	0	*1	*2	0	*1	0

To compute the Nim value for n = 13, let us look at the possible moves : we can subtract 1,4, or 9, which would leave n = 12, 9, or 4 respectively. These results have Nim values of 0, *2 and *2. Hence the smallest Nim value which does not occur in all these moves is *1. Now comes an important theorem in combinatorial game theory :

A game which is assigned a Nim value of *m, is equivalent to a game of Nim with m sticks. Hence, a game of Nim-Square with starting configuration (4,9,12) is equivalent a game of Nim with starting configuration (2, 2, 0). In this game, the first player loses.

If games G and H have Nim values *m and *n, then the Nim value of the sum G+H is *(m * n). (The definition of m * n was given previously.)

First things first : we mentioned equivalent games in the above theorem. What does it really mean for two games to be equivalent? This would be covered in further detail on subsequent lessons. For now, we shall illustrate what the above theorem means by solving Nim-Square thoroughly.



The best way to see the result is to actually play a game. We have the following Nim values for Squaring the Number.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	*1	0	*1	*2	0	*1	0	*1	*2	0	*1	0	*1	*2

15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
0	*1	0	*1	*2	0	*1	0	*1	*2	*3	*2	*3	*4	*5

Consider the game of Nim-Square which starts with (18, 26, 28). The Nim values for n=18, 26 and 28 are *1, *2 and *4. Thus, this is equivalent to game of Nim which starts with (1, 2, 4). We shall analyze one particular game between players A and B. Take note of the corresponding Nim values.

A‘s move		B‘s move
Game Value	Nim Value	Game Value	Nim Value
(18,26,28) (18,26,27)	(*1,*2,*4) (*1,*2,*3)	(18,26,27) (18,25,27)	(*1,*2,*3) (*1,*3,*3)
(18,25,27) (18,9,27)	(*1,*3,*3) (*1,*2,*3)	(18,9,27) (18,0,27)	(*1,*2,*3) (*1,0,*3)
(18,0,27) (18,0,18)	(*1,0,*3) (*1,0,*1)	(18,0,18) (18,0,14)	(*1,0,*1) (*1,0,*2)
(18,0,14) (18,0,13)	(*1,0,*2) (*1,0,*1)	(18,0,13) (18,0,12)	(*1,0,*1) (*1,0,0)
(18,0,12) (2,0,12)	(*1,0,0) (0,0,0)	(2,0,12) (2,0,8)	(0,0,0) (0,0,*1)

The game has not ended yet, but we can see how it‘s going to proceed. At each turn, A looks at the corresponding Nim game, finds the winning move (to a losing position) there, and makes the corresponding move in his game. Notice that unlike the actual game of Nim, the Nim values in this case may bob up and down. However, B cannot postpone his defeat indefinitely by increasing the Nim values - since this is a finite game, he‘s eventually forced to decrease a Nim value.



Kayles

Let us look at another game : Kayles. Some rows of skittles are drawn, and each player, upon his turn, knocks down any one skittle or two neighbouring skittles. Such a game for (3,4,3) may proceed as follows:






Hence the first player A wins. In order to analyze the game, let us assign a Nim value to a game of Kayles with n contiguous skittles. Clearly, when n=0 the Nim value is 0; and when n=1, the Nim value is *1. To compute the Nim value for n=2, note that a move may leave either 0 or 1 skittles (with Nim scores 0 or *1). Hence, the value is *2.

Computing the Nim value for n=3 is a bit tricky. A move may leave either 1 skittle, 2 contiguous skittles, or 2 separated skittles. These have Nim scores *1, *2 or *(1 * 1) = 0 respectively. Hence the desired value, being the smallest non-negative integer which does not occur among all the moves, must be *3.

Similarly, when n=4, the first move leaves (3), (1,2), (2) or (1,1). The Nim values of these results are *3, *(1 * 2) = *3, *2, *(1 * 1) = 0. Hence, the Nim value is *1.

When n=5, the first move leaves (4), (3,1), (2,2), (3) or (2,1), whose Nim values are respectively *1, *(3 * 1) = *2, *(2 * 2) = 0, *3, *(2 * 1) = *3. Hence, the Nim score is *4. Continuing in this manner, we obtain the following table:

0	1	2	3	4	5	6	7	8	9	10
0	*1	*2	*3	*1	*4	*3	*2	*1	*4	*2

Hence our game configuration (3,4,3) as shown above has a Nim score of (*3, *1, *3), which in turn has a combined score of *(3 * 1 * 3) = *1. In other words, the first player wins.



Grundy‘s Game

A heap of n stones is given. Two players alternately split the heap into two smaller heaps of different sizes. Eventually, the heap has 1 or 2 stones left and the player who is unable to perform the split loses. When n = 1 or 2, the Nim value is obviously 0. For n=3, the only legal move is (1,2), which has a Nim value of (0, 0) = 0. Hence, the Nim value for n=3 is *1.

For n=4, the only legal move is (1,3), which has a Nim value of (0, *1) = *1. Hence the Nim value for n=4 is 0.

For n=5, we have two possible moves: (1,4), (2,3), with Nim values (0, 0) = 0, (0, *1) = *1 respectively. Hence the Nim value for n=5 is *2.

Continuing in this manner, we have the following table:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	*1	0	*2	*1	0	*2	*1	0	*2	*1	*3	*2	*1

More Games

Here are some other games which you may analyze for yourself:

1. Remember our childhood game of Sticks? We have several rows of skittles / sticks, and at a player‘s turn, he may cancel out an arbitrary number of skittles provided they are all contiguous. The player to cancel the last skittle loses. Analyze this game thoroughly.
   
   
2. Dawson‘s Kayles is similar to Kayles, but the only legal move is to knock down two contiguous skittles. Analyze this game for various initial positions.
   
   
   
   
3. In Nim City, the towns A-K together with the hometown are drawn on the (simplified) map below, together with the expressways connecting them. Initially, there are three cars, whose respective locations are towns F, J and K. The game is played between two players: at each player‘s turn he must pick up a car and land it on a nearby town which is connected via an expressway. A car may only move from a higher letter to a lower one (e.g. K to C) or from a letter to the hometown. More than one car may be present in a town at any time. The first player to move all the cars back home wins. Does the first player have in this game?
   
   
4. Analyze Dawson‘s Chess - start with a 3-by-n chessboard, with two rows of pawns at opposite ends. Each player alternately move a pawn or capture his opponent‘s pawn. Here, capturing is obligatory, i.e. if a player has a chance of capturing a pawn, he must do so. If in the next move, he has more than one capture available, then he can choose from any one of them. (Recall the rules of international chess : a pawn may move only one square forward at a time, and capturing must be diagonal. Here a pawn may not be promoted.)
   
   
   
5. Consider Treblecross, which is basically one-dimensional tic-tac-toe. Here, the board is a 1-by-n grid (n at least 3), and both players share the same symbol X. The first player to connect 3 X‘s in a row wins. Who wins on a 1-by-100 board? (For example in the diagram below, the next player will lose since whatever move he makes enables the other player to connect three in a row.)