Re: [gnugo-devel] engine/influence.c (and DFA)

[Dave Denholm]

Arend Bayer <address@hidden> writes:

> On 6 Sep 2002, Dave Denholm wrote:
> 
> > <address@hidden> writes:
> > >
> > > Here are the test results after defining
> > >
> > > #define EXPLICIT_LOOP_UNROLLING 0
> > >
> > > in influence.c. Test results are current, so the unexpected results are
> > > ALL due to this change.
> > >
> >
> >
> > There are two changes required to make the unrolled version
> > exactly the same as the loop :
> >
> > 1) add  do { ... } while(0)  around the whole of the macro defn,
> >   so that continue means the correct thing.
> >
> > 2) Change the order in which the unrolled loop invokes the
> >   macro to match the order of deltai[] and deltaj[]
> 
> I have tried out 1), and got
> * exactly the same regression delta as Dan posted it a couple of days
> ago
> * unfortunately, a big slowdown:
> Running on safety.tst (which contains only early game positions):
> 
> Profile of cvs:
>  time   seconds   seconds    calls  ms/call  ms/call  name
>  10.57      7.82     7.82    21833     0.36     0.36  accumulate_influence
>   7.88     13.65     5.83    14234     0.41     0.46  compute_primary_domains
>   6.29     18.30     4.65  3702272     0.00     0.00  scan_for_patterns
>   4.10     21.33     3.03     8311     0.36     0.36  do_push_owl
>   4.08     24.35     3.02  4273229     0.00     0.00  check_pattern_light
>   3.04     26.60     2.25  4514435     0.00     0.00  fastlib
> 
> Profile with this change:
>  22.31     17.24    17.24    23074     0.75     0.75  accumulate_influence
>   6.29     22.10     4.86    12088     0.40     0.44  compute_primary_domains
>   4.72     25.75     3.65  3127560     0.00     0.00  scan_for_patterns
>   3.52     28.47     2.72     7067     0.38     0.38  do_push_owl
>   3.39     31.09     2.62  3631585     0.00     0.00  check_pattern_light
>   2.86     33.30     2.21  4146203     0.00     0.00  fastlib
> 
> In other words, we should do s.th. about the performance. Also, we
> should look at the FAILs to get an impression whether this can be
> improved.
> 




Hmm - well, I'll try to resurrect the speedups I made when I thought
accumulate_influence was important. Mainly just a case of getting
rid of the divisions from the inner loop.


But just in case I don't get round to finishing it off, below
is what I was working with, against gnugo 3.1.3 (what I happen to have at work)

