[gnugo-devel] thrashing dragons and delta territory cache

[Arend Bayer]

- make delta territory cache aware of recomputations of the initial influence

Parts of the thrashing dragon heurstics were accidentally disabled by my
influence rewrite. This reenables it.

The problem was that after the influence is recomputed due to the calls
to compute_influence() in revise_thrashing_dragon(), the delta territory
cache did not get marked invalid.

However, this patch causes no changes in the regressions at all (while I
checked that it does indeed work).

One reason could be that the conditions of revising a thrashing dragon
are pretty strict: lead >15 pts, and (more importantly) move value < 10 pts.
Note that at this point e.g. the connection heuristic against thrashing
dragons has already done its job, which might quite likely have produced
a move worth more than 10 pts.

Arend

Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.78
diff -u -p -r1.78 influence.c
--- engine/influence.c  16 Apr 2003 22:03:43 -0000      1.78
+++ engine/influence.c  3 May 2003 22:40:33 -0000
@@ -66,17 +66,16 @@ static struct influence_data escape_infl
 /* Pointer to influence data used during pattern matching. */
 static struct influence_data *current_influence = NULL;

-/* Cache of delta_territory_values. */
-static float delta_territory_cache[BOARDMAX];
-static float followup_territory_cache[BOARDMAX];
-static int territory_cache_position_number = -1;
-static int territory_cache_color = -1;
-
 /* If set, print influence map when computing this move. Purely for
  * debugging.
  */
 static int debug_influence = NO_MOVE;

+/* Assigns an id to all influence computations for reference in the
+ * delta territory cache.
+ */
+static int influence_id = 0;
+
 /* This is the core of the influence function. Given the coordinates
  * and color of an influence source, it radiates the influence
  * outwards until it hits a barrier or the strength of the influence
@@ -1010,6 +1009,9 @@ compute_influence(int color, const char
       || (move != NO_MOVE && move != debug_influence))
     debug = debug &~ DEBUG_INFLUENCE;

+  influence_id++;
+  q->id = influence_id;
+
   do_compute_influence(color, safe_stones, strength, q, move, trace_message);

   debug = save_debug;
@@ -1603,18 +1605,34 @@ compute_escape_influence(int color, cons
   active_caches[cache_number] = 1;
 }

+
+/* Cache of delta_territory_values. */
+static float delta_territory_cache[BOARDMAX];
+static float followup_territory_cache[BOARDMAX];
+static int territory_cache_position_number = -1;
+static int territory_cache_influence_id = -1;
+static int territory_cache_color = -1;
+
 /* We cache territory computations. This avoids unnecessary re-computations
  * when review_move_reasons is run a second time for the endgame patterns.
+ *
+ * (*base) points to the initial_influence data that would be used
+ * to make the territory computation against.
  */
 int
 retrieve_delta_territory_cache(int pos, int color, float *move_value,
-                              float *followup_value)
+                              float *followup_value,
+                              const struct influence_data *base)
 {
   ASSERT_ON_BOARD1(pos);
   ASSERT1(IS_STONE(color), pos);

+  /* We check whether the color, the board position, or the base influence
+   * data has changed since the cache entry got entered.
+   */
   if (territory_cache_position_number == position_number
       && territory_cache_color == color
+      && territory_cache_influence_id == base->id
       && delta_territory_cache[pos] != NOT_COMPUTED) {
     *move_value = delta_territory_cache[pos];
     *followup_value = followup_territory_cache[pos];
@@ -1628,17 +1646,20 @@ retrieve_delta_territory_cache(int pos,

 void
 store_delta_territory_cache(int pos, int color,
-                           float move_value, float followup_value)
+                           float move_value, float followup_value,
+                           const struct influence_data *base)
 {
   ASSERT_ON_BOARD1(pos);
   ASSERT1(IS_STONE(color), pos);

   if (territory_cache_position_number != position_number
-      || territory_cache_color != color) {
+      || territory_cache_color != color
+      || territory_cache_influence_id != base->id) {
     int ii;
     for (ii = BOARDMIN; ii < BOARDMAX; ii++)
       delta_territory_cache[ii] = NOT_COMPUTED;
     territory_cache_position_number = position_number;
+    territory_cache_influence_id = base->id;
     territory_cache_color = color;
     if (0)
       gprintf("Cleared delta territory cache.\n");
Index: engine/influence.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.h,v
retrieving revision 1.16
diff -u -p -r1.16 influence.h
--- engine/influence.h  15 Feb 2003 14:32:54 -0000      1.16
+++ engine/influence.h  3 May 2003 22:40:33 -0000
@@ -113,6 +113,8 @@ struct influence_data

   int intrusion_counter;
   struct intrusion_data intrusions[MAX_INTRUSIONS];
+
+  int id;
 };

 /* Typedef for pointer to either of the functions whose_territory(),
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.166
diff -u -p -r1.166 liberty.h
--- engine/liberty.h    1 May 2003 20:55:26 -0000       1.166
+++ engine/liberty.h    3 May 2003 22:40:36 -0000
@@ -679,9 +679,11 @@ float influence_delta_territory(const st
                                const struct influence_data *q, int color,
                                int move);
 int retrieve_delta_territory_cache(int pos, int color, float *move_value,
-                                  float *followup_value);
+                                  float *followup_value,
+                                  const struct influence_data *base);
 void store_delta_territory_cache(int pos, int color, float move_value,
-                                float followup_value);
+                                float followup_value,
+                                const struct influence_data *base);

 int whose_territory(const struct influence_data *q, int pos);
 int whose_moyo(const struct influence_data *q, int pos);
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.89
diff -u -p -r1.89 value_moves.c
--- engine/value_moves.c        28 Apr 2003 17:45:04 -0000      1.89
+++ engine/value_moves.c        3 May 2003 22:40:41 -0000
@@ -1938,7 +1938,8 @@ estimate_territorial_value(int pos, int
   if (does_block && move[pos].move_safety
       && tryko(pos, color, "estimate_territorial_value", EMPTY, NO_MOVE)) {
     if (!retrieve_delta_territory_cache(pos, color, &this_value,
-                                       &move[pos].influence_followup_value)) {
+                                       &move[pos].influence_followup_value,
+                                       OPPOSITE_INFLUENCE(color))) {
       compute_influence(OTHER_COLOR(color), safe_stones, strength,
                        &move_influence, pos, "after move");
       compute_followup_influence(&move_influence, &followup_influence,
@@ -1953,7 +1954,8 @@ estimate_territorial_value(int pos, int
        = influence_delta_territory(&move_influence, &followup_influence,
                                    color, pos);
       store_delta_territory_cache(pos, color, this_value,
-                                 move[pos].influence_followup_value);
+                                 move[pos].influence_followup_value,
+                                 OPPOSITE_INFLUENCE(color));
     }
     else {
       if (this_value != 0.0)