Go Programs and counting...

[Sneegurd]

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?

[karaklis]

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.)

[Li Kao]

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.

[Koroviev]

That looks pretty close to me, maybe W+1 depending on the endgame. B+13? No way.

[flOvermind]

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

[RobertJasiek]

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.

[flOvermind]

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!

[RobertJasiek]

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".

$$B Stone scoring: B wins by 1 point.
$$ -----------
$$ | . . . . |
$$ | X X X X |
$$ | O O O O |
$$ | . . . X |
$$ -----------

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?

[flOvermind]

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 ).

[RobertJasiek]

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?"

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.

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).

Using your definition of scoring,

Mine? I had predecessors.

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.

[Mike Novack]

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.

[RobertJasiek]

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.

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

Indeed. (I have not said otherwise.)

[mitsun]

$$B
$$ -----------
$$ | . . . . |
$$ | X X X X |
$$ | O O O O |
$$ | . . . X |
$$ -----------

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

[flOvermind]

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.

[Mike Novack]

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).