Life In 19x19
http://www.lifein19x19.com/

Go Programs and counting...
http://www.lifein19x19.com/viewtopic.php?f=18&t=5831		 Page 1 of 1
Author:  Sneegurd [ Tue Apr 17, 2012 10:39 pm ]
Post subject:  Go Programs and counting...
http://www.dragongoserver.net/game.php?gid=617987

SmartGo counts B+13.5
Drago counts: B+0.2 (?)

Is counting a difficult problem for computer programs?
Author:  karaklis [ Tue Apr 17, 2012 11:58 pm ]
Post subject:  Re: Go Programs and counting...
Yes, especially if the middlegame is still going on and there are groups of stones on the board where the program cannot decide correctly whether a group is alive or dead (or even depends on a ko etc.)
Author:  Li Kao [ Wed Apr 18, 2012 12:10 am ]
Post subject:  Re: Go Programs and counting...
I don't think counting is very hard for a go bot. MC bots probably need a bit of tweaking, since they optimize for winrate, and not for score, but if you do that, I expect good results.

But some counting programs, such as KGS's infamous score-estimator evaluate the game using a set of heuristics, instead of actually playing it out. And that leads to low quality counting.
Author:  Koroviev [ Wed Apr 18, 2012 9:54 am ]
Post subject:  Re: Go Programs and counting...
That looks pretty close to me, maybe W+1 depending on the endgame. B+13? No way.
Author:  flOvermind [ Wed May 09, 2012 4:46 am ]
Post subject:  Re: Go Programs and counting...
Sneegurd wrote:
Is counting a difficult problem for computer programs?

Actually, scoring a finished position is PSPACE-hard ;)
http://dl.acm.org/citation.cfm?doid=322186.322201

So in general, yes, counting is a very difficult problem for computer programs, even for finished positions. But in practice, heuristics can help. Especially for bots that is not a problem, because it can just refuse to pass and continue playing if it encounters a position that is hard to count.

As for counting games in progress, that is even harder, since the computer has to continue playing until a scorable position is reached. Ignoring ko, this problem is at least PSPACE, and depending on the exact rules used, it may even be EXPTIME-hard.

What does that mean in practice?
Counting programs that give a perfect result would be way too slow. So these programs (and also go bots) are usually written with some heuristics that speed up the computation at the cost of accuracy. But that means that sometimes, the result will be completely wrong :P
Author:  RobertJasiek [ Wed May 09, 2012 9:27 pm ]
Post subject:  Re: Go Programs and counting...
flOvermind wrote:
Actually, scoring a finished position is PSPACE-hard


Nonsense.

Only life-and-death dependent scoring is hard. Area scoring, stone scoring etc. are O(n), i.e., as trivial as flood-filling.
Author:  flOvermind [ Thu May 10, 2012 3:21 am ]
Post subject:  Re: Go Programs and counting...
RobertJasiek wrote:
Only life-and-death dependent scoring is hard. Area scoring, stone scoring etc. are O(n), i.e., as trivial as flood-filling.


Nonsense.

Your seemingly trivial flood-filling can not remove dead stones, and it also doesn't handle seki.

Read the paper I referenced.
You're of course free to disagree with a peer-reviewed paper, but then you should at least give an algorithm that proves your point!
Author:  RobertJasiek [ Thu May 10, 2012 5:14 am ]
Post subject:  Re: Go Programs and counting...
flOvermind wrote:
Your seemingly trivial flood-filling can not remove dead stones, and it also doesn't handle seki.


Sigh. Area scoring, stone scoring (the scoring itself, not the folk procedural jam for optional human agreement phases) etc. DO NOT CARE WHETHER there are dead stones or sekis.

Definition of area scoring: A player's score is the sum of numbers of his stones on the board and empty intersections (as a region) surrounded by his and only his stones.

Definition of stone scoring: A player's score is the number of his stones on the board.

Note: Either definition is INDEPENDENT of "dead" and "seki".

Click Here To Show Diagram Code
[go]$$B Stone scoring: B wins by 1 point.
$$ -----------
$$ | . . . . |
$$ | X X X X |
$$ | O O O O |
$$ | . . . X |
$$ -----------[/go]


