[gnugo-devel] optics patch

[Paul Pogonyshev]

This patch fixes a problem when an unknown eye is declared safe (or
even ultra safe, "guaranteeing" some 4 eyes).  This might be incorrect
and sometimes leads to disasters.  The patch makes optics code be less
optimistic about "bulky" eyes with code in compute_eyes_pessimistic()
and guess_eye_space().

Regression breakage:

trevora:550     PASS 1 F2 [1 F2]

        Good, the problem is solved properly.

niki:4          FAIL Q19 [Q8]

        Q19 is now thought to be owl attack against P17 dragon.  While
        i doubt it really works, i don't think this fail is bad.  And
        not considering the corner eye as safe seems logical to me --
        it's way too open and bulky.

strategy3:115   FAIL H1 [G2]

        Accidential.  GNU Go doesn't see that G2 defends the dragon
        after H1 (despite the pattern i included in the patch).  This
        is yet another problem with inessential strings being
        essential.

owl1:334        pass (failed by CVS version)

        A new test.  This the problem about 12 point corner eye i
        posted ages ago.  Properly solved.

nando:17        fail 1 C5

        Still failed, but we have a major improvement here.  Now D5 is
        not thought to give two certain eyes immediatly and is no
        longer considered owl defense.

The patch costs about 1.5% owl nodes.  This is definitely not good,
but i think we should accept it anyway.  I don't see any other way to
solve the problems.  The heuristics used in the patch can certainly be
impoved to reduce performance hit, but it's not easy.

Paul



Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.82
diff -u -p -r1.82 optics.c
--- engine/optics.c     24 Aug 2003 03:04:11 -0000      1.82
+++ engine/optics.c     8 Nov 2003 22:28:52 -0000
@@ -66,7 +66,7 @@ static int recognize_eye(int pos, int *a
                         struct half_eye_data heye[BOARDMAX],
                         struct vital_points *vp);
 static void guess_eye_space(int pos, int effective_eyesize, int margins,
-                           struct eye_data eye[BOARDMAX],
+                           int bulk_score, struct eye_data eye[BOARDMAX],
                            struct eyevalue *value, int *pessimistic_min);
 static void reset_map(int size);
 static void first_map(int *map_value);
