Scoring Completed Games

[revised Nov 2007]

Scoring conpleted games is a difficult but tractable problem; which is precisely why it was one of the first things my program did..

I only attempted to score games that were annotated with an exact score. Beyond this selection process, no human intervention or decision making was done;

The program starts with the final position, exactly as published. The program decides what is dead, fills dame, makes necessary defensive moves, removes dead and calculates the final score. The main factor that makes the problem tractable is that the situation is can be presumed to be static; there are no places where a single move by either player will change the score, given correct follow-up play.

The approximate algorithm is as follows:

Make a preliminary pass to guess which areas are absolutely alive using a zero-entropy move generator, whose objective is to fill all empty spaces, avoid capturing anything, and avoid changing connectivity among groups. At the end of this process, groups which have two eyes are considered absolutely alive. I use the a database of eye-shape outcomes determine which "big eyes" can actually make two.
Make a second pass, considering each of the not-absolutely-safe groups, and classify each as alive or dead based on several heuristics (such as "surrounded by a live group") or by invoking a problem solver to actually try to capture it. A key idea in this phase are that you can make something alive by connecting to any group previously determined to be alive. The order in which you try to secure groups has a lot of effect on the time required, but not on the outcome.
Fill all the dame, which are now well defined as the empty area adjacent to live groups of both colors. It's important that the dame filling process be fair enough to allow ataris to be answered and connections to be made, without allowing extra eyes to be formed. Since I do not run this phase as an adversarial process, sometimes mistakes are made; this is were "off by 1" errors occur.
As the dame are filled, some groups may become capturable, making it necessary to play inside territory (and change the score). The final phase looks for occurrences of this by running a tsumego solver on all groups with few liberties. This is usually the slowest phase.

This process is not quite what it would be if the program were scoring it's own play. The information from phases 1 & 2 would be gleaned from the working assumptions the program maintains as it goes along, and phases 3 and 4 would be combined and interleaved.

The most difficult aspect of the problem is keeping control over the problem solver, once you decide to invoke it. It's important that the scope of the problem be allowed to expand "as necessary" until a stable state is reached, while at the same time, expanding the problem to include adjacent life-and-death struggles tends to make the process exponentially slower.

Experimental results

Among the first 2000 professional games I collected, about 1/3 have an exact score. Of those, I can calculate the correct score for about 75%. In the other 25%, the most common errors are to be off by 1 point due to a fine point of endgame play. Occasionally, it turns out that territories aren't really final, just determined in the eyes of the pros. Gross errors, where tsumego is judged incorrectly and a wildly inaccurate score is calculated, are very rare.

A collection of over 600 professional games, with correct (or nearly correct) automatically generated scores is available here in a zip archive. The individual games are in SGF format, with the addition of a few nonstandard properties which describe the results of scoring. I expect this collection to be useful as a test set for other programs which score completed games. The nonstandard properties are in the form

FP (final position) contains an easily parseable ascii diagram of the board at the end of the official game record.
AS (after score) contains a "machine readable" property list with scoring results, including captive counts, territory counts, and another ascii diagram with all dame filled and all dead stones removed.
ES (estimated score) containst a "human readable" text describing the scoring process and results.

An Example

Here is output from my program scoring this game, the 11'th Honinbo title game 1.

the game before scoring

the game after filling dame and removing dead

#<game GAMES:PRO-LIB;HONINBO;HONINBO-11-1.BIN.NEWEST 700255657> 
There are 27 possibly dead stones to worry about 
Initial phase took 44 seconds

[30:21] fate of #<BLACK group 1m 1L 10,9 to 10,9> is DEAD captured in final moves 
[30:21] fate of #<BLACK group 6m 4L 11,1 to 14,3> is ALIVE part of moyo 
[30:21] fate of #<WHITE group 2m 2L 13,3 to 14,3> is DEAD enclosed by moyo 
[30:22] fate of #<BLACK group 4m 3L 5,3 to 7,4> is DEAD enclosed by of moyo 
[30:22] fate of #<BLACK group 1m 2L 2,6 to 2,6> is DEAD enclosed by of moyo 
[30:22] fate of #<BLACK group 1m 2L 5,6 to 5,6> is DEAD enclosed by of moyo 
[30:22] fate of #<BLACK group 2m 4L 3,5 to 4,5> is DEAD enclosed by of moyo 
[30:23] fate of #<WHITE group 1m 2L 2,18 to 2,18> is PRESUMED DEAD 
[30:25] fate of #<WHITE group 7m 3L 10,1 to 12,4> is ALIVE 
[30:26] fate of #<BLACK group 2m 2L 9,3 to 9,4> is PRESUMED DEAD 
Life and death phase took 5 seconds

