[gnugo-devel] optics / ko

[Paul Pogonyshev]

this patch is based on arend_eye_3_4.1 and includes it. i post it here
mainly for discussing, though it looks quite finished and may go to
cvs as it stands, probably.

Arend's patch is here:
http://match.stanford.edu/gnugo/patches/arend_eye_3_4.1

i tried to solve the position in Arend's mail and to get some benefits
from improved topological eye valuations. i introduced a new optics
layer between compute_eyes[_pessimistic]() and recognize_eye(). the
function is called read_eye() (can anyone think of a better name?) and
its only purpose (for now) is to solve such ko-related positions.

for the algorithm, see comments before the function.

regression delta is 4 passes, 2 fails. results are on top of the
current cvs, minus inge_3_10.1 and with pogonyshev_3_10.2b.

owl:180         PASS   properly solved.
owl:249         PASS   properly solved.
optics:1811     PASS   properly solved (same position as in owl:249).
trevor:360      PASS   properly solved (position basically the same as
                       the one in Arend's mail).

strategy3:105   FAIL   it now thinks that the black dragon along the
                       left of the board can be killed unconditionally
                       with A5 (previously saw no way to kill at all).
                       better if someone stronger looks at the test.
                       either a real FAIL or an actual PASS.
strategy4:168   FAIL   this one is not bad. it now sees that B8 can
                       defend the upper black dragon (properly). but
                       it also keeps thinking that the white dragon
                       can be attacked with B8 or C8 (as the current
                       version does). but now it no longer rejects B8
                       as an unsafe move, since it can defend black
                       stones. huge overvaluation of B8 is rather
                       owl/semeai problem which is now uncovered.

i also have some thoughts about ressurecting my eyespace/connection
code and adding it to read_eye(). it will involve some reading (very
same to the function does now), while i previously tried to implement
it statically. this is a matter of future experiments, however, and
there's no a single trace of that code in this patch.

Paul


Index: gnugo/engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.55
diff -u -r1.55 optics.c
--- gnugo/engine/optics.c       5 Oct 2002 09:20:55 -0000       1.55
+++ gnugo/engine/optics.c       9 Oct 2002 16:56:09 -0000
@@ -53,6 +53,17 @@
 
 #define MAXEYE 20
 
+
+/* This structure is used in communication between read_eye() and
+ * recognize_eye().
+ */
+struct vital_points {
+  int attacks[4 * MAXEYE];
+  int defenses[4 * MAXEYE];
+  int num_attacks;
+  int num_defenses;
+};
+
 static void
 compute_primary_domains(int color, int domain[BOARDMAX],
                        int lively[BOARDMAX],
@@ -64,11 +75,16 @@
 static void originate_eye(int origin, int pos,
                          int *esize, int *msize,
                          struct eye_data eye[BOARDMAX]);
+static int read_eye(int pos, int *attack_point, int *defense_point,
+                   struct eyevalue *value,
+                   struct eye_data eye[BOARDMAX],
+                   struct half_eye_data heye[BOARDMAX],
+                   int add_moves, int color);
 static int recognize_eye(int pos, int *attack_point, int *defense_point,
                         struct eyevalue *value,
                         struct eye_data eye[BOARDMAX],
                         struct half_eye_data heye[BOARDMAX],
-                        int add_moves, int color);
+                        int color, struct vital_points *vp);
 static void guess_eye_space(int pos, int effective_eyesize, int margins,
                            struct eye_data eye[BOARDMAX],
                            struct eyevalue *value, char *pessimistic_min);
@@ -777,8 +793,8 @@
   }
   
   /* Look up the eye space in the graphs database. */
-  if (recognize_eye(pos, attack_point, defense_point, value,
-                   eye, heye, add_moves, color))
+  if (read_eye(pos, attack_point, defense_point, value,
+              eye, heye, add_moves, color))
     return;
 
   /* Ideally any eye space that hasn't been matched yet should be two
@@ -853,8 +869,8 @@
   }
   
   /* Look up the eye space in the graphs database. */
