[gnugo-devel] Patch: Strategic effect for strategic attacks and defenses

[Inge Wallin]

Here is a patch that I have wanted to do for a very long time.  

Strategic effect is a part of the valuation of a move that is awarded
for two reasons:
 a) For connections that connect a weak dragon to a strong
 b) For strategic attacks and defenses
This patch only handles the case b) above.

The way this used to work was that a strategic bonus was awarded if we
played near a weak dragon, either our own or the opponents.  The
reasoning was that a weak opponent dragon would be further weakened if
we played near it, and our own dragon would be similarly
strengthened.  The problem was that this was assumed even though the
move itself did nothing for the strength of the dragon in question.

The way it works after this patch is that the weakness value is
recomputed after the move.  The change in weakness is multiplied with
the effective size of the dragon to get the strategic bonus.

Unfortunately, the weakness is not easy to compute after a move is
made, because the weakness value is dependent of so many other
factors, including owl status.  There is much to be improved here.
However, the patch below can be thought of as a seed for further
improvements.

I ran the regressions on the changed gnugo and got 13 PASSES and 21
FAILs.  However, then I discovered a bug and after I fixed that, some
half of the FAILs had disappeared and a number of new PASSes had
appeared.  I didn't have time to rerun it all, but that is the result
I got when I reran a few tests manually (among them strategy and
nngs1). 

I analyzed some of the results, and here is what I got:

trevora:220     PASSes, but maybe for the wrong reason.
                This test is of the form !B6, i.e to avoid a certain
                move.  This move is indeed avoided, and the strategic
                effect is smaller now.  However, it still has a far
                too high value, and it leaves too many weaknesses
                behind.  I think that there are other things wrong
                here as well and is worth further investigation.

trevora:530     FAILs, but used to pass by pure luck.
                This test used to giva strategic bonus for the dragon
                at G8, but the test would have failed if the dragon
                had been just one stone smaller (because the strategic
                effect would have been smaller).

                The real problem is that the owl code only can handle
                one attack/defense point. Owl gives G3 as a defense
                point for the lower left group at E6, and doesn't see
                that the connection at H4 saves the group as well.  Of
                course, in addition to saving E6, it also saves G8.
                I think the owl code should try connections to other
                nearby dragons first before trying to live on its
                own. 

nngs1:50        FAILs, but is almost there
                The connection gets a strategic bonus for N10 and P10
                as well as for the strategical attack on O9.  However,
                the stone at R10 is not taken into account although it
                obviously is important.

                The 3,3-invasion C3 (the chosen move) gets a valuation
                of 14.60, which might even be to low.

                The problem here is that not all stones that are
                affected by the connection are counted (no
                amalgamation across a one point jump).

strategy:27     FAILs, but for other reasons
                The wrong move F2, has an uncertain owl defense bonus
                of 14.33, which is nonsense.  The correct move C3 is
                the second best move.

strategy:39     FAILs, but partly for other reasons
                R6, which is the only move that is valued higher, has
                move reason that it owl-attacks R6 and a territorial
                value of 23.45, which is doubtful.  Also, P16, the
                correct move lacks a few followup move reasons, like
                the fact that it threatens to cut off and capture
                Q13. 

endgame:301     PASSes for the wrong reason
                The strategic effect that made A3 the move is
                indeed gone. However, gnugo still doesn't know that E5
                is worth 1 point and the half point that the ko is
                worth, somehow disappears in workarounds and
                followups.  This is worth investigating on its own.

lazarus:16      Properly solved

trevorb:220     Properly solved

trevorb:390     FAILs for other reason
                The chosen move, F7, has a valuation of 6 points for
                "defends against combination attack on several worms",
                which a) does only capture in ko and b) the correct
                move also protects against.  

                The problem here is that atari-atari only generates
                one defense point.

trevorb:450     FAILs for other reasons
                This move looks strange, but if you look at the
                valuation of the move reasons, it is hard to argue
                with them.

                The correct move F3 has a territorial value of 10.62
                points, which might be OK.  However, this move is
                bigger than that because the opponent can also claim
                this part of the board for himself.

                I think the problem is a missing reverse followup.

trevorb:660     Properly solved

All in all, for the tests that I investigated, most of them failed for
reasons other than the patch, and many of the PASSes were due to the
patch. 

