[gnugo-devel] reading and owl patch

[Gunnar Farneback]

This patch solves a somewhat serious bug with the persistent caches.
If the board size is changed, e.g. during a GTP session, bad things
can happen. Suppose a small scale reading at the bottom of a 19x19
board is stored in the cache and the board size is subsequently
changed to 9x9. Then the active area won't overlap with the
intersections on the 9x9 board and the entry is assumed to be valid.
This is of course wrong, but seems to be harmless in most
circumstances. However, when running aftermath scoring it may cause a
crash. The patch adds explicit board size information to the
persistent caches.

The patch also includes a few other changes:
* A very minor revision to break_chain_efficient_moves(), removing
some useless variations in certain positions.

* A new function reduced_init_owl() cleans up a little code
duplication.

* mark_dragon_hotspot_values() has been revised. This only has effect
on the aftermath scoring.

The patch has no impact on the regressions.

- boardsize field added to persistent caches in reading.c and owl.c
- break_chain_efficient_moves() revised
- new function reduced_init_owl() in owl.c
- mark_dragon_hotspot_values() revised

/Gunnar

Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.56
diff -u -r1.56 reading.c
--- engine/reading.c    1 Apr 2002 19:42:34 -0000       1.56
+++ engine/reading.c    4 Apr 2002 09:24:41 -0000
@@ -158,6 +158,7 @@
 #define MAX_CACHE_DEPTH 5
 
 struct reading_cache {
+  int boardsize;
   char board[BOARDMAX];
   int movenum;
   int nodes;
@@ -4784,7 +4785,8 @@
     if (adj2 == 1 && countlib(str) > 2) {
       int apos;
       findlib(adjs2[0], 1, &apos);
-      ADD_CANDIDATE_MOVE(apos, 0, moves, scores, *num_moves);
+      if (!is_self_atari(apos, color))
+       ADD_CANDIDATE_MOVE(apos, 0, moves, scores, *num_moves);
       continue;
     }
     
@@ -6080,22 +6082,28 @@
   else
     last_purge_position_number = position_number;
 
+  
+  
   for (k = 0; k < persistent_reading_cache_size; k++) {
     int played_moves = 0;
     int entry_ok = 1;
 
-    for (r = 0; r < MAX_CACHE_DEPTH; r++) {
-      int apos = persistent_reading_cache[k].stack[r];
-      int color = persistent_reading_cache[k].move_color[r];
-      if (apos == 0)
-       break;
-      if (board[apos] == EMPTY
-         && trymove(apos, color, "purge_persistent_reading_cache", 0,
-                    EMPTY, 0))
-       played_moves++;
-      else {
-       entry_ok = 0;
-       break;
+    if (persistent_reading_cache[k].boardsize != board_size)
+      entry_ok = 0;
+    else {
+      for (r = 0; r < MAX_CACHE_DEPTH; r++) {
+       int apos = persistent_reading_cache[k].stack[r];
+       int color = persistent_reading_cache[k].move_color[r];
+       if (apos == 0)
+         break;
+       if (board[apos] == EMPTY
+           && trymove(apos, color, "purge_persistent_reading_cache", 0,
+                      EMPTY, 0))
+         played_moves++;
+       else {
+         entry_ok = 0;
+         break;
+       }
       }
     }
 
@@ -6134,7 +6142,8 @@
     int apos = 0;
     if (entry->routine != routine
        || entry->str != str
-       || entry->remaining_depth < (depth - stackp))
+       || entry->remaining_depth < (depth - stackp)
+       || entry->boardsize != board_size)
       continue;
     
     for (r = 0; r < MAX_CACHE_DEPTH; r++) {
@@ -6241,14 +6250,15 @@
   }
 
   entry = &(persistent_reading_cache[persistent_reading_cache_size]);
-  entry->movenum = movenum;
-  entry->nodes   = nodes;
-  entry->score   = score;
+  entry->boardsize       = board_size;
+  entry->movenum         = movenum;
+  entry->nodes           = nodes;
+  entry->score           = score;
   entry->remaining_depth = depth - stackp;
-  entry->routine = routine;
-  entry->str    = str;
-  entry->result  = result;
-  entry->move   = move;
+  entry->routine         = routine;
+  entry->str            = str;
+  entry->result          = result;
+  entry->move           = move;
 
   for (r = 0; r < MAX_CACHE_DEPTH; r++) {
     if (r < stackp)
@@ -6353,6 +6363,7 @@
 {
   struct reading_cache *entry = &(persistent_reading_cache[k]);
   int r;
+  gprintf("%oboardsize       = %d\n",  entry->boardsize);
   gprintf("%omovenum         = %d\n",  entry->movenum);
   gprintf("%onodes           = %d\n",  entry->nodes);
   gprintf("%oscore           = %d\n",  entry->score);
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.77
diff -u -r1.77 owl.c
--- engine/owl.c        1 Apr 2002 19:42:34 -0000       1.77
+++ engine/owl.c        4 Apr 2002 09:24:40 -0000
@@ -130,6 +130,7 @@
 
 /* Persistent owl result cache to reuse owl results between moves. */
 struct owl_cache {
+  int boardsize;
   char board[BOARDMAX];
   int movenum;
   int tactical_nodes;
@@ -171,8 +172,9 @@
                                       char goal[BOARDMAX],
                                       int goal_color);
 static void print_persistent_owl_cache_entry(int k);
-static void mark_dragon_hotspot_values(float values[BOARDMAX],
-                                      int pos, float contribution);
+static void mark_dragon_hotspot_values(float values[BOARDMAX], int pos,
+                                      float contribution,
+                                      char active_board[BOARDMAX]);
 
 
 static int do_owl_attack(int str, int *move, 
@@ -239,6 +241,7 @@
 static int matches_found;
 static char found_matches[BOARDMAX];
 
+static void reduced_init_owl(struct local_owl_data **owl);
 static void init_owl(struct local_owl_data **owl, int target1, int target2,
                     int move, int use_stack);
 
@@ -4132,13 +4135,10 @@
   if (debug & DEBUG_OWL_PERFORMANCE)
     start = gg_cputime();
 
-  /* FIXME: We want to use init_owl here too (cf. similar remark below). */
-  if (owl_stack_size == 0) {
-    owl_stack = malloc((owl_reading_depth + 1) * sizeof(*owl_stack));
-    gg_assert(owl_stack != NULL);
-    owl_stack_size = owl_reading_depth + 1;
-  }
-  owl = &owl_stack[0];
+  /* FIXME: We want to use the full init_owl here too (cf. similar
+   * remark below).
+   */
+  reduced_init_owl(&owl);
 
   owl->color = OTHER_COLOR(board[str]);
   owl->local_owl_node_counter = 0;
@@ -4529,8 +4529,24 @@
 
 /****************************
  * Initialization of owl data
- ****************************
- *
+ ****************************/
+
+/* This is a temporary solution. We want to be able to use the full
+ * init_owl() also in owl_substantial.
+ */
+static void
+reduced_init_owl(struct local_owl_data **owl)
+{
+  if (owl_stack_size == 0) {
+    owl_stack_size = owl_reading_depth + 2;
+    owl_stack = malloc(owl_stack_size * sizeof(*owl_stack));
+    gg_assert(owl_stack != NULL);
+  }
+  *owl = &owl_stack[0];
+}
+
+
+/*
  * If use_stack is set, the stack is initialized, and the return value
  * of *owl is a pointer to the bottom of the stack.
  */
@@ -4538,14 +4554,8 @@
 init_owl(struct local_owl_data **owl, int target1, int target2, int move,
          int use_stack)
 {
-  if (use_stack) {
-    if (owl_stack_size == 0) {
-      owl_stack_size = owl_reading_depth + 2;
-      owl_stack = malloc(owl_stack_size * sizeof(*owl_stack));
-      gg_assert(owl_stack != NULL);
-    }
-    *owl = &owl_stack[0];
-  }
+  if (use_stack)
+    reduced_init_owl(owl);
 
   (*owl)->local_owl_node_counter = 0;
   (*owl)->lunches_are_current = 0;
@@ -4684,7 +4694,8 @@
     last_purge_position_number = position_number;
 
   for (k = 0; k < persistent_owl_cache_size; k++) {
-    if (!verify_stored_board(persistent_owl_cache[k].board)) {
+    if (persistent_owl_cache[k].boardsize != board_size
+       || !verify_stored_board(persistent_owl_cache[k].board)) {
       /* Move the last entry in the cache here and back up the loop
        * counter to redo the test at this position in the cache.
        */
@@ -4747,14 +4758,15 @@
     return;
   }
 
-  persistent_owl_cache[persistent_owl_cache_size].routine = routine;
-  persistent_owl_cache[persistent_owl_cache_size].apos   = apos;
-  persistent_owl_cache[persistent_owl_cache_size].bpos   = bpos;
-  persistent_owl_cache[persistent_owl_cache_size].cpos   = cpos;
-  persistent_owl_cache[persistent_owl_cache_size].result  = result;
+  persistent_owl_cache[persistent_owl_cache_size].boardsize     = board_size;
+  persistent_owl_cache[persistent_owl_cache_size].routine       = routine;
+  persistent_owl_cache[persistent_owl_cache_size].apos          = apos;
+  persistent_owl_cache[persistent_owl_cache_size].bpos          = bpos;
+  persistent_owl_cache[persistent_owl_cache_size].cpos          = cpos;
+  persistent_owl_cache[persistent_owl_cache_size].result        = result;
   persistent_owl_cache[persistent_owl_cache_size].result_certain = certain;
-  persistent_owl_cache[persistent_owl_cache_size].move   = move;
-  persistent_owl_cache[persistent_owl_cache_size].move2          = move2;
+  persistent_owl_cache[persistent_owl_cache_size].move          = move;
+  persistent_owl_cache[persistent_owl_cache_size].move2                 = 
move2;
   persistent_owl_cache[persistent_owl_cache_size].tactical_nodes =
     tactical_nodes;
   persistent_owl_cache[persistent_owl_cache_size].movenum = movenum;
@@ -4873,35 +4885,52 @@
 
 /* Helper for the owl_hotspots() function below. */
 static void
-mark_dragon_hotspot_values(float values[BOARDMAX], int pos, float contribution)
+mark_dragon_hotspot_values(float values[BOARDMAX], int dr,
+                          float contribution, char active_board[BOARDMAX])
 {
-  int i, j, k;
-  ASSERT1(IS_STONE(board[pos]), pos);
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++) {
-      if (BOARD(i, j) != EMPTY)
-       continue;
-      for (k = 0; k < 8; k++) {
-       int di = deltai[k];
-       int dj = deltaj[k];
-       if (IS_STONE(BOARD(i+di, j+dj))
-           && is_same_dragon(POS(i+di, j+dj), pos)
-           && (countlib(POS(i+di, j+dj)) <= 4
-               || i == 0 || i == board_size-1
-               || j == 0 || j == board_size-1)) {
-         if (k < 4) {
-           values[POS(i, j)] += contribution;
-           break;
-         }
-         else {
-           if (BOARD(i+di, j) == EMPTY || countlib(POS(i+di, j)) <= 2
-               || BOARD(i, j+dj) == EMPTY || countlib(POS(i, j+dj)) <= 2)
-             values[POS(i, j)] += 0.5 * contribution;
-           break;
-         }
+  int pos;
+  int k;
+  ASSERT1(IS_STONE(board[dr]), dr);
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (board[pos] != EMPTY)
+      continue;
+    for (k = 0; k < 8; k++) {
+      int pos2 = pos + delta[k];
+      if (IS_STONE(board[pos2])
+         && (is_same_dragon(pos2, dr)
+             || (are_neighbor_dragons(pos2, dr)
+                 && board[pos2] == board[dr]))
+         && (countlib(pos2) <= 4
+             || is_edge_vertex(pos))) {
+       if (k < 4) {
+         if (is_same_dragon(pos2, dr))
+           values[pos] += contribution;
+         else
+           values[pos] += 0.5 * contribution;
+         break;
+       }
+       else {
+         /* If pos2 = SOUTHWEST(pos), this construction makes
+          *    pos3 = SOUTH(pos) and
+          *    pos4 = WEST(pos)
+          * and corresponding for all other diagonal movements.
+          */
+         int pos3 = pos + delta[k % 4];
+         int pos4 = pos + delta[(k+1) % 4];
+         if (board[pos3] == EMPTY || countlib(pos3) <= 2
+             || board[pos4] == EMPTY || countlib(pos4) <= 2)
+           values[pos] += 0.5 * contribution;
+         break;
        }
       }
     }
+    /* If not close to the dragon, but within the active area, give
+     * negative hotspot contribution.
+     */
+    if (k == 8 && active_board[pos] == EMPTY) {
+      values[pos] -= 0.5 * contribution;
+    }
+  }
 }
   
 
@@ -4912,14 +4941,15 @@
 void
 owl_hotspots(float values[BOARDMAX])
 {
-  int m, n, k, r;
+  int pos;
+  int k, r;
   int libs[MAXLIBS];
   int liberties;
   int sum_tactical_nodes = 0;
 
-  for (m = 0; m < board_size; m++)
-    for (n = 0; n < board_size; n++)
-      values[POS(m, n)] = 0.0;
+  /* Don't bother checking out of board. Set values[] to zero there too. */
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+    values[pos] = 0.0;
   
   /* Compute the total number of tactical nodes for the cached entries. */
   for (k = 0; k < persistent_owl_cache_size; k++)
@@ -4943,15 +4973,19 @@
     case OWL_THREATEN_ATTACK:
     case OWL_DEFEND:
     case OWL_THREATEN_DEFENSE:
-      mark_dragon_hotspot_values(values, entry->apos, contribution);
+      mark_dragon_hotspot_values(values, entry->apos,
+                                contribution, entry->board);
       break;
     case OWL_DOES_DEFEND:
     case OWL_DOES_ATTACK:
-      mark_dragon_hotspot_values(values, entry->bpos, contribution);
+      mark_dragon_hotspot_values(values, entry->bpos,
+                                contribution, entry->board);
       break;
     case OWL_CONNECTION_DEFENDS:
-      mark_dragon_hotspot_values(values, entry->bpos, contribution);
-      mark_dragon_hotspot_values(values, entry->cpos, contribution);
+      mark_dragon_hotspot_values(values, entry->bpos,
+                                contribution, entry->board);
+      mark_dragon_hotspot_values(values, entry->cpos,
+                                contribution, entry->board);
       break;
     case OWL_SUBSTANTIAL:
       /* Only consider the liberties of (apos). */