"ross","General-Purpose Dead Stone Resolution Algorithm?","2008-10-16 22:39:43","I know this has been discussed at endless length both here and elsewhere, but I wanted to get some fresh thoughts on it with my particular use case in mind.
\

\
In essence, the question is: at the end of the game, after both players have passed, what is the best way of determining which stones are dead, and which stones are alive?
\

\
For my particular case, I'm building an open-protocol Go Server, and have gotten to the point where games can be played, but not finished and scored. To do this, I need some sort of game-end resolution protocol.
\

\
KGS (and most servers?) have a very simple protocol--both players must agree on which stones are dead. If they cannot, then the game cannot be finished.
\

\
This is a rather sub-optimal algorithm, particularly if both players are computers (and, as I'm designing my server to be primarily for computer programs, they likely will be). A Go bot isn't going to be able to \"change its mind\" about what stones are dead, so if the two bots disagree after two passes, the game will never be scored nor finished.
\

\
The other extreme is that all stones must be captured--any stone left on the board is considered alive under this algorithm. Many computer-only servers use this protocol, but I find it sub-optimal as well. Humans rarely have the patience to capture all dead stones (sometimes requiring dozens of moves) at the end of their games, and requiring them to do so seems annoying at best.
\

\
Is there a good general-purpose dead stone resolution algorithm that can be used successfully by both humans and by computer programs? Does anyone have any thoughts on what [i]should[/i] be implemented by a typical Go server?"
"xela","","2008-10-16 23:23:52","If you use New Zealand rules then it's easy: if the two players don't agree, you just resume the game.  The fact that area scoring is used means that taking the disputed stones off the board (or trying and failing) should cost nothing.
\

\
If you want to use Japanese rules, then it becomes a very difficult problem!"
"Bill Spight","","2008-10-17 00:56:59","The following is taken almost verbatim from [url]http://senseis.xmp.net/?SpightJapaneseStyleRules[/url] . For simplicity I have altered the rules for area scoring. Under territory rules the encore uses pass stones (See the SL page).\
\
Some computer programs do identify dead stones at the end of the game, I believe, and they could use the full procedure. Otherwise, they could simply play until all remaining stones are alive if they are using area scoring. If they are using territory scoring, then a single encore round will suffice, again with all remaining stones alive. \
\
[QUOTE]Article 7. Life and Death\
\
When play is paused according to Article 9.1, the players may agree about which stones on the board are dead, if any. If they do so, those stones are dead and all other stones on the board are alive. Dead stones are removed without further play.\
\
\
Article 9. Rounds, Encore, and Game End\
\
1. Rounds\
\
There may be more than one round of play. Each round ends in the following way. During the round one player (Player A) passes in a certain position of the whole board, and later the other player (Player B) repeats that position. The repetition may occur by a pass or by a play. The repetition need not occur on the next turn.\
\
When the round ends, unless the game ends without agreement as provided in section 3, the Player A may start the next round immediately by making a play, or she may pause play for agreement about dead stones. (She may not pass now without pausing play first.) During the pause she takes a few seconds to indicate which of her stones, if any, she considers to be dead. She may say that she has no dead stones. Then Player B takes a few seconds to agree or to ask that play resume in the next round. If Player B asks that play resume, Player A starts play in the next round. If Player B agrees about the dead stones, she takes a few seconds to indicate which of her stones, if any, she considers to be dead. Then Player A takes a few seconds to agree or to resume play in the next round. If both players agree about which stones are dead, the game ends.\
\
2. The Encore\
\
The first round of play is called the play. If the game does not end at the end of the play, there is an encore consisting of one or more rounds of play. There are special rules for play in the encore. Let us call the first player in the encore Player A and the second player Player B.\
\
a. Ko rules for the encore\
\
1. At the start of the encore there is no ko or superko ban. If there are additional rounds in the encore, each one starts without a ko or superko ban, except by the once only rule, rule 2.\
\
2. A player may make a particular board play in a particular position of the whole board only once.\
\
Comment: If a player makes a ko or superko play but does not win the ko or superko before ending the round, the opponent may be able to win that ko or superko in the next round because of the once only rule. Moonshine life is thus avoided. This rule may sound difficult to apply. However, with rare exceptions, if indeed there are any, the only positions to worry about are those reached by a sequence of ko or superko plays.\
\
3. Ending the Game\
\
If the players agree about dead stones at the end of a round of play, as provided in section 1, the game ends.\
\
If a round of play ends in a position where a previous round ended, the game ends without agreement. All stones on the board are alive.\
\
Comments: This article breaks new ground for me, with provisions for agreement about dead stones. As we know, it is possible to write rules without such provisions, allowing players to reach agreement informally. And informal agreement works in the vast majority of cases. However, in recent years misunderstandings about ending play have created problems in tournament games under both Japanese and Ing rules. So I felt that laying out a clear procedure was a good idea.\
\
One problem with reaching agreement at the end of play is that a player's view of the position may improve and alter her play in the encore. The Japanese '89 rules address that problem with the both lose article, and with resuming play by the opponent of the player who requests it. Since an encore may be necessary in any event, it should just start with the player whose turn it is.\
\
These procedures are aimed at keeping discussion to a minimum. A round may start without any attempt at reaching agreement. If the player does seek agreement, she indicates which of her own stones are dead. That way she does not telegraph to her opponent which of her opponent's stones she thinks are dead.\
\
The phrase for a few seconds indicates that the agreement procedure is not a time for cogitation. If there is any doubt about life and death, play should continue.[/QUOTE]\
\
Edit: I simplified the once only rule to return it to its original form, which prevents superkos in the encore. I had revised it for the Japanese style rules. Note that this is a kind of superko rule. If the rules allow hung games in case of a superko, that should happen during the play, not the encore. The basic assumption is that plays in the encore are made only to clarify the score, unless a mistake has been made by stopping play."
"CarlJung","","2008-10-17 02:43:11","Can bots really communicate with each other which groups they believe are alive or dead?\
\
Anyway, it can very well be a situation where two bots disagree and no one wants to make a play since that would reduce the score but instead insist that the other bot play. \
\
Bot1: group 1 is alive. \
Bot2: no it's dead. \
Bot1: no, really it's alive. Please play to kill it and I'll show you. \
Bot2: Well, since it's already dead it would reduce my score to play there. Why don't you play and prove it's alive (and give me bigger score in the process, hehe).\
Bot1: Uh, no. It's alive in seki. I can't play there silly. Are you a cheatbot?\
Bot2: You calling me a cheater? Cheater!\
Bot1: Admin!!! He's cheating!!!!\
\
Hence the need for the server to determine the status."
"liq3","","2008-10-17 03:25:50","Use area scoring. Simple, no?"
"SpongeBob","Yupp","2008-10-17 05:20:39","Area scoring is a simple and I think also the only answer to your question. There is no other way to deal with bot-to-bot conversations like CarlJung is describing. ;)"
"Harleqin","","2008-10-17 06:03:05","[QUOTE=CarlJung]Can bots really communicate with each other which groups they believe are alive or dead?\
[/QUOTE]\
\
Of course they can.  The go text protocol has a message type for this.  The bots basically send a list of stones they believe to be dead. The problem of course arises when the lists the two bots send are not equal.\
\
My approach for area rules (basic definitions assumed):\
\
[LIST]\
[*]A game of Go starts with an empty board. The players move alternatingly, black begins. Whenever both players pass successively, the game is interrupted. As long as the game does not proceed to scoring, it is played on afterwards, the opponent of the player who had the last move beginning.\
[*]When it first takes place that either during an interruption the players agree on an end position or between two interruptions no stone was played, the agreed upon end position, or in the second case, the current position is the end position.  When an end position has been determined, the game proceeds to scoring.\
[*]Scoring: the end position is then counted.\
[/LIST]\
\
For territory rules, it is much more complicated (for example like in Bill's proposal).  I think that it is easier to introduce the \"Taiwan rule\", i.e. if White firstpasses, Black's score is reduced by one (firstpassing should not count to game interrupting passes)."
"Mcgreag","","2008-10-17 06:56:11","[QUOTE=Harleqin]
\
For territory rules, it is much more complicated (for example like in Bill's proposal).  I think that it is easier to introduce the \"Taiwan rule\", i.e. if White firstpasses, Black's score is reduced by one (firstpassing should not count to game interrupting passes).[/QUOTE]
\
I thought this was an rule for area scoring? In area rules if black can get the last dame he has played one more move than white and as such gained 1 extra point which he might (depending on your viewpoint) should not have. The rule you mentioned here reducing blacks score by one if white passes first is to remove this extra possible point.
\

\
This is at least how it was used in the WMSG rules."
"Harleqin","","2008-10-17 07:09:40","Yes, WMSG rules used this, but it is not a necessary part of area rules.  Chinese, AGA, and New Zealand rules all do not have it.\
\
Originally (i.e. a few years ago), I thought that this rule was an unneeded complication, but I have since been convinced that it is a useful completion."
"planar","","2008-10-17 07:24:43","[QUOTE=Mcgreag]I thought this was an rule for area scoring? In area rules if black can get the last dame he has played one more move than white and as such gained 1 extra point which he might (depending on your viewpoint) should not have.[/QUOTE]
\
He should not have it if your viewpoint is that you want territory scoring.  In area scoring, he should have it.
\

\
In other words, it's a rule to turn area scoring into something that feels like territory scoring (but isn't completely equivalent).
\

\
[QUOTE]This is at least how it was used in the WMSG rules.[/QUOTE]
\
That's because WMSG rules are a political compromise between area-scoring and territory-scoring countries."
"Bill Spight","","2008-10-17 07:30:01","[QUOTE=Harleqin]For territory rules, it is much more complicated (for example like in Bill's proposal).  I think that it is easier to introduce the \"Taiwan rule\", i.e. if White firstpasses, Black's score is reduced by one (firstpassing should not count to game interrupting passes).[/QUOTE]
\

\
Ah, Button Go! The wave of the future. :)"
"Hicham","","2008-10-17 08:14:23","Why is it a good thing to have black lose a point if white passes first? Why can't we just allow black to keep that point? I tried but cannot see what is not fair about it:confused:"
"ross","","2008-10-17 09:12:26","[QUOTE=xela]If you use New Zealand rules then it's easy: if the two players don't agree, you just resume the game.  The fact that area scoring is used means that taking the disputed stones off the board (or trying and failing) should cost nothing.[/QUOTE]
\
I'm not sure that it's completely simple even if area scoring rules are used. What if the two players (bots, for the sake of argument) supply different \"dead stone\" lists, but refuse (aren't programmed) to resume to game, and simply continue to pass?
\

