Re: computer-go: Empty board spaces management

["Mark Boon" <tesuji@xxxxxxxxx>]

I'm not sure I understand what you try to achieve with empty space
management. For computing eyes it seems rather overkill, but maybe there's a
use for it on a strategic level.

Maybe the following idea is any use. It's probably a bit different from what
you mean, but interesting I think.

A few years ago I realised that one of the main misconceptions of
computer-programs was what I call the difference between 'inside influence'
and 'outside influence'. Evaluation of points is often based on some
influence algorithm. Points with a high influence value are evaluated to be
close to one point of territory for a certain color, whereas points with a
low influence will be evaluated as only a fraction of a point. I'm not going
into the details here about what influence algorithm or how to decide on the
fractional points. It's not important. Instead, more abstractly, what I
found was that points with (roughly) equal levels of influence for a certain
color still had a conceptual difference that was hard to express. And that
difference was what I call 'inside' and 'outside'. In Go literature you will
often find that professional players find it very important to make the
distinction between 'solid territory' and 'potential territory', sometimes
also called 'territory' and 'influence' respectively. These terms, as most
Go-terms, are not very precise and as such not very useful in programming.

I found that Goliath very often over-estimated 'potential territory' because
the decision was based on influence values. Still, it was not obvious at
first what was the essential difference between 'solid territory' and
'potential territory' in programmatic terms. I think it was Charlie Carroll,
who was working for me at the time, who came up with the idea to use a
marble. To decide whether a point's influence value is to be considered
'inside influence' or 'outside influence' a marble is placed at that point.
Marbles roll downhill, so it would move to the adjacent intersection with
the lowest influence. At some point the marble will come to a standstill
because all surrounding intersections will have equal or higher influence
values. If the marble stops at a point which still has some influence value,
it was considered to be 'inside', if it stops at a point with zero value or
a point with influence of the opponent, it was considered to be 'outside'.
Basically, you're looking whether the marble rolls into the territory, or
out.

Although we ended up tweaking the idea a bit to make it work (like, a marble
can't roll past stones) this concept proved very promising. Of course this
process turned out to be very costly to compute at first, since it needs a
lot of computation for each point. But quite some optimizations turned out
to be possible and in the end we had something that turned out to be very
usable and not too expensive. But I don't think we ever managed to find an
incremental way of computing it on a per-move basis.

----- Original Message -----
From: Bryan McQuade <bmcquade@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Tuesday, June 27, 2000 9:27 PM
Subject: computer-go: Empty board spaces management


> Hi again.  I would like to thank everyone for your responses on an unmake
> move method.  We found them all very helpful (and I hope some of you did
as
> well).  We decided to implement an unmake move method rather than copy
state.
>
> Now, we are debating how to tackle empty region management.  We would like
> to update data structures that manage empty parts of the board as the game
> moves along.  Our first thoughts were to look at the empty board as one
big
> eye of sorts.  We would consider the empty regions of the board one big
eye
> until two regions were completely separated from one another by stones
(ie:
> once a corner was sealed off, the corner would become its own "eye"
separate
> from the rest of the empty spaces on the board).  However, we found it
very
> difficult to keep track of this information efficiently (time-wise).  It
> seems logical to partition the board into empty regions as pieces are
played
> which split free areas (this will be especially helpful in determining eye
> spaces).  However, the search required to identify all separate regions of
> the board is too expensive as we see it.  I wanted to check with all of
you
> and see if you had any suggestions as to how to manage data structures for
> empty regions of the board efficiently.  Ideally, we would like to update
> this information on a per-move basis rather than completely reevaluate the
> board at every move.  However, we are open to any suggestions.
>
> Thanks for all your help,
> Bryan McQuade
>
>
>