Articles Charles Matthews | ||

CGT Becomes Hard Currency |

Those who play games tend to be saddened rather than
excited at the prospect of a "solution" to their
pastime. Why play noughts-and-crosses (tic-tac-toe)
against someone who can answer by look-up, using a
complete analysis of the game? One might as well
play a computer with an invincible program. An older
and usually less regarded approach is to look for a
"theory" of a given game. Is chess to be solved by
some as-yet-undiscovered branch of mathematics? The
evolution of games in the chess family has in fact been
towards playability and richness of content. While
*mathematics* is penetrating in some parts,
it *has little to say when faced with undigested
complexity*.

Recent developments in theory have changed the picture somewhat. While rigorous chess theory may still be confined to endgame study, there is an avenue in Go for some fundamental research. This area has been opened up by Professor Elwyn Berlekamp of Berkeley, after pioneering work of others. It is now beginning to provide novel insights.

*Deep in the background lie games*,
recognised more as recreations than
competitive mind sports, *for which a
theory exists*. The classic example is
Nim
- two players, equipment a box of matches or a pack of
cards. From a starting position of a few heaps, each
player in turn takes any number (possibly all) from a
single heap. The winner is the player taking the last
heap. This game was solved many years ago.

It was realised in time that Nim, while apparently a little too trite to be taken seriously as a game, was a key component in a whole range of games called "impartial". These are easily characterised: there must be no "mine" and "thine" but instead each play in the game is for either side, and you lose if you have no remaining lay. Each such game may in principle be reduced to Nim strategy, and so solved.

In an advance summed up in the classic "Winning Ways" by Berlekamp, Conway and Guy, a huge expansion took place in games with a common base of theory. Games were allowed to have a colour distinguishing my pieces and your pieces. The ending condition (no way to play means you lose) remains, but is flexible enough to admit a notion of scoring: my score of five can be taken in the form of five free turns when the game has ground to a halt.

The consequences of the theory included free mixing of
positions from different games. They can be considered
on the same footing, leading to a metaphor of a common
currency. The mathematical notations of "Winning
Ways", perhaps a barrier to some readers, set
up a coinage system, and worked out some everyday
ways of handling what is distinctly *funny
money*. For example Nim players know that
two heaps of the same size is a loss for the first
player - the second player has a copycat strategy. That
means in Nim money a second coin added to your purse can
cause it and the first one to disappear!

Overall this led to the emergence of Combinatorial Game
Theory (CGT). It resembles in some ways the euro zone: a
basis created for transactions between positions taken
from apparently disparate games, with a guarantee of an
underlying common scale of value. Go is a game with a
score. It turns out that *with a little massage Go
positions fit into CGT *. The benefit to both sides
is becoming clear: statements about Go in CGT terms are
in a non-traditional language, causing a foundational
rethink on the Go endgame and the articulation of
concepts from high-level play left implicit in the past.
And CGT finds a potential killer app - in the money
metaphor it turns out that the currency may be a hard
one on the exchanges of the mind sports world.

One way to see how CGT can enter Go is through players'
practice of counting, applied to several aspects of the
game. One counts liberties, eyes (up to two, anyway),
territory and the net effect of endgame plays on it,
*ko* threats by overall number and individual
value. Now the connection between games in CGT and
cardinal (counting) numbers is very strong - it was
worked out in J.H. Conway's "On Numbers and
Games", leading off into Logic. The sense in
which Go players speak of "half an eye" (a potential
eye, that may be taken away in one play) is exactly
the CGT meaning of "half". When it comes to endgame
counting, though, the CGT concepts are rather more
accurate than the Go tradition is used to. Parity ideas
are recognised in Go (with *miai* the Japanese
term applying to even parity, *tedomari* to odd
parity in the shape of a key point that can be unmasked
by discarding pairs of *miai*). But here CGT cuts
much deeper. It has been shown that it is adequate as
a complete theory of what Go players call "two-point
*yose*", the final stages of the game where each
play is worth one or two points when crudely counted.
CGT has something new to say about open-ended plays, and
has revealed fine structure showing how delicate games
can be if they depend on the last point played.

Two further areas of broad interest to players are
a developing *theory of ko fights*,
and the interfacing of Go with the

Berlekamp has pushed his ideas on evaluation of
plays by ambient testing to a new and playable Go
variant, *Environmental Go*, in which players
may take cards with a cash value at the end of
the game, in place of a conventional turn. In
recent trials
of this game with top pros Jiang Zhujiu and his wife Rui
Naiwei (on the basis of her
current games in South Korea
the highest-ever achiever among women in mind sports),
he has started to collect information relating the
actual judgements of very strong players over the board
with the basic theory. Definitive conclusions would
be premature, particularly as there is an element
of personal style: Rui seems to evaluate the early
initiative very highly. But the way is open for a range
of fresh insights into Go independent of the theoretical
apparatus. Berlekamp's group, including Bill Fraser and
Bill Spight, a prolific poster on CGT topics to the
newsgroup rec.games.go, are actively pursuing these
matters.

- Another introduction to CGT
- Elwyn Berlekamp's home page with downloadable papers on Amazons and Dots-and-Boxes puzzles as well as Go
- David Moews, Martin Müller, David Wolfe: links compiled by others in the Go and CGT field
- "Clever Games" page on games from "On Numbers and Games"
- "Games of No Chance", edited by Richard Nowakowski, downloadable by chapters: the state of the art as of 1994
- Big set of links on combinatorial games in their own right, as well as their theory, by David Eppstein; and more such links
- Aviezri Fraenkel's page links to a large downloadable bibliography of combinatorial games
- Impartial Hackenbush, Hackenstrings, Octal games: the theory in action on other games