19 Dame #<WHITE set 19m 3,1 to 17,17 > 
14,13 BLACK CONNECT 
10,8 WHITE CONNECT 
11,7 BLACK CONNECT 
4,17 WHITE CONNECT 
11,11 BLACK CONNECT 
9,7 WHITE ATARI 
10,6 BLACK FORCE-CONNECT 
3,8 WHITE ATARI 
7,9 BLACK FORCE-CONNECT 
17,9 WHITE ATARI 
18,6 BLACK FORCE-CONNECT 
14,8 WHITE NIL 
15,12 BLACK CONNECT 
17,12 WHITE FORCE-CONNECT 
16,10 BLACK NIL 
10,7 WHITE NIL 
11,1 BLACK NIL 
6,12 WHITE NIL 
5,13 BLACK NIL 
5,12 WHITE NIL 
3,15 BLACK NIL 
15,15 BLACK NIL 
Filling dame took 17 seconds 
Checking for forced connecting moves 
[30:45] checking #<BLACK group 68m 8L 2,5 to 16,18> 
[30:46] checking #<BLACK group 1m 2L 13,4 to 13,4> 
[30:48] checking #<BLACK group 3m 4L 13,6 to 15,6> 
[30:49] checking #<BLACK group 6m 5L 11,17 to 14,19> 
[30:50] checking #<BLACK group 1m 2L 9,19 to 9,19> 
[30:52] checking #<BLACK group 13m 8L 16,3 to 19,9> 
[30:52] checking #<BLACK group 5m 2L 1,11 to 3,13> 
[31:02] checking #<BLACK group 4m 5L 2,14 to 3,16> 
[31:02] checking #<BLACK group 11m 3L 14,15 to 19,17> 
[31:06] checking #<BLACK group 3m 4L 17,18 to 18,19> 
[31:09] checking #<BLACK group 7m 3L 11,1 to 14,3> 
Group #<BLACK group 7m 3L 11,1 to 14,3> looks DEAD, Testing 15,2  looks ok 
Going to make move 15,2 to stay alive 
[31:57] checking #<BLACK group 1m 2L 9,19 to 9,19> 
[31:57] checking #<BLACK group 3m 4L 13,6 to 15,6> 
[31:57] checking #<BLACK group 1m 2L 13,4 to 13,4> 
[31:58] checking #<BLACK group 6m 5L 11,17 to 14,19> 
[31:58] checking #<BLACK group 68m 8L 2,5 to 16,18> 
[31:58] checking #<BLACK group 13m 8L 16,3 to 19,9> 
[31:58] checking #<BLACK group 8m 5L 11,1 to 15,3> 
[31:59] checking #<BLACK group 4m 5L 2,14 to 3,16> 
[31:59] checking #<BLACK group 5m 2L 1,11 to 3,13> 
[31:59] checking #<BLACK group 11m 3L 14,15 to 19,17> 
[31:59] checking #<BLACK group 3m 4L 17,18 to 18,19> 
[32:00] checking #<BLACK group 4m 2L 2,17 to 3,19> 
Group #<BLACK group 4m 2L 2,17 to 3,19> looks DEAD, Testing 2,17  looks ok 
Going to make move 2,17 to stay alive 
[32:05] checking #<BLACK group 6m 5L 11,17 to 14,19> 
[32:05] checking #<BLACK group 1m 2L 9,19 to 9,19> 
[32:06] checking #<BLACK group 3m 4L 13,6 to 15,6> 
[32:06] checking #<BLACK group 1m 2L 13,4 to 13,4> 
[32:06] checking #<BLACK group 68m 8L 2,5 to 16,18> 
[32:06] checking #<BLACK group 13m 8L 16,3 to 19,9> 
[32:07] checking #<BLACK group 8m 5L 11,1 to 15,3> 
[32:07] checking #<BLACK group 9m 6L 2,14 to 3,19> 
[32:07] checking #<BLACK group 5m 2L 1,11 to 3,13> 
[32:07] checking #<BLACK group 3m 4L 17,18 to 18,19> 
[32:08] checking #<BLACK group 11m 3L 14,15 to 19,17> 
[32:10] checking #<WHITE group 50m 6L 11,6 to 19,19> 
[32:11] checking #<WHITE group 27m 6L 2,6 to 11,13> 
[32:11] checking #<WHITE group 4m 2L 7,4 to 9,5> 
[32:20] checking #<WHITE group 30m 3L 1,9 to 8,19> 
[32:26] checking #<WHITE group 4m 2L 6,18 to 8,19> 
[32:32] checking #<WHITE group 7m 2L 10,1 to 12,4> 
Group #<WHITE group 7m 2L 10,1 to 12,4> looks DEAD, Testing 9,2  looks ok 
Going to make move 9,2 to stay alive 
[32:41] checking #<WHITE group 50m 6L 11,6 to 19,19> 
[32:42] checking #<WHITE group 9m 4L 8,1 to 12,4> 
[32:42] checking #<WHITE group 27m 6L 2,6 to 11,13> 
[32:42] checking #<WHITE group 4m 2L 7,4 to 9,5> 
[32:43] checking #<WHITE group 4m 2L 6,18 to 8,19> 
Connection check took 2 minutes 
Forced connecting moves for Black: <18,6> <7,9> <15,2> <2,17> 
Forced connecting moves for White: <17,12> <9,2> 
Dead WHITE groups: <2m 13,3 to 14,3> <2,18> 
Dead BLACK groups: <2m 9,3 to 9,4> <5,6> <2m 3,5 to 4,5> <2,6> <4m 5,3 to 7,4> 
Black Territory #<BLACK set 53m 1,1 to 19,19 > 
White Territory #<WHITE set 46m 1,1 to 19,19 >

Final score for GAMES:PRO-LIB;HONINBO;HONINBO-11-1.BIN.NEWEST:  
White: 41.5 =  4.5 komi + <46m> - 9 captured 
Black: 35 = <53m> - 18 captured 
White wins by 6.5 points 
total time: 3 minutes 6 seconds

go back