Re: computer-go: question

[Daniel Bump <bump@xxxxxxxxxxxxxxxxxx>]

About finding territory David Fotland wrote:

> 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.

This method is used by GNU Go to determine eye-spaces of groups
for determining life and death. These are the calls to safe_move()
from make_domains() in src/optics.c. This invokes the reading
code, and asks if the string can be captured. This can generate
thousands of variations, and it isn't infallible. The reading
code calls a string alive if it can get 5 liberties, four or
three at deeper plies.

But the time penalty doesn't seem too exorbitant.

Although we use this criterion for determining eye space, we do
not use it for estimating territory. For that, it seems too
conservative. It doesn't find regions which will "probably" become
territory due to overwhelming influence of one player, but where
an opponent move might be difficult to immediately capture. We use
Bouzy's algorithm for estimating territory.

Dan