Recommend
2 
 Thumb up
 Hide
23 Posts

Go» Forums » General

Subject: Computer Go Endgame rss

Your Tags: Add tags
Popular Tags: [View All]
Brendan Tracey
United States
Unspecified
California
flag msg tools
Avatar
mbmbmbmb
The wikipedia entry on Computer Go states:
"When two computers play a game of Go against each other, the ideal is to treat the game in a manner identical to two humans playing. However, this can be difficult especially during the end game. The main problem is that Go playing software has no standardized interface to communicate in a dialog with its opponents. So if there is a disagreement about the status of a group of stones, there is no general way for two different programs to “talk it out” and resolve the conflict."

Does this actually come up? Do games with non beginners ever have questions about the life of a certain group? I guess I haven't gotten into many games that had seki situations, but I don't think I've ever been in a game since I had a solid grasp of the rules whether a group was alive or dead (by the end of the game anyway). It makes more sense to me that computers disagree, but still it seems that a computer that is able to play decently well should be able to evaluate life quiet well. Do I just not know about some tricky situations?
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Bart
United States
Winnetka
California
flag msg tools
designer
Baseball been bery bery good to me
badge
This is a picture of a published game designer
Avatar
mbmbmbmbmb
It's a genuine problem. As you note it's usually seki. Several years back I was surprised that an online Go game didn't count the points. I was told it's impossible for a computer to count the points, which is nonsense, but it's not easy. You really need to have someone declare stones dead, then have the opponent agree or disagree. If players disagree, but don't see a reason to move, what next? It's easier with Chinese scoring, since you can just make enough moves to make the dead stones dead. In Japanese scoring you don't want to waste moves, so dead stones can be left with many liberties.

