[gnugo-devel] arend_1_26.1: experimental influence speed-up

[Arend Bayer]

 - experimental influence: matchpat_goal_anchor used for followup influence
 - followup_influence_callback restructured
 - some comments added
 
This patch should give a substantial speedup for experimental influence.
(I now get an increase of 8.6% for the nngs test suite, but as I had it
running in background, that might not be exact.)

It does so by changing a stupid order of checks in
followup_influence_callback (I had constraints of a pattern checked before
checking whether there was a saved stone involved.) Another, probably
smaller, improvement is made is by using matchpat_goal_anchor for the
followup influence. 

The effect of this patch on genmove decision is almost zero. (But not
exactly zero; B patterns with 2 or more O stones now have on of these
stones singled out "from which the influence originates". This can
make a difference due to the experimental influence policy about
intrusions.)

Some figures and analysis:

For the nngs test suite, I find
 - 2.31 * 10^9 tried moves with standard influence
 - 2.84 * 10^9 tried moves with experimental influence before the patch
 - 2.49 * 10^9 tried moves with experimental influence after this patch

This is still an increase of 7.8%. I assume the following two factors are
responsible for this:
1. Owl is called more frequently, probably caused by small changes in the
   moyo size due to changes in the influence values.
   I will try turning experimental influence off in the pre-owl influence
   computations. This might not be such a bad idea after all, as it might
   restore other tuning that gets broken at the moment.
   (There were 61 or 4.6% more calls to owl_attack and 12 or 1.3% more
   calls to owl_defend. This resulted in an increase of owl nodes by
   5.5% and matched owl patterns by 7.4%.)
2. There are a few more patterns in barriers.db; also, some of them are
   more general and might be more expensive than Gunnar's patterns. As
   these have to be evaluated for each move considered in value_moves,
   this might be more performance critical than I had assumed. I will
   see what I can do about that.


