[gnugo-devel] influence cleanup - arend_3_11.1a

[Arend Bayer]

This is the first of four incremental patches doing some internal cleanup
in influence.c. (Cleaning up the interface to influence.c is probably more
important, but I thought I'd rather start here.)

This one kills the array q->w. It was used for different purposes in
accumulate_influence() and segment_region(), and both are IMHO better
served with a private static variable.

Defintely ugly was however its use in the followup_influence callback
structure. (For those who don't know, this part of the code was written
by myself, so I assume I am free to insult it...) This was used to
implement the following rule:
* An intrusion pattern (from barriers.db) is used for followup influence if
        a) the Q-marked stone (the anchor of the pattern) is a saved stone
           or directly or diagonally adjacent to one
        b) one stone in the pattern is a saved stone

Changing this to the simple rule
* The pattern is used if the anchor is a saved stone

makes the code much cleaner and results in two PASSes, no FAILs in
the regressions.

Arend




Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.66
diff -u -r1.66 influence.c
--- engine/influence.c  4 Oct 2002 18:52:35 -0000       1.66
+++ engine/influence.c  30 Oct 2002 15:41:11 -0000
@@ -131,12 +131,12 @@
        } \
        if (contribution <= INFLUENCE_CUTOFF) \
          continue; \
-       if (q->w[arg_i][arg_j] == 0.0) { \
+       if (working[arg_i][arg_j] == 0.0) { \
          q->queuei[queue_end] = (arg_i); \
          q->queuej[queue_end] = (arg_j); \
          queue_end++; \
        } \
-       q->w[arg_i][arg_j] += contribution; \
+       working[arg_i][arg_j] += contribution; \
       } } while (0)
 #endif

@@ -153,11 +153,21 @@
   float inv_attenuation;
   float inv_diagonal_damping;
   float (*permeability_array)[MAX_BOARD];
-
+
   /* Clear the queue. Entry 0 is implicitly (m, n). */
   int queue_start = 0;
   int queue_end = 1;

+  static float working[MAX_BOARD][MAX_BOARD];
+  static int working_area_initialized = 0;
+
+  if (!working_area_initialized) {
+    for (i = 0; i < board_size; i++)
+      for (j = 0; j < board_size; j++)
+       working[i][j] = 0.0;
+    working_area_initialized = 1;
+  }
+
   if (0)
     gprintf("Accumulating influence for %s at %m\n",
            color_to_string(color), m, n);
@@ -183,9 +193,9 @@
   q->queuej[0] = n;

   if (color == WHITE)
-    q->w[m][n] = q->white_strength[m][n];
+    working[m][n] = q->white_strength[m][n];
   else
-    q->w[m][n] = q->black_strength[m][n];
+    working[m][n] = q->black_strength[m][n];


   /* Spread influence until the stack is empty. */
@@ -199,13 +209,13 @@
       continue;
     if (0)
       gprintf("Picked %m from queue. w=%f start=%d end=%d\n",
-             i, j, q->w[i][j], queue_start, queue_end);
+             i, j, working[i][j], queue_start, queue_end);
     if (queue_start == 1)
       b = 1.0;
     else
       b = 1.0 / ((i-m)*(i-m) + (j-n)*(j-n));

-    current_strength = q->w[i][j] * inv_attenuation;
+    current_strength = working[i][j] * inv_attenuation;

 #if !EXPLICIT_LOOP_UNROLLING
     /* Try to spread influence in each of the eight directions. */
@@ -267,12 +277,12 @@
        if (0)
          gprintf("  Spreading %s influence from %m to %m, d=%d\n",
                  color_to_string(color), i, j, i+di, j+dj, d);
-       if (q->w[i+di][j+dj] == 0.0) {
+       if (working[i+di][j+dj] == 0.0) {
          q->queuei[queue_end] = i + di;
          q->queuej[queue_end] = j + dj;
          queue_end++;
        }
-       q->w[i+di][j+dj] += contribution;
+       working[i+di][j+dj] += contribution;
       }
     }
 #else
