Combinatorial Game Theory I

[ Prerequisites required: none for now. ]

In the middle of 2000, I was waiting to go to graduate school and had a bit of free time on my hands. So I decided to prepare a website which teaches combinatorial game theory (CGT) methodically. The subject fascinated me in various ways: it was simple enough that a sufficiently motivated primary school child can probably learn much of it. Yet at the same time, notes and books on it were scarce. Recall that back then, there was no wikipedia, youtube, online courses, and even lecture notes were quite scarce on the internet. Due to time constraints and possibly waning interest, the notes were never complete.

Fast forward another 8 years, and I decided to give it another shot. This time, I offered to teach the course as an elective at NUS High School. It was a stressful yet tremendously rewarding experience since I believe there’s no precendent for teaching CGT to pre-university (grades 7-12) students. The challenge was in dividing the materials into discrete packages, so that there’s something interesting for the students to learn every week. I must say I was reasonably pleased with the results, though no doubt there’s much room for improvement.

Since I don’t think I’ll be conducting the course again, here’re the notes. Hopefully, they’re fit for public consumption. There should be 12-13 lessons in all. Stay tuned! 🙂

[ My first website (together with all personal homepages on the server) got taken down recently. However, they’re still available at archive.org if anyone’s interested. ]

Lesson 1

Combinatorial game theory (CGT) explores games with the following properties:

  • Deterministic: no luck is involved.
  • Finite: the game is guaranteed to end within a finite time.
  • Two-player: only two players are involved.
  • No draws: there must be a winner.
  • Open: all information and legal moves are known to both players.
  • The player who is unable to make a move loses.

Note that many classical games do not fall under this criteria. Even so, the theory is of interest for a variety of reasons.

The case for Weiqi is especially interesting, since it has been known to solve Weiqi endgame problems which are tricky enough to stump 9-dan professionals(!). Unfortunately, we won’t delve into this aspect as it is rather difficult.

Course Requirements

This course does not assume prior knowledge of other areas of mathematics. However, some familiarity with classical games like Chess and Chinese Chess may come in handy for certain problems. Also, although homework submissions are mostly proof-free, the course lectures will involve quite a few proofs, especially towards the later part.

No programming is required, but it’s definitely fun to program the games covered in the course to see the outcome for yourself. Challenge your friends and stump them!

Square Game

Consider the following game, which we shall call the Square Game (for lack of a better name):

Start with a positive number of stones and play alternates between players A and B. At each player’s turn, he must remove m stones, where m is a positive square number. The player who is unable to make a move loses. Equivalently, the player who removes the last stone wins.

Here’s an example of how the game may proceed:

23 \to 22 \Rightarrow 18 \to 14 \Rightarrow 10 \to 9 \Rightarrow 0,

So the second player wins the game by removing all stones. The nagging question is: could the first player have won by making some better move? Indeed, we shall soon see that the first player’s second move (18→14) was a very bad one. He could have won by taking (18→17) instead.

To analyse the game, we need the following concept:

Definition : A number n is said to be winning if the first player can win by playing well. Conversely, n is losing if the first player has no chance of winning, assuming the second player plays well.

For example, 0 is losing since the first player can’t do anything, 1 is winning and 2 is losing. By considering all possible moves for small n, we easily see that:

  • 0, 2, 5 are losing;
  • 1, 3, 4 are winning.

But this approach quickly wears us out. We need a more systematic method:

Observations
1. If n is winning, then there is a move from n to a losing position.
2. If n is losing, then all possible moves from n lead to a winning position.

Let’s examine how this is useful in practice. Suppose we know the status of all numbers from 0 to 16, as follows:

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

To find the status of 17, let us consider all possible moves from 17:

17 → 16, 13, 8, 1.

These moves all result in winning numbers – so a player who’s given 17 has no choice but to move to a winning position and let his opponent win. Thus, 17 is a losing position.

Sieving Method

There’s an even more efficient method to compute the status of all number below a certain bound M. Students who’re familiar with the sieve of Eratosthenes will see its similarity. The algorithm is as follows:

  1. Start with an array A[i] of labels, indexed by i = 0, 1, \ldots, M.
  2. Initially, all entries are unlabelled.
  3. Pick the smallest i for which A[i] is unlabelled and label it ‘L’.
  4. All numbers which have a move to i, i.e. i+1, i+4, i+9, i+16 … are then labelled ‘W’.
  5. If there is still an unlabelled A[i], go back to step (3).

