[gnugo-devel] dragon field in struct eye_data

[Gunnar Farneback]

This patch removes the dragon field from struct eye_data. The purpose
of the dragon field is to keep track of to which dragon to count an
eyespace. This is problematic, however, since it requires all strings
surrounding an eyespace to be amalgamated. While this may sound
natural, the eyespace generation just isn't good enough to trust for
amalgamations. Moreover, it isn't particularly expensive to
dynamically find the dragons surrounding an eyespace, and the patch
implements the new function find_eye_dragons() for this purpose.

Notice that this patch does not take out the amalgamations around eye
spaces done by dragon_eye(), but it does make it possible to do that
in the future. Then find_eye_dragons() may return multiple dragons for
a single eyespace.

- dragon field in struct eye_data removed
- new function find_eye_dragons() in optics.c
- dragon_invincible() and genus computation in make_dragons() revised

Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.61
diff -u -r1.61 dragon.c
--- engine/dragon.c     9 Apr 2002 16:46:46 -0000       1.61
+++ engine/dragon.c     16 May 2002 19:00:46 -0000
@@ -89,7 +89,6 @@
   int i, j;
   int dr;
   int d;
-  int k;
   int last_move;
 
   start_timer(2);
@@ -105,12 +104,8 @@
    */
   find_connections();
   time_report(2, "  time to find connections", NO_MOVE, 1.0);
-  
-  /* Amalgamate dragons sharing an eyespace (not ko). At the same time
-   * we decide to which dragon an eyespace belongs. Ko eyespaces
-   * (typically false eyes but sometimes halfeyes) get assigned to an
-   * arbitrary neighbor that is not the ko stone.
-   */
+
+  /* Amalgamate dragons sharing an eyespace (not ko). */
 
   for (str = BOARDMIN; str < BOARDMAX; str++)
     if (ON_BOARD(str)) {
@@ -120,13 +115,6 @@
        if (!is_ko_point(str)
            || black_eye[str].esize > 1) /* Only exclude living kos. */
          dragon_eye(str, black_eye);
-       else {
-         for (k = 0; k < 4; k++)
-           if (ON_BOARD(str + delta[k]) && !is_ko_point(str + delta[k])) {
-             black_eye[str].dragon = dragon[str + delta[k]].origin;
-             break;
-           }
-       }
       }
          
       if (white_eye[str].color == WHITE_BORDER
@@ -134,17 +122,10 @@
        if (!is_ko_point(str)
            || white_eye[str].esize > 1) /* Only exclude living kos. */
          dragon_eye(str, white_eye);
-       else {
-         for (k = 0; k < 4; k++)
-           if (ON_BOARD(str + delta[k]) && !is_ko_point(str + delta[k])) {
-             white_eye[str].dragon = dragon[str + delta[k]].origin;
-             break;
-           }
-       }
       }
     }
   time_report(2, "  time to amalgamate dragons", NO_MOVE, 1.0);
