Archive of Doug's go blog for July 2003.
In the long running debate over scoring, several positions are heard. One sometimes hears that territory scoring provides a sharper game: after all, the final score difference takes on all integer values, while area score differences move by twos. One might also claim that area scoring provides a more difficult game: it is hotter, after all, and players must continue to contest points after the territory game is over, providing opportunities for tactics that do not exist in the territory game. These tactics are more than just remembering to fill dame, examples exist of strong players losing what could have been winnable games, had they been familiar with area tactics. A third position is that they are simply different games. All of these arguments are suspect, however. As far as the territory partisan argument, there is really only one bit being fought over: one side wins, the other side loses. The extra bit interacts with the komi parity, as we will see. As far as the area partisan argument, neither temperature nor length of the game, by themselves, define the difficulty of playing. And finally, simply claiming that the games are different does not explain why the vast majority of games can be played well without reference to which game is being played.
Let's look at the score parity. Play a game through the end, including filling the dame, and remove dead stones as prisoners. If T is territory, S is stones, D is dame (which must be seki dame), and N is the number of intersections on the board, we have
N = T_b + T_w + S_b + S_w + D
Let P refer to prisoners and K the negative komi, then the territory score is
T_b - P_b - T_w + P_w + K,
the area score is
T_b + S_b - T_w - S_w + K,
and the difference between them is
delta = -(P_b + S_b) + (P_w + S_w) = -M
where M is the difference in number of moves made by each side. This is the standard argument for equivalence of area and territory scoring. Both sides make about the same number of moves, so M is close to zero. If we force M to zero (eg., by making passes cost a point and having white move last) we have equivalence scoring, a la AGA. Typical values for M are zero and one (White moves last, or Black does), but it could in principle have any value: it's possible to force multiple passes by your opponent at the end.
Let's set M = 1, so Black gets the last move, and look at the case where it decides the game in Black's favor for area but not territory. We have for the area score (rounding the komi down, with the noninteger part giving Black victory)
0 = T_b + S_b - T_w - S_w + floor(K),
and if we add N-D from the first equation, take everything modulo 2 to look at parity, we have
(N-D) mod 2 = floor(K) mod 2
This equation is interesting, because it connects scoring differences (the ones that actually change the game result) to komi parity. N-D is usually odd (361 points on a board, and seki with odd numbers of shared liberties are very rare). So having M = 1 change the game result can happen only with odd komi: K = -6.5, -4.5, etc. For -5.5 komi, the game result is not affected by who gets the last move, unless the game ends with a hane seki! This leaves the territory partisan in an interesting position: the additional subtlety of territory scoring depends on the parity of the komi, so territory is superior if komi = -4.5, but not -5.5. This is a little surprising, given that the komi makes no difference whatsoever to what move is the best move in any possible position.
Fortunately for territory partisans, the world seems to be moving to a -6.5 komi. Thus, going from 5.5 to 6.5 does not simply touch up the win/loss balance, but adds an additional layer of subtlety and sharpness to the game that had heretofore been lacking, something which seems to have been missed in the discussions on the change in komi. Of course, going to 7.5 will lose it again, so the territory go world must be careful about future changes that they make.
I showed up at Martin Mueller's go seminar Friday afternoon. I had a bit of a difficult time explaining who I was, and what I was doing there ("looking for material for my go blog" didn't sound quite right) but once I got past that, I had fun. Thomas Wolf, of GoTools fame, was visiting. I'd missed his formal talk (apparently, he'd presented some results on optimizing parameters in GoTools: by adjusting move ordering heuristics, he'd created 20-30% speedups) but got to hear about recent work in progress. His group is trying to build an exhaustive database of life death positions. Databases have revolutionized games like chess and checkers, by allowing huge classes of positions to be simply looked up, without search. It will be quite interesting to see what impact they will have on computer go.
The current methodology is straightforward. First, create all eyespaces of a certain size, and place them in all locations in the center, side, and corner. Surround the eyespace with a complete wall of White stones (the group whose life is in question), which is itself completely enclosed by Black stones, with possibly some extra liberties. Then, setup all possible combinations of White and Black stones inside the eyespace, and pass the position to GoTools for solving.
One could question the usefulness of fully surrounded groups, and the resulting states (live, ko, dead) don't allow adding multiple eyespaces together. But it's early days for this work: the databases aren't constructed yet, much less applied in the context of real programs. And constructing databases from complete search has the great advantage of permanently increasing knowledge: the things you learn will never need to be unlearned. Without a doubt there is a future in databases.
I'm still trying to understand capturing races. At some point, one needs to start counting liberties, so I might as well start today.
First, consider the simplest capturing race: two strings, no eyes, shared liberties, kos or anything other than plain outside liberties. Since there are no shared liberties, seki can't happen, and the winner depends on the balance of the outside liberties. These are easy to count, and the result is easy too. Call Δ the number of Black outside liberties minus the number of White outside liberties. If Δ > 0, Black wins (and could tenuki Δ-1 times if White started filling), if Δ < 0 White wins, and if Δ = 0 then whoever goes first wins. So far, so good.
Let's add the possibility of eyes, still with no shared liberties. Seki remains impossible, so again, there will be a winner and a loser. You capture a group with an eyespace by first filling the outside liberties, then working on the eye. A single point eye needs to be filled last, to capture the group, but is otherwise exactly equivalent to an outside liberty. This liberty is called an eye liberty, and gets added to the outside liberties to make up the exclusive liberties of the group. For larger eyespaces, you need to play moves to almost fill the eye, putting the group in atari. Your opponent captures (for any eye larger than two), leaving the next size smaller of eye. So this gives a recursion relation for the number of liberties an eye of size n:
L(n) = (n-1)-1 + L(n-1)
(That's n-1 of your moves to almost fill, minus one because your opponent spends a move capturing you.) The recursion relation starts at L(2) = 2, and the general solution is L(n) = (n^2-3n)/2 + 3, usually remembered as four is five, and five is eight, and six is twelve. Above n = 7, the formula becomes irrelevant, because it's always possible for the opponent to make two eyes in the captured eyespace. And be sure to subtract off the number of stones already in the eyespace: for the larger eyes, there will have to be some, otherwise the opponent could make two eyes right off.
Once we've computed the eye liberties for both sides, we can add them to the outside liberties, call them exclusive liberties, and just compare them as above to see who wins, exactly as if there were outside liberties alone. When there are shared liberties, things become more complicated: how many shared liberties matters, and how big the various eyes are, but I'll get to that another day.
It was a good vacation. I spent two weeks away, and didn't think about go even once. (Well, maybe I tried to count the UL ko from my June 19 entry while driving across the prairie -- 7 pts/move Japanese, I think, but since both sides have to thrown in to start the ko, whoever starts gives up a point and a move.)
Browsing r.g.g., I found the work of Teigo Nakamura -- one of those rare people being paid to do theoretical go research. Recently, he has been applying CGT to capturing races. The text of his 2003 paper is in Japanese, but you can get the gist from the abstract and diagrams. His examples are two-group capturing races with no mutual liberties. Whoever has more outside liberties will win, a simple matter of counting, right? However, outside liberties need not be simple numbers: there may be various kinds of moves which add or subtract liberties, or threaten to. This is precisely what CGT was made for. Here are a couple of positions stolen from a figure:
Assume that connects to a larger Black group involved in a capturing race. Black has one outside liberty, and could play to get three more. White could take it all away with one gote move.
Here, a White play at a threatens to cut off three stones and leave Black with no liberties, whereas answering leaves Black with four liberties. If Black plays a, he has six. So what should he count? And where should he play, if both positions are in the same capturing race?
The answers are 2* and 4^, if I understand the figure correctly, and where you should play depends upon what the rest of the capturing race looks like. This is CGT at work. In general, you can use CGT on anything you can count. So far it's been applied to points, eyes, and moves to capture in capturing races. What's next? Ko threats? What else do we count in go?
More archives: Doug's go blog/August 2003 - /June 2003