\
My thoughts are: after four consecutive passes, (a) all stones are alive, or (b) all disputed stones [ones that don't appear in both lists] are alive. Both, unfortunately, seem to benefit bots who aren't programmed to know about dead stones, and simply play everything out to the end, at the expense of bots who can accurately identify dead stones, but who lack the ability to \"prove\" it through playout. Is this desired?
\

\
Then also there is the question: if play continues after two passes and dead stone disagreement, and then the two players pass again after that, but still disagree, what should the result be? Should the process continue, or should the game be scored as-is, with either (a) or (b) from above?"
"Bill Spight","","2008-10-17 09:24:54","[QUOTE=Hicham]Why is it a good thing to have black lose a point if white passes first? Why can't we just allow black to keep that point? I tried but cannot see what is not fair about it:confused:[/QUOTE]\
\
Button go is not a question of fairness, but of compromise or synthesis between area and territory scoring. IMO, it combines the best qualities of each: the simplicity of area scoring and the sharpness of territory scoring. We have two widely used forms of scoring which produce the same win/loss results for the vast majority of games, and which have minor effects upon strategy. As go becomes more internationalized, a compromise or synthesis of these forms of scoring seems like a good idea. :)\
\
Having a pass gain something confuses the issue. Instead, let us suppose that there is a button, a token that is worth 1/2 point by area scoring. On her turn, a player may take the button instead of making a play on the board. Surely that is fair. :)\
\
Let us also suppose that we give White an extra 1/2 point komi. Combining that with the button score, if Black takes the button she gains 1/2 pt. for the button but gives 1/2 pt. komi, for a net of 0. If White takes the button he gains 1/2 pt. for the button and also gets 1/2 pt. komi, for 1 pt. in total. In terms of the score, this is equivalent to letting White get 1 pt. for making the first pass. \
\
Is this fair? Well, that depends upon whether the komi is fair. \
\
I think that on the 19x19 board fair komi is 7. Adding the button does not change that, since it adds 0 to the mean value of the board and nothing to the expected value of playing first. If, instead of using a button, we award White 1 pt. for passing first, we should reduce the komi by 1/2, yielding a 6.5 pt. komi. If a 7 pt. komi is fair with the button, a 6.5 pt. komi is fair if White gets 1 pt. for the first pass. :)"
"Bill Spight","","2008-10-17 09:51:16","[QUOTE=ross]I'm not sure that it's completely simple even if area scoring rules are used.[/QUOTE]\
\
Ing solved the problem for area rules, but only if you can tell a disturbing ko from a fighting ko. My procedure is basically Ing's, but is more complicated because it does not make a distinction between fighting and disturbing kos. (And, of course, there are further complications for territory scoring, and even more for Japanese style rules, but bots typically use area scoring.)\
\
[QUOTE] What if the two players (bots, for the sake of argument) supply different \"dead stone\" lists, but refuse (aren't programmed) to resume to game, and simply continue to pass?[/QUOTE]\
\
Under my procedure, bot A sends a list of its own dead stones. If that agrees with bot B's assessment (or perhaps A's list includes additional stones), bot B sends a list of its own dead stones. If bot A agrees, the game ends and the stones in each list are removed from the board, and then the board is counted.\
\
If no agreement is reached, play resumes.\
\
[QUOTE]My thoughts are: after four consecutive passes, (a) all stones are alive, or (b) all disputed stones [ones that don't appear in both lists] are alive. Both, unfortunately, seem to benefit bots who aren't programmed to know about dead stones, and simply play everything out to the end, at the expense of bots who can accurately identify dead stones, but who lack the ability to \"prove\" it through playout. Is this desired?[/QUOTE]\
\
How does it benefit either side? After all, the default by area scoring is to play the game out until only living stones remain on the board. Pausing play to agree about dead stones does not disadvantage the more knowledgeable bot.\
\
(My rules also avoid Moonshine Life, as Ing rules also did, but as Tromp-Taylor and AGA rules do not always do. But that is a separate question.)\
\
Edit: What does it mean to say that a bot (or a person) can accurately identify dead stones but cannot capture them in a playout? Let us stick to an operational definition. The stones are dead iff they are captured in the playout, or if the opponent agrees that they are, and there is no playout.\
\
[QUOTE]Then also there is the question: if play continues after two passes and dead stone disagreement, and then the two players pass again after that, but still disagree, what should the result be? Should the process continue, or should the game be scored as-is, with either (a) or (b) from above?[/QUOTE]\
\
My procedure allows multiple rounds, and also provides for ending play without agreement. That happens when a round stops in the same board position as a previous round. In that case all stones on the board are alive. You can also simply not ask for agreement if play is resumed, and all stones remaining on the board when play ends are alive."
"ross","","2008-10-17 10:09:55","[QUOTE=Bill Spight]If no agreement is reached, play resumes.[/QUOTE]
\
My question is: what does it mean for play to resume if both players continue to pass, even if no agreement is reached?
\

\
[QUOTE]My procedure allows multiple rounds, and also provides for ending play without agreement. That happens when a round stops in the same board position as a previous round. In that case all stones on the board are alive. You can also simply not ask for agreement if play is resumed, and all stones remaining on the board when play ends are alive.[/QUOTE]
\

\
So, if there are 20 dead groups/chains on the board, and the players agree that 19 of them are dead, but disagree about 1 of them, and after the disagreement they continue to pass (the round stops in the same board position as the previous round), then all 20 would be considered alive?
\

\
[QUOTE]How does it benefit either side? After all, the default by area scoring is to play the game out until only living stones remain on the board. Pausing play to agree about dead stones does not disadvantage the more knowledgeable bot.
\

\
...
\

\
Edit: What does it mean to say that a bot (or a person) can accurately identify dead stones but cannot capture them in a playout? Let us stick to an operational definition.[/QUOTE]
\

\
Let's say that a bot can correctly identify dead stones, but cannot capture them in a playout. Perhaps this is simply because the programmer was lazy, and didn't add this extra functionality.
\

\
Let's take a simple shape like \"straight three,\" with a white stone at the critical point. Let's say white \"knows\" this is a dead shape for black, but doesn't \"know\" (or isn't programmed to) make the moves to remove it from the board.
\

\
If white plays against a \"well-behaved\" opponent (say a human or a similarly-programmed bot), then the game will be properly scored, and white will get the points he \"deserves\". If white plays against an \"ill-behaved\" opponent (a bot or human that incorrectly thinks that group is alive), then white will not get the points for the group he's \"killed\".
\

\

\
One might argue that white hasn't *really* killed those stones, nor does he deserve those points, if he doesn't \"know\" the moves required to actually remove them from the board. That's the question I'm asking--do people think that this is the case? That punishing white for being unable to actually remove the stones, when challenged, is fair? Or should white be able to simply \"know\" that this is a dead shape and not have to be able to remove the stones?"
"Bill Spight","","2008-10-17 10:42:22","[QUOTE=ross]My question is: what does it mean for play to resume if both players continue to pass, even if no agreement is reached?[/QUOTE]\
\
By my procedure if there is disagreement and then play continues with two consecutive passes, the game ends without agreement and all stones on the board are alive. The game has to end without agreement if it ends at all, and the default is that all stones on the board at the end of play by area scoring are alive. WTP? (What's the problem?)\
\
[QUOTE]So, if there are 20 dead groups/chains on the board, and the players agree that 19 of them are dead, but disagree about 1 of them, and after the disagreement they continue to pass (the round stops in the same board position as the previous round), then all 20 would be considered alive?[/QUOTE]\
\
Yup. By definition. ;)\
\
[QUOTE]Let's say that a bot can correctly identify dead stones, but cannot capture them in a playout. Perhaps this is simply because the programmer was lazy, and didn't add this extra functionality.[/QUOTE]\
\
I am curious about this concept of extra functionality. It seems to me that we are simply talking about capturing capturable stones. How does the bot play go at all without that functionality?\
\
[QUOTE]Let's take a simple shape like \"straight three,\" with a white stone at the critical point. Let's say white \"knows\" this is a dead shape for black, but doesn't \"know\" (or isn't programmed to) make the moves to remove it from the board.\
\
If white plays against a \"well-behaved\" opponent (say a human or a similarly-programmed bot), then the game will be properly scored, and white will get the points he \"deserves\". If white plays against an \"ill-behaved\" opponent (a bot or human that incorrectly thinks that group is alive), then white will not get the points for the group he's \"killed\".\
\
One might argue that white hasn't *really* killed those stones, nor does he deserve those points, if he doesn't \"know\" the moves required to actually remove them from the board. That's the question I'm asking--do people think that this is the case? That punishing white for being unable to actually remove the stones, when challenged, is fair? Or should white be able to simply \"know\" that this is a dead shape and not have to be able to remove the stones?[/QUOTE]\
\
The question is more subtle than that. People have constructed positions where the score is known, and one of two groups is dead, but without playout, which one it is is undetermined. The concept of dead stones is tricky, without even getting into the question of what a player deserves. With area scoring it is unnecessary to end play with dead stones on the board, and that is the default. Agreement about dead stones is unnecessary, but humans find it convenient. In case of disagreement, play resumes until only live stones remain.\
\
As to the question of what people (or bots) deserve, consider the fact that some games, such as hex, are known to be wins for one player or the other, but the winning strategy is not known. If two players are playing, do we simply award the win to that player? Of course not. The proof is in the pudding. Or suppose that in Nim a player has reached a winning position and knows it, but does not know how to win a won game. Do we stop play and award him the win? Of course not. If I could win all my won games, I would be at least one stone stronger. Playing things out is the default. Promises are not enough. You have to back them up.\
\
Edit: Here is a computer example that I like. Suppose that a program has an absolutely accurate evaluation function that takes 15 sec. to evaluate a position. Suppose also that the program finds a play that this function tells it yields a win. The program is in 1 min. byoyomi. Do we let it make the play and claim the win? Of course not."
"Bill Spight","","2008-10-17 11:34:45","About extra functionality, I think I get it now. ;)
\

\
Suppose that we have a semi-random bot that makes random plays except that it recognizes certain dead shapes, and does not waste moves killing the opponent's dead stones. However, if forced to play in an encore, it still does not kill them. If it plays against a human or a bot that agrees that its stones are dead, so that there is no encore, the bot will get better results than if the human or bot calls its bluff and requires an encore. ;)"
"yoyoma","","2008-10-17 11:38:57","Please see AGA rule #10 \"Disputes\""
"ross","","2008-10-17 19:20:17","[QUOTE=Bill Spight]By my procedure if there is disagreement and then play continues with two consecutive passes, the game ends without agreement and all stones on the board are alive. The game has to end without agreement if it ends at all, and the default is that all stones on the board at the end of play by area scoring are alive. WTP? (What's the problem?)[/QUOTE]
\

\
There isn't [i]necessarily[/i] any problem. It just doesn't seem to be how humans generally (like to) play Go.
\

\
For example, let's say you have a group on the board that you think is alive in seki. I think the group is dead. We both pass, and we agree on the other several dozen dead groups on the board, but disagree about this possible-seki position. After the dispute, I look at the group, and I decide that I can't kill it after all, so I pass. (This makes three consecutive passes.) If you pass again, the game ends with all stones alive, not just the disputed seki, so you are forced to play somewhere else.
\

\
That doesn't seem \"natural\" to me, but maybe it's okay for a Go server. That's why I say, there isn't necessarily any problem, it just doesn't seem to be how humans generally play.
\

\
[QUOTE]I am curious about this concept of extra functionality. It seems to me that we are simply talking about capturing capturable stones. How does the bot play go at all without that functionality?[/QUOTE]
\

\
Suffice it to say, bots are programmed in a lot of different ways. :)
\