-  
+
   /* At this time, all dragons have been finalized and we can
    * initialize the dragon2[] array. After that we can no longer allow
    * amalgamation of dragons.
@@ -195,22 +176,6 @@
     }
   time_report(2, "  time to find lunches", NO_MOVE, 1.0);
 
-  /* In case origins of dragons got moved, put the dragons of eyes aright. */
-  for (str = BOARDMIN; str < BOARDMAX; str++) {
-    if (!ON_BOARD(str))
-      continue;
-    
-    if (black_eye[str].dragon != NO_MOVE) {
-      dr = dragon[black_eye[str].dragon].origin;
-      black_eye[str].dragon = dr;
-    }
-    
-    if (white_eye[str].dragon != NO_MOVE) {
-      dr = dragon[white_eye[str].dragon].origin;
-      white_eye[str].dragon = dr;
-    }
-  }
-  time_report(2, "  time to fix origins", NO_MOVE, 1.0);
   
   /* Find topological half eyes and false eyes by analyzing the
    * diagonal intersections, as described in the Texinfo
@@ -226,8 +191,7 @@
 
       if (black_eye[str].color == BLACK_BORDER
          && (!black_eye[str].marginal || life)
-         && black_eye[str].neighbors <= 1
-         && black_eye[str].dragon != NO_MOVE) {
+         && black_eye[str].neighbors <= 1) {
        sum = topological_eye(str, BLACK, black_eye, white_eye, half_eye);
        if (sum >= 4.0) {
          half_eye[str].type = FALSE_EYE;
@@ -242,8 +206,7 @@
       
       if (white_eye[str].color == WHITE_BORDER
          && (!white_eye[str].marginal || life)
-         && white_eye[str].neighbors <= 1
-         && white_eye[str].dragon != NO_MOVE) {
+         && white_eye[str].neighbors <= 1) {
        sum = topological_eye(str, WHITE, black_eye, white_eye, half_eye);
        if (sum >= 4.0) {
          half_eye[str].type = FALSE_EYE;
@@ -268,8 +231,7 @@
       str = POS(i, j);
 
       if (black_eye[str].color == BLACK_BORDER
-         && black_eye[str].origin == str
-         && black_eye[str].dragon != NO_MOVE)
+         && black_eye[str].origin == str)
       {
        int max, min, attack_point, defense_point;
 
@@ -285,8 +247,7 @@
       }
 
       if (white_eye[str].color == WHITE_BORDER
-         && white_eye[str].origin == str
-         && white_eye[str].dragon != NO_MOVE)
+         && white_eye[str].origin == str)
       {
        int max, min, attack_point, defense_point;
 
@@ -304,50 +265,45 @@
   time_report(2, "  time to find eyes", NO_MOVE, 1.0);
 
   /* Now we compute the genus. */
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++) {
-      str = POS(i, j);
-
-      if (black_eye[str].color == BLACK_BORDER
-         && black_eye[str].dragon != NO_MOVE
-         && black_eye[str].origin == str)
-      {
-       dr = black_eye[str].dragon;
-
-       gg_assert(board[dr] == BLACK);
-       TRACE("eye at %1m found for dragon at %1m--augmenting genus\n",
-             str, dr);
-       DRAGON2(dr).genus += (black_eye[str].mineye);
-       DRAGON2(dr).heyes += (black_eye[str].maxeye - black_eye[str].mineye);
-       if (black_eye[str].maxeye - black_eye[str].mineye > 0)
-         DRAGON2(dr).heye = black_eye[str].attack_point;
-      }
-      if ((white_eye[str].color == WHITE_BORDER) 
-         && (white_eye[str].dragon != NO_MOVE)
-         && (white_eye[str].origin == str)) 
-      {
-       dr = white_eye[str].dragon;
-
-       gg_assert(board[dr] == WHITE);
-       TRACE("eye at %1m found for dragon at %1m--augmenting genus\n", 
-             str, dr);
-       DRAGON2(dr).genus += (white_eye[str].mineye);
-       DRAGON2(dr).heyes += (white_eye[str].maxeye - white_eye[str].mineye);
-       if (white_eye[str].maxeye - white_eye[str].mineye > 0) {
-         DRAGON2(dr).heye = white_eye[str].attack_point;
-       }
+  for (str = BOARDMIN; str < BOARDMAX; str++) {
+    if (!ON_BOARD(str))
+      continue;
+    
+    if (black_eye[str].color == BLACK_BORDER
+       && black_eye[str].origin == str
+       && find_eye_dragons(black_eye[str].origin, black_eye,
+                           BLACK, &dr, 1) == 1) {
+      
+      gg_assert(board[dr] == BLACK);
+      TRACE("eye at %1m found for dragon at %1m--augmenting genus\n",
+           str, dr);
+      DRAGON2(dr).genus += black_eye[str].mineye;
+      DRAGON2(dr).heyes += (black_eye[str].maxeye - black_eye[str].mineye);
+      if (black_eye[str].maxeye - black_eye[str].mineye > 0)
+       DRAGON2(dr).heye = black_eye[str].attack_point;
+    }
+    
+    if (white_eye[str].color == WHITE_BORDER
+       && white_eye[str].origin == str
+       && find_eye_dragons(white_eye[str].origin, white_eye,
+                           WHITE, &dr, 1) == 1) {
+      
+      gg_assert(board[dr] == WHITE);
+      TRACE("eye at %1m found for dragon at %1m--augmenting genus\n",
+           str, dr);
+      DRAGON2(dr).genus += white_eye[str].mineye;
+      DRAGON2(dr).heyes += (white_eye[str].maxeye - white_eye[str].mineye);
+      if (white_eye[str].maxeye - white_eye[str].mineye > 0) {
+       DRAGON2(dr).heye = white_eye[str].attack_point;
       }
     }
+  }
   time_report(2, "  time to compute genus", NO_MOVE, 1.0);
 
   /* Compute the escape route measure. */
   for (str = BOARDMIN; str < BOARDMAX; str++)
-    if (ON_BOARD(str)) {
-      if (dragon[str].origin == str
-         && IS_STONE(board[str])) {
-       DRAGON2(str).escape_route = compute_escape(str, 0);
-      }
-    }
+    if (IS_STONE(board[str]) && dragon[str].origin == str)
+      DRAGON2(str).escape_route = compute_escape(str, 0);
   time_report(2, "  time to compute escape", NO_MOVE, 1.0);
 
   /* Update the segmentation of the initial influence before we
@@ -991,42 +947,56 @@
  */
 
 static int
-dragon_invincible(int pos)
+dragon_invincible(int dr)
 {
   struct eye_data *eye;
-  int i, j;
-  int ii;
+  int eye_color;
+  int k;
+  int pos;
   int strong_eyes = 0;
-
-  gg_assert(IS_STONE(board[pos]));
+  int mx[BOARDMAX];
+  
+  gg_assert(IS_STONE(board[dr]));
 
   /* First look for invincible strings in the dragon. */
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++) {
-      ii = POS(i, j);
-
-      if (is_same_dragon(ii, pos) && worm[ii].invincible)
-        return 1;
-    }
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (ON_BOARD(pos) && is_same_dragon(pos, dr) && worm[pos].invincible)
+      return 1;
+  }
 
   /* Examine the eye spaces.
    * FIXME: The check for half eyes or false eyes may be too weak.
    */
-  if (board[pos] == BLACK)
+  if (board[dr] == BLACK) {
     eye = black_eye;
-  else
+    eye_color = BLACK_BORDER;
+  }
+  else {
     eye = white_eye;
+    eye_color = WHITE_BORDER;
+  }
 
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++) {
-      ii = POS(i, j);
+  memset(mx, 0, sizeof(mx));
 
-      if (eye[ii].origin == ii
-          && is_same_dragon(eye[ii].dragon, pos)) {
-        if (eye[ii].msize == 0 && eye[ii].mineye > 0)
-          strong_eyes++;
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (board[pos] == board[dr] && is_same_dragon(pos, dr)) {
+      for (k = 0; k < 4; k++) {
+       int pos2 = pos + delta[k];
+       if (ON_BOARD(pos2)
+           && eye[pos2].color == eye_color
+           && eye[pos2].origin != NO_MOVE
+           && !eye[pos2].marginal)
+         mx[eye[pos2].origin] = 1;
       }
     }
+  }
+
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (mx[pos]
+       && eye[pos].msize == 0
+       && eye[pos].mineye > 0)
+      strong_eyes++;
+  }
 
   if (strong_eyes >= 2)
     return 1;
