[gnugo-devel] dragon amalgamation revisited

[Gunnar Farnebäck]

This patch makes some small simplifications of the dragon amalgamation
procedure. This is primarily a question of breaking out the call to
find_cuts() from make_domains() and stop find_cuts() from modifying
the eye data. For those who are new, the history with this is that the
dragon construction once was based on the principle that eye spaces
were constructed first and then dragons were built by amalgamation
around eye spaces. The main weakness of this approach was that the
main eye construction algorithm did not involve any real connection
analysis, so this was left to pattern matching in find_cuts() and to
stop amalgamation it had to add in marginal eye vertices to split the
involved eye spaces into two. This worked to an extent but was kind of
messy and sometimes did weird things to the eyespaces.

Since then the connection reading has been implemented and the
amalgamation these days is only based on pattern matching and
connection reading, but not on eyespaces. Still find_cuts() has the
power to modify eyespaces (and sometimes does) but that is more a
distraction than a useful feature now.

This patch completely does away with the cut field and the
INHIBIT_CONNECTION bit of the type field of struct eye_data. The work
of those are instead done by the new global array cutting_points[].
Also find_cuts() is no longer allowed to modify the eyespaces.

The real point of simplifying the amalgamation code is that then we
can easily run amalgamation independently of anything else, and in
particular at stackp>0. This is also implemented by the patch in form
of the new function compute_new_dragons() in dragon.c. It is not
actually used anywhere yet but that will change in a later patch.

The only effect on regressions is a PASS of optics:1801, probably due
to find_cuts no longer being allowed to make eye vertices marginal.
Changes in node counts are negligible.

- find_cuts() called from make_dragons() instead of make_domains()
- new function compute_new_dragons() and new static function
  join_new_dragons() in dragon.c
- new global array cutting_points[]
- cut field removed from struct eye_data
- INHIBIT_CONNECTION bit no longer used in the type field of struct
  eye_data
- find_cuts() no longer allowed to modify eyespaces

/Gunnar

Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.139
diff -u -r1.139 dragon.c
--- engine/dragon.c     25 May 2004 03:13:28 -0000      1.139
+++ engine/dragon.c     29 May 2004 23:16:50 -0000
@@ -108,11 +108,11 @@
   dragon2_initialized = 0;
   initialize_dragon_data();
 
-  make_domains(black_eye, white_eye, 0);
-
   /* Find explicit connections patterns in database and amalgamate
    * involved dragons.
    */
+  memset(cutting_points, 0, sizeof(cutting_points));
+  find_cuts();
   find_connections();
 
   /* At this time, all dragons have been finalized and we can
@@ -121,6 +121,8 @@
    */
   initialize_supplementary_dragon_data();
   
+  make_domains(black_eye, white_eye, 0);
+
   /* Find adjacent worms which can be easily captured: */
   find_lunches();
 
@@ -1661,6 +1663,66 @@
 }
 
 
+static int new_dragon_origins[BOARDMAX];
+
+/* Compute new dragons, e.g. after having made a move. This will not
+ * affect any global state.
+ */
+void
+compute_new_dragons(int dragon_origins[BOARDMAX])
+{
+  int pos;
+  int saved_cutting_points[BOARDMAX];
+
+  /* This is currently necessary in order not to mess up the
+   * worm[].cutstone2 field. See cutstone2_helper in
+   * patterns/helpers.c. On the other hand it shouldn't be very
+   * interesting to recompute dragons in the original position.
+   */
+  gg_assert(stackp > 0);
+  
+  memcpy(saved_cutting_points, cutting_points, sizeof(cutting_points));
+  memset(cutting_points, 0, sizeof(cutting_points));
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+    if (ON_BOARD(pos)) {
+      if (board[pos] == EMPTY)
+       new_dragon_origins[pos] = NO_MOVE;
+      else
+       new_dragon_origins[pos] = find_origin(pos);
+    }
+  
+  find_cuts();
+  find_connections();
+
+  memcpy(cutting_points, saved_cutting_points, sizeof(cutting_points));
+  memcpy(dragon_origins, new_dragon_origins, sizeof(new_dragon_origins));
+}
+
+
+/* This gets called if we are trying to compute dragons outside of
+ * make_dragons(), typically after a move has been made.
+ */
+static void
+join_new_dragons(int d1, int d2)
+{
+  int pos;
+  /* Normalize dragon coordinates. */
+  d1 = new_dragon_origins[d1];
+  d2 = new_dragon_origins[d2];
+
+  /* If d1 and d2 are the same dragon, we do nothing. */
+  if (d1 == d2)
+    return;
+
+  ASSERT1(board[d1] == board[d2], d1);
+  ASSERT1(IS_STONE(board[d1]), d1);
+
+  /* Don't bother to do anything fance with dragon origins. */
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+    if (ON_BOARD(pos) && new_dragon_origins[pos] == d2)
+      new_dragon_origins[pos] = d1;
+}
+
 /* 
  * join_dragons amalgamates the dragon at (d1) to the
  * dragon at (d2).
@@ -1672,6 +1734,14 @@
   int ii;
   int origin; /* new origin */
 
