Lesson 11
In this lesson, we will cover more on canonical forms. First recall that for m↑ + (*n) with m > 0, this game is positive except when (m, n) = (1, 1). Let’s consider the canonical forms of these games.
First, we know that ↑ = {0 | *}.
What about ↑* = ↑ + * ? By definition, we get:
since * + * = 0 < ↑. Now let’s consider the Left option ↑. This has a Right option *. Now is it true that * ≤ ↑*. Of course! So we can replace the Left option ↑ by all the Left options of *. This gives:
We’ll leave it to the reader to check that further simplification is impossible. So we have the canonical form of ↑*.
Next, what about 2↑ = ↑ + ↑? Again, by definition,
Let’s see if move reversal takes place. Left‘s option to ↑ has the Right option *. Now is it true that * ≤ 2↑ ? Yup! So we can replace Left‘s option ↑ by all Left options of *. This gives .
Now let’s consider the Right option to ↑*. Since we already saw that ↑* = {0, * | 0}, this has Left options 0 and *. Now is it true that 0 (or *) ≥ 2↑ ? Nope to both cases! So we obtain the following canonical form:
.
We’ll leave it to the reader to calculate the canonical forms of the following and find a pattern among them (see exercise 2).
- 2↑ + *
- 3↑
- 3↑ + *
- 4↑
- 4↑ + *
Next, let’s consider G = ↑ + *2. By definition, we have:
.
Since ↑ > *2 we can erase the Left option *2. Likewise, since *3 < ↑ and *3 < ↑* we can erase the Right options ↑ and ↑*. This leaves:
Any move reversals possible? Let’s consider the Left option ↑, which has Right option *. Since * < G, move reversal happens and we replace ↑ by the Left options of *, thus giving . By the same token, the Left option ↑* has Right option 0 < G, so we shall replace ↑* by the Left options of 0, i.e. nothing! This gives us:
.
Next, calculate the canonical forms of the following and find a pattern among them (see exercise 3).
- ↑ + *3
- ↑ + *4
- ↑ + *5
More Domineering
It turns out for small m and n, the m-by-n Domineering board has rather nice canonical forms. The following can be calculated on a computer using cgsuite:
1 | 2 | 3 | 4 | 5 | 6 | |
1 | 0 | |||||
2 | 1 | ±1 | ||||
3 | 1 | {1/2 | -2} | ±1 | |||
4 | 2 | +2 | 3/2 | G | ||
5 | 2 | 1/2 | 1 | -1 | 0 | |
6 | 3 | {1 | -1+(+2)} | {7/2 | 1} | #&!?* | 3/2 | Out of mem |
7 | 3 | {1/2 | -3/2} | {3 | 3/4} | -1 |
where
- –2 = {{2 | 0} | 0},
- +2 = – (-2) = {0 | {0 | -2}},
- G = {0, H | 0, –H}, and H = {{2|0}, 2+(+2) | {2|0}, –2}.
There are also many sequences of Domineering configurations which admit a general formula. E.g.:
More on Toppling Dominoes
Recall the game of Toppling Dominoes in lesson 9. We already know the following games:
- Contiguous row of n Light dominoes : n.
- Contiguous row of n Light dominoes, followed by m dominoes : {n-1 | -(m-1)}.
As a special case, a Light domino placed beside a daRk domino forms the game {0 | 0} = *. Now we can calculate the following games:
See if you can find a pattern for this game (see exercise 1).
Exercises
- Guess the canonical forms of the following games (the first game has n+1 Light and n daRk dominoes; the second game has n Light and n daRk dominoes). Can you prove it?
- Write down the canonical forms of n↑ and n↑ + *. Prove it. [ For this and the next two problems, take note of the fact that ↑* is fuzzy. ]
- Write down the canonical form of ↑ + *m. Prove it.
- Even more generally, write down the canonical form of n↑ + *m. Prove it.
- Given the following two Domineering games:
simplify the following into canonical form:
- Given the following Toads-and-Frogs games:
simplify the following games into canonical forms: