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

[Arend Bayer]

The next patch converts all data structures in influence.c to use a
one-dimensional board representation, and correspondingly of course all
board loops now use 1D as well.

As the patch is 63K and rather boring, I've put it up at
www.uni-bonn.de/~uzsxtn/arend_3_11.1b. Only the changes to
accumulate_influence() are shown below.

This was tested by running GNU Go with -d9 -m0x3ff -t on two .tst test
suites and comparing the output of the patched version and one that only
contained CVS + arend_3_11.1a. As they were (after a few small bug fixes)
no changes in some 130 MB of debug output, the change should be safe.

Arend


@@ -112,15 +110,15 @@
  */


-#define code1(arg_di, arg_dj, arg_i, arg_j, arg_d) do { \
-      if (q->p[arg_i][arg_j] == EMPTY \
+#define code1(arg_di, arg_dj, arg, arg_d) do { \
+      if (q->p[arg] == EMPTY \
          && ((arg_di)*(i-m) + (arg_dj)*(j-n) > 0 \
              || queue_start == 1)) { \
        float contribution; \
-       float permeability = permeability_array[i][j]; \
+       float permeability = permeability_array[ii]; \
        if (arg_d) { \
-         permeability *= gg_max(permeability_array[arg_i][j], \
-                                permeability_array[i][arg_j]); \
+         permeability *= gg_max(permeability_array[ii + DELTA(arg_di, 0)], \
+                                permeability_array[ii + DELTA(0, arg_dj)]); \
          if (permeability == 0.0) \
            continue; \
        } \
@@ -131,20 +129,21 @@
        } \
        if (contribution <= INFLUENCE_CUTOFF) \
          continue; \
-       if (working[arg_i][arg_j] == 0.0) { \
-         q->queuei[queue_end] = (arg_i); \
-         q->queuej[queue_end] = (arg_j); \
+       if (working[arg] == 0.0) { \
+         q->queue[queue_end] = (arg); \
          queue_end++; \
        } \
-       working[arg_i][arg_j] += contribution; \
+       working[arg] += contribution; \
       } } while (0)
 #endif


 static void
-accumulate_influence(struct influence_data *q, int m, int n, int color)
+accumulate_influence(struct influence_data *q, int pos, int color)
 {
-  int i, j;
+  int ii;
+  int m = I(pos);
+  int n = J(pos);
   int k;
 #if !EXPLICIT_LOOP_UNROLLING
   int d;
@@ -152,19 +151,18 @@
   float b;
   float inv_attenuation;
   float inv_diagonal_damping;
-  float (*permeability_array)[MAX_BOARD];
+  float (*permeability_array);

   /* 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 float working[BOARDMAX];
   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;
+    for (ii = 0; ii < BOARDMAX; ii++)
+      working[ii] = 0.0;
     working_area_initialized = 1;
   }

@@ -174,9 +172,9 @@

   /* Attenuation only depends on the influence origin. */
   if (color == WHITE)
-    inv_attenuation = 1.0 / q->white_attenuation[m][n];
+    inv_attenuation = 1.0 / q->white_attenuation[pos];
   else
-    inv_attenuation = 1.0 / q->black_attenuation[m][n];
+    inv_attenuation = 1.0 / q->black_attenuation[pos];

   if (q->is_territorial_influence)
     inv_diagonal_damping = 1.0 / TERR_DIAGONAL_DAMPING;
@@ -189,33 +187,34 @@
     permeability_array = q->black_permeability;

   /* We put the original source into slot 0.  */
-  q->queuei[0] = m;
-  q->queuej[0] = n;
+  q->queue[0] = pos;

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


   /* Spread influence until the stack is empty. */
   while (queue_start < queue_end) {
     float current_strength;
+    int i, j;

-    i = q->queuei[queue_start];
-    j = q->queuej[queue_start];
+    ii = q->queue[queue_start];
+    i = I(ii);
+    j = J(ii);
     queue_start++;
-    if (permeability_array[i][j] == 0.0)
+    if (permeability_array[ii] == 0.0)
       continue;
     if (0)
-      gprintf("Picked %m from queue. w=%f start=%d end=%d\n",
-             i, j, working[i][j], queue_start, queue_end);
+      gprintf("Picked %1m from queue. w=%f start=%d end=%d\n",
+             ii, working[ii], 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 = working[i][j] * inv_attenuation;
+    current_strength = working[ii] * inv_attenuation;

 #if !EXPLICIT_LOOP_UNROLLING
     /* Try to spread influence in each of the eight directions. */
@@ -286,27 +285,27 @@
       }
     }
 #else
-    if (i < board_size-1)
-      code1(1, 0, i+1, j, 0);
-    if (j > 0)
-      code1(0, -1, i, j-1, 0);
-    if (i > 0)
-      code1(-1, 0, i-1, j, 0);
-    if (j < board_size-1)
-      code1(0, 1, i, j+1, 0);
+    if (ON_BOARD(ii + delta[0]))
+      code1(deltai[0], deltaj[0], ii + delta[0], 0);
+    if (ON_BOARD(ii + delta[1]))
+      code1(deltai[1], deltaj[1], ii + delta[1], 0);
+    if (ON_BOARD(ii + delta[2]))
+      code1(deltai[2], deltaj[2], ii + delta[2], 0);
+    if (ON_BOARD(ii + delta[3]))
+      code1(deltai[3], deltaj[3], ii + delta[3], 0);

     /* Update factors for diagonal movement. */
     b *= 0.5;
     current_strength *= inv_diagonal_damping;

-    if (i < board_size-1 && j > 0)
-      code1(1, -1, i+1, j-1, 1);
-    if (i > 0 && j > 0)
-      code1(-1, -1, i-1, j-1, 1);
-    if (i > 0 && j < board_size-1)
-      code1(-1, 1, i-1, j+1, 1);
-    if (i < board_size-1 && j < board_size-1)
-      code1(1, 1, i+1, j+1, 1);
+    if (ON_BOARD(ii + delta[4]))
+      code1(deltai[4], deltaj[4], ii + delta[4], 1);
+    if (ON_BOARD(ii + delta[5]))
+      code1(deltai[5], deltaj[5], ii + delta[5], 1);
+    if (ON_BOARD(ii + delta[6]))
+      code1(deltai[6], deltaj[6], ii + delta[6], 1);
+    if (ON_BOARD(ii + delta[7]))
+      code1(deltai[7], deltaj[7], ii + delta[7], 1);
 #endif
   }

@@ -316,21 +315,20 @@
    * it.
    */
   for (k = 0; k < queue_end; k++) {
-    i = q->queuei[k];
-    j = q->queuej[k];
+    ii = q->queue[k];

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

-    working[i][j] = 0.0;
+    working[ii] = 0.0;
   }
 }