computer-go: Scoring

["T.R. Christie" <trc23@xxxxxxxxxxxxxxxx>]

> Tromp/Taylor is not hard for me to implement at all, although testing
> would take a little longer :)
> My only real objection is that I want computer programs to play the same
> game that people play, and people don't use Tromp/Taylor rules.

Clearly it would be nice if there was a simple scoring algorithm
that did return a correct score, but that would not require
that all the dead stones be removed by the players.
Then computers could play by the same rules as people.

I think Ive come up with a good solution.
Its a *very* simple scoring algorithm, that really knows
nothing about life or death, but it scores games very well.



Ill define things in terms of white throughout,
obviously the same definitions apply for
black, with the colours reversed.

DEFINITIONS:
A 'white score area' is a continuous area of non-white intersections.
plus the intersections of the bordering white groups.

A white score area and a black score area 'intersect' if they
share any of the same intersections.

A white score area is said to be 'contained' if it
intersects with one, and only one black score area.

A white score area is said to be 'non-containing' if
it does not intersect with any contained black score area.

A white score area can also be said to score
so long as it is non-containing, and so long as it does
not intersect with any non-containing black score area.


Dame + forced connections:
(not really essential, but...)

Any empty intersections that are not within a scoring
score area for either side are dame.

If there are any [white+dame] groups that border only one empty,
non-dame intersection, then that intersection may not
be scored for white.


2 possible scoring methods:

1. Chinese style
The final score for each player is one for each intersection
in each of his/her scoring score areas, plus one for
each intersection of his/her color that is not in
an opponents scoring score area.

2. Japanese style
Any stone that lies in an opponents scoring score area
is added to the opponents prisoners.
The final score for each player is one for each intersection
in each of his/her scoring score areas plus the
number of prisoners they have captured.



I tested this on 50 random games, from Dave Dyer's
score-annotated collection.
(many thanks, dave :)     )

Its performance was:

19/50 scored exactly the same.
36/50 scored to within 1 point difference
40/50 scored to within 3 point difference

In all the cases that were incorrectly scored, the correct
result could be gained by playing on just a few stones more.


Using the chinese scoring method the players can be assured
of the correct result, because if the algorithm is going to
give an incorrect result either player can play on, removing
his opponents dead stones without penalty.

If all the dead stones are removed, and dame filled,
the algorithm will score as tromp/taylor,
provided an additional constraint is added to prevent
scoring of seki positions:
* A white score group may not score if it consists of
exactly two empty intersections, and at least one black intersection
(similarly for black)

(Wont go into why I think it is the case that it would score
as tromp/taylor after filling dame and removing dead stones,
but Im fairly sure it's true...)



Really it needs more testing than 50 games.
Also there are some improvements that could be made,
but this would be at the cost of making it more complicated.
Does anybody think something like this might
be useful for a computer go tournament?

It would allow most games to finish when human players would
finish them, but in all cases the correct result can be assured,
because a program can always play on without penalty
and remove any dead stones.

comments?


  tom