wms's Dame-Seki Challenge
wms: I have a problem, but I won't put it as problem of the month because it is not a "typical" go problem.
Lately in rec.games.go a discussion has sprouted up and KGS' implementation of Japanese rules. That jogged my memory about something I thought about a while back, but was never able to prove one way or the other. It occurred to me that it might make a nice problem for people interested in go oddities.
The problem comes from KGS' seki detection code. The goal of the KGS seki detection code is to always correctly spot seki, as long as both a) all dame that can be filled, are filled, and b) all dead stones are marked correctly.
But I thought of one situation that would make the KGS algorithm have an error. I think it is not possible for such a situation to exist, but I'll put it here, and invite people to try to find such a situation, or prove that it cannot exist:
Can you find a position where one player (black, let's say) has two one-eyed seki groups separated by a bamboo joint (or similar connected-by-dame-but-can't-connect shape) of white's. If black tries to push through the bamboo joint, black will die, but if white tries to fill one of the "gap" dame in the bamboo joint, then white will suffer some problem (either dying or allowing one or more black seki groups to become fully alive).
If anybody can find such a board position, then it will be interesting, and I will have to adjust my seki algorithm. If somebody can prove it can't exist, then that's great, my algorithm is fine.
If you want to know more about the algorithm itself, just use google to search rec.games.go for the terms "shubert" and "seki".
wms: OK, to help things along, here is an example position that is close but not quite there:
This looks like what I need, but note that if black plays first, then black can connect, make life, and kill white by pushing through the bamboo joint; if white moves first, white can just fill the bamboo joint and end up killing both black groups. So this isn't even a seki at all, but it shows what I need - two one-eyed groups, separated by dame. I need a position like this, but where neither player can fill the dame separating the two one-eyed groups. Or, just as good, I need proof that in such a situation, one player will always be able to fill the dame.
impu1se: I think something like the second example under number 4 in StrangeSekis is what you're looking for. wms: No, #4 in strange sekis doesn't match - the two one-eyed groups are opponsing colors, so "connecting" them won't give a living group.
Like this? Neither can attempt to make a move inside the bamboo
Because if you want them to have eyes it's clearly impossible as filling the dame and connecting would saperate the other 2 killing them... <- That's if I understand you correctly. Because 2 eyes always win vs anything else... And an eye wins vs none providing there aren't enough outside liberties - But if there it wouldn't make sense in the first place...
wms: The example above doesn't work, KGS/CGoban scores it perfectly - there is only a single one-eyed group. Again, look at my example above, the key thing is two one-eyed groups of the same color, connected by dame that neither player can fill. You say that it's clearly impossible, but I don't see that; my point is that filling the dame must be impossible. Don't forget, when you fill dame, you also under certain circumstances reduce your liberties - so there are cases where dame simply cannot be filled safely.
firefox04?: Wms, in your example, what if B attempts to capture the 2 stones?
- wms: Then white dies. :-) That's why my example isn't a solution, but it's just an attempt to show what I am looking for.
- wms: Annual? Well, no, but I will give a full 3 month membership to anybody who finds such a position. So try to find one!
Scatee?: Like this black has two eyes and neither black nor white can file those dames. wms: Oh, very very close! The only issue here is that the two black one-eyed groups must be able to reach each other through the seki spaces. But this really is very close.
yoyoma: Can't white choose to kill either the two top groups or the two left groups here? When he starts to kill the left groups, the top ones can connect and live, but that's still better for White than leaving it as seki right? Same comment for Position 2.
yoyoma: But wms is looking for situations where neither side wants to add a move. Here White wants to add a move to kill the two left groups, instead of leaving them as seki.
Bill: I think this one does, too, but I like the first one better. ;-)
seldon: But both players will very much want to play there, white to kill all, black to save at least one group:
seldon: Note that if black 2 at 3, white a. black can't make two eyes with the lower group, and white has two liberties to win the semeai.
seldon: If black goes first, white is short one liberty to kill both, so one black group (the lower, since it's worth less) will live.
Bill: OK, here is position where neither player wants to play first by territory scoring, since it makes a difference of one point. (To prevent seki, White will have to play first before ending the game.)
wms: Very interesting, Bill. But it seems to me that by territory scoring, it is better for White to play, killing two of the black groups, letting the other two, live, right? If white does nothing, then nobody has any points. If white kills two groups, then white gets 22 points (kills 10 stones, gets 12 territory) and black gets 2. So really this is just an unfinished position, White needs to take the last 20 points profit, right? Yoyoma had my intent correct - sure, you can construct a position where if players refuse to move, then you get a weird seki that CGoban will score incorrectly. But I'm looking for a position where all moves with nonnegative value have been played, but cgoban still scores incorrectly.
Bill: In this position neither player wants to play in the same sense that neither player wants to play in three points without capturing. Letting the other player play first is worth a point. By Japanese scoring, White needs to play here to avoid seki, but that is an artifact of the rules. By other territory rules, such as Lasker-Maas or mine, the players could agree to the score at the end of the game or play the position out in the encore. (I do not think it would be played out under the Japanese '49 rules, either.) All moves with non-negative values have already been played.
These examples were based upon your suggestion that White's killing the two one-eyed Black groups might allow another Black group to become fully alive. IOW, if White has one less liberty that group can become fully alive. But Black can enforce that (or full life for the disconnected groups) himself by playing a dame which threatens to connect. If Black does that, it may cost a point for losing the played stone, by comparison with White's killing the two groups. Such a position is going to be like these, where by Japanese scoring White does better to kill at the very end of the game than to allow seki.
For White to be able to kill when Black attempts to connect, White needs two extra dame (possibly including a dame in an eye or false eye). Therefore killing immediately leaves these White stones with at least three dame. These stones cannot be killed. If reducing the dame to three allows other White stones to be killed to offset the loss of the Black stones, then there seem to be two cases.
1) They must be disconnected from these stones and if Black fills one of the extra dame the White stones cannot connect because of connect and die. In that case Black can fill that dame anyway, and if White connects all the White stones will have only two dame and Black can kill.
Comme ca. But this cannot be seki, either.
2) The other White stones cannot connect to these White stones, and White shares the extra dame with other Black stones. And killing the disconnected Black stones means that White cannot fill both of the shared dame with the other Black stones. That is, those Black stones gain a dame. That allows Black to capture or kill the other White stones. But since there are two shared dame, Black can do that, anyway (possibly by attempting to connect and taking away a White dame), at the cost of allowing White to kill the disconnected Black stones.
If Black can make the kill without sacrificing another stone, there is a seki only when the mutual kill produces a local score of zero. IOW, the seki is unstable.
Can he do so? Say that he tries, and White fills one or more shared liberties to prevent it, finally reducing them to only one. Now Black can play in the bamboo joint, reducing White's liberties to two and killing the White stones unless White can put Black into atari from the other side. But we know that that is impossible, because Black could effect the kill by playing in the bamboo joint to start with. All we have done is to transpose moves. So Black can do so, and any seki is unstable.
(Later): No, there's a flaw here. White now has the option of killing the other Black stones while allowing the connection. White may not be able to do that if Black starts with threatening the connection. :-( Still, we're close to a proof or a construction, I think.
(Still later): Hmmm. In this case, where Black's attempt to kill the other White stones fails without reducing White's dame by attempting the connection first, can White not attack Black from the other side, forcing Black to make that play, anyway? The result could be an exchange, dissolving the seki, or life for both, leaving a seki in between. In either case, the seki is unstable, no?
wms: I'm not sure I understand all of your reasoning, Bill...a lot of the time you talk about "the black group," etc., when there are several black groups in the diagram, and I'm not sure which one you mean. The reason why I only care about Japanese in this case, and not other territory scoring rules, is because I'm really trying to determine whether or not KGS/CGoban scores games correctly when all nonnegative points are filled. Since Japanese is the only territory scoring system that KGS/CGoban supports, it is the one that is of the most interest to me :-). But your position was very interesting, because it does have the case where white killing one pair of black chains lets the other pair of black chains go from seki to a living group.
What if both of the pairs of black chains each had another white group behind them, where if the pairs of black chains became completely alive, they would be able to kill the "back" white groups? Then white will get 22 points by killing two of the black chains, but then black gets two points (for making life) and x points (for killing a white group that was in seki before the black stones made life). Would that be possible? In that case we may indeed have a position where for white to move costs white points (by letting black make life, and kill a large white group), but for black to move costs black points (by letting white kill all the black seki stones).
Mef: wms - Is something like this what you were thinking of? This one doesn't quite work, since B connecting just makes another seki, but I'm sure Bill can come up with something....
Bill: I think I can streamline the argument for the case where the question is the life of other White stones ( and friends)that cannot connect to the main White group vs. full life for the Black stones in the corner. That involves a possible semeai between the group and the intervening Black group ( and friends).
In that semeai Black has 3 external liberties, because White has to play (or the adjacent point) before playing . (If White plays right away kills.
There are 2 shared liberties between the main White group and the group. If there were N shared liberties, the group would have N+1 liberties for the semeai.
One condition for seki in such cases is that enables Black to win the semeai. Actually, it reduces Black's liberties for that semeai by 1. So these cases cannot be seki.
To recap the argument, there are three cases.
1) Where White's capturing some Black stones (by playing on one of two potential connecting points) allows others to make full life. Example: Position 3. Such cases may be seki-like, in that the position can remain on the board with correct play until all the dame are filled, but the local score is in White's favor, and, by Japanese rules, White must play them out to get that score.
2) Where White's capturing some Black stones as above allows some White stones to be captured or killed because they can no longer safely connect to the main White group. Example: Position 4. These are not stable seki, because
a) Black can threaten that connection earlier (as in the example), or
b) if Black cannot afford to threaten that connection because it reduces one of Black's libeties, White can connect and take away that liberty earlier.
3) Where White's capturing some Black stones as above allows Black to capture some White stones that are separated from White's main group. Example: Position 5. But that capture cannot aid Black's capture of the other White stones because it takes away one of Black's liberties of a Black group adjacent to White's main group.
Conceivably there are more complex positions combining these elements, but they will either be unstable, or if stable, positions that White should resolve at the end of the game to get a favorable local score.
1) Where White's capturing some Black stones (by playing on one of two potential connecting points) allows others to make full life. Example: Position 3. Such cases may be seki-like, in that the position can remain on the board with correct play until all the dame are filled, but the local score is in White's favor, and, by Japanese rules, White must play them out to get that score.
wms: Can you explain why the local score is always in white's favor in such cases? This is what I keep getting stuck on. Let's say there are some small black groups, and some big ones. We've all seen cases where black can choose which to save - the small or the large. Can there be a situation where, when white tries to capture one of the groups, that reduces white's liberties in a way that gives black the choice on which to save - but if black maves the first move, trying to bring his groups out of seki, that gives white the choice on which black group dies? I can't find such a shape, but I can't understand why it is impossible either - and if such a shape existed, then the local score might not be in white's favor, it might be better for white to leave everything in seki.
Bill: Let me see if I understand the problem.
In this position White will certainly choose to kill the Black groups on the left rather than on the top.
But what if there were some position where White cannot choose to kill those groups, but only the groups on the top. And in addition, Black cannot save those groups, but only the groups on top. Then that would be a seki. Is that the problem?
If so, how does Black save the top groups? By threatening to live with the groups on the side, which White kills. But if Black cannot make them live, even with the move, surely White can kill them, given the move.
But maybe that move does not kill, but only preserves the seki. But that move has prevented the larger, left groups from making full life, possibly at the cost of a liberty. White still has at least three liberties left, and can kill the top groups, wiping out everything. If White has only three liberties left, however, Black can connect the top groups, killing White unless White kills the left groups. The White move does not preserve the seki.
Scatee?:Cgoban counts circles as points.
yoyoma: The two central dame can be safely filled by either white or black (the other player will respond by filling the other). Then Cgoban will score it correctly.
Notochord: I think that you have laid all the necessary ingredients on the table. Would this beast work out? If either side tries to take one of the sets of groups in exchange for the other, he ends up getting a group that is devalued. If black tries to take the four stones instead of connecting, white gives atari to that group, and plays up top, taking three groups out of four (or if Black plays on top, White gets an extra captured black stone on bottom). If White tries to approach by adding to the four, he is just captured, not a hair to Black's loss. I may have done poor arithmetic here, but we have the freedom to add or subtract increments of two to the score here (by adding white/black stones to the dumplings). Also, I assumed that kgs doesn't penalize for having more stones in seki than the other? If not, our degree of freedom can still be brought to bear, I think.
wms: Very, very, interesting, notochord! I worked it out, I get these options:
- Both players pass: B+158
- Black tries to connect: B+157
- White tries to kill: B+158
So you have a situation where black would prefer to let the seki stand than connect through and settle it. For white, it is basically just a huge ko threat - there is no profit or loss in trying to settle the seki. I tried tinkering with it, and I could shift who gets to treat it as a ko, but couldn't make it -1 for both to play first. I'll have to look at this and see how it matches what arno and bill have been saying - maybe (probably?) I'm being thick, but I just keep seeing assumptions in their arguments that I don't see as being clearly true. This looks close enough, if it can be tipped one more stone, then maybe it could be bad for both to move first while keeping the bamboo joint connections.
Notochord: I read a score of zero (outside aside) if both players pass, since all the stones seem like they would then be counted in seki (does the eye of a group in seki count?). The difference between 'White tries' and 'Black tries' seemed to be that in the first situation, White must play three times on his side: once to cut, once when under atari and once to prevent the group surrounding the four stones from living (to touch the group surrounding the four stones is suicide for White's big group). If Black tries, then he ends up playing a stone on white's side in place of the third white stone, and so black is two points worse off than the situation when White makes first move, leaving room for one score to be positive and the other negative.
Bill: Very nice, Notochord! :-) By adding a couple of White stones you can even get a positive score for Black inside the seki-like complex. You exposed my error.
wms again: On second look, it looks like in this case, black must connect through. If the situation stands this way at the end of the game, then all the black stones in the "seki" die. Am I right? Because White can choose which to kill (either the top two black groups or the bottom two black groups), and by japanese rules, that means that all four of the "seki" black groups are dead at the end of the game! That changes things a lot, I hadn't thought of how that affected this challenge...suddenly it becomes trickier.
Bill: Bill, I think it's OK. Whichever Black groups White chooses to kill, doing so enables new Black stones to arise on the board that are alive. So White's claim that all of the Black groups are dead does not stand.
I was wrong about the local score being in White's favor. But I think that this kind of position (a choice of Black groups to be fully alive) still does not have to be considered seki. The reason is that the score remains the same under area scoring, even though there is a one point difference by territory scoring, depending on who plays first. You could get a greater difference if there is a ko involved, but you are not contemplating that, are you? If you are, maybe we can construct something with a two stage ko.
wms: I'm pretty sure that in fact all four black "seki" groups are dead in the given situation. There have been several variations of Japanese rules of course, but in general at the end of the game white can claim the top stones are dead. To prove it, they play it out, white kills the stones, proving his point. Then the board reverts back to the position before playing it out, but the stones (although replaced) are still considered dead for scoring purposes. Then White can claim that the bottom stones are dead, and prove it in the same way. Thus all the black stones are dead. Note that black can only claim that the two four stone groups are dead; and in that case, there is a dead white group inside a dead black group, so the territory is white anyway.
And you are right, I do not want kos involved! Kos are always either resolved at the end of the game, or are some form of eternal ko, in which case the score just doesn't matter because the game has no result at all.
Notochord: I'm no ologist of rulesets, but I think that this makes the task trickier in the infinite sense. One could probably (with nontrivial difficulty, no doubt) prove from first principles that no such "can't connect through open gap" seki can exist, since the (should I say topological?) space that we can work with becomes so much smaller; no back groups within black's seki groups, really, PLUS more restrictions. I think that if this is the case with the japanese ruleset, then you can probably either eek out the cogitation (or the petition to a math major) to prove, or much easier, very confidently go without proof that your code works fine. Or say very extremely confidently that the probability of such a position arising to be miscored (without co-operative play) is on the order of your server mistakenly flipping a bit and miscoring, or worse (better?): game can't be scored on account of end of the world :-)
wms: Notochord, I made a mistake in my analysis. I forgot that white had to make the bulky 5 shape to kill a black group on the top or bottom (middle of edge) after cutting! So you are right, in that assuming this is a seki, then we have exactly what I asked for - a seki situation where we have two one-eyed groups separated by bamboo joints! It really is a very clever solution, I couldn't find anything like it. And you have demonstrated to Arno and Bill that in fact, it is possible, despite their reasoning otherwise. I am prepared to give you a 3 month KGS Plus membership in return for answering my puzzle, if you wish. :-)
"Notochord: I believe that I wish :-) Thanks, wms! (My KGS account is under the same name)"
However, it seems that the KGS scoring system is probably safe, which is also good news! There are two reasons why Notochord's amazing position doesn't break the scoring system:
- As discussed above, I'm pretty sure that in fact black must play in this position, sacrificing top or bottom to connect through, or else by Japanese (fairly convoluted) rules all 4 groups are dead.
- Even if that isn't necessary, KGS will score correctly, because the white groups inside the black eyes are alive. The KGS scoring system would consider the black groups to be fully alive if they had eyes with no living stones inside. In this case, black cannot kill the stones in the upper left and lower left corners, and thus KGS will not get confused.
I'm pretty sure now that the KGS scoring system is "safe". I think that issue 1 above keeps it that way - the only way I can imagine such a situation is where you have two of these "connections" and cutting one will let the other live. As long as it is possible for one player to choose which side lives and which dies, by Japanese rules, the non-choosing player will have to play to force a choice to be made or else lose both sides...thus one of the players should keep playing in the position until it is no longer seki.
But although I'm 99.9% sure that the score system is safe, I could be wrong. :-) I will happily give out another KGS Plus membership if somebody manages to find a position which fixes the two issues with this one...or if you manage to fix issue #2 and if you can show that I am mistaken about how Japanese rules work in a position like this.
By the way, there are several bestiaries of weird seki floating around. It's fairly abstruse, but I'm pretty sure none has a position like yours, so I think you have truly invented something new here. :-)
Bill: Congratulations, Notochord! I misread the position, too.
I overlooked the Black pass after . Within the broken seki Black has 48 points, White 47.
Notochord: I think that at least under Japanese scoring, having capture will force White to take a loss. Black holds the prisoners in his hand, so I think that White will be better off breaking the seki, going from a position valued at +5 because of the prisoners to one which is the same as if White began with , except for the addition of a black and a white stone to either Black's or White's territory, which cannot alter the score: +1. I think that there might be some trickyness here, too? If White passes after capture, then Black should pass, too, since if he plays at the center of the eyeshape to live the group, White can then settle the shape so that by tewari, Black has played a superfluous move inside her own territory: +1 -1 = 0.
Notochord: Sorry if I'm not being clear. What I mean is that the capture should force White's hand in settling the seki. If Black passes, then can't White pass too and leave it as seki :+0? Or am I not thinking of the correct rules? There seems to be nothing flawed (from the is-it-seki standpoint) in passing since the onus is still on White to gain something, from moving first, but wouldn't capture be the optimal response?
Bill: Thanks for the clarification. I thought you meant a loss by comparison with the diagram.
If Black plays first Black still gets 48 points, but White gets 49.
Neither player can afford to play first, so it is seki. :-)
wms, take a look at the first diagram. White indeed can kill the top groups of stones. However, that allows Black to play two new live stones ( and ). Therefore the Black stones on the top are alive. Similarly for the Black stones on the bottom, if White killed them.
Here is the relevant clause:
Article 7. Life and death 1. Stones are said to be "alive" if they cannot be captured by the opponent, or if capturing them would enable a new stone to be played that the opponent could not capture. Stones which are not alive are said to be "dead."
- wms: I think I've seen translations or interpretations of this that indicate that by "a new stone to be played" they mean as a replacement for one or more captured stones. So for example, in a standard 2-stones-take-1-enemy-stone-to-become-empty-triangle-in-atari snapback, the single stone is alive - if it is captured, then it can be replaced with an unkillable stone. In Notochord's example, the unkillable stones are not replacements for captured stones, so they don't help black.
One official example is this seki.
The stones are alive because if White captures them,
Black can play two new stones, and , that are alive.
I'm not sure what you mean by issue #2. Do you mean the KGS scoring system getting confused? Can it handle Notochord's example plus the next two slight variations?
wms: Whoever wrote this, I don't know what you mean when you say you don't know what I mean. :-) It is quite simple. For KGS to become confused, you need a position like notochord's, but with no living stones inside the seki eyes. The positions you give don't even seem to be at the end of the game - you talk about one player or another having to move - so they don't matter at all.
Bill: Does the KGS scorer require that the players make all necessary protective plays? Thanks.
wms: Not sure what "all necessary protective plays" means. What is a protective play? To guarantee correct score, KGS requires you to fill all dame that can be filled without costing you points. 99%+ of the time, you don't even have to do that, but if you try to score a game on KGS and see that (after correctly marking which stones are dead) it misjudges false eyes, then you press undo, fill the dame, then score again and it will be correct.
Bill: So if those dame are filled, the only stones remaining with dame are dead or in seki. And the dead stones should be marked, right?
wms: Yes, but interestingly enough, you cannot always spot seki groups by dame! There are cases where a chain in seki will have no dame directly bordering it. Instead it will have a false eye separating it from the dame.
Bill: Right. But then can't all of these examples be recognized as being in seki because of the dame?
wms: Perhaps, but that isn't the algorithm I use. I count eyes instead. The problem with saying "dame means seki" is that then you must fill all dame to have any hope of a correct score, which would irritate a lot of players who would prefer to spend as little time as possible filling dame. So I count eyes instead, which means you only have to fill dame points if they are in a bamboo join or other such position.
- wms: "wms's" is correct if by "wms" you mean my full name. If you mean just my initials by "wms" then "wms'" is correct. I don't think it's a big deal.
- (Sebastian:) That raises the question: What characterizes you better? ;-)
- wms: It doesn't matter. I answer to both. "Bill" is fine, and is what people actually call me, but "wms" is more explicit I guess since there are quite a few othel Bills who play go.
Arno: I don't know if the following is a proof that such a position cannot exist, but maybe it is a hint for other people:
As far as I can tell these are the only possible postions, as the requirement says: two dame points which have the potential to connect the two black groups.
- let' call the concerned groups , (the one eyed seki groups) and , (the surrounding white groups on either side of the dame points); for here onwards dame refers to the critical two dame points in question.
- by definition each group has at least two liberties:
- , have at least two liberties: one liberty which is dame, and one eye
- , have at least two liberties: one which is dame and at least one other liberty (otherwise they are in atari and Black just captures).
- If Black moves from or
- the liberty count for / is not reduced (the filled dame has at least one more liberty adjacent to the other B group)
- White loses a liberty of at least one of or .
- White has to move on the other dame in order to prevent Black from linking up and making life:
- Black loses a liberty on each group , .
- Either White's play connects with or the W group (the one from which the move extends) loses a liberty.
- As we look for seki the position must now satisfy: liberties( or ) > liberties( or ) (otherwise Black can capture one of the two groups , and thereby connect both of his groups, as / are cutting groups in regard to /)
- or to be more exact in the initial position (not counting the dame points!):
- bamboo joint: liberties(+) > MIN(liberties(), liberties()) (+ denotes the connected group)
- diagonal joint: MIN(liberties(), liberties()) > MIN(liberties(), liberties())
- With the result from above, let us assume that White moves from or first:
- as White has more liberties she can just fill one of the dame points and kill one of the Black groups (the one with less liberties) and therfor the other one as well.
So is this a proof? I don't know. Maybe I have overlooked something?
wms: You assume that white having fewer liberties than black means that white can always be killed. I'm not sure that is the case. If white has outside liberties which are part of another seki position, then it is possible that black cannot fill all those outside liberties, in which case and/or might actually have fewer liberties than and/or , but it will still be impossible for Black to capture. Am I right? Or is there some reason why this is not possible? Or is it possible but irrelevant for some reason?
Arno: I would argue that it is not as you mention: if the white groups are caught in another seki, then the liberties of Black and White groups there must be equal. If you play the dame, the liberty count for White reduces (by 2 in case of bamboo joint, by 1 each in case of the diagonal joint), so the other seki should get destroyed as well and Black can start filling liberties, no? I know my train of thought sounds to easy to be true. I also have doubts that it is that easy.
On a side note: unless / are caught in another seki, White can always play as to reduce / to two liberties. This is because, by definition (no seki) White is able to surround / completely. This raises the bar for the sought after freak position (some sekis interwined): as / cannot be caught in another seki with less than two liberties this means that / have to be in another seki as well. Sounds ever more impossible.
: not really equal as that seki might not have been played out. But in that case, Black should play out the seki first (i.e. play until there are no more moves that would keep the position a seki) before starting on the dame points.
aib: If black has two one-eyed groups, then connecthing them will result in unconditional life. For black to get in trouble when attempting to connect, white has to play (inside the dame). However, it has already been proposed that playing inside the dame damages white (else she would have already connected). Thus white cannot prevent the black groups from connecting and getting life.
This would explain why the closest we've been able to get is with two dames (diagonal empty spaces as in Scatee?'s example).
As long as black has a clear path between the two one-eyed groups (i.e. a dame), a black move will not change the situation (i.e. will always result in at least one liberty). Thus, black will always be able to connect.
Does that seem logical? It does to me.
Imagist: The situation in the top left is a seki in which neither player benefits from playing a. If black plays a, black loses the game by 1.5 points. If white plays a. black starts a round robin ko which ends in no result: a failure for white. Therefore neither player plays a and the top left is seki.
wms: Imagist, it is a very interesting position, but white must play at a or else lose their group. In Japanese rules, the white stones are dead since black can kill them (with no kos involved) by moving first. If white plays a, however, then as you point out a round robin ko forms and the game is scored as no result (which is better than a loss for white). So it is not a seki.
RobertJasiek: Since life and death or ko problems are in EXPTIME, the complexity of detecting sekis won't be easy enough for any algorithm. The research of all possible seki shape classes has just started. In this context, claims that a server scoring algorithm could possibly be always right are absurd while the intention of any server scoring ought to be being 100% correct in all possible positions. - Something that is locally not a seki can behave like a seki globally, e.g., a pair of anti-seki and its colour-inverse anti-seki. Similarly, a multiple ko situation can remain on the board until the end of alternation when its colour-inverse double is also on the board, the local score on the rest of the board equals the negative of the komi, and the players want to end the game in the fewest number of perfect play moves, i.e. just successive passes. Then there are sekis involving groups without any dame, as discovered by Matti Siivola.
wms: Robert, you make claims here that you do not back up. Please provide a shape where all dame are filled, dead stones are correctly marked, and the KGS seki system does not correctly find the seki. In 8 years of operation no such shape has yet been brought to my attention.
RobertJasiek: I have not claimed that KGS has already made a mistake in finding sekis (this is unlike the teire thing). What I have claimed is that KGS cannot detect all theoretically possible shapes should they ever occur in a game. Above I have given some example classes that KGS would likely not detect, but of course each of them is extremely rare.
wms: Robert, you have named shapes that you think it will make a mistake on. Please provide an actual board diagram. I do not think that it is possible to construct a shape which will make the KGS algorithm make a mistake. And to be clear: "mistake" hear means marking a board location as territory, when it is actually in a seki, and thus not territory at all.
pwaldron: I put the second of these examples into CGoban, and it treated all the white groups as being in seki. According to the scoring algorithm in the offline CGoban, black wins by 4 points.
wms: Gaah! The page on suomigo.net is totally broken in my browser (firefox 1.0). The diagram shows me only one half of one column of stones. Could somebody either copy it here or email me a screen shot at firstname.lastname@example.org so I can check for myself?
wms: OK, I tried lynx and was able to view it. pwarldron, I assume you marked no groups dead. In that case, cgoban is 100% correct. All white groups *ARE* seki if the black groups are all alive, so it seems that my seki detection algorithm is still undefeated. :-)
- pwaldron: You are correct. I just turned on the scoring mode, and CGoban, which I assume implements the KGS seki detection offline, claimed that only the two two-eyed black groups had territory.
Bill: FWIW, I think that the White stones without two eyes are dead according to the Japanese '89 rules. They might be seki under Jasiek's '03 rules, however.
RobertJasiek: wms, I have sent the shape examples to rec.games.go. If you publish the KGS seki algorithm, Harry Fearnley will give you a counter-example, I'd guess. Until then, may I doubt the algorithm's existence? :)
wms: Robert, the algorithm is visible to anybody with cgoban! I have also described it, and in addition a (mostly the same) algorithm was in cgoban 1.0, which was released under GPL. It is very simple. All dame are considered "grey" space, which both white and black can connect through, but which provides no liberties. Then any groups with only one liberty must fill their remaining liberty (this is when false eyes are filled). Then I count eyes. Groups with 1 eye are subject to a very simple pattern matching system to determine if the space can be split into two eyes. Dead stones are treated as "empty space" until the final pattern match; note that a three-space eye can be split into two *unless* there is a dead enemy stone in the middle of it, for example! The end result is that all living groups with zero or one eyes are found and considered seki.
As for r.g.g., I don't visit there any more. But we'll see if Harry Fearnley can come up with something?
IanDavis: As Robert uses KGS i don't understand why he doesn't submit the shapes he believes defeat the algorithm. if he can't be bothered too, I'm not really interested in listening. :)
RobertJasiek: "Using KGS" is very different from "testing KGS's seki algorithm", "testing ScoreEstimator", or "testing CGoban's scoring" (I do not know which of the latter two might use the KGS seki algorithm.) The first two are very different because, when playing, only boring standard seki shapes (or the capturable-2 corner seki) occur. Generally playing practice does not create the obscure seki shapes. My criticism about KGS's seki algorithm has not been to guess correctly in 99.999% of all played games (ignoring the much more frequent teire failure here) but to fail assuming 100% correctness on a theoretically proven basis. - What do you mean by "doesn't submit the shapes"? I have submitted them on RGG. If you wonder, why I don't submit the shapes here(!), it is because editing and saving go diagrams here consumes more time than I have and because only some types of diagrams can be created by editing here at all. - If you can't even imagine a triple-ko and its colour-inverse on the same board, without seeing a diagram, then that cannot be helped. Since wms has said something that such would lead to no-result, it is already a counter-example of his algorithm, which should at least offer pass-pass as a valid strategic alternative.
Herman Hiddema: In reading the discussion, there seems to be somewhat of a misunderstanding regarding the algorithm. You suggest above that it should offer pass-pass as a valid strategic alternative. But the CGoban seki algorithm is not meant to offer suggestions of play. It is a scoring algorithm. It requires that the players agree on which groups are alive (possibly in seki) and which are dead. Once it knows which groups are alive and dead, it then detects whether alive groups are alive in seki, and if so does no reward any points for eyes those groups might have. Note that any statements regarding the fact that life/death/ko problems are EXPTIME are not directly relevant with regard to this algorithm, as the algorithm requires human input on life & death status.
RobertJasiek: The pass-pass has been meant for hypothetical analysis as part of the seki detection algorithm only - not as actual play. - I am not whether your guess about the assumption is right that the algorithm presumes the players to have removed all dead stones (and then there is the additional assumption whether they would have removed all dead stones from sekis, something that is ambiguous under KGS-Japanese Rules). wms should tell us what exactly are the made assumptions when the seki detecttion algorithm starts to apply.
Herman Hiddema: He stated in the third line of this article: "The goal of the KGS seki detection code is to always correctly spot seki, as long as both a) all dame that can be filled, are filled, and b) all dead stones are marked correctly.". My presumption was not that players had removed all dead stones, just that they had marked them as dead. This is the definition given here by wms. Reading the rest of the page, I think the further assumption is made that: There are no moves left for either player that will gain that player any points. So the algorithm may fail on unfinished positions.
Harry Fearnley: Thank you Robert for volunteering my services. :-)
Where can I get a printed copy of the explicit algorithm (maybe C code)?
If I have a seki position to test, is there a way for me to type in the position to a computer, and then have it checked by WMS' algorithm?
Herman Hiddema: Enter the position into CGoban3 (or load it from an SGF file). Mark all dead stones as dead, then ask CGoban to score the game. If you can find a position where points are awarded inside eyes of a group that is alive in seki, then you have found an example for which the algorithm does not work.
Harleqin: How do I ask cgoban to score? There is no such option when editing or demonstrating.
Herman Hiddema: Upper left corner. Change Tool to Score Tool.
wms: I want to say that Herman Hiddema is correct in both points. The score tool will use the seki identification system. And his description of the requirements to ensure it correctly spots seki are very close, but not quite: He wrote that you must play until there are no plays worth points left any more, but in fact, in some cases you must fill the dame in the game also (this is really only necessary when there is a bamboo joint dame or other shape where filling will change the connectedness of groups).
Herman Hiddema: Actually, that's already mentioned in the bit I quoted from the start of the page (condition a), I just expanded on that to prevent some unfinished positions. :-)
walleye: Since KGS's scoring algorithm tries to find the teire, would it not be nice and natural to allow the players to unmark some of the points that the algorithm identified incorrectly as territory. I understand the players could simply add stones on those points, but it would be more natural to just unmark them and click 'Done'.
walleye: There is another practical reason why I want to be able to do that. Sometimes I load pro games, which I want to be able to score without adding any new moves or changing anything. Since professional players usually leave all teire unfilled, the only way to score the game correctly without changing it is to unmark some empty intersections.
Harry Fearnley: It is possible that Robert Jasiek was confused -- I certainly was at first. I had not read the specification carefully -- sorry WMS! WMS's algorithm relies on the humans first marking all dead stones as such. There are 2 consequences of this:
1) Obviously, the humans should do this correctly for his algorithm to be guaranteed to behave properly.
2) I am very interested in seki in which either, or both, players may be able to capture stones (perhaps on the next move), but do not do so because they then will lose more than they gain. Recognising that although a stone _can_ be killed, it should not be, is a tricky, and potentially very skilled, function. What I would like, and perhaps what Robert expected, is an algorithm which _recognises_ sekis like this, without being told which stones are alive/dead ...
Maybe the interesting remaining possibilities reside in groups having "common" liberties but which (in some sense) have different values for each player -- see Figs 6a and 6b in my paper "Shared life in Go -- an overview" at http://harryfearnley.com/go/seki/overview/overview_full.pdf
wms: Yes, clearly identifying dead stones is itself incredibly difficult. As for commen liberties with different values - I think that will not bother my algorithm, it will properly see each group in the area as alive, no 2-eye groups, thus seki.
QWerner: I think the question is wrong. You say, black has two one-eyed seki groups...than some other conditions. You surge an example where one of the both groups could live. This position can not exist. Asume you finde a position where one of the two groups get live, but this means one of the groups was not a seki. Dont get confused by miai seki groups in a position with mirror symmetry, but this is not seki.
Anonymous: If any of you guys want, why don't you guys just make it public instead of in SL. That way we will get the answer faster.
EliDupree: If we had a superko rule, we could abuse that. Simply construct the position (something like the very first example position on this page), have Black push the joint from one side, then have both players play in their own eyes until all the stones are captured, then construct the position again - repeat this three more times so that black's other intrusion and white's two connections can't be played.
Neither player can play either marked move because of superko, and the only other possible moves are huge losses (playing in their own eyes and getting captured).
It's harder with the Japanese rules, though. Here's the best I can come up with. White just captured in the ko, and then passed. Black's only legal moves would be self-atari, so black also passed and the game went into the scoring phase. White still dies because of the scoring rules, though.
And... Aha! Here, two one-eyed groups are in seki, and could connect, but would be better off not to." White can connect the two white one-eyed groups by capturing at the marked point, then recapturing it after black snapbacks the four white stones. This would also allow white to capture the two black one-eyed groups, but doing so loses the whole top, which is worth more points and which would otherwise be seki. Black playing there first loses the whole corner with no compensation. So the entire position is seki. (Adapted from the hane-seki example in https://www.cs.cmu.edu/~wjh/go/rules/Japanese.html ) I'm pretty sure this plays nicely with the Japanese rules on life and death: White can force the capture of the two black one-eyed groups, but "capturing them would enable a new stone to be played that the opponent could not capture" (in the top left), so they are alive in seki like the other groups. This isn't quite like a bamboo joint, but the marked point is a dame and does connect the groups if played.
I'm also working on a proof that it can't be done with directly connected dame, but it involves some fairly sophisticated math...
EliDupree: Verdict: There's no such proof, because it's possible. Here's the position.
The black clump in the middle is dead if scored as-is, and everything else is alive (some in seki). The score is 64-6. KGS/CGoban incorrectly says 64-8.
If Black moves first one of in the marked dame: White plays the other, which double-ataris the one-eyed groups. Black gets one corner but loses much more (164-43).
If Black moves first to force a connection by sacrificing two corners: It works, which is bad for Black. White captures the black clump in the center while black connects (95-12).
If White moves first in one of the marked dame: Black sacrifices two corners in sente and then fills the other dame, and the black clump in the middle lives in seki (40-12), or possibly White ignores one of the corner moves, giving up that corner to capture the center (79-45).
If White moves first to capture the black clump: Black connects through the marked dame (62-8).
If White moves first in a corner (threatening to atari a black one-eyed group by playing in the dame): Black sacrifices another corner to save that group. Black gets one of the corners and connects through the dame while White captures the black clump (85-48).
Anon: Interesting position. This is a temporary seki though, isn't it? If White moves first, White wins. If Black moves first, White wins. So can it be said that all the neutral points have been filled? Frankly, I am not sure. :)
EliDupree: Okay, then add a komi of negative 58 points. Now it's a jigo that neither player can deviate from without losing.
EliDupree: Or since we're using Japanese rules, use 0 komi and make black have 58 prisoners. Or 6.5 komi and 64 prisoners (then White is winning but loses with any further play).
evdw?: Nice, seems like you've solved it! I'm still a bit confused though. Why exactly do you say "The black clump in the middle is dead if scored as-is"? I thought it is also in seki.
EliDupree: Oh dang, it's not dead, is it. White can force capturing it, but if White does, then Black can place unremovable stones in the dame. I'll have to rethink this. (edit:) I've figured out how to fix it, but it's so hard fitting all these live groups into a 19x19 board! I was lucky it worked the first time! I'll get there...
Okay, got it. Unfortunately, in this version, the only disadvantage white gets by moving first is the one point loss of the move itself - since it's a one point difference, ideally, at least one of the players would lose no more than 0 points by playing, so it's not the strictest possible seki. However, it's still effective at causing trouble for CGoban. Here's why:
With no komi and no prisoners, this position is jigo; all groups are alive, mostly in seki. However, CGoban incorrectly scores two of Black's one-point eyes, so Black appears to be two points up. If Black plays sacrifice-two-corners-then-connect, then that results in a jigo that CGoban will recognize. If White plays first in the dame, then White loses by one point.
In short: According to the true rules, White loses 1 point by playing (and Black loses 0). According to CGoban, Black loses 2 points by playing (and White gains 1). So if this situation arose in a real game (pfffff ha ha ha ha ha ha ha *choke*), it's likely that neither player would continue and so the incorrect score would stand. And I think a lot of players would (rightly?) balk at the idea that you must sacrifice a bunch of stones to capture a bunch of other stones at endgame, just because it doesn't lose you any points and is irreversible. (Compare double ko seki, where swapping the kos doesn't lose you any points and is reversible, and certainly isn't obligatory.)
I'm going to keep looking for a situation where both players would lose >0 points by playing, but I'm not convinced that one exists.
fractic: I get black winning by 3 if he plays first and by 4 if white plays first. I think you made a mistake in the endgame play with the hanezekis. After Black captures a stone, White recaptures and then Black recaptures too White will play atari on the black corner group. If at this points Black fills liberties from the outside I get the same result as you. But correct endgame play is for Black to capture the three white stones in the corner creating a semedori.
Fortunatly this can be easily fixed by making the black corner groups just one stone bigger making the cost of the sacrifice 2 points bigger for each corner.
fractic: The only change from the diagram above are the four marked black stones.
EliDupree: Thanks, it looks like you're right. I went through a whole lot of variations, including one where the stones are how you put them - I actually got to the current setup by starting with what you posted, then turning those four stones white. I guess I forgot that endgame quirk in my final run-through.
EliDupree: Was that last one not monstrous enough for you? >:)
I don't think I could build this on 19x19, but it fit on 36x36, which is within what CGoban allows.
I'd like someone to check it over - there are a lot of variations, so I might have missed something. But if I didn't miss something, then this is an inarguable solution - a seki where every possible move is a point-losing move, with the dame as specified.
The key insight (compared to my last answer) is that if Black sacrifices a hanezeki in preparation for trying to connect, then White doesn't need to make the sacrifice at (a) at all, because white can instead capture the rear group in the hanezeki Black sacrificed.
If Black plays in the dame before sacrificing, then White takes (a) and double ataris, because capturing a black one-eyed group is bigger than the cost of (a). If White plays in the dame at all, White is a liberty slower and either has to make the sacrifice at (a) (which is bigger than Black's two sacrifices together) or has to to trade the smaller hanezeki (White gets one and Black gets one), which is unfavorable to White. (That's the part I'm most uncertain about with the current position - those groups might have to be adjusted a little to punish White more for losing one. But the play sequences I tried are all lose at least one point for White, and if it doesn't quite work, fixing it is just a matter of adding a few stones, not a conceptual issue.)
I'm not sure if the outer band is necessary anymore - I put it there because an earlier version I was experimenting with needed White to have abundant, unremovable, huge ko threats. (Fun fact: That border is worth more for White than the entire rest of the board is for Black.) It could be replaced by more black stones, and possibly removed (although the surrounding black group still needs to be worth a lot of points so that white (a) is sente.)
EliDupree: Whoops, forgot I need to duplicate the outer hanezeki like the others. (Otherwise, Black (a) either captures the white loop (which saves the outside as well) or just gets the white clump without losing anything big.) This fixes it. I also made White's live groups worth more points so that the starting position is jigo, just to make it more elegant.
wms: Could we have a winner? I transcribed this into SGF and tried it out myself. See the SGF file at my web site. As the game stands, it is a tie; the question is, is there any move that black or white can make, that (with correct play by the opponent) will be break even or profitable? I can't find one, every move leads to a loss by the player who moves, the best either can do is to pass and have a jigo! I'll give it a week or two, but if nobody finds anything...EliDupree wins the KGS Plus membership and the KGS scoring system is broken! (I know a way to fix it, but I'm not sure if I'll bother; it look ridiculously unlikely to ever strike in real life. :) )
I think this is pretty amazing. It seemed everybody had decided that there was no solution...so if there was, well, a lot of smart people were wrong. In any case it's a spectacularly bizarre position!