Doug's go blog/August 2003

For some time, I've been working through a topological picture of capturing races, using adjacency. But looking at the diagram (taken from one stone alive in seki), I realize that even I have no idea what I'm talking about, much less any one of my few remaining readers. I'd written

I'll just post one position, in the form of a problem. Can Black make trouble? How much?

Added later: "Make trouble" is pretty vague. If Black sacrifices his stones with , how can he reinvade and live in a new seki? And, once he's made that seki, can he sacrifice it, and make a third seki?

13 Aug: How to count without counting

A game of go normally consists of two separate phases: playing and counting. After play is over, as determined by agreement or two passes, the players count the points for each side, and determine the difference and the winner. There are various ways of counting the score, but the entire counting phase is a little bit funny. Strong players do not need it: they are capable of scoring the position precisely without manual counting or rearranging the stones. Counting serves to confirm what they already knew, and if counting produces a different result than they had been expecting, they are likely to want to repeat the count. People who play on computers do not need to count: the computer takes care of that, quickly and precisely. For weaker players, with a less certain score estimate, less familiarity with the counting procedure, and less ability to replay the game and recover the final position, the count is an opportunity for confusion and miscreancy. For novices, the ending of the game and the final counting is a mystery. It's not clear why the game stops when it does, what is happening at the end, or why it is that after the smoke clears it's always announced that they have lost. In most games, winning and losing is obvious from moves themselves: the last marker is removed from the board, the king is captured, spades beat diamonds or full house beats two of a kind. In most games, even if you know nothing else you know when you lost, but go requires accountants to move in after the battle to determine the victor.

Counting as I've seen it done in person requires rearrangement of the stones. This limits the amount of tedious point by point counting, since you can choose simple arrangements of the blocks. However, it opens the door to slight-of-hand, and disturbs the position, making reevaluation difficult. These aren't problems in casual games between competent adults. New Zealand uses point-by-point counting: run your finger over the board, row by row, and count your points. It sounds tedious, and requires the ability to count to 180, but it's claimed to be faster and easier than it sounds, and does not disturb the position. Ing uses fill in counting, where every point is filled in with a stone, using a specified number of stones: 181 black and 180 white. Whichever side has stones left over loses. You still have to count to 180, but you do it with the stones, before the game, and if you have the special bowls it's pretty quick. For children, I've heard fill-in counting followed by pairwise removal recommended. Once the board is full of stones, whoever has more stones on the board wins. The idea is that even children who are too young to count can understand removing the stones two at a time, one black, one white. Daniel Gilder recommends filling in territories during play, using pass stones, and counting prisoners only. The number of prisoners will usually be fairly small, but must nevertheless be counted.

