Combinatorial Game Theory VIII

Lesson 8

In this lesson, we will further familiarise ourselves with games involving numbers. At the end of the lesson, we will encounter our first positive infinitesimal: the “up” ↑. Here, an infinitesimal is a value which is strictly between –r and r for any positive (dyadic) rational number r. We saw in the last lesson that *n is an infinitesimal for any n, but these are fuzzy games. The game ↑ is positive, i.e. 0 < ↑ < r for any positive rational r.

Toads-and-Frogs

Here’s an interesting game which can be analysed effectively using numbers. Without CGT, such a detailed analysis of the game would be difficult!

The game of Toads-and-Frogs is played on several rows of squares as above, where each square contains at most one creature. Each creature can only move in the direction it’s facing. E.g. in the first row, the toads in the first and third square can only go right, and the frog in the fourth square can only go left. By convention, player Left controls the TOads which go from Left to Right, while player Right controls the FROgs which go from Right to Left.

At each player’s turn, he may pick up one of his creatures and perform one and only one of the following moves:

move one square in its direction and land on an empty square; or
jump over an opponent‘s creature and land onto an empty square.

Play proceeds until a player loses for having no available moves.

Stop and think : how do we get the negative of a Toads-and-Frogs game? [ Answer (highlight to read) : we reflect the row about a vertical axis, so that all the toads facing right become frogs facing left, and vice versa. ]

Numbers in Toads-and-Frogs

In the case where there’s one toad and one frog in a row, the solution is usually a number or a * so analysis is quite easy. However, if there’s more than one frog / toad, the situation can become rather complicated.

For starters, consider the following configurations:

Instead of tracing through the whole game tree of each configuration, it is much more efficient to systematically consider a row with a single toad and a single frog. For a row in which the animals have already jumped past each other, it is easy to compute the value. Next, we start from the case where the frog and toad are side-by-side facing each other.

Examples

For the first row, if Right starts, he has no move available. On the other hand, if Left starts, the resulting configuration has 3 free moves for Left and 1 free move for Right. Thus, the first row = {3-1 | } = {2 | } = 3 by the Simplicity Rule.
For the second row, if Right starts, the resulting configuration has 4 free moves for Left and no move for Right. On the other hand, if Left starts, the resulting configuration has 2 free moves for Left and 2 free moves for Right. Thus, the second row = {2-2 | 4} = {0 | 4} = 1 by Simplicity Rule.

Next consider the case where there’s an empty space between them.

E.g. let’s consider the first row. If Left starts, the resulting game is 1, as we saw above. If Right starts, the resulting game is 3. Thus the overall game is {1 | 3} = 2. Now we’ll leave it to the reader to fill in the remaining entries…

To check your answers, click here.

Next we consider the case where there are exactly two toads (going Left to right) and two frogs (going Right to left). There are altogether 30 such configurations. Compute and simplify them as much as you can. [ Hint: recall that a game where the second player wins is a zero game. ] For the answer, click here.

A Positive Infinitesimal Game

The last 3 games are of particular interest to us. Let’s label

$\uparrow = \{0\ |\ *\}$ and $\downarrow = - \uparrow = \{-*\ |\ -0\} = \{*\ |\ 0\}$ .

The final game in the diagram is then equal to $\{ \uparrow\ |\ \downarrow\}$ . In a later lesson, we will learn another simplification rule, which will enable us to show that this is equal to *.

For now, let’s look at ↑ = {0 | *}. The interesting thing is that this game is positive, yet it is less than any positive number. The first claim is easy; as for the second claim, let us use the following useful comparison tool.

Theorem: Consider two games

$G = \{A, B, \ldots | X, Y, \ldots\}$ and $H = \{A', B, \ldots | X, Y, \ldots\}$ ,

where all options are identical except A and A’, where A ≥ A’. Then we must have G ≥ H.

Similarly, if we replace Right option X by X’ where X ≥ X’, then the resulting game H also satisfies G ≥ H.

Proof: We need to show that in G–H, if Right starts then Left wins. The strategy for Left is simple: whatever his opponent does in one component, he just mirrors in the other. The only problem occurs when Right tries moving (-H) to (-A’). To counter this, Left just moves G to A, thus leaving A – A’ for Right. Since this game ≥ 0 and Right goes next, Left wins. ♦

Warning : If A > A’, it does not follow that G > H (see exercise 1).

Now we can show that:

For any n > 0, we have 0 < ↑ < 1/2ⁿ.

Indeed, recall that we have * < 1/2ⁿ for any positive integer n. Hence, we have ↑ = {0 | *} ≤ {0 | 1/2ⁿ} = 1/2ⁿ⁺¹ < 1/2ⁿ. In fact, it turns out that any finite number copies of ↑ is smaller than 1/2ⁿ (see exercise 2).

Finally, we have the following result:

↑ is confused with *, i.e. ↑* is a first-player win.

For other Nim values however, we have:

↑ is larger than *2, *3, *4, … .

Also, for more copies of ↑, we have:

If m > 1 and n ≥ 0, then m↑ is larger than *n, where m↑ refers to the sum of m copies of ↑.

The proofs of all these results are in exercises 3 and 4. Finally since ↓ = -↑ , we also have the corresponding statements for the “down” game ↓.

For any n > 0, we have 0 > ↓ > -1/2ⁿ.
On the other hand, ↓ is confused with *.
But ↓ is smaller than *2, *3, *4, … .
Finally, for each m > 1 and n ≥ 0, m↓ is smaller than *n.

Exercises

Find games A, A’, B, such that A < A’ and {A | B} = {A’ | B}.
We already know that 0 < ↑ < 1/2ⁿ for any positive n. Use this to prove that for any positive integer m and integer n ≥ 0, we have m↑ + *n < 1/2ⁿ.
Prove that if n = 1, then ↑ + *n is a first-player win, and that if n > 1, then ↑ + *n is positive.
Prove that ↑ + ↑ + *n is positive for any n ≥ 0. Hence, prove that for any m > 1, and non-negative integer n, the game m↑ + *n is positive.
Compare the following: is the first expression greater than / less than / confused with / equal to the second expression?
- -1 + 3↑ and -5/4 + 100↑
- -2 + 100↓ + *2 and -1
- -1 + ↑ and -1 + *
- 2 + ↑ and 2 + ↓ + *
- 2 + ↓ + (*7) and 2 + ↑ + (*8)
- -1/2 + 10↑ + (*3) and -1/2 + 11↑ + (*2)
- -1/2 + 10↑ + (*8) and -1/2 + 11↑ + (*7)
State a general method of determining whether a + b↑ + (*c) is positive, negative, fuzzy or zero.
Decide the status of the following Toads-and-Frogs game. For each player, find his best move if he were to go first.