@@ -310,17 +320,17 @@
     j = q->queuej[k];

     if (color == WHITE) {
-      if (q->w[i][j] > 1.01 * INFLUENCE_CUTOFF
+      if (working[i][j] > 1.01 * INFLUENCE_CUTOFF
          || q->white_influence[i][j] == 0.0)
-       q->white_influence[i][j] += q->w[i][j];
+       q->white_influence[i][j] += working[i][j];
     }
     else {
-      if (q->w[i][j] > 1.01 * INFLUENCE_CUTOFF
+      if (working[i][j] > 1.01 * INFLUENCE_CUTOFF
          || q->black_influence[i][j] == 0.0)
-       q->black_influence[i][j] += q->w[i][j];
+       q->black_influence[i][j] += working[i][j];
     }

-    q->w[i][j] = 0.0;
+    working[i][j] = 0.0;
   }
 }

@@ -383,7 +393,6 @@
       /* Initialize. */
       q->white_influence[i][j] = 0.0;
       q->black_influence[i][j] = 0.0;
-      q->w[i][j] = 0.0;
       q->white_attenuation[i][j] = attenuation;
       q->black_attenuation[i][j] = attenuation;
       q->white_permeability[i][j] = 1.0;
@@ -526,7 +535,7 @@
   q->intrusion_counter++;
 }

-/* Experimental influence: Comparison of intrusions datas, to sort them. */
+/* Comparison of intrusions datas, to sort them. */
 static int
 compare_intrusions(const void *p1, const void *p2)
 {
@@ -545,11 +554,35 @@
     return -1;
 }

-/* Experimental influence: This function goes through the list of
- * intrusion sources, and adds the intrusion as influence sources for color.
- * The strength is corrected so that each stone's intrusions sources
- * can have total strength of at most 60%/100% of the strength of the stone.
- * (100% is if q=&followup_influence, 60% otherwise).
+/* It may happen that we have a low intensity influence source at a
+ * blocked intersection (due to an intrusion). This function resets the
+ * permeabilities.
+ */
+static void
+reset_unblocked_blocks(struct influence_data *q)
+{
+  int m, n;
+  for (m = 0; m < board_size; m++)
+    for (n = 0; n < board_size; n++) {
+      if (q->p[m][n] == EMPTY && q->white_strength[m][n] > 0.0
+         && q->white_permeability[m][n] != 1.0) {
+       DEBUG(DEBUG_INFLUENCE, "  black block removed from %m\n", m, n);
+       q->white_permeability[m][n] = 1.0;
+      }
+      if (q->p[m][n] == EMPTY && q->black_strength[m][n] > 0.0
+         && q->black_permeability[m][n] != 1.0) {
+       DEBUG(DEBUG_INFLUENCE, "  white block removed from %m\n", m, n);
+       q->black_permeability[m][n] = 1.0;
+      }
+    }
+}
+
+
+/* This function goes through the list of intrusion sources, and adds
+ * the intrusion as influence sources for color. The strength is
+ * corrected so that each stone's intrusions sources can have total
+ * strength of at most 60%/100% of the strength of the stone.
+ * (100% is if q == &followup_influence, 60% otherwise).
  */
 static void
 add_marked_intrusions(struct influence_data *q, int color)
@@ -561,6 +594,7 @@
   float correction;
   float source_strength;
   float allowed_strength;
+
   gg_sort(q->intrusions, q->intrusion_counter, sizeof(q->intrusions[0]),
           compare_intrusions);

