Canonical Form

Canonical form

The simplest form of a game is its canonical form. Obviously, the definition is set up so that two games are equal if their canonical forms are the same.
There are two basic methods for reducing a game to its canonical form. First, eliminate dominated options.

E. g.,

`` { 2, 2, 1 | -1, 0} = {2 | -1} ``

Left will prefer to play to 2 rather than 1, and Right will prefer to play to -1 rather than 0.

Second, replace reversible options

E. g.,

`` { 3 " || " 1 | -3 " ||| " -1} = {1 | -1} ``

(In slash notation the number of vertical strokes indicates how close a game is to the root. Here the root has 3 strokes.) Left's play reverses because, after Left moves to

`` { 3" || "1 | -3 } ``

Right can move to

`` { 1 | -3} ``

which is less than the original game. So to keep from suffering a loss, Left must continue to ``1``. Left's play would also reverse if Right moved to a game that was equal to the original.

The rub there is showing that `` {1 | -3} `` is less than or equal to the original. In practice, you usually show reversal by showing that the game derived by replacing the reversible option is equal to the original. You can do that by playing their difference game.

Example moved to reversible. According to a basic result of Berlekamp, these two methods suffice. Charles Matthews.

In go, the actual form of the game may really matter. For instance, a zero game may be a ko threat. Therefore something may be lost by passing to the canonical form.

Example of reduction to canonical form

What is the canonical form of this game?

Example  

(Note on the diagram: Not a whole board. The current stones are alive.)

We know that the hane reverses, and obviously plays further inside the opponent's territory are dominated, as are plays inside one's own territory. But there is one other play that looks pretty good: the descent. (In fact, Takagawa's Go Reader mentions it as an alternative with the possibility of retaining sente.) Does it dominate the hanetsugi, or vice versa, or neither?

Again, the difference game will tell us.

Hanetsugi vs. descent

On the left, Black has played hanetsugi; on the right, White has played descent. Does this position favor one player?

Hanetsugi vs. descent (Black plays first)

If Black plays first, he wins by 1 point.

Hanetsugi vs. descent (White plays first)

If White plays first, the result is jigo.

The difference game favors Black, so the hanetsugi dominates the sagari.

(Having read Takagawa when I was learning go, I was surprised when David Wolfe informed me that the sagari was dominated. But so it is.)

The descent is dominated, and the hane reverses, so the canonical form of this game is quite simple:

`` { 1 | -1 } ``

--Bill Spight

Tom: I find this comment very interesting. It has led me to compose my first go problem. I think I'll call it non-locality.

Moved from Combinatorial game theory by Charles Matthews.