Combinatorial Game Theory XI

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:

\uparrow * = \{0\ |\ *\} + \{0\ |\ 0\} = \{*, \uparrow\ |\ *+*, \uparrow\} = \{*, \uparrow\ |\ 0\}

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:

\uparrow * = \{0, *\ |\ 0\}.

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,

2\uparrow = \{\uparrow\ |\ \uparrow*\}.

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 2\uparrow = \{0\ |\ \uparrow*\}

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:

2\uparrow = \{0\ |\ \uparrow*\}.

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:

G = \{*2, \uparrow, \uparrow*\ |\ *3, \uparrow, \uparrow*\}.

Since ↑ > *2 we can erase the Left option *2. Likewise, since *3 < ↑ and *3 < ↑* we can erase the Right options ↑ and ↑*. This leaves:

G = \{\uparrow, \uparrow*\ |\ *3\}.

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 G = \{0, \uparrow*\ |\ *3\}. 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:

\uparrow + *2 = \{0\ |\ *3\}.

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

  1. 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?

  1. 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.  ]
  2. Write down the canonical form of ↑ + *m. Prove it.
  3. Even more generally, write down the canonical form of n↑ + *m. Prove it.
  4. Given the following two Domineering games:

simplify the following into canonical form:

  1. Given the following Toads-and-Frogs games:

simplify the following games into canonical forms:

This entry was posted in Notes and tagged , , , , , , , , . Bookmark the permalink.

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