[gnugo-devel] invasion_penalty_1_29.1

[Arend Bayer]

 - new function influence_initial_territory to export territory valuation
 - negative strategic value added to invasion type moves
 - pattern tuning: keima shape bonus removed
 
This patch devalues two types of moves: moves that enter the opponent's
moyo, without any support from a friendly stone nearby, and moves that
try to run away with a single stone directly adjacent to a strong hostile
dragon, typically a wall.

These moves are singled out by some heuristics:
* All adjacent intersecions have to belong to the opponent's moyo.
* Almost all move reasons are incompatible with a move as described above.
* In particular, an owl defense is only allowed for a dragon consisting of
  a single stone; this single stone has to be directly adjacent to an
  opponent's dragon whose safety is STRONGLY_ALIVE or better. (Some more
  rules for this case.)
  
The rationale for this is that the influence module cannot be responsible
for seeing what the opponent can gain by attacking this new weak group.

This penalty is added as a negative value to the strategical value of the
move. The value subtracted is 12 times the territory valuation of the
point where we want to play. This is not a very sophisticated guess,
but it seems to work.

Due to the rather strict heuristics, there are only 5 changed regressions,
all of them PASSes. But I think the phenomenon is rather frequent in
recent games, and the patch should help GNU Go a bit to stay out of
trouble. The urgent test case nngs:900 gets only slightly better, the correct
move has at least made it into the top ten :-) (Its a little better if run
with --owl-threats.)

The influence_initial_territory function might also be useful as an
autohelper, in cases where whose_moyo etc. are too coarse.

The keima shape bonus seems rather unnecessary with new influence :-)

Arend

Changed regressions:

./regress.sh . nngs1.tst
16 unexpected PASS!
17 unexpected PASS!
./regress.sh . trevorb.tst
180 unexpected PASS!
./regress.sh . trevorc.tst
280 unexpected PASS!
./regress.sh . arend.tst
38 unexpected PASS!


Platform depencies (it would be quite good if we could solve these before 3.2):
./regress.sh . ld_owl.tst
301 unexpected FAIL: Correct '3 B18', got '0'
./regress.sh . 13x13.tst
27 unexpected PASS!

Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.43
diff -u -r1.43 influence.c
--- engine/influence.c  7 Mar 2002 05:35:28 -0000       1.43
+++ engine/influence.c  25 Mar 2002 07:48:57 -0000
@@ -1586,6 +1586,18 @@
   }
 }
 