All of these methods require a counting phase, regardless of how the counting is done. I'd rather see the counting moved into the play of the game itself, so that you're not done playing until the result is determined. You could do this with a no-pass version of stone counting: standard capturing and ko rule, suicide prohibited, passing requires returning a captured prisoner, and is allowed only when you have prisoners to return. The game ends when one side has no legal move and cannot pass; this side loses. Voila: no counting phase, the two players fill in their own territories during play in alternation, a bit like players filling in the dame during play in alternation. (A bit like Daniel's suggestion, but with no counting at all.) Games would be a bit longer in terms of number of moves, but shouldn't take longer, since the filling of territories is quite rote. In a tournament, it would be done on the clock, which would have the added advantage of allowing round scheduling to be more precise, since players would not be rearranging the position, counting the score, and arguing about the result off the clock. And for beginners and children, it provides instant gratification: you're either still playing, or the game is over with a known winner and loser. To me, this is the biggest advantage.

12 Aug: Three group capturing races, no eyes

Following up on earlier entries, I ought to actually show how to do a multigroup capturing race. Let's begin with the easiest case: three groups, no eyes anywhere. Label the groups

  -  - 

The eye statuses will be e_1, e_W, and e_2, the exclusive liberties are E_1, E_W, and E_2, and the shared liberties are S_1 and S_2. No eyes means e_1 = e_W = e_2, and no eye liberties means that exclusive liberties are just outside liberties.

You might think that White would be at a disadvantage in races like this, because she's surrounded on all sides, but the opposite is true: White could win everything by capturing either or , e.g. by filling shared liberties on one side only, whereas Black must fill liberties on both sides of to capture White. In particular, White gets to count liberties on both sides, but each Black group only gets to count one side. As a result, Black must take responsibility for filling all the shared liberties. And worse, Black gets to count his difference in exclusive liberties from the worse off of his two groups: White will attack the weaker one. So we have

Δ = min_i E_i - E_W

How many moves ahead does Black need to be? That's just F, the number of shared liberties that Black needs to fill. To put White in atari, he needs to fill all of them but one (because White has no eye).

 F = max(sum_i S_i - 1, 0)

where the max is just stuck in there to take care of the case where there are no shared liberties at all. With this, the capturing race formula holds: Black will succeed if

  Δ >= F

and need move only if Δ = F. With no eyes, seki is impossible, so if Black fails, he loses everything.

Finally, why write everything in terms of i? Well, in this case anyway, the discussion holds for any number of Black groups surrounding a single White one; i.e. any star topology.

What about eyes? Well, if only White has an eye, then the only thing that changes is that the -1 goes away: Black must fill all the shared liberties. Black eyes may make things more complicated.

7 Aug: Pair Go

I played a game of pair go last night. Well, not strict pair go, which requires the bridge convention of four players, mixed genders, so call it team go. We did follow the convention of not discussing moves before they are made, and, most important, we had the requisite wide range of strengths. Really, the bigger the spread, the better!

Strategy is completely different. When reading, it's important to consider who will be making which moves. Moves that normally would be considered a pointless waste of a ko threat suddenly make a lot of sense: when sent to a stronger player, it's kind of like walking a batter in baseball. You know where they'll go, and how much damage they can do. And when sent to a weaker player, who knows: pehaps they won't spot the atari. (Sometimes, I found myself hoping that my partner wouldn't spot an atari!) There's a high degree of randomness, which makes for a lot of fun. It was either that, or the beer...

It was hilarious. It was a gas. It's highly recommended.

4 Aug: Three group seki

Multigroup sekis are a rarity, usually appearing in composed positions, examples in rule texts, and that kind of thing. For the three group capturing race

  -  - 

seki can occur only if both Black groups have an eye, the White group has no eye, and there is one shared liberty on each side. It's not easy to see how this would come up in play, but it has been reported in amateur play. It would be interesting to know if it had ever happened in a pro game.

deg Well it depends on your definition of group. This shape is quite common.

Doug: I'd call that two strings forming a single group. Give Black an outside liberty, or let the White group inside be larger, and Black could connect the strings completely. Still, it'd be nice to have a clearer definition.

unkx80: A similar discussion is in maximum number of live groups.

3 Aug: Credit where credit is due

In response to JF: my capturing race discussion (and also the earlier eye liberties) is based heavily on Martin Mueller's GPW 99 paper (very heavily, if you take a look), which in turn credits a 1982 DGZ paper by Lenz as the first known appearance in the Western literature, but presumably this stuff has been known much longer. I haven't read Richard's book, much as I ought to, but from the table it seems clear we're working the same ground. Landman 96 also has some material on this.

I knew I'd get in trouble eventually for failing to cite properly. I have written things here which I believe to be novel, but this isn't one of them.

John F. I've never been able to read any of Martin's stuff as I don't have the required technology. Anyone know how to access it in more user-friendly form (e.g. paper, html, doc, txt, zip, non-Postscript)?

Try this nearly legible PDF.

2 Aug: Shared liberties and the capturing race formula

John F. What am I missing here? Doug's reformulation of the base rules for fighting semeais seems a major, major improvement on anything that's gone before (no more memorising Type 1~6, etc), but no-one's commented on it. I checked the simple new rule fairly extensively last night and it seems to work 100%. And it's so easy to apply. Come on - credit where credit's due?

Blake: I'm not up on game theory, but I just wanted to note that you can make an actual delta symbol with Δ. Isn't that lovely?

Let's look at what happens in the case of two groups, some outside liberties, perhaps with some eye liberties, and shared liberties. Wthout shared liberties, seki is impossible, so one side or the other will win. We can find out who by counting the exclusive liberties (outside liberties plus eye liberties) for each: the winner is the side with more, with equal counts being unsettled, and going to the side on the move.

Things start to become more interesting when we start adding shared liberties. It's bad to fill your own liberties in a capturing race, but those liberties must get filled eventually before anyone gets captured. The central question is always, who has to do the filling?

There's in fact a general answer to that question: it's the side that needs to put the other side in atari first that must fill. Mueller calls this side the attacker. There are a couple of different cases of this. The first is where neither side has an eye but one side has more outside liberties. He ought to be better off, so he'd like to use his surplus of liberties to capture the other side. To do this, he needs to fill the shared liberties to put his opponent into atari. Call the number of shared liberties which he needs to fill F: it will in this case be equal to the number of shared liberties S minus 1. He'll be able to capture the other side if his surplus of exclusive liberties Δ (see 17 July) is equal to or more than F:

 Δ >= F

where Δ = F is the critical (unsettled) case. This formula is called the capturing race formula, and as we will see is general to all cases. In this case, once the attacker has filled all of his opponent's outside liberties, and is reduced to exactly Δ of his own, he begins filling the inside ones. With his Fth move, he puts the opponent into atari, and has one outside liberty left allowing him victory. The other way to think about this is that the opponent gets to count the shared liberties in the liberty count for the group, but the attacker does not. This is the approach taken by Richard Hunter in Counting Liberties.

The other case is where there is a difference in eyes for the two groups. If the other side has an eye and you don't, you'll have to fill all the shared liberties before getting him into atari. So here, you're the attacker, F = S, and the semeai formula still applies. Or if you both have eyes, but you have more exclusive liberties, again you're the attacker.

Small eyes (one, two, or three points) all act the same, and just give liberties and make an eyeless opponent fill the common liberties. Big eyes (four or more) are worth even more though. Remember how they are captured: you fill them up, put the group into atari, get captured, and start over again on a smaller eye. To do this, you have to put the group into atari, which means that all the shared liberties must be filled first. The side with a bigger shared eye has an advantage here, because it's up to the side with the smaller eye to fill the shared liberties. The smaller eye is the attacker, F = S, and the formula applies.

So there it is: difference in eyes? weaker side is the attacker, same eyes? more exclusive liberties is the attacker, F = S if the defender has an eye or S=0, S-1 otherwise, attacker succeeds if Δ >= F, and need not move unless Δ = F.

If the attacker fails, two outcomes are possible: seki and death. If seki is possible, it will happen. Seki is possible only if the eye status of the two groups is the same and there are enough shared liberties: two for eyeless groups, one for groups with eyes. Otherwise, the attacker loses everything.

So that's it: the standard workup of capturing races. Next, to extend it to three or more groups, include ko liberties, and so on.