@@ -895,7 +929,6 @@
 {
   int k;
   int t;
-  int saved_stone_involved = 0;
   struct influence_data *q = data;
   UNUSED(color);

@@ -903,22 +936,6 @@
   if (!(pattern->class & CLASS_B))
     return;

-  /* We check first whether a saved stone is involved. */
-  for (k = 0; k < pattern->patlen; ++k) /* match each point */
-    if (pattern->patn[k].att == ATT_O) {
-      /* transform pattern real coordinate */
-      int x, y;
-      TRANSFORM(pattern->patn[k].x, pattern->patn[k].y, &x, &y, ll);
-      x += m;
-      y += n;
-      if (q->w[x][y] == MARKED)
-        saved_stone_involved = 1;
-    }
-
-  if (!saved_stone_involved)
-    return;
-
-
   t = AFFINE_TRANSFORM(pattern->movei, pattern->movej, ll, m, n);
   /* If the pattern has a constraint, call the autohelper to see
    * if the pattern must be rejected.
@@ -1014,24 +1031,7 @@
          }
        }
       }
-
-  /* It may happen that we have a low intensity influence source at a
-   * blocked intersection (due to an intrusion). Reset the
-   * permeability at this point.
-   */
-  for (m = 0; m < board_size; m++)
-    for (n = 0; n < board_size; n++) {
-      if (q->p[m][n] == EMPTY && q->white_strength[m][n] > 0.0
-         && q->white_permeability[m][n] != 1.0) {
-       DEBUG(DEBUG_INFLUENCE, "  black block removed from %m\n", m, n);
-       q->white_permeability[m][n] = 1.0;
-      }
-      if (q->p[m][n] == EMPTY && q->black_strength[m][n] > 0.0
-         && q->black_permeability[m][n] != 1.0) {
-       DEBUG(DEBUG_INFLUENCE, "  white block removed from %m\n", m, n);
-       q->black_permeability[m][n] = 1.0;
-      }
-    }
+  reset_unblocked_blocks(q);
 }

 /* Compute the influence values for both colors, after having made a
@@ -1383,9 +1383,16 @@
               int type, int (*segmentation)[MAX_BOARD])
 {
   int m, n;
+  static char marked[MAX_BOARD][MAX_BOARD];
+
+  /* Reset the markings. */
+  for (m = 0; m < board_size; m++)
+    for (n = 0; n < board_size; n++)
+      marked[m][n] = 0;
+
   for (m = 0; m < board_size; m++)
     for (n = 0; n < board_size; n++) {
-      if (q->w[m][n] == UNMARKED && region_owner(q, m, n) != EMPTY) {
+      if ((!marked[m][n]) && region_owner(q, m, n) != EMPTY) {
        /* Found an unlabelled intersection. Use flood filling to find
          * the rest of the region.
         */
@@ -1395,7 +1402,7 @@
        int queue_end = 1;
        int color = region_owner(q, m, n);
        q->number_of_regions++;
-       q->w[m][n] = MARKED;
+       marked[m][n] = 1;
        q->queuei[0] = m;
        q->queuej[0] = n;
        while (queue_start < queue_end) {
@@ -1413,12 +1420,12 @@
            int di = deltai[k];
            int dj = deltaj[k];
            if (ON_BOARD2(i+di, j+dj)
-               && q->w[i+di][j+dj] == UNMARKED
+               && !marked[i+di][j+dj]
                && region_owner(q, i+di, j+dj) == color) {
              q->queuei[queue_end] = i+di;
              q->queuej[queue_end] = j+dj;
              queue_end++;
-             q->w[i+di][j+dj] = MARKED;
+             marked[i+di][j+dj] = 1;
            }
          }
        }
@@ -1434,10 +1441,6 @@
                  color_to_string(color), m, n, size);
       }
     }
-  /* Reset the working area w. */
-  for (m = 0; m < board_size; m++)
-    for (n = 0; n < board_size; n++)
-      q->w[m][n] = UNMARKED;
 }

 /* Segment the influence map into connected regions of territory,
@@ -1640,8 +1643,6 @@
                            char saved_stones[BOARDMAX])
 {
   int i, j;
-  int ii;
-  int k;
   char goal[BOARDMAX];

   UNUSED(m);
@@ -1652,20 +1653,11 @@
    * and in q->w.
    */
   for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++) {
-      goal[POS(i,j)] = 0;
-      followup_influence.w[i][j] = UNMARKED;
-    }
-  for (i = 0; i < board_size; i++)
     for (j = 0; j < board_size; j++)
