[gnugo-devel] Optics improvement

[Martin Holters]

Hi!

I have tried to make GNU Go handle eye spaces like

.....OOOOO
.OOOO.XX.O
.OXXXX.X.O
.OX.OOOX.O
----------

better, which was previously considered unconditionally alive (in seki).

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.

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?

Despite my own objections, the results are promising:

lazarus:11      PASS S15 [S15]
lazarus:12      PASS T18 [T18]
lazarus:17      FAIL F2 [T8]
nngs:820        PASS L9 [J13|L9]
nngs:1160       PASS H8 [!A8]
nngs:1190       PASS 0 [0]
owl1:274        PASS 1 G7 [1 G4|G7|B6]
owl1:322        PASS 0 [0]
owl1:323        PASS 0 [0]
owl1:362        PASS 1 M16 [1 M16]
strategy5:284   FAIL E9 [R12|Q9]

That's 9 PASSes vs. 2 FAILs at a node counter increase between 0.25% and
0.45%.

I have not analysed the regression delta because I am a little short on
time at the moment. As I don't know when that might change, I have
decided to post the patch anyway before it starts gathering dust. Maybe
it is of use as it is, or someone else might want to polish it up?

/Martin

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     25 Jan 2005 06:54:54 -0000
@@ -1772,11 +1772,56 @@
   
   /* 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);
+    if (val < 2.0 && 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 (is_proper_eye_space(libs[r]))
+             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.