@@ -808,11 +808,15 @@ compute_eyes_pessimistic(int pos, struct
                         struct eye_data eye[BOARDMAX],
                         struct half_eye_data heye[BOARDMAX])
 {
+  static int bulk_coefficients[5] = {-1,-1, 1, 4, 12};
+
   int pos2;
   int margins = 0;
   int halfeyes = 0;
   int margins_adjacent_to_margin = 0;
   int effective_eyesize;
+  int bulk_score = 0;
+  char chainlinks[BOARDMAX];
 
   /* Stones inside eyespace which do not coincide with a false eye or
    * a halfeye.
@@ -820,10 +825,11 @@ compute_eyes_pessimistic(int pos, struct
   int interior_stones = 0;
 
   for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) {
+    int k;
+
-    if (!ON_BOARD(pos2))
-      continue;
-    if (eye[pos2].origin != pos)
+    if (!ON_BOARD(pos2) || eye[pos2].origin != pos)
       continue;
+
     if (eye[pos2].marginal || is_halfeye(heye, pos2)) {
       margins++;
       if (eye[pos2].marginal && eye[pos2].marginal_neighbors > 0)
@@ -833,6 +837,21 @@ compute_eyes_pessimistic(int pos, struct
     }
     else if (IS_STONE(board[pos2]))
       interior_stones++;
+
+    bulk_score += bulk_coefficients[(int) eye[pos2].neighbors];
+
+    for (k = 0; k < 4; k++) {
+      int neighbor = pos2 + delta[k];
+
+      if (board[neighbor] == eye[pos].color) {
+       if (!chainlinks[neighbor]) {
+         bulk_score += 4;
+         mark_string(neighbor, chainlinks, 1);
+       }
+      }
+      else if (!ON_BOARD(neighbor))
+       bulk_score += 2;
+    }
   }
 
   /* This is a measure based on the simplified assumption that both
@@ -872,7 +886,7 @@ compute_eyes_pessimistic(int pos, struct
    * eyespaces.
    */
   else {
-    guess_eye_space(pos, effective_eyesize, margins, eye,
+    guess_eye_space(pos, effective_eyesize, margins, bulk_score, eye,
                    value, pessimistic_min); 
     DEBUG(DEBUG_EYES, "  guess_eye - %s, pessimistic_min=%d\n",
          eyevalue_to_string(value), *pessimistic_min);
@@ -882,7 +896,7 @@ compute_eyes_pessimistic(int pos, struct
     *pessimistic_min = 0;
     DEBUG(DEBUG_EYES, "  pessimistic min revised to 0\n");
   }
-  
+
   /* An eyespace with at least two interior stones is assumed to be
    * worth at least one eye, regardless of previous considerations.
    */
@@ -890,7 +904,7 @@ compute_eyes_pessimistic(int pos, struct
     *pessimistic_min = 1;
     DEBUG(DEBUG_EYES, "  pessimistic min revised to 1 (interior stones)\n");
   }
-  
+
   if (attack_point
       && *attack_point == NO_MOVE
       && max_eyes(value) != *pessimistic_min) {
@@ -957,19 +971,30 @@ compute_eyes_pessimistic(int pos, struct
 
 static void
 guess_eye_space(int pos, int effective_eyesize, int margins,
-               struct eye_data eye[BOARDMAX],
+               int bulk_score, struct eye_data eye[BOARDMAX],
                struct eyevalue *value, int *pessimistic_min)
 {
   if (effective_eyesize > 3) {
     set_eyevalue(value, 2, 2, 2, 2);
+    *pessimistic_min = 1;
+
     if ((margins == 0 && effective_eyesize > 7)
        || (margins > 0 && effective_eyesize > 9)) {
       int eyes = 2 + (effective_eyesize - 2 * (margins > 0) - 8) / 2;
-      *pessimistic_min = eyes;
+      int threshold = (4 * (eye[pos].esize - 2)
+                      + (effective_eyesize - 8) * (effective_eyesize - 9));
+
+      DEBUG(DEBUG_EYES, "size: %d(%d), threshold: %d, bulk score: %d\n",
+           eye[pos].esize, effective_eyesize, threshold, bulk_score);
+
+      if (bulk_score > threshold && effective_eyesize < 15)
+       eyes = gg_max(2, eyes - ((bulk_score - threshold) / eye[pos].esize));
+
+      if (bulk_score < threshold + eye[pos].esize || effective_eyesize >= 15)
+       *pessimistic_min = eyes;
+
       set_eyevalue(value, eyes, eyes, eyes, eyes);
     }
-    else
-      *pessimistic_min = 1;
   }
   else if (effective_eyesize > 0) {
     set_eyevalue(value, 1, 1, 1, 1);
Index: patterns/owl_defendpats.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/owl_defendpats.db,v
retrieving revision 1.104
diff -u -p -r1.104 owl_defendpats.db
--- patterns/owl_defendpats.db  3 Oct 2003 21:20:03 -0000       1.104
+++ patterns/owl_defendpats.db  9 Nov 2003 23:18:37 -0000
@@ -3656,6 +3656,17 @@ Pattern D839
 ;does_attack(*,A) && xplay_attack(b,*,c,A)
 
 
+Pattern D840
+# pp New pattern (3.5.3)
+
+|OOOOO     workaround lunch problem (the eye is not considered a unit)
+|..*.O
+|.X..O
++-----
+
+:8,-,value(80)
+
+
 #########################################################
 #                                                       #
 #                  Prevent intrusion                    #
Index: regression/owl1.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/owl1.tst,v
retrieving revision 1.79
diff -u -p -r1.79 owl1.tst
--- regression/owl1.tst 5 Nov 2003 13:55:11 -0000       1.79
+++ regression/owl1.tst 9 Nov 2003 23:17:04 -0000
@@ -298,6 +298,12 @@ loadsgf games/nngs/tommmal-gnugo-3.5.1-2
 333 owl_defend C17
 #? [0]*
 
+# A problem with extremely enthusiastic guess_eye_space() estimation.
+# Must be solved with "bulky eye" heuristic in compute_eyes_pessimistic().
+loadsgf games/selfplay1.sgf 206
+334 owl_attack E19
+#? [1 C18]
+
 ########### end of tests #####################
 
 # Report number of nodes visited by the tactical reading
Index: regression/games/selfplay1.sgf
===================================================================
RCS file: regression/games/selfplay1.sgf
diff -N regression/games/selfplay1.sgf
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ regression/games/selfplay1.sgf      9 Nov 2003 23:17:22 -0000
@@ -0,0 +1,27 @@
+(;GM[1]FF[3]
+RU[Japanese]SZ[19]HA[2]KM[0.5]
+PW[White]
+PB[Black]
+GN[White (W) vs. Black (B)]
+DT[2003-05-25]
+SY[Cgoban 1.9.14]TM[-]AB[pd][dp];W[cd];B[pq];W[po];B[qo];W[qn];B[qp];
+W[pn];B[nq];W[qj];B[ed];W[ee];B[fe];W[de];B[gd];W[cn];B[cl];W[cq];
+B[dq];W[cp];B[do];W[bn];B[em];W[qf];B[hp];W[mo];B[lp];W[ci];B[nd];
+W[ec];B[fc];W[eb];B[ek];W[ha];B[kn];W[rd];B[qc];W[rc];B[ll];W[id];
+B[kc];W[mm];B[nk];W[ol];B[fi];W[if];B[ff];W[hg];B[gh];W[ii];B[hj];
+W[ke];B[kk];W[dg];B[ki];W[ib];B[md];W[qb];B[pb];W[qh];B[ij];W[cr];
+B[dr];W[rb];B[ro];W[rn];B[ih];W[kb];B[lb];W[jc];B[ka];W[jb];B[cs];
+W[lc];B[mf];W[mc];B[mh];W[bs];B[ds];W[so];B[sp];W[sn];B[ma];W[pa];
+B[pg];W[nb];B[ph];W[qg];B[oa];W[qa];B[ob];W[bk];B[bl];W[ar];B[bj];
+W[bi];B[ak];W[ok];B[ai];W[nj];B[ag];W[be];B[cj];W[di];B[mk];W[mb];
+B[na];W[pf];B[la];W[og];B[pi];W[oh];B[ld];W[qk];B[kd];W[op];B[jd];
+W[je];B[mp];W[oq];B[or];W[rq];B[qr];W[rp];B[pp];W[np];B[lo];W[mn];
+B[qd];W[rr];B[he];W[qs];B[pr];W[ps];B[os];W[rs];B[mr];W[gb];B[ie];
+W[nf];B[fb];W[fa];B[jf];W[dd];B[dj];W[oe];B[hd];W[od];B[nc];W[gc];
+B[fd];W[ic];B[dn];W[oc];B[pc];W[ng];B[co];W[bo];B[mg];W[nl];B[mj];
+W[ni];B[hc];W[hb];B[mi];W[lm];B[km];W[ef];B[fg];W[eh];B[ei];W[qe];
+B[bm];W[am];B[ja];W[ea];B[cf];W[cm];B[eg];W[df];B[cg];W[bh];B[ah];
+W[dm];B[dl];W[an];B[al];W[ap];B[ne];W[pe];B[nh];W[oi];B[ae];W[ad];
+B[af];W[bd];B[fh];W[dh];B[ml];W[ga];B[bf];W[ln];B[ia];W[bg];B[ch];
+W[qq];B[cb];W[tt];B[dc];W[tt];B[tt]
+)