+  /* If not called from make_dragons(), we don't work on the main
+   * dragon[] array.
+   */
+  if (stackp > 0) {
+    join_new_dragons(d1, d2);
+    return;
+  }
+  
   /* Normalize dragon coordinates. */
   d1 = dragon[d1].origin;
   d2 = dragon[d2].origin;
@@ -1864,12 +1934,7 @@
       queue_start++;
 
       /* Do not pass connection inhibited intersections. */
-      if ((color == WHITE
-          && ((white_eye[ii].type & INHIBIT_CONNECTION)
-              || white_eye[ii].cut == 1))
-         || (color == BLACK
-             && ((black_eye[ii].type & INHIBIT_CONNECTION)
-                 || black_eye[ii].cut == 1)))
+      if (cut_possible(ii, OTHER_COLOR(color)))
        continue;
       if (distance == 4)
        escape_potential += escape_value[ii];
Index: engine/globals.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v
retrieving revision 1.65
diff -u -r1.65 globals.c
--- engine/globals.c    28 Apr 2004 16:37:30 -0000      1.65
+++ engine/globals.c    29 May 2004 23:16:50 -0000
@@ -156,6 +156,8 @@
 struct surround_data  surroundings[MAX_SURROUND];
 int                   surround_pointer;
 
+int cutting_points[BOARDMAX];
+
 double slowest_time = 0.0;
 int    slowest_move = NO_MOVE;
 int    slowest_movenum = 0;
Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.102
diff -u -r1.102 influence.c
--- engine/influence.c  25 May 2004 03:13:31 -0000      1.102
+++ engine/influence.c  29 May 2004 23:16:50 -0000
@@ -1303,11 +1303,8 @@
     color = WHITE; 
   else
     color = EMPTY;
-  
-  if (color == WHITE && (white_eye[pos].type & INHIBIT_CONNECTION))
-    return EMPTY;
-  
-  if (color == BLACK && (black_eye[pos].type & INHIBIT_CONNECTION))
+
+  if (cut_possible(pos, OTHER_COLOR(color)))
     return EMPTY;
   
   return color;
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.217
diff -u -r1.217 liberty.h
--- engine/liberty.h    27 May 2004 00:08:47 -0000      1.217
+++ engine/liberty.h    29 May 2004 23:16:50 -0000
@@ -37,7 +37,6 @@
 
 #define FALSE_EYE          1
 #define HALF_EYE           2
-#define INHIBIT_CONNECTION 4
 
 
 #define REVERSE_RESULT(result)         (WIN - result)
@@ -304,6 +303,7 @@
 int safe_move(int move, int color);
 int does_secure(int color, int move, int pos);
 
+void compute_new_dragons(int dragon_origins[BOARDMAX]);
 void join_dragons(int d1, int d2);
 int dragon_escape(char goal[BOARDMAX], int color, char escape_value[BOARDMAX]);
 void compute_refined_dragon_weaknesses(void);
