Re: [gnugo-devel] Optics improvement

[Gunnar Farnebäck]

Martin wrote:
> I have extended topological_eye to set the value for a diagonal to 2.0,
> if all of the following holds:
> a) It is not 2.0 already.
> b) The diagonal is occupied by an opponent string,
> c) which is also adjacent to the (potential) eye and 
> d) at least three stones long.
> e) The (potential) eye is not on the edge (to steer clear of all the
> hairy cases that are handled by eyes.db anyway).
> f) At least two own strings are adjacent to the (potential) eye.
> g) At least one of the own strings adjacent to the (potential) eye has
> only one liberty which is an eye space and not decided false, yet.

You missed one rather important condition:

h) The (potential) eye is empty.

If it's occupied by an opponent string inside the eye things become
strange. Adding this condition solves the two regression failures and
removes two accidental passes.

> I am dubious about d), which seems a little arbitrary. However, it did
> help reduce OWL tries of irrelevant marginal eye spaces. Furthermore,
> I'm not to sure whether using is_proper_eye_space (for g) ) at this
> point is reasonable. Maybe someone with more intimate knowledge could
> comment on this?

As I said before, is_proper_eye_space() is unreasonable, but it can
trivially be replaced by

my_eye[libs[r]].color == OTHER_COLOR(color) && !my_eye[libs[r]].marginal

Appended is a revised patch which adds the revisions above,
documentation, some major FIXMEs, and a relevant test.

Please read the FIXME portion of the patch to see some remaining
important issues. Still I propose we use this patch as is unless the
regressions turn up something bad.