It is not yet ready for inclusion, but I'd better send it in case 
someone else gets a chance to polish / test it before me. (Just when I
thought I'd get a chance to do some gnugo development, another rush
has turned up at work :-(  )



The main point being that the inner loop now just has

        contribution = permeability * current_strength; \
        if (i!=m || j!=n) { \
          int a = (arg_di)*(i-m) + (arg_dj)*(j-n); \
          gg_assert(a > 0); \
          contribution *= (a*a) * b; \
        } \


rather than

        damping = (arg_d) ? diagonal_attenuation : attenuation; \
        if (i==m && j==n) \
          cos2phi = 1.0; \
        else { \
          float a = (arg_di)*(i-m) + (arg_dj)*(j-n); \
          float c = (arg_di)*(arg_di) + (arg_dj)*(arg_dj); \
          gg_assert(a > 0.0); \
          cos2phi = (a*a) / (b*c); \
        } \
        contribution = cos2phi * permeability * current_strength / damping; \



- b now stores the inverse of what it was before, and since
c is 1 for straight or 2 for diagonal, I just halve b before doing
the diagonal ones.

Note that I've hardwired that diagonal_attentuation is twice attenuation
(by halving current_strength)




> I haven't done 2), because I think if anything we should fix the fact
> that the order makes a difference. (I think I can also explain why this
> does make a difference, in case anybody is interested -- I believe it is
> a rare problem and not much worth worrying about.)
> 


Hmm - without thinking too hard about it, I had decided that it
was an inherent problem with the algorithm, in that it only
looks at each outlying point once, and so it depends on the
path taken to reach that point on whether the influence is
spread from it. ie if we reach a point from which influence
has already spread, the new contribution is not distributed
further.

But I'm probably mistaken...



> For the record, below is the patch.


Sorry, I was hoping to get round to it... honest...



dd
-- 
address@hidden          http://www.insignia.com




--- influence.c.orig    Tue Sep  3 12:58:25 2002
+++ influence.c Wed Sep  4 11:00:04 2002
@@ -82,26 +82,35 @@
 
 #if EXPLICIT_LOOP_UNROLLING
 
-#define code1(arg_di, arg_dj, arg_i, arg_j, arg_d) \
+
+/* In addition to the parameters, this macro expects
+ *  m,n = original source of influence
+ *  i,j = point influence is being spread from
+ *  current_strength combines strength and damping factor
+ *  b is 1/(square of distance from m,n to i,j) ; or halved
+ *    for diagonals
+ * 
+/*  arg_i is i + arg_di ; arg_j is j + arg_dj
+ *  arg_d is 1 for diagonal movement
+ *
+ */
+#define code1(arg_di, arg_dj, arg_i, arg_j, arg_d) do {\
       if (q->p[arg_i][arg_j] == EMPTY \
          && ((arg_di)*(i-m) + (arg_dj)*(j-n) > 0 \
              || queue_start == 1)) { \
-       permeability = permeability_array[i][j]; \
+       float permeability = permeability_array[i][j]; \
+       float contribution; \
        if (arg_d) \
          permeability *= gg_max(permeability_array[arg_i][j], \
                                 permeability_array[i][arg_j]); \
        if (permeability == 0.0) \
          continue; \
-       damping = (arg_d) ? diagonal_attenuation : attenuation; \
-       if (i==m && j==n) \
-         cos2phi = 1.0; \
-       else { \
-         float a = (arg_di)*(i-m) + (arg_dj)*(j-n); \
-         float c = (arg_di)*(arg_di) + (arg_dj)*(arg_dj); \
-         gg_assert(a > 0.0); \
-         cos2phi = (a*a) / (b*c); \
+       contribution = permeability * current_strength; \
+       if (i!=m || j!=n) { \
+         int a = (arg_di)*(i-m) + (arg_dj)*(j-n); \
+         gg_assert(a > 0); \
+         contribution *= (a*a) * b; \
        } \
-       contribution = cos2phi * permeability * current_strength / damping; \
        if (contribution <= INFLUENCE_CUTOFF) { \
           if (permeability < 1.0 || q->w[arg_i][arg_j] != 0.0) \
            continue; \
@@ -114,7 +123,7 @@
          queue_end++; \
        } \
        q->w[arg_i][arg_j] += contribution; \
-      }
+     } } while(0)
 #endif
 
 static void
@@ -125,19 +134,13 @@
 #if !EXPLICIT_LOOP_UNROLLING
   int d;
 #endif
-  float damping;
   float b;
-  float current_strength;
-  float cos2phi;
-  float permeability;
-  float contribution;
-  float attenuation;
-  float diagonal_attenuation;
+  float inv_attenuation;
   float (*permeability_array)[MAX_BOARD];
   
