Re: [gnugo-devel] Go: Quick Strategic Assessments

[Gunnar Farneback]

Phil Freihofner wrote:
> Out of curiousity, I did a web search to see the state of Go
> programming these days, and came across the Gnu Go site. From your
> documentation website, you list as a need the following: "Create a way
> to quickly assess the safety of a group. This might take into account
> number of eyes / half eyes, moyo in corners, moyo along the edge, moyo
> in the center, proximity to living friendly groups, weak opponent
> groups etc. The point is that it should involve no reading and that it
> is quick. This could be used to make a strategic estimation of how a
> move strengthens a friendly group and/or weakens an opponent group and
> how strong/weak groups influence each other."

As Arend wrote the real problem here is not that we are entirely
missing these components but to improve the quality and reliability of
what we have.

> It seems to me that what I programmed would fit the bill. The idea is
> simple enough. I'd be surprised if no one implemented it before. I
> would be interested to know if it is something your team has used or
> considered using.

Yes, we do have an influence module.

> Theoretically, an influence topo map could have many uses:
> (1) Compare overall changes in the "influence topography" of a move by
> summing ALL the topo values for every unoccuppied point.

Exists in GNU Go.

> (2) Get an approximate game score by counting the number of squares
> that are either elevated or depressed.

Exists in GNU Go.

> (3) Break the scoring into bands with differing significance. Perhaps
> there is a certain range that is ripe for invasion or erasure, another
> that would indicate over-concentration (e.g. gaining 10 points, from
> -5 to +5 is more significant than gaining 10 points from +40 to +50,
> the latter probably indicating an "overconcentrated" move).

In GNU Go terminology such bands are called territory, moyo, and area
for decreasing levels of influence.

> (4) The presence or absence of high peaks/deep valleys could be used
> as a tool for estimating connection between stones, or the
> "life-force" of a group.

I assume you're talking about vague connections here. In GNU Go
terminology this would be escape potential. Small scale connections
are determined by reading.

> (5) Structures like eyes or moyos have defineable "influence"
> generating characteristics that might prove useful.

I'm not quite following you here. Please elaborate.

> My current influence generator uses a tapering influence range of 8
> moves. The rate of taper (per move) and the range can be easily
> adjusted. I have come up with what I think is an elegant addition to
> give stones near the edge of a board an appropriate amount of extra
> influence, so that the map yields values that seem to be realistic and
> consistent over the entire board, even corners. The algorithm trees
> out from a given square in a fairly efficient fashion, able to wrap
> around existing stones (it seems most logical to consider a stone as
> being opaque, and not allow any other stone's influence to pass
> through it) in every direction, yet also able to avoid reduncancies
> and duplications.

This sounds possibly similar to what is done in GNU Go today. See the
function accumulate_influence() in engine/influence.c and the
documentation in doc/influence.texi.

> Would anyone on the Gnu-Go team like to look at this further?

You're welcome to give a closer description of how it works or show us
some code. If nothing else it might provide some new ideas in the
area.

> Perhaps this influence mapper could be made into a C++ class that
> could be easily linked and incorporated to your existing program.

We are committed to plain C, so a C++ class wouldn't be of any use as
such.

> By the way, could you tell me what the strength is of the current
> Gnu-Go program?

I suppose you're aware of the difference in perceived strength between
someone who plays a computer program the first time and someone who
has had time to learn its weaknesses, which makes it difficult to
measure the strength of programs. That notwithstanding, the best
estimate of current GNU Go strength is that it has a rating of 10 kyu
on the NNGS server over thousands of games against varied (mostly
human) opponents.

> And what the strength is of the current strongest Go program?

The available data to determine this is somewhat limited, but based on
recent tournament games I would estimate that GNU Go is somewhere
between 1 and 3 stones behind the top.

> I am also intrigued by what your team has done so far with
> encoding "josekis" of small technical matters such as shoulder hits,
> certain standard attachments and such.

Mainly included in pattern databases.

> It seems to me these could be very useful in winnowing min-max
> trees.

The current engine doesn't do any full board searching. (But lots of
local searches to determine tactical stability of strings, connections
between strings, life and death of groups, and semeais between
groups.)

> And if they could be fruitfully linked to the "influence topo map
> evaluations," this might add to the ability to weigh results of
> possible standard invasions and reducing moves,

We do have mechanisms to modify the exact characteristics of the
influence function by patterns, although it doesn't involve playing
out actual move sequences.

/Gunnar