/Gunnar

Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.96
diff -u -r1.96 optics.c
--- engine/optics.c     13 Nov 2004 04:46:43 -0000      1.96
+++ engine/optics.c     4 Feb 2005 04:44:37 -0000
@@ -1772,11 +1772,145 @@
   
   /* Loop over the diagonal directions. */
   for (k = 4; k < 8; k++) {
+    int diag = pos + delta[k];
     val = evaluate_diagonal_intersection(I(pos) + deltai[k],
                                         J(pos) + deltaj[k], color,
                                         &attack_point, &defense_point, 
                                         my_eye);
+
+    /*
+     * Eyespaces with cutting points are problematic. In this position
+     * 
+     * .....XXXXX
+     * XXXXX.OO.X
+     * X.OOOO.O.X
+     * X.O.XXXO.X
+     * ----------
+     * 
+     * the eyespace will be .XXX. which evaluates to two eyes (seki)
+     * unless countermeasures are taken.
+     *
+     * This can be worked around in the topological analysis by
+     * sometimes setting the diagonal value to 2.0 for vertices inside
+     * the eyespace which are occupied by opponent stones. More
+     * precisely all of the following conditions must hold:
+     *
+     * a) The value is not already 2.0.
+     * a) The (potential) eyepoint is empty.
+     * b) The diagonal is occupied by an opponent string,
+     * c) which is also adjacent to the (potential) eye and 
+     * d) at least three stones long.
+     * e) The (potential) eye is not on the edge (to steer clear of all the
+     *    hairy cases that are handled by eyes.db anyway).
+     * f) At least two own strings are adjacent to the (potential) eye.
+     * g) At least one of the own strings adjacent to the (potential) eye has
+     *    only one liberty which is an eye space and not decided false, yet.
+     *
+     * With this revision the eyespace above becomes .XXXh or
+     * equivalently .XXX.! which is almost evaluated correctly, eye
+     * value 0122 instead of the correct 1122. Compared to the
+     * previous value 2222 it's a major improvement.
+     *
+     * FIXME: This approach has a number of shortcomings.
+     *
+     *        1. d) is kind of arbitrary and there may be exceptional
+     *           cases.
+     *
+     *        2. This diagonal value modification should not apply to
+     *           two diagonals of the same strings inside the eyespace.
+     *           E.g. if we have a partial eyespace looking like
+     *
+     *           .OOO.
+     *           OO.OO
+     *           OXXXO
+     *
+     *           it doesn't make sense to mark the middle vertex as a
+     *           false eye. Possibly this doesn't make any difference
+     *           in practice but it's at the very least confusing.
+     *
+     *        3. Actually it doesn't make sense to mark vertices as
+     *           false otherwise either due to these revisions (half
+     *           eyes make good sense though) as can be seen if a
+     *           stone is added to the initial diagram,
+     * 
+     *           .....XXXXX
+     *           XXXXXXOO.X
+     *           X.OOOO.O.X
+     *           X.O.XXXO.X
+     *           ----------
+     *
+     *           Now the eyespace instead becomes .XXX! which has the
+     *           eye value 0011 but if X tries to attack the eye O
+     *           suddenly gets two solid eyes!
+     *
+     *           The correct analysis would be to remove the vertex
+     *           from the eyespace rather than turning it into a false
+     *           eye. Then we would have the eyespace .XXX which is
+     *           correctly evaluated to one eye (eye value 1112).
+     *
+     *           The problem with this is that removing eye points is
+     *           messy. It can surely be done but currently there is
+     *           no support in the code for doing that. It has existed
+     *           at an earlier time but was removed because the
+     *           implementation was not robust enough and there was no
+     *           longer any apparent need for it. To correct this
+     *           problem is sufficient reason to reimplement that
+     *           functionality.
+     *
+     *        4. The test of condition g) has a result which
+     *           potentially depends on the ordering of the eyespaces
+     *           and thus presumably on the orientation of the board.
+     *           It might make more sense to examine whether the
+     *           string neighbors more than one empty vertex in the
+     *           same eyespace.
+     */
+    if (val < 2.0 && board[pos] == EMPTY && board[diag] == OTHER_COLOR(color)
+       && !is_edge_vertex(pos) && neighbor_of_string(pos, diag)
+       && countstones(diag) >= 3) {
+      int strings[3];
+      int string_count;
+      int s;
+      string_count = 0;
+      for (r = 0; r < 4; r++) {
+       int str;
+       str = pos + delta[r];
+
+       if (board[str] != color)
+         continue;
+
+       ASSERT1(string_count < 3, pos);
+       for (s = 0; s < string_count; s++)
+         if (same_string(str, strings[s]))
+           break;
+       if (s != string_count)
+         continue;
+
+       strings[string_count++] = str;
+      }
+      if (string_count > 1) {
+       for (s = 0; s < string_count; s++) {
+         int libs[MAX_LIBERTIES];
+         int adj_eye_count;
+         int lib_count;
+         adj_eye_count = 0;
+         lib_count = findlib(strings[s], MAX_LIBERTIES, libs);
+         if (lib_count > MAX_LIBERTIES)
+           continue;
+
+         for (r = 0; r < lib_count && adj_eye_count < 2; r++)
+           if (my_eye[libs[r]].color == OTHER_COLOR(color)
+               && !my_eye[libs[r]].marginal)
+             adj_eye_count++;
+         if (adj_eye_count < 2) {
+           val = 2.0;
+           break;
+         }
+       }
+      }
+    }
+
     sum += val;
+
     if (val > 0.0 && val < 2.0) {
       /* Diagonals off the edge has value 1.0 but no attack or defense
        * point.
Index: regression/owl1.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/owl1.tst,v
retrieving revision 1.104
diff -u -r1.104 owl1.tst
--- regression/owl1.tst 20 Jan 2005 19:04:34 -0000      1.104
+++ regression/owl1.tst 4 Feb 2005 04:44:43 -0000
@@ -422,6 +422,12 @@
 363 owl_defend F9
 #? [1 (F5|G5|G6|H6)]*
 
+loadsgf games/owl54.sgf
+364 owl_attack E9
+#? [1 (PASS|A7|D6|F8|F9)]
+365 owl_defend E9
+#? [0]
+
 ########### end of tests #####################
 
 # Report number of nodes visited by the tactical reading
Index: regression/games/owl54.sgf
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/games/owl54.sgf,v
retrieving revision 1.1
diff -u -r1.1 owl54.sgf
--- regression/games/owl54.sgf  1 Jan 2005 19:40:15 -0000       1.1
+++ regression/games/owl54.sgf  4 Feb 2005 04:44:43 -0000
@@ -1,5 +1,5 @@
 (;GM[1]FF[3]
 SZ[9]
-AW[ib][hc][ic][id][ae][be][ce][he][cf][df][ef][ff][gf][hf][ag][bg][cg][bh][dh][gh][hh][bi][ci][hi]
-AB[fa][ha][fb][gb][hb][ec][gc][ad][bd][cd][dd][ed][fd][gd][hd][if][dg][eg][fg][gg][hg][eh][ih][di][ei]
+AW[ea][ab][bb][cb][eb][ib][dc][ec][hc][ic][id][he][af][bf][cf][df][ef][ff][gf][hf][bg][cg][ah][bh][dh][gh][hh][bi][ci][hi]
+AB[ba][ca][da][ha][gb][hb][bc][cc][fc][gc][ad][cd][ed][gd][hd][ae][be][ce][de][ee][fe][ge][if][dg][eg][fg][gg][hg][eh][ih][di][ei]
 )