http://en.wikipedia.org/wiki/Flood_fill

Did the referenced paper declare to be applicable also to area scoring and stone scoring?
Author:  flOvermind [ Thu May 10, 2012 5:32 am ]
Post subject:  Re: Go Programs and counting...
No, it does not apply to the technical definition of stone/area scoring. It applies to the practical problem of determining who won the game at the end.

Of course you can always simplify a problem by just changing the problem statement in a way that is convenient, but in doing so, you didn't actually solve any practically relevant problem. The original question was whether scoring in go is hard for computers. The answer is a definite yes, regardless of the scoring method used.

Using your definition of scoring, you just shift the difficulty to the problem of reaching a strictly finished position, starting from a position that human players would consider finished. Actually, that makes the whole problem harder, since it involves continuing to play, which is probably (for Japanese rules definitely, for most area rulesets unknown) EXPTIME-complete, which is probably (also not yet proven) strictly harder than PSPACE, and definitely strictly harder than P (for PSPACE there is a minor chance that in might still be equal P, but probably not :P).
Author:  RobertJasiek [ Thu May 10, 2012 6:04 am ]
Post subject:  Re: Go Programs and counting...
flOvermind wrote:
No, it does not apply to the technical definition of stone/area scoring. It applies to the practical problem of determining who won the game at the end.


Your problem continues to be that you don't express clearly what you mean. The "practical problem of determining who won the game at the end" is solved by "applying the (what you call) technical scoring definition". What you mean probably is: "For a given starting situation, how hard is it to identify perfect play followed by scoring?"

Quote:
Of course you can always simplify a problem by just changing the problem statement in a way that is convenient,


That has not been my motivation.

Quote:
The original question was whether scoring in go is hard for computers.


Again you don't express your intention clearly. You do not mean whether scoring is hard but whether perfect play... (see above).

Quote:
Using your definition of scoring,


Mine? I had predecessors.

Quote:
you just shift the difficulty to the problem of reaching a strictly finished position,


Once more you fail to express yourself clearly. You do not mean the problem of reaching a strictly finished position (any legal sequence would) but of using perfect play to do so.
Author:  Mike Novack [ Thu May 10, 2012 12:33 pm ]
Post subject:  Re: Go Programs and counting...
RobertJasiek wrote:
flOvermind wrote:
you just shift the difficulty to the problem of reaching a strictly finished position,


Once more you fail to express yourself clearly. You do not mean the problem of reaching a strictly finished position (any legal sequence would) but of using perfect play to do so.


No Robert, he doesn't mean perfect play but adequate play. "Any legal sequence" will not determine the life or death of groups. Will a single example do? Suppose we have a solidly connected group whose interior space is "four in a row". We say that is a live group. Why? Because if the opponent plays in one of the two middel spaces can respond with the other and makes the group absolutely alive. BUT (very big but) if instead of making that correct response simply made "any legal move somewhere else on the board the group dies when the opponet plays the second middle space.
Author:  RobertJasiek [ Thu May 10, 2012 1:55 pm ]
Post subject:  Re: Go Programs and counting...
Mike Novack wrote:
he doesn't mean perfect play but adequate play.


And what is "adequate"? The talk has also been about hardness of a computer determining status correctly. This is related to perfect play - not to some weaker kind of play. Adequate appears to be a weaker word than perfect.

Quote:
"Any legal sequence" will not determine the life or death of groups.


Indeed. (I have not said otherwise.)
Author:  mitsun [ Thu May 10, 2012 4:03 pm ]
Post subject:  Re: Go Programs and counting...
Click Here To Show Diagram Code
[go]$$B
$$ -----------
$$ | . . . . |
$$ | X X X X |
$$ | O O O O |
$$ | . . . X |
$$ -----------[/go]

Suppose both players pass in this position and ask the computer to score the result and announce the winner.

I guess RJ would say that it is simple to calculate that B wins by 1 point (stone scoring) or 5 points (area scoring)? And to avoid this result, W should not have passed.