\
But the \"extra functionality\" is not just in \"capturing capturable stones\", it's \"knowing when to capture certain capturable stones, and being able to do so\".
\

\
For example, GnuGo has a \"--capture-all-dead\" flag that you can run it with. If you use this flag, it will capture all capturable stones, rather than passing at the \"normal\" time when it considers the game to be over. However, there's no functionality in GnuGo (that I'm aware of) that allows you to \"switch\" modes in a resolution phase (after it learns that its opponent has a different idea of which stones are dead), much less a mode that allows it to only capture [i]certain[/i] dead stones (the disputed ones).
\

\
So, this is the \"extra functionality\" that I'm talking about. And some bots won't even have an extra flag like GnuGo has--changing them from \"pass normally\" to \"capture all dead\" would require a recompile.
\

\
[QUOTE]Agreement about dead stones is unnecessary, but humans find it convenient. In case of disagreement, play resumes until only live stones remain.[/QUOTE]
\

\
It depends, I suppose, what you mean by \"unnecessary\". Mathematically speaking, it's true--dead stone agreement is unnecessary. But if I were to make a Go Server that didn't have dead stone agreement, and required all players (human or not) to \"capture all dead\", then practically speaking, no human would ever use it. So, as part of a realistic server that people will actually use, agreement about dead stones is a necessary part of the game.
\