-  if (recognize_eye(pos, attack_point, defense_point, value,
-                   eye, heye, 0, EMPTY)) {
+  if (read_eye(pos, attack_point, defense_point, value,
+              eye, heye, 0, EMPTY)) {
     *pessimistic_min = min_eyes(value) - margins;
 
     /* A single point eye which is part of a ko can't be trusted. */
@@ -990,19 +1006,99 @@
 }
 
 
-/* recognize_eye(pos, *attack_point, *defense_point, *max, *min, eye_data, 
- * half_eye_data, add_moves, color), where pos is the origin of an eyespace,
- * returns 1 if there is a pattern in eyes.db matching the eyespace, or
- * 0 if no match is found. If there is a key point for attack, (*attack_point)
- * is set to its location, or NO_MOVE if there is none.
- * Similarly (*defense_point) is the location of a vital defense point. *min
- * and *max are the minimum and maximum number of eyes that can be
- * made in this eyespace respectively. Vital attack/defense points
- * exist if and only if *min != *max.
+/* This function does some minor reading to improve the results of
+ * recognize_eye(). Currently, its only purpose is to read positions
+ * like this:
+ *
+ *      .XXXX|        with half eye         with proper eye
+ *      XXOOO|
+ *     XO.O.|           .   (1 eye)           .   (2 eyes)
+ *     XXOa.|         !..                    .*
+ *     -----+
+ *
+ * recognize_eye() sees the eyespace of the white dragon as shown
+ * (there's a half eye at a and it is considered the same as '!.' by
+ * the optics code). Normally, that eye shape gives only one secure
+ * eye, and owl thinks that the white dragon is dead unconditionally.
+ * This function tries to turn such ko-depended half eyes into proper
+ * eyes and chooses the best alternative. Note that we don't have any
+ * attack/defense codes here, since owl will determine them itself.
  *
- * If add_moves==1, this function may add a move_reason for (color) at
- * a vital point which is found by the function. If add_moves==0,
- * set color==EMPTY.
+ * If add_moves != 0, this function may add move reasons for (color)
+ * at the vital points which are found by recognize_eye(). If add_moves 
+ * == 0, set color to be EMPTY.
+ */
+static int
+read_eye(int pos, int *attack_point, int *defense_point,
+        struct eyevalue *value, struct eye_data eye[BOARDMAX], 
+        struct half_eye_data heye[BOARDMAX], 
+        int add_moves, int color)
+{
+  int eye_color;
+  int k;
+  int pos2;
+  int ko_halfeye = NO_MOVE;
+  int apos = NO_MOVE, dpos = NO_MOVE;
+  struct eyevalue ko_value;
+  struct vital_points vp;
+  struct vital_points ko_vp;
+  struct vital_points *best_vp = &vp;
+  
+  eye_color = recognize_eye(pos, attack_point, defense_point, value,
+                            eye, heye, color, &vp);
+  if (!eye_color)
+    return 0;
+
+  for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++)
+    if (eye[pos2].origin == pos
+        && heye[pos2].type == HALF_EYE && heye[pos2].value < 3.0) {
+      if (ko_halfeye != NO_MOVE) {
+       ko_halfeye = NO_MOVE;   /* We can't win two kos at once. */
+       break;            
+      }
+      
+      ko_halfeye = pos2;
+    }
+
+  if (ko_halfeye != NO_MOVE) {
+    int result;
+
+    heye[ko_halfeye].type = 0;
+    result = recognize_eye(pos, &apos, &dpos, &ko_value, eye,
+                          heye, color, &ko_vp);
+    heye[ko_halfeye].type = HALF_EYE;
+
+    /*if (result && max_eyes(value) < max_eyes(&ko_value)) {
+      *value = ko_value;
+      *attack_point = apos;
+      *defense_point = dpos;
+      best_vp = &ko_vp;
+    }*/
+  }
+
+  if (add_moves) {
+    if (eye_color != color) {
+      for (k = 0; k < best_vp->num_attacks; k++)
+       add_vital_eye_move(best_vp->attacks[k], pos, eye_color);
+    }
+    else {
+      for (k = 0; k < best_vp->num_defenses; k++)
+       add_vital_eye_move(best_vp->defenses[k], pos, eye_color);
+    }
+  }
+  
+  return 1;
+}
+
+
+/* recognize_eye(pos, *attack_point, *defense_point, *max, *min, eye_data,
+ * half_eye_data, color, vp), where pos is the origin of an eyespace, returns
+ * owner of eye (his color) if there is a pattern in eyes.db matching the
+ * eyespace, or 0 if no match is found. If there is a key point for attack,
+ * (*attack_point) is set to its location, or NO_MOVE if there is none.
+ * Similarly (*defense_point) is the location of a vital defense point.
+ * *value is set according to the pattern found. Vital attack/defense points
+ * exist if and only if min_eyes(value) != max_eyes(value).
  */
 
 static int
@@ -1010,7 +1106,7 @@
              struct eyevalue *value,
              struct eye_data eye[BOARDMAX], 
              struct half_eye_data heye[BOARDMAX], 