+/* Export the territory valuation at an intersection from initial_influence;
+ * it is given from (color)'s point of view.
+ */
+float
+influence_initial_territory(int pos, int color)
+{
+  if (color == WHITE)
+    return initial_influence.territory_value[I(pos)][J(pos)];
+  else
+    return -initial_influence.territory_value[I(pos)][J(pos)];
+}
+
 /* Compute the influence before a move has been made, which can
  * later be compared to the influence after a move. Assume that
  * the other color is in turn to move.
@@ -1601,14 +1613,16 @@
     experimental_influence = 0;
   compute_influence(&initial_influence, OTHER_COLOR(color), -1, -1,
                    dragons_known, NULL, NULL);
-  if (experimental_influence)
-    new_value_territory(&initial_influence);
-  else
-    value_territory(&initial_influence);
-  if ((printmoyo & PRINTMOYO_VALUE_TERRITORY)
-      && (printmoyo & PRINTMOYO_INITIAL_INFLUENCE))
-    print_influence_territory(&initial_influence,
-                              "territory (initial influence):\n");
+  if (dragons_known) {
+    if (experimental_influence)
+      new_value_territory(&initial_influence);
+    else
+      value_territory(&initial_influence);
+    if ((printmoyo & PRINTMOYO_VALUE_TERRITORY)
+       && (printmoyo & PRINTMOYO_INITIAL_INFLUENCE))
+      print_influence_territory(&initial_influence,
+                               "territory (initial influence):\n");
+  }
 
   compute_influence(&initial_opposite_influence, color, -1, -1,
                    dragons_known, NULL, NULL);
@@ -1746,7 +1760,9 @@
       value_territory(&move_influence);
     if (m == (board_size - 19) + debug_influence_i
          && n == debug_influence_j && m >= 0) {
-      print_influence_territory(&move_influence, "territory (after move):\n");
+      if (printmoyo & PRINTMOYO_VALUE_TERRITORY)
+        print_influence_territory(&move_influence,
+                                 "territory (after move):\n");
       if (experimental_influence) {
         print_influence(&followup_influence, "followup influence");
         if (printmoyo & PRINTMOYO_VALUE_TERRITORY)
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.91
diff -u -r1.91 liberty.h
--- engine/liberty.h    21 Mar 2002 14:23:09 -0000      1.91
+++ engine/liberty.h    25 Mar 2002 07:49:02 -0000
@@ -534,6 +534,7 @@
 void influence_get_moyo_segmentation(int opposite, struct moyo_data *moyo);
 float influence_estimate_score(float moyo_coeff, float area_coeff);
 void influence_mark_non_territory(int pos, int color);
+float influence_initial_territory(int pos, int color);
 
 void  old_estimate_score(int color, float *lower_bound, float *upper_bound);
 float estimate_score(float *upper, float *lower);
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.19
diff -u -r1.19 value_moves.c
--- engine/value_moves.c        20 Mar 2002 15:02:22 -0000      1.19
+++ engine/value_moves.c        25 Mar 2002 07:49:13 -0000
@@ -1044,6 +1044,100 @@
   return adjusted_value;
 }
 
+/* The new (3.2) territorial evaluation overvalues moves creating a new
+ * group in the opponent's sphere of influence. The influence module cannot
+ * see that the opponent will gain by attacking the new (probably weak)
+ * group.
+ * This function uses some heuristics to estimate the strategic penalty
+ * of invasion moves, and moves that try to run away with a group of size
+ * 1 in front of opponent's strength.
+ */
+static float
+strategic_penalty(int pos, int color)
+{
+  int k;
+  float ret_val;
+  
+  /* We try to detect support from an alive friendly stone by checking
+   * whether all neighboring intersections belong to the opponent's moyo.
+   */
+  for (k = 0; k < 4; k++)
+    if (board[pos + delta[k]] != OTHER_COLOR(color)
+        && influence_moyo_color(pos + delta[k]) != OTHER_COLOR(color))
+      return 0.0;
+
+  for (k = 0; k < MAX_REASONS; k++) {
+    int r = move[pos].reason[k];
+    if (r == -1)
+      break;
+    /* We assume that invasion moves can only have the move reasons listed
+     * below.
+     */
+    switch (move_reasons[r].type) {
+    case EXPAND_TERRITORY_MOVE:
+    case BLOCK_TERRITORY_MOVE:
+    case EXPAND_MOYO_MOVE:
+    case STRATEGIC_ATTACK_MOVE:
+      continue;
+    /* An owl defense of a single stone might be a stupid attempt to run
+     * away with an unimportant (kikashi like) stone. We assume this is the
+     * case if this single stone has a strong hostile direct neighbor.
+     */
+    case OWL_DEFEND_MOVE:
+      {
+       int target = dragons[move_reasons[r].what];
+       int has_strong_neighbor = 0;
+       int has_weak_neighbor = 0;
+       int i;
+       /* We award no penalty for running away with a cutting stone. */
+       if (dragon[target].size > 1
+           || worm[target].cutstone > 0
+           || worm[target].cutstone2 > 0)
+         return 0.0;
+       /* Third line moves (or lower) are ok -- they try to live, not run
+         * away.
+         */
+        if (gg_min(gg_min(I(pos), board_size-1 - I(pos)),
+                   gg_min(J(pos), board_size-1 - J(pos)))
+            < 3)
+         return 0.0;
+       for (i = 0; i < 4; i++)
+         if (board[target + delta[i]] == OTHER_COLOR(color)) {
+           if (dragon[target + delta[i]].size == 1) {
+             has_weak_neighbor = 1;
+             break;
+           }
+           switch (DRAGON2(target + delta[i]).safety) {
+           case INVINCIBLE:
+           case STRONGLY_ALIVE:
+             has_strong_neighbor = 1;
+             break;
+           case ALIVE:
+             continue;
+           default:
+             has_weak_neighbor = 1;
+           }
+         }
+       if (has_weak_neighbor || (!has_strong_neighbor))
+         return 0.0;
+       else
+         continue;
+      }
+    default:
+      return 0.0;
+    }  
+  }
+
+  /* We have to make a gues how much the point where we want to play
+   * is dominated by the opponent. The territorial valuation is a
+   * good try here.
+   */
+  ret_val = influence_initial_territory(pos, OTHER_COLOR(color));
+  
+  ret_val *= 12.0;
+  ret_val = gg_max(0.0, ret_val);
+  return ret_val;
+}
 
 /*
  * Estimate the direct territorial value of a move at (pos).
@@ -1986,6 +2080,14 @@
     TRACE("  %1m: %f - strategic effect on %1m\n",
          pos, dragon_value[k], dragons[k]);
     tot_value += dragon_value[k];
+  }
+  
+  /* Finally, subtract penalty for invasion type moves. */
+  this_value = strategic_penalty(pos, color);
+  if (this_value > 0.0) {
+    TRACE("  %1m: %f - strategic penalty, considered as invasion.\n",
+         pos, -this_value);
+    tot_value -= this_value;
   }
 
   move[pos].strategical_value = tot_value;
Index: patterns/patterns.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/patterns.db,v
retrieving revision 1.57
diff -u -r1.57 patterns.db
--- patterns/patterns.db        20 Mar 2002 15:02:22 -0000      1.57
+++ patterns/patterns.db        25 Mar 2002 07:49:30 -0000
@@ -7298,6 +7298,7 @@
 
 
 Pattern CB204b
+# ab removed shape value (3.1.28)
 
 .....        knight's move to claim space
 .....
@@ -7305,7 +7306,7 @@
 O....
 ?X...
 
-:8,OXEd,shape(2)
+:8,OXEd
 
 e....
 .....