Let’s see how this algorithm works for M=14. Initially, we have:

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

After this we pick all numbers of the form 0+j^2 and label them ‘W‘.

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

The next unlabelled number is i = 2, so we label it L.

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

And next, all numbers of the form 2+j^2 are labelled ‘W‘:

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

And so on… until we fill up the entire table.

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


Remoteness

The remoteness of a position is heuristically its distance from the endgame. The idea is that even if you’re given a losing position, you can hope to confuse the opponent by playing a tricky move. We define the remoteness value as below:

  1. The remoteness of 0 is 0.
  2. If n is winning, the remoteness of n is one more than the smallest remoteness among all possible moves to losing positions.
  3. If n is losing, the remoteness of n is one more than the largest remoteness among all possible moves.

To understand this definition, one looks at a player’s mentality during a game.

  • Upon given a winning position, he wants to move to a losing position for his opponent. To minimise the possibility of error,  he wants to move to a losing position with small remoteness, so he can win quickly.
  • Upon given a losing position, all moves are to winning positions. The player hopes to delay his defeat by choosing a position with high remoteness.

The above principles can be summarised as:

Win quickly. Lose slowly.

For example, suppose we have the following remoteness values:

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

Then the remoteness value of 17 is computed as follows: 17 has four possible moves, to 16, 13, 8, 1 with remoteness values of 1, 7, 5, 1 respectively. Since 17 is a losing position, its remoteness value is then given by 1+max(1,7,5,1) = 8. Hence, if you get the number 17 in a game, your best bet would be to move to 13 (the worst possible moves are to 1 and 16, since you’re guaranteeing a win for your opponent in the next move).

Exercises

  1. Consider our Square Game.
    1. For each n ≤ 40, determine the status of n.
    2. For each n ≤ 40, determine the remoteness of n.
    3. Starting with n = 40, what is the best move for the first player? What is his worst possible move?
    4. Starting with n = 39, what is the best move for the first player? What is his worst possible move?
  2. Prove that a position with even remoteness is losing, while a position with odd remoteness is winning.
  3. Wythoff’s Game works as follows. Given two piles of stones (m, n), each player alternately makes a legal move, which is either (a) remove a positive number of stones from any one single pile, or (b) remove the same positive number of stones from both piles. The player who removes the last stone wins. Find the remoteness values of (m, 8), for m = 0, … , 8.
  4. A prime power is a number of the form pr, where p is prime and r is a non-negative integer [Warning: this differs from the usual definition, since it includes 1.] Consider the Prime-power Game, whereby two players alternately subtract a prime-power number (i.e. 1, 2, 3, 4, 5, 7, 8, 9, 11, 13, … ) of stones. Again, the one who removes the last stone wins.
    1. Find all losing numbers ≤ 40, and formulate a conjecture on the set of all losing numbers.
    2. Assuming this conjecture, is 10000000000  winning or losing? If you were the first player, what move could you play to win (note: ignore the remoteness, just focus on winning)?
  5. Recall that the set of losing numbers in Square Game is: {0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, … }. Go to Sloane’s online encyclopedia of sequences and enter this sequence. Can you prove the property listed on the website?
  6. (Hard) Begin with 1000 cheques of various worth, placed face-up on a table. Two players alternately remove a cheque from either the extreme left or the extreme right, then immediately cashes it in to get the money. At the end of the game, each player has cashed in exactly 500 cheques. Prove that the first player can obtain at least as much money as the second player. Is this true for 1001 cheques?
This entry was posted in Notes and tagged , , , , . Bookmark the permalink.

2 Responses to Combinatorial Game Theory I

  1. Reblogged this on intjerest and commented:
    Game theory is a bit of an obsession of mine. It started with the entirely benign activity of watching an anime called Death Note. In an economics class, we discussed game theory, and–reminded of Death Note–I looked it up on the revered Wikipedia for my own entertainment. Things escalated from there.

  2. Pingback: Lý thuyết về trò chơi | pascalteacher

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s