# Open source territory scoring with seki detection

I spent the last week attempting to implement an algorithm to do territory scoring with seki detection, assuming that correct life and death markings are given but it still needs to figure out what is a seki or not. It was kind of a fun puzzle to iterate on and implement good enough conditions and heuristics, and quite tricky!

Anyways, I think I have something that might be good enough for people to try! Here’s a link, feel free to throw all your weird cases at it!
https://lightvector.github.io/goscorer/web_test/test.html

You can play stones or upload SGFs, you can mark the life and death of stones, and the site will continuously report how it would score the position if the game were ended there with no further play.

Just for fun, I think I got it to handle bamboo joints. e.g. here it doesn’t wait for black to connect the bamboo joints before recognizing the seki and declining to count the eyes as territory for white:

Are there any cases where this algorithm really screws up right now? Especially cases that can’t be fixed - where filling all the safe dame and making necessary protective moves still results in a wrong scoring even with all stones marked correctly. Or false positives: wrongly thinking an independently living group is a seki therefore failing to count any points for it would be bad.

The raw code is here GitHub - lightvector/goscorer: Territory scoring in Go with seki detection. The algorithm is implemented in both python and javascript and should be identical in the two implementations. I don’t think I know of a good open source implementation of this kind of thing yet, so if it becomes good enough maybe this can become the little library that devs can call out to for this.

17 Likes

Coool!

I know you said the “correct” life and death has to be marked but there’s a lot of debate here about what that actually means and I’m curious about how it handles the cases that are arguably incorrect.

One thing I noticed is that marked dead stones can affect the calculation:

Is there some case that would break if we ignored dead stones for the seki determination?

EDIT: I realized that some of my questions about this position didn’t make much sense. For example here is a big properly-marked dame:

1 Like

There’s a lot of really weird examples on Senseis library like

In case one is looking for some funky test ideas.

Picking one example

It’d take me a decent while to figure out if that’s what I would expect or not (well symmetry helps a bit)

1 Like

I believe they call this the Igo Hexahedron.

The positions you posted are a nice demo of some of the algorithm’s behavior, yeah.

For now, dead stones affecting things is deliberate because a dead stone can affect eyespaces. Like, an eyespace with a weakness can be falsified by dead stones thrown in, even if those stones can be easily captured. The group having fewer eyes can affect things.

So in the case you posted, the way the algorithm parses it is that Black has a move to live in the first case of the empty bulky 5 (generally the way the heuristics try to break ties in unsettled positions is to rule in favor of living), and in the second case the dead white stone, even if it is supposed dead, is still sitting on the point black needs, therefore the algorithm still considers it to prevent two eyes just as a dead throw-in stone might falsify an eye.

Here’s another example:

The dead white stone, on the right, even though it really is dead, still means that all of black’s spaces on the right are false eyes and can’t become territory whereas on the left they could (if black plays first… or if both players are beginners and never see anything wrong with it black will even score the point at A5 too).

Ignore the black square right above the dead white stone - I didn’t actually expect that to be there when setting up this example! I should look into why it’s still counting a territory point there, it might be a bug.

5 Likes

There’s a lot of choices that are unclear and can be argued either way for scoring unsettled positions or positions that haven’t been fully played out - the less played out, the harder it is to score them accurately with a fixed algorithm. I guess that’s why I’m most interested in hearing if anyone finds any anomalies in positions that persist even after being played out, such that correcting them would require a player to play extra moves and lose points, or even be impossible to correct through play. Those are the ones that are important to fix, although even for stuff that can be fixed by play I’m definitely still interested in things that anyone thinks are weird!

5 Likes

Ooo cool looks like actually there’s a “CGoban1” that was open sourced with an older version of KGS’s code for this and a bunch of stuff. I don’t think it affects anything I’m doing in python and javascript (also license being GPL means it’s not quite compatible), but that’s really cool - I didn’t know this existed. Sourceforge, way back in 2002! https://cgoban1.sourceforge.net/

7 Likes

Isn’t it still available as a binary package in Debian ? It used to be, not so long ago.

In case it’s easy for you to change, it would be a lot easier to use the “territory tester” if I could place and remove arbitrary black or white stones without having to alternate colors.

The “edit mode” kind of does that in that it seems to just place one color, but I don’t know how to toggle which color, and unclicking it to go back to alternating removes everything.

1 Like

I updated the testing page to allow that! There’s a dropdown at the top now that lets you pick other stone editing modes.

I also added an area scoring implementation and updated the github page with a picture

3 Likes

Also a little while back I updated the algorithm slightly so that in the example here Open source territory scoring with seki detection - #5 by hexahedron there isn’t an extra territory point.

There are some cases with repeated multistone throwins that won’t be scored “correctly” if they aren’t played out further before scoring, but I think it’s not worth going down a rabbit hole of trying to “fix” them to allow increasingly less dame filling than the tool already tolerates (especially when there’s not a great way to “mark” points in areas where captures might happen more than once on the same points).

Many unusual shapes for you to test your program. It’s in Japanese. Fortunately we have google translate .

Updated the algorithm to count territory in single-big-eye groups whose single big eye is filled with a living shape that is marked dead, as discussed in Score Estimate vs Result - #33 by hexahedron.

This case is a bit unclear (the common position that would be affected by this is one that isn’t fully finished anyways and the players should keep playing), but I do think it’s more intuitive than not counting it.

Any further bashing on Territory Scoring Test is welcome.

2 Likes