[gnugo-devel] Re: eye value patch

[Gunnar Farneback]

I wrote:
> This is a preparation for a later change to a more sophisticated eye
> value scheme, which will be slightly more powerful than the one
> described in the paper "Eyespace Values in Go" (linked from the web
> page). More about this later.

The current eye values are represented by two values, max and min. Max
is the number of eyse resulting if the defender moves first (followed
by alternating play) and min is the corresponding number if the
attacker moves first. This is a little too crude, however, since it
fails to distinguish between e.g.

OOOOX       OOOOX
OO.OX  and  OO.OX
O...X       O..OX
-----       -----

which are significantly different, although both evaluate to max=2
and min=1.

To improve on this we need to realize that in the left diagram, the
attacker can destroy one eye, leaving a followup threat to destroy
also the second one. Another way to describe this is that there are 2
eyes if the defender moves first but only 1/2 eye if the attacker
does. Yet another way is to give it the eyespace value 3/4, which is
what Howard Landman does in his paper Eyespace Values in Go.

The scheme I propose is similar to Landman's eyevalue algebra, but
with the additional power to include certain ko threats and count to
more than two eyes. Instead of the current two values we double this
number to four values, namely the number of eyes obtained if:

1. The attacker moves first and is allowed yet another move because
   the defender plays tenuki.
2. The attacker moves first and the defender responds locally.
3. The defender moves first and the attacker responds locally.
4. The defender moves first and is allowed yet another move because
   the attacker plays tenuki.

If we limit ourselves to a maximum of two eyes, we have the following
15 distinct cases:

0000   0 eyes.
0001   0 eyes, but the defender can threaten to make one eye.
0002   0 eyes, but the defender can threaten to make two eyes.
0011   1/2 eye, 1 eye if defender moves first, 0 eyes if attacker does.
0012   3/4 eyes, 3/2 eyes if defender moves first, 0 eyes if attacker does.
0022   1* eye, 2 eyes if defender moves first, 0 eyes if attacker does.
0111   1 eye, attacker can threaten to destroy the eye.
0112   1 eye, attacker can threaten to destroy the eye,
              defender can threaten to make another eye.
0122   5/4 eyes, 2 eyes if defender moves first, 1/2 eye if attacker does.
0222   2 eyes, attacker can threaten to destroy both.
1111   1 eye.
1112   1 eye, defender can threaten to make another eye.
1122   3/2 eyes, 2 eyes if defender moves first, 1 eye if attacker does.
1222   2 eyes, attacker can threaten to destroy one eye.
2222   2 eyes.

The 0, 1/2, 3/4, 1, 1*, 5/4, 3/2, and 2 values are used by Landman.
The 0001, 0002, 0111, 0112, 0222, 1112, and 1222 pure threat cases are
new to this scheme.

To be useful, we need the ability to add eye values. Let
(a1, b1, c1, d1) be the four values corresponding to one eyespace and
(a2, b2, c2, d2) the ones corresponding to another eyespace. Let the
sum eyevalue be (a3, b3, c3, d3). Then we get the equations

    a3 = min(a1 + c2, c1 + a2, max(a1 + b2, b1 + a2));
    b3 = min(max(b1 + b2, min(a1 + d2, b1 + c2)),
             max(b1 + b2, min(d1 + a2, c1 + b2)));
    c3 = max(min(c1 + c2, max(d1 + a2, c1 + b2)),
             min(c1 + c2, max(a1 + d2, b1 + c2)));
    d3 = max(d1 + b2, b1 + d2, min(d1 + c2, c1 + d2));

which seem to work right with the annoying exception that we need:

    if ((d1 - c1 == 2 && c2 - b2 == 1)
        || (c1 - b1 == 1 && d2 - c2 == 2)) {
      d3 = max(min(c1 + d2, d1 + b2), min(d1 + c2, b1 + d2));
    }

Otherwise we get 0011 + 0002 = 0012, which is wrong.

Actually I'm not entirely convinced that these equations are strictly
correct, but they are good enough to emulate Landman's eyevalue
algebra and it seems to behave reasonably well for the threat values.

/Gunnar