-             int add_moves, int color)
+             int color, struct vital_points *vp)
 {
   int m, n;
   int k;
@@ -1191,15 +1287,13 @@
       *value = graphs[graph].value;
       if (eye_move_urgency(value) > 0) {
        /* Collect all attack and defense points in the pattern. */
-       int attack_points[4 * MAXEYE];
-       int defense_points[4 * MAXEYE];
-       int num_attacks = 0;
-       int num_defenses = 0;
+       vp->num_attacks = 0;
+       vp->num_defenses = 0;
 
        for (k = 0; k < graphs[graph].esize; k++) {
          if (graphs[graph].vertex[k].type == '*'
              || graphs[graph].vertex[k].type == '<')
-           attack_points[num_attacks++] = vpos[map[k]];
+           vp->attacks[vp->num_attacks++] = vpos[map[k]];
          else if (graphs[graph].vertex[k].type == '@'
                   || graphs[graph].vertex[k].type == '(') {
            /* check for marginal matching half eye diagonal
@@ -1212,15 +1306,16 @@
              struct half_eye_data *this_half_eye = &heye[vpos[map[k]-1]];
              
              for (ix = 0; ix < this_half_eye->num_attacks; ix++)
-               attack_points[num_attacks++] = this_half_eye->attack_point[ix];
+               vp->attacks[vp->num_attacks++] =
+                 this_half_eye->attack_point[ix];
            }
            else
-             attack_points[num_attacks++] = vpos[map[k]];
+             vp->attacks[vp->num_attacks++] = vpos[map[k]];
          }
          
          if (graphs[graph].vertex[k].type == '*'
              || graphs[graph].vertex[k].type == '>')
-           defense_points[num_defenses++] = vpos[map[k]];
+           vp->defenses[vp->num_defenses++] = vpos[map[k]];
          else if (graphs[graph].vertex[k].type == '@'
                   || graphs[graph].vertex[k].type == ')') {
            /* Check for marginal matching half eye diagonal. */
@@ -1230,24 +1325,24 @@
              struct half_eye_data *this_half_eye = &heye[vpos[map[k]-1]];
 
              for (ix = 0; ix < this_half_eye->num_defends; ix++)
-               defense_points[num_defenses++] 
+               vp->defenses[vp->num_defenses++] 
                  = this_half_eye->defense_point[ix];
            }
            else
-             defense_points[num_defenses++] = vpos[map[k]];
+             vp->defenses[vp->num_defenses++] = vpos[map[k]];
          }
        }
        
-       gg_assert(num_attacks > 0 && num_defenses > 0);
+       gg_assert(vp->num_attacks > 0 && vp->num_defenses > 0);
 
-       *attack_point = attack_points[0];
+       *attack_point = vp->attacks[0];
        /* If possible, choose a non-sacrificial defense point.
          * Compare white T8 and T6 in lazarus:21.
         */
-       *defense_point = defense_points[0];
-       for (k = 0; k < num_defenses; k++) {
-         if (safe_move(defense_points[k], eye_color) == WIN) {
-           *defense_point = defense_points[k];
+       *defense_point = vp->defenses[0];
+       for (k = 0; k < vp->num_defenses; k++) {
+         if (safe_move(vp->defenses[k], eye_color) == WIN) {
+           *defense_point = vp->defenses[k];
            break;
          }
        }
@@ -1256,20 +1351,10 @@
              *attack_point, *defense_point);
        DEBUG(DEBUG_EYES, "  pattern matched:  %s\n", graphs[graph].patname);
 
-       if (add_moves) {
-         if (eye_color != color) {
-           for (k = 0; k < num_attacks; k++)
-             add_vital_eye_move(attack_points[k], pos, eye_color);
-         }
-         else {
-           for (k = 0; k < num_defenses; k++)
-             add_vital_eye_move(defense_points[k], pos, eye_color);
-         }
-       }
       }
       TRACE("eye space at %1m of type %s\n", pos, graphs[graph].patname);
 
-      return 1;
+      return eye_color;
     }
   }
 
@@ -1639,7 +1724,7 @@
   if (board[pos] == EMPTY) {
     /* We should normally have a safe move, but occasionally it may
      * happen that it's not safe. There are complications, however,
-     * with a position like this
+     * with a position like this:
      *
      * .XXXX|
      * XXOO.|
@@ -1647,6 +1732,8 @@
      * XXO.O|
      * -----+
      *
+     * Therefore we ignore our own safety if opponent's safety depends
+     * on ko.
      */
 
     int our_safety = safe_move(pos, color);
@@ -1654,16 +1741,14 @@
     
     if (your_safety == 0)
       value = 0.0;
-    else if (our_safety == 0 && your_safety == WIN)
+    else if (your_safety != WIN)
+      value = a;
+    else if (our_safety == 0)        /* So your_safety == WIN. */
       value = 2.0;
-    else if (our_safety == WIN && your_safety == WIN)
+    else if (our_safety == WIN)
       value = 1.0;
-    else if (our_safety == WIN && your_safety != WIN)
-      value = a;
-    else if (our_safety != WIN && your_safety == WIN)
+    else                             /* our_safety depends on ko. */
       value = b;
-    else
-      value = 1.0; /* Both contingent on ko. Probably can't happen. */
 
     apos = pos;
     dpos = pos;