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 CGT concept of "temperature".
It is part of the folklore of Go, but hard to argue out from first principles,
that opening plays are worth something in the range of 20 to 30 points. One
of the confusing aspects of the game to beginners is the way stronger players
switch around the board: "They seem to stop playing in a place just as I start
understanding what's going on". A start on describing what is seen in real
games is the combination of disjunction (two or more games played side-by-side
in a modular way), and a rigorous idea of an ambient temperature, relative to
which the hot spots and low-priority areas in the overall game may be charted.
These are both among the CGT fundamentals.
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.