@@ -977,7 +977,6 @@
   char type;                 /* Various characteristics of the eyespace    */
   char neighbors;            /* number of neighbors in eyespace            */
   char marginal_neighbors;   /* number of marginal neighbors               */
-  char cut;                  /* Opponent can cut at vertex.                */
 };
 
 struct vital_eye_points {
@@ -990,6 +989,12 @@
 
 extern struct eye_data white_eye[BOARDMAX];
 extern struct eye_data black_eye[BOARDMAX];
+
+/* Array with the information which was previously stored in the cut
+ * field and in the INHIBIT_CONNECTION bit of the type field in struct
+ * eye_data.
+ */
+extern int cutting_points[BOARDMAX];
 
 /* The following declarations have to be postponed until after the
  * definition of struct eye_data or struct half_eye_data.
Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.91
diff -u -r1.91 optics.c
--- engine/optics.c     27 May 2004 00:08:47 -0000      1.91
+++ engine/optics.c     29 May 2004 23:16:51 -0000
@@ -105,7 +105,6 @@
   eye->type = 0;
   eye->neighbors = 0;
   eye->marginal_neighbors = 0;
-  eye->cut = 0;
 }
 
 
@@ -209,15 +208,6 @@
       }
     }
   }
-  
-  /* 
-   * If called from make_dragons, search connection database for cutting
-   * points, which may modify the eyespace in order to avoid amalgamation and
-   * reflect the weakness in the position. The following test fails
-   * if called from the owl code.
-   */
-  if (!owl_call)
-    find_cuts();
   
   /* The eye spaces are all found. Now we need to find the origins. */
   partition_eyespaces(b_eye, BLACK);
Index: engine/utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.93
diff -u -r1.93 utils.c
--- engine/utils.c      27 May 2004 00:08:47 -0000      1.93
+++ engine/utils.c      29 May 2004 23:16:51 -0000
@@ -79,12 +79,7 @@
 int
 cut_possible(int pos, int color)
 {
-  if (color == WHITE)
-    return (black_eye[pos].cut
-           || (black_eye[pos].type & INHIBIT_CONNECTION));
-  else
-    return (white_eye[pos].cut
-           || (white_eye[pos].type & INHIBIT_CONNECTION));
+  return (cutting_points[pos] & OTHER_COLOR(color)) != 0;
 }
 
 
Index: engine/worm.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/worm.c,v
retrieving revision 1.62
diff -u -r1.62 worm.c
--- engine/worm.c       29 Apr 2004 23:59:21 -0000      1.62
+++ engine/worm.c       29 May 2004 23:16:51 -0000
@@ -152,7 +152,7 @@
    *     cutting or connecting the surrounding dragons. 
    *
    * The cutstone field will now be set. The cutstone2 field is set
-   * later, during find_cuts(), called from make_domains().
+   * later, during find_cuts(), called from make_dragons().
    *
    * We maintain both fields because the historically older cutstone
    * field is needed to deal with the fact that e.g. in the position
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.150
diff -u -r1.150 play_gtp.c
--- interface/play_gtp.c        25 May 2004 03:13:48 -0000      1.150
+++ interface/play_gtp.c        29 May 2004 23:16:52 -0000
@@ -4114,7 +4114,6 @@
   gtp_printf("type                 %d\n", e->type);
   gtp_printf("neighbors            %d\n", e->neighbors);
   gtp_printf("marginal_neighbors   %d\n", e->marginal_neighbors);
-  gtp_printf("cut                  %d\n", e->cut);
   
   gtp_printf("\n");
   return GTP_OK;
Index: patterns/connections.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/connections.c,v
retrieving revision 1.39
diff -u -r1.39 connections.c
--- patterns/connections.c      24 Jan 2004 04:04:56 -0000      1.39
+++ patterns/connections.c      29 May 2004 23:16:52 -0000
@@ -26,10 +26,9 @@
 
 
 /* Try to match all (permutations of) connection patterns at (m,n).
- * For each match, if it is a B pattern, set cutting point in worm
- * data structure and make eye space marginal for the connection
- * inhibiting entries of the pattern. If it is a C pattern, amalgamate
- * the dragons in the pattern.
+ * For each match, if it is a B pattern, set cutting point in
+ * cutting_points array. If it is a C pattern, amalgamate the dragons
+ * in the pattern.
  */
 
 static void
@@ -49,10 +48,6 @@
   if ((pattern->class & CLASS_B) && !safe_move(move, other))
     return;
 
-  /* Reject C patterns in which an INHIBIT_CONNECTION was set
-   * previously during find_cuts.
-   */
-
   if (pattern->class & CLASS_C) {
     /* If C pattern, test if there are more than one dragon in this
      * pattern so that there is something to connect, before doing any
@@ -103,9 +98,9 @@
        /* transform pattern real coordinate */
        int pos = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor);
 
-       if (worm[pos].attack_codes[0] == WIN
-         && (move == NO_MOVE
-             || !does_defend(move, pos)))
+       if (attack(pos, NULL) == WIN
+           && (move == NO_MOVE
+               || !does_defend(move, pos)))
          return; /* Match failed */
       }
     }