-      if (saved_stones[POS(i,j)]) {
-       ii = POS(i, j);
-        goal[ii] = 1;
-       followup_influence.w[i][j] = MARKED;
-       for (k = 0; k < 8; k++)
-         if (board[ii] == board[ii+delta[k]])
-           goal[ii+delta[k]] = 1;
-      }
+      if (saved_stones[POS(i,j)])
+        goal[POS(i, j)] = 1;
+      else
+       goal[POS(i, j)] = 0;

   followup_influence.intrusion_counter = 0;

@@ -1673,34 +1665,11 @@
   /* Match B patterns for saved stones. */
   matchpat_goal_anchor(followup_influence_callback, color, &barrierspat_db,
                       &followup_influence, goal, 1);
-
-  /* Reset the working area w. */
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++)
-      followup_influence.w[i][j] = UNMARKED;

   /* Now add the intrusions. */
   add_marked_intrusions(&followup_influence, color);

-  /* It may happen that we have a low intensity influence source at a
-   * blocked intersection (due to an intrusion). Reset the
-   * permeability at this point.
-   */
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++) {
-      if (followup_influence.p[i][j] == EMPTY
-          && followup_influence.white_strength[i][j] > 0.0
-         && followup_influence.white_permeability[i][j] != 1.0) {
-       DEBUG(DEBUG_INFLUENCE, "  black block removed from %m\n", i, j);
-       followup_influence.white_permeability[i][j] = 1.0;
-      }
-      if (followup_influence.p[i][j] == EMPTY
-          && followup_influence.black_strength[i][j] > 0.0
-         && followup_influence.black_permeability[i][j] != 1.0) {
-       DEBUG(DEBUG_INFLUENCE, "  white block removed from %m\n", i, j);
-       followup_influence.black_permeability[i][j] = 1.0;
-      }
-    }
+  reset_unblocked_blocks(&followup_influence);

   /* Spread influence for new influence sources. */
   for (i = 0; i < board_size; i++)
Index: engine/influence.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.h,v
retrieving revision 1.12
diff -u -r1.12 influence.h
--- engine/influence.h  19 Jun 2002 22:30:04 -0000      1.12
+++ engine/influence.h  30 Oct 2002 15:41:11 -0000
@@ -19,12 +19,14 @@
  * Boston, MA 02111, USA.                                            *
 \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

+#if 0
 #include <stdio.h>
 #include <stdlib.h>
 #include <assert.h>
 #include <string.h>

 #include "liberty.h"
+#endif

 /* Default attenuation coefficient.
  * The "TERR_.."-values are used in the influence computations used
@@ -51,10 +53,6 @@
  */
 #define NOT_COMPUTED (-2.0 * MAX_BOARD * MAX_BOARD)

-/* Values for the float working area w when used only for marking. */
-#define UNMARKED 0.0
-#define MARKED 1.0
-
 /* Territory, moyo, and area are segmented into connected components
  * and given a number from the same series. These values are used in
  * region_type[][].
@@ -116,7 +114,6 @@

   int color_to_move; /* Which color is in turn to move. */

-  float w[MAX_BOARD][MAX_BOARD];         /* Working area. */
   int queuei[MAX_BOARD * MAX_BOARD];     /* Points receiving influence. */
   int queuej[MAX_BOARD * MAX_BOARD];

Index: regression/connection.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/connection.tst,v
retrieving revision 1.37
diff -u -r1.37 connection.tst
--- regression/connection.tst   21 Oct 2002 15:15:20 -0000      1.37
+++ regression/connection.tst   30 Oct 2002 15:41:20 -0000
@@ -314,6 +314,10 @@
 95 disconnect O4 P3
 #? [1 (N1|N2)]

+loadsgf games/handtalk/handtalk1.sgf 31
+96 same_dragon C16 C13
+#? [0]
+
 # Report number of nodes visited by the tactical reading
 10000 get_reading_node_counter
 #? [0]&