[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: computer-go: Scoring
> Jean-Pierre, do you have a link to Benson's algorithm?
I browsed through the archive compiled by François Grieu
http://persoweb.francenet.fr/~fgrieu/
and found:
http://www.chapman.edu/students/phil/benson.zip
This is a scanned version of the '76 paper.
The "transitive closure" part of the algorithm is a bit confusing. Actually
it is pretty easy.
Examples:
"b"=enclosing block (black stones for instance),
"R"=small and healthy region (black region = maximum connected set of empty
and white points),
"-"=link between black region and enclosing block of black stones.
R-b-R is Benson-safe. (a string enclosing two eye-spaces)
R-b is Benson-safe.
| |
b-R
b2-R2 is not Benson-safe.
| |
b1-R1-b3-R3
b1 is connected to only one region R1, which eliminates R1.
b2 is then connected to only one region R2, which eliminates R2.
b3 is then connected to only one region R3, which eliminates R3.
It is exactly like pulling a thread.
Jean-Pierre Vesinet