-  /* Clear the queue. */
-  int queue_start = 0;
-  int queue_end = 0;
+  /* Clear the queue : [0] is implicitly (m,n). */
+  int queue_start = 1;
+  int queue_end = 1;
 
   if (0)
     gprintf("Accumulating influence for %s at %m\n",
@@ -145,37 +148,45 @@
 
   /* Attenuation only depends on the influence origin. */
   if (color == WHITE)
-    attenuation = q->white_attenuation[m][n];
+    inv_attenuation = 1.0 / q->white_attenuation[m][n];
   else
-    attenuation = q->black_attenuation[m][n];
-  diagonal_attenuation = attenuation * DIAGONAL_DAMPING;
+    inv_attenuation = 1.0 / q->black_attenuation[m][n];
 
   if (color == WHITE)
     permeability_array = q->white_permeability;
   else
     permeability_array = q->black_permeability;
+
+  /* We put the original source into slot 0 of the queue not
+   * for the main loop, but for the final cleanup loop.
+   */
+
+  q->queuei[0] = m;
+  q->queuej[0] = n;
+
     
-  /* Put the influence origin on the stack. */
+  /* Prime the state variables for first pass. This avoids
+   * having to special-case to avoid division by 0 for
+   * calculating b when i==m && j==n (see end of loop).
+   */
+
   if (color == WHITE)
     q->w[m][n] = q->white_strength[m][n];
   else
     q->w[m][n] = q->black_strength[m][n];
-  q->queuei[queue_end] = m;
-  q->queuej[queue_end] = n;
-  queue_end++;
 
-  /* Spread influence until the stack is empty. */
-  while (queue_start < queue_end) {
+  i=m;
+  j=n;
+  b=1.0;
+
+  for(;;) {
+
+    /* (i,j) is the point we are radiating influence from.
+     * q->w[i][j] is the influence at this point.
+     * b is 1/((i-m)*(i-m) + (j-n)*(j-n))
+     */
 
-    /* Pick first element in queue. */
-    i = q->queuei[queue_start];
-    j = q->queuej[queue_start];
-    b = (i-m)*(i-m) + (j-n)*(j-n);
-    if (0)
-      gprintf("Picked %m from queue. w=%f start=%d end=%d\n",
-             i, j, q->w[i][j], queue_start, queue_end);
-    current_strength = q->w[i][j];
-    queue_start++;
+    float current_strength = q->w[i][j] * inv_attenuation;
 
 #if !EXPLICIT_LOOP_UNROLLING
     /* Try to spread influence in each of the eight directions. */    
@@ -193,49 +204,36 @@
          && (di*(i-m) + dj*(j-n) > 0
              || queue_start == 1)) {
 
+       float contribution;
+       float dfactor;  /* 1 for straight, 0.5 for diagonal */
+
        /* Now compute the damping of the influence.
         * First we have the permeability at the point we are
         * spreading from. For diagonal movement we also take the
         * permeability of the vertices we are "passing by" into
         * account.
         */
-       permeability = permeability_array[i][j];
-       if (d > 3) /* diagonal movement */
+       float permeability = permeability_array[i][j];
+       if (d > 3) /* diagonal movement */ {
          permeability *= gg_max(permeability_array[i+di][j],
                                 permeability_array[i][j+dj]);
+         dfactor = 0.5;
+       } else {
+         dfactor = 1.0;
+       }
 
        if (permeability == 0.0)
          continue;
        
-       /* Then we have the distance dependent damping. */
-       damping = 1.0;
-       switch (d) {
-       case 0: /* south */
-       case 1: /* west */
-       case 2: /* north */
-       case 3: /* east */
-         damping = attenuation;
-         break;
-       case 4: /* southwest */
-       case 5: /* northwest */
-       case 6: /* northeast */
-       case 7: /* southeast */
-         damping = diagonal_attenuation;
-         break;
-       }
-       
+       contribution = permeability * current_strength * dfactor;
+
        /* Finally direction dependent damping. */
-       if (i==m && j==n)
-         cos2phi = 1.0;
-       else {
-         float a = di*(i-m) + dj*(j-n);
-         float c = di*di + dj*dj;
+       if (i!=m || j!=n) {
+         int a = di*(i-m) + dj*(j-n);
          gg_assert(a > 0.0);
-         cos2phi = (a*a) / (b*c);
+         contribution *= (a*a) * b * dfactor;
        }
 
-       contribution = cos2phi * permeability * current_strength / damping;
-
        /* Stop spreading influence if the contribution becomes too low. */
        if (contribution <= INFLUENCE_CUTOFF) {
           if (permeability < 1.0 || q->w[i+di][j+dj] != 0.0)
@@ -259,24 +257,47 @@
       }
     }
 #else
-    if (i>0)
-      code1(-1, 0, i-1, j, 0);
     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 (i>0 && j>0)
-      code1(-1,-1, i-1, j-1, 1);
+
+    /* Update factors for diagonals */
+
+    b *= 0.5;
+    current_strength *= 0.5;
+
     if (i<board_size-1 && j>0)
       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 (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);
  
 #endif
+
+
+    /* Now pop the next node from the queue */
+
+    if (queue_start == queue_end)
+      break;  /* queue empty */
+
+    i = q->queuei[queue_start];
+    j = q->queuej[queue_start];
+    queue_start++;
+
+    if (0)
+      gprintf("Picked %m from queue. w=%f start=%d end=%d\n",
+             i, j, q->w[i][j], queue_start, queue_end);
+
+    b = 1.0 / ((i-m)*(i-m) + (j-n)*(j-n));
+
   }