Introductory Combinatorial Game Theory

Introductory Combinatorial Game Theory
Lesson 1 (Simple Games)
We shall begin our session with a simple game: Squaring the Number. Beginning with a positive integer (say 75), players A and B alternately subtract a positive square integer from it, leaving a non-negative integer. In other words, the players can only subtract 1, 4, 9, 16, 25, 36 etc. The player who is unable to make a move loses. For example, a typical game might proceed as follows:

Here A's moves are indicated by a red arrow, while B's moves are indicated by a green arrow. Hence, in the above game, player B wins since A has no legal move left. There is a nagging suspicion though, that one (possibly both) of the players has not played wisely. If both players had played well, who would win?

Suppose the game begins with the non-negative integer n. There are two possible outcomes for the game.

the first player can definitely win, by playing a crucial move; or
no such move is available to him, so the second player can definitely win.

If (a) holds, then we say that n is a winning number; otherwise, (b) holds and we call n a losing number.

Let us look at some simple examples.

0 is definitely a losing number, because no move is available to him at all!
Every square number 1, 4, 9, 16, 25 etc, is a winning number, since the first player can easily reduce it to zero, thereby giving his opponent a losing position.

After some elementary reasonings, we get: Table 1

0	1	2	3	4	5

where the cross-bones indicate a losing number and a blank space refers to a winning number. The rules for continuing our analysis may be plainly stated as:

If the first player can make a move, such that the resulting number is losing, then n is a winning number.
Otherwise, each of the first player's move results in a winning number, hence n is a losing number.

If you think about the above rules of thumb, it becomes intuitively obvious why : naturally you want the other player to lose. So, if you are the first player, you try to leave a losing number to the second player. If you are unable to do that, you lose since every move you make is a winning number for the other player.

To give a feel of how the above guidelines work, suppose we have continued our analysis for table 1 till n=21 :

Table 2

0	1	2	3	4	5	6	7	8	9	10

11	12	13	14	15	16	17	18	19	20	21

Now we wish to analyze n=22. From 22, we have 4 possible moves:

Each of the four moves : 6, 13, 18, 21 are winning numbers. Hence 22 is a losing number. This gives us an efficient method of finding the status of each number.

Making Good Moves
It is not enough to simply know whether each number is winning or losing. We must know how to make 'good' moves, so that we can win when placed in an advantageous situation.

Example 1 : In the game with n=19, what is the first move you should make?

Answer : Look at Table 2 above, 19 is a winning number which spells good news for you. Now consider the options you have : n=18, 15, 10, or 3. Since you want your opponent to lose, you should give him a losing number : i.e. n=10 or 15.

Example 2 : In the game with n=18, the first player decided to subtract 4, leaving n=14. What would happen?

Answer : Again, from Table 2, we see that 14 is a winning number - hence the first player's move was unwise. The second player may now turn the tables around by subtracting 4, leaving a losing number n=10 for the first player. Victory!

Here, we shall describe an even more efficient method to find the outcome of a number n. This method is similar to the sieve of Eratosthenes (which finds all primes below a certain range). Suppose we wish to compute the outcomes of all numbers up to 15. We know for sure that 0 is a losing number :

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

Adding square numbers to 0 gives us 1, 4, 9 (which are winning numbers since there is a choice for player A to leave a losing number).

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

So we know that the first unlabelled number is losing (2 in this case) :

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

Adding square numbers to 2 gives us more winning numbers : (2+1, 2+4, 2+9) :

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

The next unlabelled number 5 must be losing. Continuing in this manner, we eventually obtain :

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

Remoteness

Example 3 : Uh-oh, now I'm left with the number n=17, which is a losing number. There's no hope for me now, is there?

Answer : Don't panic. Although in theory a losing position is a sure-lose case, you can bet that your opponent isn't well-versed enough to find the exact strategy. Hence, your next move should serve to confuse your opponent as much as possible. In your example, it would be daft to take away 1 leaving 16, since 16 is such a clear-cut case for your opponent. In short, we want to find a move to a winning position for the opponent which is as remote from the winning goal as possible.

The remoteness values of n are assigned under the following rules:

If n=0, then the remoteness is given 0 by default.
If n is a winning position, then the remoteness of n is one more than the smallest possible remoteness among all the possible moves to losing positions.
If n is a losing position, then the remotenes of n is one more than the largest possible remoteness among all possible moves.

The above values follow from the fact that if a player is given a winning number, he'd most definitely want to win as fast as possible to minimise any chance of error. Conversely, a losing player would like to delay his opponent's win for as long as possible, hoping that his opponent would blunder in some move. Hence the rule:

WIN QUICKLY.
LOSE SLOWLY.

To demonstrate the above rules of thumb, suppose the values of remoteness have already been found for up to n=16. We wish to calculate the case for n=17.

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

There are 4 possible moves for n=17, to values of n=16, 13, 8 or 1. The respective values of remoteness are 1, 7, 5, 1. Hence, the remoteness value of 17 is one more than the maximum of these values, which is 8. To answer Question 3, the best move is to make a move to 13, which has a remoteness value of 7, the highest among all possible moves. Finally, observe that odd values of remoteness correspond to winning positions while even values correspond to losing positions.

Wythoff's Game

The rules of this game are as follows: given a pair of non-negative integers (which may be distinct), two players alternately make a move. Each move consists of either (a) subtracting a positive integer from one of them, or (b) subtracting the same positive integer from both. The constraint is that none of the integers may be left negative. As before, the player who is unable to make a move loses (i.e. the player who leaves (0,0) for his opponent wins).

This game is equivalent to Wythoff's Queen which is played on a checkerboard, with the queen at position (m, n). Each player may, upon his turn, move a queen in one of the three directions towards the home square (0,0). The player who manages to 'home' his queen wins.

We may now apply the same analysis as before.

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

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

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

Continuing in this manner, we find the losing positions (m, n) (m < n) : (0,0), (1,2), (3,5), (4,7), (6,10), (8, 13) ... .In general, to find the (i+1)-th losing position, we look for the smallest positive integer k which has not appeared in the sequence (in either the first or second position), and write down (k, k+i).

Back to the main page...