Arend


Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.35
diff -u -r1.35 influence.c
--- engine/influence.c  13 Feb 2002 05:40:10 -0000      1.35
+++ engine/influence.c  15 Feb 2002 22:31:45 -0000
@@ -614,7 +614,6 @@
 {
   int pos;
   int k;
-  int saved_pos = NO_MOVE;
   struct influence_data *q = data;
   
   /* Patterns marked FY get ignored in experimental influence,
@@ -706,8 +705,6 @@
          if ((color == WHITE && q->white_strength[x][y] == 0.0)
              || (color == BLACK && q->black_strength[x][y] == 0.0))
            return; /* Match failed. */
-          else
-            saved_pos = POS(x, y);
        }
        
        if ((pattern->class & (CLASS_A | CLASS_t))
@@ -838,7 +835,7 @@
       /* Low intensity influence source for the color in turn to move. */
       if (pattern->class & CLASS_B) {
         if (experimental_influence)
-          enter_intrusion_source(saved_pos, POS(x, y), pattern->value,
+          enter_intrusion_source(POS(m, n), POS(x, y), pattern->value,
                                 EXP_DEFAULT_ATTENUATION, q);
         else
           add_influence_source(POS(x, y), color,
@@ -850,16 +847,25 @@
 }
 
 /* Callback for matched barriers patterns in followup influence.
- * This adds a influence source of color O at !-marked points if any
- * of the O-stones in the pattern is marked INFLUENCE_SAVED_STONES.
+ * This adds an intrusion source for all B patterns in barriers.db for
+ * the color that has made a move if all the following conditions are
+ * fulfilled:
+ * - the anchor ("Q") is adjacent (directly or diagonally) to a "saved stone"
+ *  (this is ensured by matchpat before calling back here)
+ * - at least one of the O stones in the pattern is a saved stone.
+ * - the usual pattern constraint ("; oplay_attack_either(...)") is fulfilled
+ * - the pattern action (typically ">return (!xplay_attack(...))") returns
+ *   true if  called with parameter action = FOLLOWUP_INFLUENCE_CALLBACK.
+ * "Saved stones" are: the move played + tactically rescued stones + stones
+ *                     in a critcal dragon brought to life by this move
  */
 static void
 followup_influence_callback(int m, int n, int color, struct pattern *pattern,
                             int ll, void *data)
 {
   int k;
-  int ti, tj;
-  int saved_stone = NO_MOVE;
+  int t;
+  int saved_stone_involved = 0;
   struct influence_data *q = data;
   UNUSED(color);
  
@@ -867,14 +873,28 @@
   if (!(pattern->class & CLASS_B))
     return;
 
-  TRANSFORM(pattern->movei, pattern->movej, &ti, &tj, ll);
-  ti += m;
-  tj += n;
+  /* 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.
    */
   if (pattern->autohelper_flag & HAVE_CONSTRAINT) {
-    if (!pattern->autohelper(pattern, ll, POS(ti, tj), color, 0))
+    if (!pattern->autohelper(pattern, ll, t, color, 0))
       return;
   }
 
@@ -882,35 +902,20 @@
    * be rejected.
    */
   if (pattern->helper) {
-    if (!pattern->helper(pattern, ll, POS(ti, tj), color)) {
+    if (!pattern->helper(pattern, ll, t, color)) {
       DEBUG(DEBUG_INFLUENCE,
             "Influence pattern %s+%d rejected by helper at %1m\n",
-            pattern->name, ll, POS(ti, tj));
+            pattern->name, ll, t);
       return;
     }
   }
  
  /* Actions in B patterns are used as followup specific constraints. */
  if ((pattern->autohelper_flag & HAVE_ACTION)
-     && !pattern->autohelper(pattern, ll, POS(ti, tj), color,
+     && !pattern->autohelper(pattern, ll, t, color,
                              FOLLOWUP_INFLUENCE_CALLBACK))
     return;
 
-  /* First loop: We check 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 = POS(x,y);
-    }
-
-  if (saved_stone == NO_MOVE)
-    return;
-  
   DEBUG(DEBUG_INFLUENCE, "influence pattern '%s'+%d matched at %1m\n",
        pattern->name, ll, POS(m, n));
 
@@ -922,10 +927,10 @@
                             ll, m, n);
 
       /* Low intensity influence source for the color in turn to move. */
-      enter_intrusion_source(saved_stone, pos, pattern->value,
-                            EXP_DEFAULT_ATTENUATION, &followup_influence);
+      enter_intrusion_source(POS(m, n), pos, pattern->value,
+                            EXP_DEFAULT_ATTENUATION, q);
       DEBUG(DEBUG_INFLUENCE, "  followup for %1m: intrusion at %1m\n",
-            saved_stone, pos);
+            POS(m, n), pos);
     }
 }
 
@@ -1635,32 +1640,45 @@
                            char saved_stones[BOARDMAX])
 {
   int i, j;
+  int ii;
+  int k;
+  char goal[BOARDMAX];
 
   UNUSED(m);
   UNUSED(n);  
   memcpy(&followup_influence, &move_influence, sizeof(move_influence));
  
-  /* We mark the saved stones in the q->w array. */
+  /* We mark the saved stones and their neighbors in the goal array
+   * and in q->w.
+   */
   for (i = 0; i < board_size; i++)
     for (j = 0; j < board_size; j++) {
-      if (saved_stones[POS(i,j)]) 
-        followup_influence.w[i][j] = MARKED;
-      else
-        followup_influence.w[i][j] = UNMARKED;
+      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;
+      }
 
   followup_influence.intrusion_counter = 0;
 
   current_influence = &followup_influence;
   /* Match B patterns for saved stones. */
-  matchpat(followup_influence_callback, color, &barrierspat_db, 
-           &followup_influence, NULL);
- 
-  /* Clean the q->w array. */
+  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);
 
Index: patterns/barriers.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/barriers.db,v
retrieving revision 1.24
diff -u -r1.24 barriers.db
--- patterns/barriers.db        13 Feb 2002 05:40:10 -0000      1.24
+++ patterns/barriers.db        15 Feb 2002 22:31:48 -0000
@@ -25,10 +25,16 @@
 #  ? - don't care
 #  . - empty
 #  O - color to move
+#  Q - same as O, plus sets the pattern anchor
 #  X - opposite color of O
 #  o - O or empty
 #  x - X or empty
 #  , - point which influence can't pass through
+# A/D patterns:
+#  ! - point where influence gets weakened when passing through
+#      (permeability multiplied by 0.7) 
+# B patterns:
+#  ! - marks an intrusion for the anchor stone with indicated value
 #
 #
 # Four different classes of patterns are used here.
@@ -38,6 +44,16 @@
 #  B - Intrusions (where O can intrude into X'x territory)
 #  t - Nonterritory patterns indicating points where one color cannot
 #      get territory
+#
+# Constraints are as usual.
+# B patterns are matched for the color to move, and for the color having
+# made a move in followup influence, in order to compute the followup
+# value of this move. (Only patterns including the played move or any
+# stone saved by this move are taken into account.)
+# For the followup influence, a pattern is used if the usual constraint
+# is satisfied, and if the action returns true. See the influence
+# documentation for explanation and influence.c for details.
+
 
 Pattern Barrier1
 
@@ -857,7 +873,7 @@
 
 xxxx
 ...X
-!!.O
+!!.Q
 ----
 
 :8,B,value(30)
@@ -874,7 +890,7 @@
 
 xxxx
 X..X
-..!O
+..!Q
 ----
 
 :8,B,value(30)
@@ -890,7 +906,7 @@
 
 xxxx
 X..X
-.!.O
+.!.Q
 ----
 
 :8,B,value(30)
@@ -908,14 +924,14 @@
 
 xxxx
 !!.X
-...O
+...Q
 ----
 
 :8,B,value(30)
 
 xxxx
 a!cX
-..bO
+..bQ
 ----
 
 ;!oplay_defend(a,b,c,b)
@@ -924,7 +940,7 @@
 Pattern Intrusion2
 
 xXx?
-...O
+...Q
 !!..
 ----
 
@@ -943,7 +959,7 @@
 # ab 3.1.22 Constraint added (see 13x13:52)
 
 xxX?
-...O
+...Q
 !!..
 ----
 
@@ -960,7 +976,7 @@
 
 Pattern Intrusion4
 
-XOOX
+XQOX
 !!X.
 !...
 ----
@@ -978,7 +994,7 @@
 
 Pattern Intrusion5a
 
-X.OX
+X.QX
 .!X.
 .!..
 ----
@@ -995,7 +1011,7 @@
 
 Pattern Intrusion5b
 
-.OX
+.QX
 !X.
 
 :8,BY,value(30)
@@ -1009,7 +1025,7 @@
 
 Pattern Intrusion6
 
-?OX
+?QX
 X!!
 x..
 
@@ -1018,7 +1034,7 @@
 
 Pattern Intrusion7a
 
-OX.
+QX.
 .!!
 X.x
 
@@ -1034,7 +1050,7 @@
 
 Pattern Intrusion7b
 
-OX
+QX
 !!
 
 :8,BY,value(30)
@@ -1050,7 +1066,7 @@
 # ab 3.1.22 revised constraint (see territory valuation in 13x13:2)
 
 X.X
-O!!
+Q!!
 ?X.
 
 :8,B,value(30)
@@ -1066,13 +1082,13 @@
 Pattern Intrusion9
 
 X.
-OX
+QX
 .!
 
 :8,B,value(30)
 
 X.
-OC
+QC
 ba
 
 ;oplay_attack(a,b,C)
@@ -1082,7 +1098,7 @@
 
 xxx?
 ..XO
-!!.O
+!!.Q
 ----
 
 :8,B,value(30)
@@ -1100,7 +1116,7 @@
 # O can intrude on either side. The position of the influence source
 # here isn't entirely accurate.
 
-.O.
+.Q.
 .X.
 .!.
 ...
@@ -1108,7 +1124,7 @@
 
 :|,B,value(30)
 
-dOb
+dQb
 cXa
 .!.
 ...
@@ -1121,7 +1137,7 @@
 # O can intrude on either side. The position of the influence source
 # here isn't entirely accurate.
 
-!O!
+!Q!
 !X!
 ...
 ...
@@ -1129,7 +1145,7 @@
 
 :|,B,value(30)
 
-dOb
+dQb
 cXa
 ...
 ...
@@ -1137,23 +1153,10 @@
 
 ;oplay_attack(a,b,b) || oplay_attack(c,d,d)
 
-Pattern Intrusion12a
-
-oOo
-.X!
-...
-
-:8,OBY,value(30)
-
-oOb
-.Ca
-...
-
-;o_somewhere(b) || oplay_attack_either(a,b,b,C)
 
 Pattern Intrusion12b
 
-oOo
+oQo
 .X!
 ...
 
@@ -1182,7 +1185,7 @@
 
 Pattern Intrusion13
 
-?OoO?
+?OoQ?
 X.!X.
 X.!..
 .....
@@ -1201,7 +1204,7 @@
 
 Pattern Intrusion14
 
-?OO?
+?QO?
 X!X.
 .!..
 .!..
@@ -1209,7 +1212,7 @@
 
 :8,B,value(30)
 
-?OO?
+?QO?
 XaXd
 .bc.
 .!..
@@ -1220,13 +1223,13 @@
 
 Pattern Intrusion15
 
-oOo
+oQo
 .XO
 !.X
 
 :8,B,value(30)
 
-oOo
+oQo
 aXO
 cbX
 
@@ -1236,7 +1239,7 @@
 Pattern Intrusion16
 # ab value decreased (3.1.24)
 
-O!.
+Q!.
 !!.
 .xX
 
@@ -1246,7 +1249,7 @@
 Pattern Intrusion17
 # ab value decreased (3.1.24)
 
-O!.
+Q!.
 .!.
 XxX
 
@@ -1257,7 +1260,7 @@
 
 xXx
 o..
-O!!
+Q!!
 o..
 xXx
 
@@ -1267,7 +1270,7 @@
 Pattern Intrusion19
 
 X..
-O!.
+Q!.
 o..
 xXx
 
@@ -1283,7 +1286,7 @@
 
 Pattern Intrusion20
 
-oO!
+oQ!
 OX!
 
 :8,B,value(30)
@@ -1297,7 +1300,7 @@
 
 Pattern Intrusion21
 
-O.X
+Q.X
 .!.
 x..
 
@@ -1313,7 +1316,7 @@
 Pattern Intrusion21b
 
 ooX
-O!.
+Q!.
 x..
 
 :8,B,value(30)
@@ -1326,7 +1329,7 @@
 
 Pattern Intrusion22
 
-O.X
+Q.X
 ...
 .!.
 
@@ -1341,7 +1344,7 @@
 
 Pattern Intrusion23
 
-O..
+Q..
 .!!
 ---
 
@@ -1358,7 +1361,7 @@
 Pattern Intrusion24
 
 O..
-O!!
+Q!!
 ---
 
 :8,B,value(30)
@@ -1367,7 +1370,7 @@
 Pattern Intrusion25
 
 !!.O
-!XO.
+!XQ.
 ....
 ....
 ----
@@ -1378,7 +1381,7 @@
 Pattern Intrusion26
 
 !!.O
-.XO.
+.XQ.
 ..X!
 ....
 ----
@@ -1388,7 +1391,7 @@
 
 Pattern Intrusion27
 
-O..
+Q..
 .!.
 .!.
 ...
@@ -1398,7 +1401,7 @@
 
 Pattern Intrusion28
 
-??O?
+??Q?
 x.!X
 ..!.
 ....
@@ -1406,7 +1409,7 @@
 
 :8,B,value(30)
 
-??O?
+??Q?
 xdaX
 .cb.
 ....
@@ -1419,7 +1422,7 @@
 
 oooo
 oooo
-.O.o
+.Q.o
 ....
 .!!.
 .!..
@@ -1431,7 +1434,7 @@
 
 oooo
 oooo
-XO.o
+XQ.o
 ....
 .!!.
 .!..
@@ -1440,7 +1443,7 @@
 
 oooo
 oooo
-XOfo
+XQfo
 dbc.
 .ae.
 .!..
@@ -1451,7 +1454,7 @@
 Pattern Intrusion31
 
 ooo
-XO.
+XQ.
 .!!
 .!.
 ?.?
@@ -1470,7 +1473,7 @@
 Pattern Intrusion32
 
 ooo
-XO.
+XQ.
 .!.
 ?.?
 
@@ -1487,7 +1490,7 @@
 Pattern Intrusion33
 
 oOo
-XOX
+XQX
 .!.
 ?.?
 
@@ -1497,14 +1500,14 @@
 Pattern Intrusion34
 
 o.o
-XOX
+XQX
 .!.
 ?.?
 
 :8,B,value(30)
 
 obo
-XOX
+XQX
 .a.
 ?.?
 
@@ -1515,7 +1518,7 @@
 Pattern Intrusion35
 
 |..X??
-|...O?
+|...Q?
 |..X!X
 |...!.
 |...!.
@@ -1524,7 +1527,7 @@
 :8,B,value(30)
 
 |..X??
-|.baO?
+|.baQ?
 |.fXcX
 |..ed.
 |...!.
@@ -1536,7 +1539,7 @@
 Pattern Intrusion36
 
 ?X
-O!
+Q!
 Xx
 
 :8,B,value(30)
@@ -1568,7 +1571,7 @@
 Pattern Intrusion38
 
 X?
-!O
+!Q
 --
 
 :8,B,value(5)
@@ -1584,13 +1587,13 @@
 Pattern Intrusion39
 
 ?Xx
-O!.
+Q!.
 o!X
 
 :8,B,value(30)
 
 ?Xx
-Oa.
+Qa.
 o!X
 
 ;safe_omove(a)
@@ -1599,12 +1602,12 @@
 Pattern Intrusion40
 
 X!
-O?
+Q?
 
 :8,B,value(30)
 
 A!
-O?
+Q?
 
 ;lib(A)==1
 
@@ -1612,12 +1615,12 @@
 Pattern Intrusion41
 
 X!
-O!
+Q!
 
 :8,B,value(30)
 
 A!
-O!
+Q!
 
 ;lib(A)==1
 
@@ -1625,7 +1628,7 @@
 Pattern Intrusion42
 
 ?Ooo
-.XOo
+.XQo
 .!X.
 ....
 ----
@@ -1633,7 +1636,7 @@
 :8,B,value(30)
 
 ?Oeo
-bXOo
+bXQo
 .aDc
 ....
 ----
@@ -1644,13 +1647,13 @@
 Pattern Intrusion43
 
 ??XO
-..XO
+..XQ
 ?!!o
 
 :8,B,value(50)
 
 ??AO
-.cAO
+.cAQ
 ?dbo
 
 ;lib(A)==2 && !attack(A) && !oplay_attack(b,c,d,d)
@@ -1659,7 +1662,7 @@
 Pattern Intrusion44
 # gf New pattern. (3.1.20)
 
-.XO
+.XQ
 !!o
 
 :8,B,value(30)
@@ -1676,14 +1679,14 @@
 Pattern Intrusion45
 # gf New pattern. (3.1.20)
 
-X.Oo
+X.Qo
 .!X.
 ....
 ----
 
 :8,B,value(30)
 
-XbOo
+XbQo
 .aC.
 ....
 ----
@@ -1698,7 +1701,7 @@
 #        on one of the sides, but we don't know which one he will
 #        choose. This may or may not be a problem in practice.
 
-x.O.x
+x.Q.x
 .!X!.
 x...x
 x...x
@@ -1720,7 +1723,7 @@
 
 ??X.?
 o..!.
-O....
+Q....
 -----
 
 :8,B,value(20)
@@ -1738,7 +1741,7 @@
 
 ?X.
 ...
-O.!
+Q.!
 ..X
 
 :8,B,value(20)
@@ -1753,7 +1756,7 @@
 Pattern Intrusion49
 # ab added (3.1.24)
 
-XOX
+XQX
 .!!
 
 :8,B,value(30)
@@ -1768,7 +1771,7 @@
 # ab added (3.1.25)
 
 ?..
-OX!
+QX!
 ...
 ---