Summary:
 - compute_escape() made public
 - compute_dragon_weakness() made public
 - compute_dragon_weakness_value() enhanced to make recomputing
   possible
 - dragon_delta_safety(): new function
 - use dragon_delta_safety() for valuation of strategic bonus for
   strategic attacks and defenses
 - minor cleanup of eyes.db

        -Inge

================================================================
diff -ur gnugo-3.3.8/engine/combination.c gnugo-3.3.8.iw/engine/combination.c
--- gnugo-3.3.8/engine/combination.c    Thu Sep  5 01:19:17 2002
+++ gnugo-3.3.8.iw/engine/combination.c Sun Oct  6 15:53:51 2002
@@ -102,6 +102,7 @@
   int k;
   int l;
 
+  /* Loop through all board positions and see if there are double threats. */
   for (ii = BOARDMIN; ii < BOARDMAX; ii++) {
     int num_a_threatened_groups;
     int a_threatened_groups[MAX_THREATENED_STRINGS];
diff -ur gnugo-3.3.8/engine/dragon.c gnugo-3.3.8.iw/engine/dragon.c
--- gnugo-3.3.8/engine/dragon.c Thu Sep  5 01:19:17 2002
+++ gnugo-3.3.8.iw/engine/dragon.c      Sat Oct 12 22:02:13 2002
@@ -57,7 +57,6 @@
 static int dragon_looks_inessential(int origin);
 static int compute_crude_status(int pos);
 static void dragon_eye(int pos, struct eye_data[BOARDMAX]);
-static int compute_escape(int pos, int dragon_status_known);
 static void compute_surrounding_moyo_sizes(int opposite,
                                           int dragon_status_known);
 
@@ -1548,7 +1547,7 @@
 /* Wrapper to call the function above and compute the escape potential
  * for the dragon at (pos).
  */
-static int
+int
 compute_escape(int pos, int dragon_status_known)
 {
   int ii;
@@ -1591,6 +1590,7 @@
   return dragon_escape(goal, board[pos], escape_value);
 }
 
+
 /*
  * Sum up the surrounding moyo sizes for each dragon. Write this into
  * dragon2[].moyo if it is smaller than the current entry. If (opposite)
@@ -1652,14 +1652,16 @@
  * a dragon. This coefficient * the effective size of the dragon can be
  * used to award a strategic penalty for weak dragons.
  */
-static float
-compute_dragon_weakness_value(int d)
+float
+compute_dragon_weakness_value(int d, float extra_territorial_value,
+                             float initial_escape_route)
 {
   float true_genus = (((float) dragon2[d].genus)
                      + 0.5 * ((float) dragon2[d].heyes
                               + (dragon2[d].lunch != NO_MOVE ? 1.0 : 0.0)));
   int origin = dragon2[d].origin;
-  float escape_route = (float) dragon2[d].escape_route;
+  float escape_route;
+  float territorial_value;
   int dragon_safety = dragon2[d].safety;
   int i, j;
 
@@ -1692,10 +1694,16 @@
    * - possible connections to neighbour dragons
    */
 
-  weakness_value[0] = gg_interpolate(&moyo_value2weakness,
-                                    dragon2[d].moyo_territorial_value);
-  weakness_value[1] = gg_interpolate(&escape_route2weakness,
-                                    escape_route);
+  territorial_value = (dragon2[d].moyo_territorial_value
+                      + extra_territorial_value);
+  weakness_value[0] = gg_interpolate(&moyo_value2weakness, territorial_value);
+
+  if (initial_escape_route == -1.0)
+    escape_route = (float) dragon2[d].escape_route;
+  else
+    escape_route = initial_escape_route;
+  weakness_value[1] = gg_interpolate(&escape_route2weakness, escape_route);
+
   weakness_value[2] = gg_interpolate(&genus2weakness, true_genus);
 
   DEBUG(DEBUG_DRAGONS, "Computing weakness of dragon at %1m:\n", origin);
@@ -1704,6 +1712,7 @@
        dragon2[d].moyo_territorial_value, weakness_value[0],
        escape_route, weakness_value[1], true_genus, weakness_value[2]);
 
+  /* Sort intermediate weakness values. */
   for (i = 0; i < 3; i++)
     for (j = i + 1; j < 3; j++)
       if (weakness_value[j] < weakness_value[i]) {
@@ -1755,11 +1764,12 @@
    * this yields smaller results.
    */
   compute_surrounding_moyo_sizes(1, 1);
-
   for (d = 0; d < number_of_dragons; d++)
-    dragon2[d].weakness = compute_dragon_weakness_value(d);
+    dragon2[d].weakness = compute_dragon_weakness_value(d, 0.0, -1.0);
 }
 
+
+
 /* 
  * Test whether two dragons are the same. Used by autohelpers and elsewhere.
  */
diff -ur gnugo-3.3.8/engine/liberty.h gnugo-3.3.8.iw/engine/liberty.h
--- gnugo-3.3.8/engine/liberty.h        Tue Sep  3 16:13:37 2002
+++ gnugo-3.3.8.iw/engine/liberty.h     Sat Oct 12 21:56:02 2002
@@ -803,6 +803,10 @@
 
 #define DRAGON(d) dragon[dragon2[d].origin]
 
+int   compute_escape(int pos, int dragon_status_known);
+float compute_dragon_weakness_value(int d, float extra_territorial_value,
+                                   float initial_escape_route);
+
 struct aftermath_data {
   int white_captured;
   int black_captured;
diff -ur gnugo-3.3.8/engine/value_moves.c gnugo-3.3.8.iw/engine/value_moves.c
--- gnugo-3.3.8/engine/value_moves.c    Tue Sep  3 16:13:37 2002
+++ gnugo-3.3.8.iw/engine/value_moves.c Sun Oct 13 15:11:07 2002
@@ -847,6 +847,96 @@
   return (1.0 - DRAGON2(dr).weakness);
 }
 
+
+static float
+dragon_delta_safety(int dr, int pos, int color)
+{
+  int    dragon_safety = DRAGON2(dr).safety;
+  char   saved_stones[BOARDMAX];
+  float  weakness;
+  float  delta_terri;
+  float  followup_value;
+  struct dragon_data  save_dragon_data;
+  float  escape_route;
+  float  retval;
+  int    i;
+
+#if 0
+  gprintf("dragon_delta_safety() for dragon %1m, %C move at %1m\n",
+         dr, color, pos);
+#endif
+
+  /* Kludge: If a dragon is dead, we return 1.0 in order not
+   * to try to run away.
+   */
+  if (dragon_safety == DEAD
+      || dragon_safety == INESSENTIAL
+      || dragon_safety == TACTICALLY_DEAD)
+    return 1.0;
+
+  /* When scoring, we don't want to reinforce ALIVE dragons. */
+  if (doing_scoring && dragon_safety == ALIVE)
+    return 1.0;
+
+  weakness = DRAGON2(dr).weakness;
+  memset(saved_stones, 0, BOARDMAX);
+  saved_stones[pos] = INFLUENCE_SAVED_STONE;
+  delta_terri = influence_delta_territory(pos, color, saved_stones,
+                                         &followup_value);
+  
+  /* Add the move at 'pos' to the dragon if the move is the same
+   * color as the dragon.  Otherwise find a neighboring dragon and 
+   * add to that one.
+   *
+   * FIXME: Do this for real later, but test it first.
+   */
+  save_dragon_data = dragon[pos];
+  if (color == board[dr])
+    dragon[pos] = dragon[dr];
+  else {
+    /* Find a neighbour dragon. */
+    for (i = 0; i < 4; i++) {
+      int  pos2 = pos + delta[i];
+
+      if (ON_BOARD1(pos2) && board[pos2] == color) {
+       dragon[pos] = dragon[pos2];
+       break;
+      }
+    }
+    if (i == 4) {
+      /* There was no neighbor.  Fake one.
+       * FIXME: This is *real* ugly, but is necessary because 
+       *        influence_delta_moyo has an assertion for id != 0.
+       */
+      dragon[pos].id = number_of_dragons;
+    }
+  }
+  escape_route = compute_escape(dr, 1);
+  dragon[pos]  = save_dragon_data;
+
+#if 0
+  gprintf("delta_terri: %f, escape_route: was %f now %f\n", 
+         delta_terri, (float) (DRAGON2(dr).escape_route), escape_route);
+#endif
+  /* The safety value is the negation of the weakness value. */
+  retval = -(compute_dragon_weakness_value(dragon[dr].id, 
+                                          delta_terri, escape_route)
+            - weakness);
+
+  /* If we move on our own dragon, we strengthen it, if we move on the
+   * opponents, we weaken it. */
+  if (color != board[dr])
+    retval = -retval;
+
+#if 0
+  gprintf("dragon_delta_safety result:  %f (old weakness: %f)\n", 
+         retval, weakness);
+#endif
+
+  return retval;
+}
+
+
 /*
  * Strategical value of connecting (or cutting) the dragon at (dragona)
  * to the dragon at (dragonb). Notice that this function is asymmetric.
@@ -1800,7 +1890,10 @@
   float this_value = 0.0;
   float tot_value = 0.0;
 
-  /* Strategical value of connecting or cutting dragons. */
+  /* Strategical value of:
+   *  - connecting or cutting dragons.
+   *  - strategicly attacking or defending dragons.
+   */
   static float dragon_value[MAX_DRAGONS];
 
   /* This loop used to be up to next_dragon, but that is not safe
@@ -1871,13 +1964,16 @@
            d1 = lunch_dragon[l];
            bb = dragons[d1];
 
-           /* FIXME: This value cannot be computed without some
-            * measurement of how the actual move affects the dragon.
-            * The dragon safety alone is not enough. The question is
-            * whether the dragon is threatened by the move or not.
+           /* FIXME: We must take into account the color of the move
+            *        and the dragon (see below).
             */
+#if 0
            this_value = (dragon[bb].effective_size
                          * (1.0 - dragon_safety(bb, 0)));
+#else
+           this_value = (dragon_delta_safety(bb, pos, color)
+                         * dragon[bb].effective_size);
+#endif
 
            /* If this dragon consists of only one worm and that worm
             * can be tactically captured or defended by this move, we
@@ -2136,13 +2232,15 @@
        d1 = move_reasons[r].what;
        aa = dragons[d1];
 
-       /* FIXME: This value cannot be computed without some
-        * measurement of how the actual move affects the dragon. The
-        * dragon safety alone is not enough. The question is whether
-        * the dragon is threatened by the move or not.
+       /* Check how much the weakness of the dragon is affected by
+        * the move and put a score on that.
         */
-       this_value = (dragon[aa].effective_size
-                     * (1.0 - dragon_safety(aa, 1)));
+       if (color == board[pos])
+         this_value = (dragon_delta_safety(aa, pos, color)
+                       * dragon[aa].effective_size);
+       else
+         this_value = -(dragon_delta_safety(aa, pos, color)
+                        * dragon[aa].effective_size);
 
        /* To prefer good connections and cuts, we lower this value
         * somewhat.
@@ -2241,6 +2339,7 @@
            pos, dragon_value[k], aa);
       continue;
     }
+
     /* If the dragon has been owl captured, owl defended, or involved
      * in a semeai, we have likewise already counted the points as
      * territorial value.
diff -ur gnugo-3.3.8/engine/worm.c gnugo-3.3.8.iw/engine/worm.c
--- gnugo-3.3.8/engine/worm.c   Thu Sep  5 01:19:17 2002
+++ gnugo-3.3.8.iw/engine/worm.c        Sun Oct  6 13:22:50 2002
@@ -1180,6 +1180,7 @@
     if (!is_worm_origin(pos, pos))
       continue;
 
+    /* Report attacks and attack threats on the opponents worms. */
     if (board[pos] == OTHER_COLOR(color)) {
       for (k = 0; k < MAX_TACTICAL_POINTS; k++) {
        if (worm[pos].attack_codes[k] != 0)
@@ -1190,7 +1191,8 @@
                                 worm[pos].attack_threat_codes[k]);
       }
     }
-      
+
+    /* Report defenses and defense threats on our own worms. */
     if (board[pos] == color) {
       for (k = 0; k < MAX_TACTICAL_POINTS; k++) {
        if (worm[pos].defend_codes[k] != 0)
diff -ur gnugo-3.3.8/patterns/eyes.db gnugo-3.3.8.iw/patterns/eyes.db
--- gnugo-3.3.8/patterns/eyes.db        Sat Jun 15 17:00:00 2002
+++ gnugo-3.3.8.iw/patterns/eyes.db     Fri Oct 11 21:40:56 2002
@@ -622,14 +622,6 @@
 
 
 Pattern 512
-# FIXME: The correct form of this pattern is
-# 
-# |.X>
-# |< X
-# +---
-# 
-# but the code towards the end of recognize_eye() can't handle the
-# pattern because there is no '*' or '@'.
 
 |.X>
 |< X