As it says, it's more a question of how to structure the dialog between two programs that are designed to play against people not each other.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
This isn't true. Computer vs computer go games usually play by Chinese rules, where it is easy to resolve conflicts; you just play them out.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Brendan Tracey
United States
Unspecified
California
flag msg tools
Avatar
mbmbmbmb
Are there examples of times when it's tricky to tell whether a group is alive or dead?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Brendan Tracey
United States
Unspecified
California
flag msg tools
Avatar
mbmbmbmb
I guess many life and death problems could be considered that.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
howeman wrote:
Are there examples of times when it's tricky to tell whether a group is alive or dead?
The bent four in the corner is tricky, and happens rarely but not all that rarely (it's happened in probably 4 or 5 of my games, so maybe 1 in 1000?):

+------------
| O O . # O .
| O # # # O .
| . # O O O .
| # # O . . .
| O O O . . .
| . . . . . .

Is # alive or dead? Answer: Dead. But it is very complicated to know why. In Chinese rules, if the players play well, it will almost always end up dead (although there some extremely rare cases where it might not be dead). If you play by Japanese rules it is always dead, but why is very complicated to explain and relies on some lesser-known parts of the rules.
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Brendan Tracey
United States
Unspecified
California
flag msg tools
Avatar
mbmbmbmb
Okay, I understand now how it can be complicated. Thanks William.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Bart
United States
Winnetka
California
flag msg tools
designer
Baseball been bery bery good to me
badge
This is a picture of a published game designer
Avatar
mbmbmbmbmb
wmshub wrote:
This isn't true. Computer vs computer go games usually play by Chinese rules, where it is easy to resolve conflicts; you just play them out.

Put another way, this is true for Japanese rules, so computer v computer games usually use Chinese rules. But then you give an example.

wmshub wrote:

+------------
| O O . # O .
| O # # # O .
| . # O O O .
| # # O . . .
| O O O . . .
| . . . . . .

This is a good example of the problem. This is seki unless one player says otherwise. I can see a game between competent players where black thinks this is seki while white thinks black is dead. This is where the dialog must take place, and the programs need a way to engage in this dialog.

I am having trouble understanding your comments on this. White resolves the corner as follows:

Clear all ko threats from the board.

Move 3,1. Black responds 1,3. White moves 2,1. As you said, this is bent four in the corner.

But what lesser known rule is involved? What is the unusual case with Chinese rules where white can't win this? I think you need to get into triple-ko situations for there to be a chance of the rule differences mattering. I can't see how triple ko can effect this, since we cleared the ko threats before we moved. Triple ko is a draw, unless one player chooses to lose a ko to exit the triple ko. Perhaps there is a situation where there are two positions of this nature on the board, and neither can be cleared before the other, but I can't see that either.

Please elucidate.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
Barticus88 wrote:
wmshub wrote:
+------------
| O O . # O .
| O # # # O .
| . # O O O .
| # # O . . .
| O O O . . .
| . . . . . .

This is a good example of the problem. This is seki unless one player says otherwise. I can see a game between competent players where black thinks this is seki while white thinks black is dead. This is where the dialog must take place, and the programs need a way to engage in this dialog.

I am having trouble understanding your comments on this. White resolves the corner as follows:

Clear all ko threats from the board.

Move 3,1. Black responds 1,3. White moves 2,1. As you said, this is bent four in the corner.

But what lesser known rule is involved? What is the unusual case with Chinese rules where white can't win this? I think you need to get into triple-ko situations for there to be a chance of the rule differences mattering. I can't see how triple ko can effect this, since we cleared the ko threats before we moved. Triple ko is a draw, unless one player chooses to lose a ko to exit the triple ko. Perhaps there is a situation where there are two positions of this nature on the board, and neither can be cleared before the other, but I can't see that either.
By Chinese rules, O can remove all ko threats from the board, then kill unconditionally by creating a ko where # must find the first threat. But if there is a ko threat that O cannot remove (for example, a seki elsewhere on the board), then O must either leave this as a seki, or fight the ko.

By Japanese rules, when you are disputing the life of a group after the end of the game, the only valid ko threat is a pass, so O does not need to remove ko threats or fight the ko. O simple waits until the game is over, and if # claims that it is alive, then O starts the ko, # cannot retake the ko without passing first, so O will automatically win. The bit about "when disputing a group, only a pass clears a ko" is the little-known part of the rules I was talking about. In fact, the whole dispute part of Japanese rules is little-known. (Also, in many versions of the Japanese rules, they simple state that bent 4 is dead, although the reasoning behind that is the ko-clearing rule).

Expecting computer programs to have a protocol for disputing the life of a group, then playing it out by the complex Japanese dispute system, is not practical. By Chinese rules, they can simply play it out as they play the rest of the game, problem solved very easily. The only "dialog" necessary is for the programs to know how and when to keep on playing until dead stones are removed. This is implemented in many of the computer go players that play on KGS, it is trivial to do. Wikipedia's statement "So if there is a disagreement about the status of a group of stones, there is no general way for two different programs to 'talk it out' and resolve the conflict" is simply incorrect.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Andy Latto
United States
Foxboro
Massachusetts
flag msg tools
designer
mbmbmbmbmb
Quote:
The bit about "when disputing a group, only a pass clears a ko" is the little-known part of the rules I was talking about. In fact, the whole dispute part of Japanese rules is little-known. (Also, in many versions of the Japanese rules, they simple state that bent 4 is dead, although the reasoning behind that is the ko-clearing rule).


Where can I find a copy of the full Japanese rules, including the dispute part and the "when disputing, only a pass clears a ko" rule? All the Japanses rules I've seen have just said "Bent 4 in the corner is dead". I'd really like to see a complete set of Japanese-style rules that resolved this by some general principle, rather than a special case.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
The best general source for information about rule sets is Robert Jasiek. His web page is at http://home.snafu.de/jasiek/rules.html - but a warning: He is a detail oriented person (to put it mildly). His rules discussions are not for people learning the game or trying to understand the game, it is only for people who want to undestand the minutia of the rule systems.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Bart
United States
Winnetka
California
flag msg tools
designer
Baseball been bery bery good to me
badge
This is a picture of a published game designer
Avatar
mbmbmbmbmb
wmshub wrote:
The bit about "when disputing a group, only a pass clears a ko" is the little-known part of the rules I was talking about. In fact, the whole dispute part of Japanese rules is little-known.

Indeed. I was aware of the need for such rules, but they never seemed to exist.

So what we have here is something that cannot be resolved until the ko threats are cleared. In Chinese rules, you clear all the ko threats, then resolve this corner. If there is another seki on the board, you cannot clear the last ko threat, so this remains seki as well. Of course if this seki were larger than the other one, the player could take this one and cede the other.

In Japanese rules, you don't want to make the moves to clear the ko threats. Therefore there is a secret Japanese rule that says when something lasts to the end you resolve it as though the ko threats have been cleared. This works, but in the case where there is another seki, this rule is a little too strong and allows this to be cleared.

wmshub wrote:
Expecting computer programs to have a protocol for disputing the life of a group, then playing it out by the complex Japanese dispute system, is not practical.

Are you aware that one of my pet peeves is people making excuses for bad programming. It could be done. It's not even terribly hard. As the Wiki article says, the problem is defining the protocol.

wmshub wrote:
Wikipedia's statement "So if there is a disagreement about the status of a group of stones, there is no general way for two different programs to 'talk it out' and resolve the conflict" is simply incorrect.

Are you aware that you are claiming something is false after making a brilliant explanation of why it is true (with Japanese rules)?

Fans of the Japanese rules will tell you the Chinese rules are inferior, because they lead to tacky end play. Fans of the Chinese rules will tell you the Japanese rules are inferior, because they lead to tacky end play. This discussion reinforces my belief that both sides are right.

So this Wikipedia page needs a little fix up. Anyone interested in how to state this at Wikipedia, please discuss it on the talk page.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
Barticus88 wrote:
wmshub wrote:
Wikipedia's statement "So if there is a disagreement about the status of a group of stones, there is no general way for two different programs to 'talk it out' and resolve the conflict" is simply incorrect.

Are you aware that you are claiming something is false after making a brilliant explanation of why it is true (with Japanese rules)?
You keep coming back to the Japanese rules. What rule set does it matter? It's the same game. You are splitting hairs here. Computer programs play go. Go can be played just fine by computer programs today. When they disagree on endgame score, they resolve it by the Chinese rules. Problem solved.

(I had a much longer rant and deleted it. This is more to the point).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Bart
United States
Winnetka
California
flag msg tools
designer
Baseball been bery bery good to me
badge
This is a picture of a published game designer
Avatar
mbmbmbmbmb
wmshub wrote:
What rule set does it matter? It's the same game.

Have the Japanese abandoned the Japanese rules in favor of the Chinese rules? If not, they must think the rules matter.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
Barticus88 wrote:
wmshub wrote:
What rule set does it matter? It's the same game.

Have the Japanese abandoned the Japanese rules in favor of the Chinese rules? If not, they must think the rules matter.
It's a tradition, and they know it, so why change? But it's just a difference in counting the score at the end of the game. Most people I know are happy to play any rule set that they understand. They only push back if it's a rule set they haven't played with before.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Kory Stevens
Canada
Vancouver
BC
flag msg tools
mbmbmbmbmb
For some reason I feel it necessary to add my two cents into this....

The problems being discussed in this thread are real, but in practice they are extremely rare. In 9 years of playing, I have never once had a problem with determining the life of a group, its has always been agreed without a word from either me or my opponent, we just remove the stones.

I will admit that that might be a little strange on my part, people do have these sorts of problems (and one might reasonably expect at least one over the course of 9 years), but they are really rare and in many ways are just addressed for sake of completeness.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Colin Clay
Canada
Vancouver
British Columbia
flag msg tools
I have to agree with Kory. I've seen comments on the geek saying that go is broken because of rules problems. This is nonsense.

I've played a few thousand games, and I've only had one minor rules dispute.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
This discussion wasn't about humans, but computers. Yes, for humans any score system is fine - that was my point above.

For automated computer vs. computer play, it doesn't matter how unlikely it is, you want the game to be properly scored at the end with no human intervention.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Bart
United States
Winnetka
California
flag msg tools
designer
Baseball been bery bery good to me
badge
This is a picture of a published game designer
Avatar
mbmbmbmbmb
wmshub wrote:
It's a tradition, and they know it, so why change?

Exactly. Why change? Why did they change? When Go was brought from China to Japan it had a 17x17 board and the Chinese scoring system. Why did the Japanese game change? Someone must have thought it was a good idea.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
フィル
Australia
Ashfield
NSW
flag msg tools
designer
badge
I am the wasp / that burrows in! I am the shriek / of twilight din!
Avatar
mbmbmbmbmb
I think they did it to make scoring faster, at the cost of leaving some ambiguous situations.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sverre Haga
Norway
Unspecified
Unspecified
flag msg tools
mbmb
Barticus88 wrote:
wmshub wrote:
It's a tradition, and they know it, so why change?

Exactly. Why change? Why did they change? When Go was brought from China to Japan it had a 17x17 board and the Chinese scoring system. Why did the Japanese game change? Someone must have thought it was a good idea.


Did go use a 17x17 board at the time it was imported from China to Japan? Chinese go definitely used a 19x19 later, so this detail must have changed in both countries, in that case (although IIRC Tibetan go uses/used a 17x17 board). Also, ancient Chinese rules used Stone Scoring instead of the Area Scoring used today, so both the Japanese and Chinese have adapted their scoring rules since then. A reason for the rules changing like this may be that the rules were rarely written down, and there are hardly any differences in practical play, so it was easy for the rules to change over time.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Bart
United States
Winnetka
California
flag msg tools
designer
Baseball been bery bery good to me
badge
This is a picture of a published game designer
Avatar
mbmbmbmbmb
Mors wrote:
Did go use a 17x17 board at the time it was imported from China to Japan? Chinese go definitely used a 19x19 later, so this detail must have changed in both countries, in that case (although IIRC Tibetan go uses/used a 17x17 board).

When I originally learned this history, all Go boards were 17x17 until the Japanese changed it. I didn't know that there was a known 19x19 Chinese board with the outer line being the edge of the board. It was thought that the edges weren't used, so that this was a 17x17 board. More recent research reveals that stones were place on the edge and this really was a 19x19 board. However, the 17x17 became standard, and the 19x19 was reinvented in Japan centuries later. I think Korea adopted the 19x19 board under Japanese occupation, and China adopted 19x19 in the 20th century.

Mors wrote:
Also, ancient Chinese rules used Stone Scoring instead of the Area Scoring used today, so both the Japanese and Chinese have adapted their scoring rules since then.

I wasn't aware of that. It makes Seki scoring a little easier.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sverre Haga
Norway
Unspecified
Unspecified
flag msg tools
mbmb
Barticus88 wrote:

When I originally learned this history, all Go boards were 17x17 until the Japanese changed it. I didn't know that there was a known 19x19 Chinese board with the outer line being the edge of the board. It was thought that the edges weren't used, so that this was a 17x17 board. More recent research reveals that stones were place on the edge and this really was a 19x19 board. However, the 17x17 became standard, and the 19x19 was reinvented in Japan centuries later. I think Korea adopted the 19x19 board under Japanese occupation, and China adopted 19x19 in the 20th century.


The games of Huang Longshi, in the 1600's were on a 19x19 board. AIUI, the only major rules adaption from Japanese to Chinese go in the 1900's was the abandonment of the initial stones on the hoshi points.

EDIT: Regarding Go in Korea, Sensei's Library claims the Korean go variant Sunjang Baduk was popular during the 16th century, and shows a starting setup on a 19x19 board.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.