Combinatorial Game Theory IV

Lesson 4

In this lesson, we will work on a large class of games, known as take-and-break games. First consider a simple example.

Kayles

Kayles is an example of a take-and-break game:

Start with a few heaps of contiguous bottles, e.g.

Each player alternately knocks down one or two adjacent bottles, until there is nothing left. The player who removes the last bottle wins. Note that knocking down a bottle or two splits a heap into two smaller heaps unless the bottle(s) are at the end of the heap.

An example of a valid move of the above game is:

which divides the middle heap into two. This can then be followed by:

etc. We will analyse this game using the theory we’ve just developed. First consider the Kayles game with one single heap of n bottles. If we can find the Nim value of one heap, then we can certainly find the solution to any number of heaps.

Sum of Two Games

First we define the sum of two games G+H to be the combined game, whereby at each turn, a player can choose a valid move in G or a valid move in H but not both – there are no constraints on which component (G or H) he can choose. The player who is unable to make a valid move in either G or H loses in this combined game G+H.

For example, consider the sum of Chinese chess and international chess, as below. (In this particular game sum, though, it’s not clear how to determine the winner.)

For another example of game sum, consider the two Nim games (3, 4, 5) and (7, 10, 11). Their sum is the Nim game (3, 4, 5, 7, 10, 11). More generally, any Nim game can be broken up as the sum of its individual heaps, i.e. (3, 4, 5) is the sum of the three Nim games (3), (4) and (5). The Nim-Square game in the previous lesson is then merely a sum of one or more copies of the Square-Game.

Having described the concept of sum,  we may state the main result.

If G has Nim value *m and H has Nim value *n, then the sum G+H has Nim value , where is the “addition without carry” operation defined in the last lecture.

We will not prove this theorem here, but eventually we will when we introduce the general abstract theory. For now let us contend ourselves with some heuristic understanding.

The idea is that if G has Nim value *m, then we saw in the previous lesson that one can replace the game G by *m in a game sum without significantly altering the game play. Oh there’re some slight differences alright, such as the ability for the players to increase the Nim value. However, this makes no difference to the winning player, since he can make a winning move to a position with a smaller Nim value. It makes no difference to the losing player either, since his opponent can push back the Nim value to the old one.

Confused? Hopefully, the following example gives you a better idea.

Solving Kayles

Let be the game of Kayles with a single heap of n bottles. Our objective here is to compute the Nim value of . It is easy to see that K₀, K₁ and K₂ have Nim values 0, *1, *2 respectively. What about for higher values of n?

Let’s suppose the following Nim values are known:

n	0	1	2	3	4	5	6	7
Kn	0	*1	*2	*3	*1	*4	*3	??

To compute the Nim value of K₇, we need to consider all possible positions after one move: K₆, K₁+K₅, K₂+K₄, K₃+K₃, K₅, K₁+K₄, K₂+K₃. These have the following Nim values:

• ;
• ;
• ;
• ;
• ;
• ;
• .

The Nim value of K₇  is the smallest Nim value which does not occur among all its moves, i.e. *2 in this case.

Playing Kayles

In our definition of Kayles, we used the example of a game with heaps of (3, 4, 5, 2, 5). Let’s analyze this game. The Nim values of the heaps are *3, *1, *4, *2, *4, with a combined Nim sum of 0. So the second player wins.

Suppose the first player makes a move 4 → (2, 1). How would you respond? Well, since the resulting game (3, 2, 1, 5, 2, 5) has Nim values *3, *2, *1, *4, *2, *4 with a Nim sum of *2, one possible move is *3 → *1, which corresponds to 3 → 1.

Exercises

1. Dawson’s Kayles has the same rules as Kayles, except that every player must remove exactly two contiguous bottles. Consider the following configurations which describe the number of bottles in each heap. Are the following first- or second-player wins?
   • (12, 13, 14);
   • (8, 9, 10, 13).
2. If you know programming, find the Nim values for Dawson’s Kayles and Kayles up to n=150. Do you see a pattern?
3. In Grundy’s Game, we begin with some heaps of stones. Here, the only legal move for each player is to split a heap into two smaller heaps of differentsizes. Solve this game for:
   • (10, 11, 12);
   • (13, 14, 15).
4. In Lasker’s Nim, we have one or more heaps of stones. Each player, at his turn, takes a number of stones from any one heap, and may in addition splits that heap into two smaller heaps. Analyse Lasker’s Nim for three heaps, of sizes 7, 11, 15. How does Lasker’s Nim differ from ordinary Nim?
5. Analyse two-dimensional Kayles: start with an m × n board. At each player’s turn, he picks a board and removes a horizontal or vertical slice of width 1, possibly breaking the board into two smaller boards. The slice must be along the edge of the grid squares. For example, a game on a 7 × 4 board may proceed as follows:

6. In Treblecross, also known as one-dimensional tic-tac-toe, you start with an n × 1 board, where initially all n squares are empty. Two players alternately pick an empty square and fill it with an ‘X’. The first player to fill in three X’s in a row wins. Analyse the n× 1 board for n up to 15: i.e. determine who wins.For 11 ≤ n ≤ 15, if the first player wins, find the winning move.

7. (For chess players) In Dawson’s Chess, two players start with an n × 3 chessboard, with pawns of different colours lining opposite edges. At each player’s turn, he may move his own pawn or capture an opponent’s pawn, where the rules for movement and capturing are the same as that of chess. Furthermore, capturing is obligatory, i.e. if a player has a chance to capture his opponent’s pawn, he must do so; if more than one capture is available, he can choose any one of them. Analyse the following board.