While fO would argue that a more intelligent calculation is needed to figure out that one B stone is dead, then calculate the score accordingly, with the result that W wins by 1 point?

In actual practice, most programs require the user to mark known dead stones, to help the computer avoid the difficult life/death calculation. But I suppose both RJ and fO would reject that practical solution as not relevant to the problem :)
Author:  flOvermind [ Mon May 14, 2012 7:15 am ]
Post subject:  Re: Go Programs and counting...
It depends on the context. Sometimes you want the computer to determine the score without human interaction.

But in the standard case, I agree, the most practical solution is to let the players remove the dead stones manually, and then solve the much simpler sub-problem of flood-filling the territory.
Author:  Mike Novack [ Mon May 14, 2012 11:45 am ]
Post subject:  Re: Go Programs and counting...
That does not solve the problem because in general the humans (except at the very highest levels of strength) cannot determine dead or alive either. Have you never seen a really difficult life and death problem? (you are asked to determine the status of a group, alive unconditionally or live with ko or seki or dead).
Author:  jts [ Mon May 14, 2012 9:07 pm ]
Post subject:  Re: Go Programs and counting...
Mike Novack wrote:
That does not solve the problem because in general the humans (except at the very highest levels of strength) cannot determine dead or alive either. Have you never seen a really difficult life and death problem? (you are asked to determine the status of a group, alive unconditionally or live with ko or seki or dead).

But in the human case each player can be expected to act as his own advocate, and only agree that a group is dead if he sees no conceivable way for it to live. (Or vice-versa.)
Author:  Mike Novack [ Tue May 15, 2012 4:18 am ]
Post subject:  Re: Go Programs and counting...
jts wrote:
But in the human case each player can be expected to act as his own advocate, and only agree that a group is dead if he sees no conceivable way for it to live. (Or vice-versa.)


But we are discussing the time rquired to come to a correct count. Of course two 10 kyu human players might come to an agreement about whether a group is alive or dead but is their answer correct? (assuming that was a 2 kyu life and death problem).

This all began with curiosity about how different computer programs might come up with a significantly different count for the same board position. Not completely different from the situation with humans (those two 10 kyu players counting their game vs a 2 dan player doing it for them)
Author:  jts [ Tue May 15, 2012 9:07 am ]
Post subject:  Re: Go Programs and counting...
That's fair enough. It's hard to tell what exactly the original poster meant, which perhaps has muddied the waters.

If I asked "Is it hard for a computer to do your taxes?" you might be inclined to respond "no, not at all - there are dozens of cheap programs that will do that for you and never make a mistake." But then I might be disappointed to find out that the computer can't gather my receipts for me and figure out whether my partner is my dependent or figure out which parts of my income are taxable and which aren't.

I think Karakalis and Li Kao and I all see "counting" as a distinct skill, for bots as for humans. For humans, counting can be hard (both in terms of accuracy and bias), and it can be unpleasant, and it can take some time, and it can require practice. But for computers counting, and even the endgame skills that are a prerequisite for an accurate count, are relatively easy. Everything else in Go, and in particular life and death, is much harder for them. However, just as with humans, when they've screwed up a L&D problem their count is likely to be spectacularly off. But if I play a lost game to the end and then realize I had misjudged a L&D problem, I wouldn't say "Argh! Damn, I suck at counting." I would blame my counting if I lost a game by 0.5 because I backed down from the final ko - that's the sort of mistake even mediocre programs never make, because their counting is awesome.

But in your interpretation, "counting" is the same as "being good at Go" - after all, if a computer can count the board after all of its possible candidate moves and never err, it should never lose. And yes, in this conception counting is quite hard! ;-)
Author:  Sneegurd [ Fri Jun 22, 2012 9:20 am ]
Post subject:  Re: Go Programs and counting...
The original poster meant: "Why do different Go programs calculate different results?". OK, now I understand that finding correct results requires correct (whatever that is - shortest winning path?) continuation of the game - I'd say that is the dark side of go. Not as easy as 0!=1.
Page 1 of 1 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/