RE: computer-go: question

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

I think there are 4 basic algorithms used in Computer go
for territory evaluation, and you might want to think
about each of them before you choose one.

1) Expansion and contraction from live stones.  Zobrist,
Goliath, Poka, and many other programs use this.  I think
Goliath had a very fast incremental implementation.

2) Find connection lines, to form boundaries, and flood fill.
I think an early Nemesis might have used this one.

3) Radiate influence from stones, add it up, and use some
thresholds.  Many Faces and Handtalk, and perhaps Go
Intellect use this.  Some programs radiate as 1/d, some
as 1/d^2, some as 1/2^d (where d is the distance from the
stone).  I use this one because it is fast and simple, and
seems to work well enough.

4) Find every empty point's connectivity to nearby white and
black stones.  This means the degree to which a hypothetical
stone of each color can be connected to nearby living friendly
stones.  Points which are strongly connected to one color and
not connected to the other color are territory.  Go4++ uses
something like this.

My personal favorite is:  If black can not place a live stone on
a point, then that point is white terriory (and vice versa).
This would use 4) above, and include an evaluation of whether
an invasion is possible.  But I don't know an algorithm for
evaluating this in a reasonable time.  In the most general
case it seems more difficult than the full board life and death
problem.

Ideally, to correctly evaluate territory, you have to consider
the sente or gote endgame plays at each of the boundaries.  This
is also a hard problem.

David Fotland

At 01:47 PM 12/13/99 -0500, you wrote:
>>
>> Hi All,
>>
>> 	Can anybody gives descriptions in more detail? The English
>> summary has very little information about the algorithm.
>> 	Thanks a lot.
>>
>> -- Mousheng Xu
>>
>
>Why not have a look at some of the papers written by Bouzy that are listed
>at
>
>http://home.t-online.de/home/markus.enzenberger/compgo_biblio/compgo_biblio.
>html
>
>Some of them discuss the computation of the territory (perhaps not in great
>detail, but probably sufficiently to understand the ideas behind it). 'The
>INDIGO program' paper has about a page about it. It's not really a terribly
>complex algorithm, and probably doesn't require much explanation in how to
>implement it (more space would probably be required to show the validity, I
>would assume).
>
>Regards,
>Lars Nilsson
>
>