@@ -1262,18 +1232,6 @@
            }
          }
        }
-      }
-    }
-  
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++) {
-      ii = POS(i, j);
-
-      if ((eye[ii].color == BLACK_BORDER 
-          || eye[ii].color == WHITE_BORDER) 
-         && eye[ii].origin == pos)
-      {
-       eye[ii].dragon = dr;
       }
     }
 }
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.99
diff -u -r1.99 liberty.h
--- engine/liberty.h    6 May 2002 14:27:31 -0000       1.99
+++ engine/liberty.h    16 May 2002 19:00:46 -0000
@@ -807,7 +807,6 @@
   int mineye;        /* number of eyes if attacker plays first               */
   int attack_point;  /* vital point for attack                               */
   int defense_point; /* vital point for defense                              */
-  int dragon;        /* origin of the surrounding dragon                     */
 
   /* The above fields are constant on the whole eyespace. */
   /* ---------------------------------------------------------------- */
@@ -845,6 +844,8 @@
                   struct half_eye_data heye[BOARDMAX],
                     int add_moves, int color);
 void propagate_eye(int pos, struct eye_data eye[BOARDMAX]);
+int find_eye_dragons(int origin, struct eye_data eye[BOARDMAX], int eye_color,
+                    int dragons[], int max_dragons);
 float topological_eye(int pos, int color,
                      struct eye_data b_eye[BOARDMAX],
                      struct eye_data w_eye[BOARDMAX],
Index: engine/move_reasons.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.c,v
retrieving revision 1.86
diff -u -r1.86 move_reasons.c
--- engine/move_reasons.c       10 May 2002 17:18:59 -0000      1.86
+++ engine/move_reasons.c       16 May 2002 19:00:47 -0000
@@ -1550,11 +1550,9 @@
          aa = eyes[move_reasons[r].what];
          ecolor = eyecolor[move_reasons[r].what];
          if (ecolor == WHITE)
-           gprintf("Move at %1m vital eye point for dragon %1m (eye %1m)\n",
-                   pos, white_eye[aa].dragon, aa);
+           gprintf("Move at %1m vital eye point for eye %1m\n", pos, aa);
          else
-           gprintf("Move at %1m vital eye point for dragon %1m (eye %1m)\n",
-                   pos, black_eye[aa].dragon, aa);
+           gprintf("Move at %1m vital eye point for eye %1m\n", pos, aa);
          break;
          
        case EITHER_MOVE:
Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.43
diff -u -r1.43 optics.c
--- engine/optics.c     16 May 2002 09:07:48 -0000      1.43
+++ engine/optics.c     16 May 2002 19:00:47 -0000
@@ -103,7 +103,6 @@
   eye->mineye = 0;
   eye->attack_point = NO_MOVE;
   eye->defense_point = NO_MOVE;
-  eye->dragon = NO_MOVE;
   eye->marginal = 0;
   eye->type = 0;
   eye->neighbors = 0;
@@ -582,10 +581,47 @@
       eye[pos].mineye        = eye[origin].mineye;
       eye[pos].attack_point  = eye[origin].attack_point;
       eye[pos].defense_point = eye[origin].defense_point;
-      eye[pos].dragon        = eye[origin].dragon;
     }
 }
 