\
[QUOTE]As to the question of what people (or bots) deserve, consider the fact that some games, such as hex, are known to be wins for one player or the other, but the winning strategy is not known. If two players are playing, do we simply award the win to that player? Of course not. The proof is in the pudding.[/QUOTE]
\

\
Again, this is a mathematical answer, but it does not seem to be the way that people usually play Go. There is typically a threshold of \"obviousness\" that varies from person to person and from strength to strength. Playing it out past the \"obvious\" point is usually the last resolution strategy I've seen on most players' minds.
\

\

\
But finally, I definitely want to say that I don't think I disagree with you on any real points, here. I agree with everything you've been saying, and I am probably going to use your protocol or some variation of it. I am just uncertain that others--shall we say, the less \"mathematically minded\"--will accept the [i]practical[/i] results of such an implementation, and that's what I'm trying to explore here."
"planar","","2008-10-17 23:23:07","[QUOTE=ross]So, this is the \"extra functionality\" that I'm talking about. And some bots won't even have an extra flag like GnuGo has--changing them from \"pass normally\" to \"capture all dead\" would require a recompile.[/QUOTE]
\

\
KGS defines a GTP command for that, and I'm pretty sure GnuGo implements it."
"Bill Spight","","2008-10-18 00:23:56","[Quote=Bill Spight]\
By my procedure if there is disagreement and then play continues with two consecutive passes, the game ends without agreement and all stones on the board are alive. The game has to end without agreement if it ends at all, and the default is that all stones on the board at the end of play by area scoring are alive. WTP? (What's the problem?)[/QUOTE]\
\
[QUOTE=ross]There isn't necessarily any problem. It just doesn't seem to be how humans generally (like to) play Go.[/QUOTE]\
\
For most of go history humans have ended games informally by agreement. On occasion that led to problems. Now we have entered the era of formal written rules. And bots need formal rules. \
\
[QUOTE=ross]For example, let's say you have a group on the board that you think is alive in seki. I think the group is dead. We both pass, and we agree on the other several dozen dead groups on the board, but disagree about this possible-seki position. After the dispute, I look at the group, and I decide that I can't kill it after all, so I pass. (This makes three consecutive passes.) If you pass again, the game ends with all stones alive, not just the disputed seki, so you are forced to play somewhere else.\
\
That doesn't seem \"natural\" to me, but maybe it's okay for a Go server. That's why I say, there isn't necessarily any problem, it just doesn't seem to be how humans generally play.[/QUOTE]\
\
What is natural? I know of no formal agreement procedure that seems natural. However, the ones that settle disagreement by playout all default to regarding stones left on the board at the end of play as alive. As a human player you should know (be told) that the purpose of playout in the case of disagreement is to remove dead stones. If you pass instead of capturing what you can, you pay the price. The same holds for bots, but they don't have to know about purpose. ;)\
\
[Quote=Bill Spight]Agreement about dead stones is unnecessary, but humans find it convenient. In case of disagreement, play resumes until only live stones remain.[/QUOTE]\
\
[QUOTE=ross]It depends, I suppose, what you mean by \"unnecessary\". Mathematically speaking, it's true--dead stone agreement is unnecessary. But if I were to make a Go Server that didn't have dead stone agreement, and required all players (human or not) to \"capture all dead\", then practically speaking, no human would ever use it. So, as part of a realistic server that people will actually use, agreement about dead stones is a necessary part of the game.[/QUOTE]\
\
Yes. But the commentary on the server rules about agreement should make clear that if the players do not agree, there is a way of ending the game without agreement.\
\
[Quote=Bill Spight]As to the question of what people (or bots) deserve, consider the fact that some games, such as hex, are known to be wins for one player or the other, but the winning strategy is not known. If two players are playing, do we simply award the win to that player? Of course not. The proof is in the pudding.[/QUOTE]\
\
[QUOTE=ross]Again, this is a mathematical answer, but it does not seem to be the way that people usually play Go. There is typically a threshold of \"obviousness\" that varies from person to person and from strength to strength. Playing it out past the \"obvious\" point is usually the last resolution strategy I've seen on most players' minds.[/QUOTE]\
\
This is how people play games. They play them, rather than proving things about them.\
\
Edit: As for obviousness, the player disagree. We are not in obvious territory. ;)\
\
[QUOTE=ross]But finally, I definitely want to say that I don't think I disagree with you on any real points, here. I agree with everything you've been saying, and I am probably going to use your protocol or some variation of it. I am just uncertain that others--shall we say, the less \"mathematically minded\"--will accept the practical results of such an implementation, and that's what I'm trying to explore here.[/QUOTE]\
\
As a practical matter, I think that formal rules for agreement about life and death will always seem unnatural. Informal agreement works almost all the time, and players will ignore, forget, or never bother to learn procedures for handling disagreement, except for rules lawyers. You need to take players by the hand. For instance, after two consecutive passes, the server may ask the next player to click on her own dead stones (if you are using my protocol). And if there is disagreement, an informative screen should pop up explaining what happens next and emphasizing that the players should capture the opponent's dead stones before passing. Etc., etc. If you just expect players to know and understand the procedures, you are asking for trouble. As for bots, their programmers should learn the procedures and tailor their programs accordingly."
"ross","","2008-10-18 09:58:24","[QUOTE=planar]KGS defines a GTP command for that, and I'm pretty sure GnuGo implements it.[/QUOTE]
\
After some searching, I found that it's called \"kgs-genmove_cleanup\". So, it may be extra functionality for some bots, but it looks like GnuGo [i]does[/i] already have that ability. :)
\