@@ -126,23 +121,10 @@
     pattern->autohelper(ll, move, color, 1);
   }
 
-  /* If it is a B pattern, set cutting point in eye data and make eye
-   * space marginal. Also set the connection inhibition property.
-   */
+  /* If it is a B pattern, set cutting point. */
   
   if (pattern->class & CLASS_B) {
-    if (color == WHITE) {
-      white_eye[move].cut = 1;
-      white_eye[move].type |= INHIBIT_CONNECTION;
-    }
-    else {
-      black_eye[move].cut = 1;
-      black_eye[move].type |= INHIBIT_CONNECTION;
-    }
-    if (color == WHITE && white_eye[move].color == WHITE)
-      white_eye[move].marginal = 1;
-    else if (color == BLACK && black_eye[move].color == BLACK)
-      black_eye[move].marginal = 1;
+    cutting_points[move] |= color;
   }
   else if (!(pattern->class & CLASS_C))
     return; /* Nothing more to do, up to the helper or autohelper
@@ -164,7 +146,7 @@
     if ((pattern->class & CLASS_C)
        && board[pos] == color
        && pattern->patn[k].att == ATT_O
-       && ((pattern->class & CLASS_s) || worm[pos].attack_codes[0] == 0)) {
+       && ((pattern->class & CLASS_s) || attack(pos, NULL) == 0)) {
       if (first_dragon == NO_MOVE)
        first_dragon = dragon[pos].origin;
       else if (second_dragon == NO_MOVE
@@ -186,14 +168,8 @@
     if (pattern->class & CLASS_B) {
       if (pattern->patn[k].att != ATT_not)
        break; /* The inhibition points are guaranteed to come first. */
-      if (color == WHITE && white_eye[pos].color == WHITE) {
-       white_eye[pos].type |= INHIBIT_CONNECTION;
-       DEBUG(DEBUG_DRAGONS, "inhibiting connection at %1m\n", pos);
-      }
-      else if (color == BLACK && black_eye[pos].color == BLACK) {
-       black_eye[pos].type |= INHIBIT_CONNECTION;
-       DEBUG(DEBUG_DRAGONS, "inhibiting connection at %1m\n", pos);
-      }
+      cutting_points[pos] |= color;
+      DEBUG(DEBUG_DRAGONS, "inhibiting connection at %1m\n", pos);
     }
   } /* loop over elements */
 }
Index: patterns/helpers.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/helpers.c,v
retrieving revision 1.61
diff -u -r1.61 helpers.c
--- patterns/helpers.c  25 May 2004 03:14:04 -0000      1.61
+++ patterns/helpers.c  29 May 2004 23:16:52 -0000
@@ -218,6 +218,9 @@
   int dpos;
   UNUSED(pattern);
   UNUSED(color);
+
+  if (stackp > 0)
+    return 0;
   
   apos = OFFSET_BY(-1, -1);
   bpos = OFFSET_BY(-1,  0);