+
+int
+find_eye_dragons(int origin, struct eye_data eye[BOARDMAX], int eye_color,
+                int dragons[], int max_dragons)
+{
+  int mx[BOARDMAX];
+  int num_dragons = 0;
+  int pos;
+
+  memset(mx, 0, sizeof(mx));
+  if (debug & 0x800000)
+    gprintf("find_eye_dragons: %1m %C\n", origin, eye_color);
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (board[pos] == eye_color
+       && mx[dragon[pos].origin] == 0
+       && ((ON_BOARD(SOUTH(pos))
+            && eye[SOUTH(pos)].origin == origin
+            && !eye[SOUTH(pos)].marginal)
+           || (ON_BOARD(WEST(pos))
+               && eye[WEST(pos)].origin == origin
+               && !eye[WEST(pos)].marginal)
+           || (ON_BOARD(NORTH(pos))
+               && eye[NORTH(pos)].origin == origin
+               && !eye[NORTH(pos)].marginal)
+           || (ON_BOARD(EAST(pos))
+               && eye[EAST(pos)].origin == origin
+               && !eye[EAST(pos)].marginal))) {
+      if (debug & 0x800000)
+       gprintf("  dragon: %1m %1m\n", pos, dragon[pos].origin);
+      mx[dragon[pos].origin] = 1;
+      if (dragons != NULL && num_dragons < max_dragons)
+       dragons[num_dragons] = dragon[pos].origin;
+      num_dragons++;
+    }
+  }
+  
+  return num_dragons;
+}
 
 /* Print debugging data for the eyeshape at (i,j). Useful with GDB.
  */
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.36
diff -u -r1.36 value_moves.c
--- engine/value_moves.c        6 May 2002 14:27:31 -0000       1.36
+++ engine/value_moves.c        16 May 2002 19:00:47 -0000
@@ -279,9 +279,9 @@
        int ecolor = eyecolor[move_reasons[r].what];
        
        if (ecolor == WHITE)
-         dd1 = white_eye[ee].dragon;
+         find_eye_dragons(ee, white_eye, WHITE, &dd1, 1);
        else
-         dd1 = black_eye[ee].dragon;
+         find_eye_dragons(ee, black_eye, BLACK, &dd1, 1);
        
        if (dd1 == NO_MOVE) /* Maybe we should assert this not to happen. */
          continue;
@@ -1721,7 +1721,6 @@
   int d2 = -1;
   int worm1 = -1;
   int worm2 = -1;
-  int ecolor = 0;
   
   float this_value = 0.0;
   float tot_value = 0.0;
@@ -1962,6 +1961,7 @@
        break;
        
       case VITAL_EYE_MOVE:
+#if 0
        /*
         * The value of the threatened group itself has already been
         * accounted for in territorial_value. Now we need to determine
@@ -1992,7 +1992,6 @@
          break;
        }
 
-#if 0
        if (dragon[bb].matcher_status == CRITICAL) {
          this_value = ???
          TRACE("  %1m: %f - vital for %1m\n",
Index: interface/debugboard/gui.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/debugboard/gui.c,v
retrieving revision 1.15
diff -u -r1.15 gui.c
--- interface/debugboard/gui.c  4 Mar 2002 06:49:08 -0000       1.15
+++ interface/debugboard/gui.c  16 May 2002 19:00:47 -0000
@@ -382,12 +382,14 @@
   gg_wprintw(info_window, "%d   ", eyedata[pos].esize);
   wmove(info_window, 6, 18);
   gg_wprintw(info_window, "%d   ", eyedata[pos].msize);
+#if 0
   wmove(info_window, 7, 18);
   if (eyedata[pos].dragon == NO_MOVE)
     gg_wprintw(info_window, "---");
   else
     gg_wprintw(info_window, "%s ",
               location_to_string(eyedata[pos].dragon));
+#endif
 
   wmove(info_window, 11, 18);
   gg_wprintw(info_window, "%d  ", eyedata[pos].type);