\
(Although not for disputed stones, just for all stones.)"
"liq3","","2008-10-19 09:04:32","There is another way. You could make your own program that will check if groups are dead instead of the AIs. That means after both AIs pass, they lose control of the game, and you're program would score. This way there would be no disputes. 
\

\
You could even have the bots check dead stones themselves, then if there are disputed groups, have your program check those groups."
"Harleqin","","2008-10-19 09:59:31","[QUOTE=liq3]There is another way. You could make your own program that will check if groups are dead instead of the AIs. That means after both AIs pass, they lose control of the game, and you are program would score. This way there would be no disputes. 
\
[/quote]
\

\
Not between the bots that play, but perhaps between those bots and the server algorithm.  The problem is that there is no perfect algorithm that can resolve the dead stone question by itself."
"ross","","2008-10-19 11:00:23","[QUOTE=Harleqin]Not between the bots that play, but perhaps between those bots and the server algorithm.  The problem is that there is no perfect algorithm that can resolve the dead stone question by itself.[/QUOTE]
\
Yeah, and even simple ones are fairly CPU-intensive. If you have a server with hundreds of games ending every minute, trying to have the server algorithm resolve disputes would probably not be scalable.
\

\
And again, even ignoring the cases where the server algorithm would be wrong, I don't think humans would accept this very well. Again the seki example--if I say it's alive in seki, and you say it's dead, and the computer algorithm runs and says, \"it's alive\" and scores it thus, I can't imagine either human being very satisfied with the result.
\

\
(And what if the computer algorithm comes back and says, \"it's unsettled\"?)"