Charles Matthews
| 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 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.