Re: [gnugo-devel] Semeai

[Gunnar Farneback]

Dan wrote:
> After a lot of mucking around I convinced myself that
> the Hashnode next pointer was getting trashed and it seemed
> the function hashtable_partially_clear() itself was
> responsible. So I changed one line of that function to:
> 
>     hashtable_unlink_closed_results(node, 
>                             (1 << OWL_ATTACK |
>                             1 << OWL_DEFEND  |
>                             1 << SEMEAI), 3, statistics);
> and the crashes seem to have stopped. I'm most of the
> way through the third regression batch (running strategy3.tst
> right now).

This doesn't make all that much sense to me. It would be valuable to
know exactly where the pointer got trashed.

> This does not mean that we can take out the calls to 
> reading_cache_clear() entirely. It's still needed because
> apos does not determine the semeai.

So why don't we implement support for two strings then? The
connection reading will need it too.

The patch below revises the implementation of the cache code so that
two strings and two results can be handled. It also fixes two minor
bugs and simplifies the code to lookup the cache in reading.c and
owl.c.

In this block, the call to rr_set_compressed_data() is redundant since
get_read_result() already has set up all data:

  if ((stackp <= depth) && (hashflags & HASH_FIND_DEFENSE)) {
    found_read_result = get_read_result(FIND_DEFENSE, komaster, kom_pos, 
                                        &str, &read_result);
    if (found_read_result) {
      TRACE_CACHED_RESULT(*read_result);
      if (rr_get_result(*read_result) != 0)
        if (move)
          *move = rr_get_move(*read_result);

      SGFTRACE(rr_get_move(*read_result),
               rr_get_result(*read_result), "cached");
      return rr_get_result(*read_result);
    }

    /* This data should always be recorded. */
    if (read_result) {
      rr_set_compressed_data(*read_result, FIND_DEFENSE, 
                             komaster, kom_pos, str, stackp);
    }
  }
  else
    read_result = NULL;

This patch conflicts with Dan's semeai_1_23.1a patch, but it shouldn't
be hard to reimplement the READ_RETURN_SEMEAI() macro.

Ah, looking once more at that patch I see a bug:

>  #define OWL_ATTACK      8
>  #define OWL_DEFEND      9
> +#define SEMEAI         10
>  
>  #define MAX_ROUTINE     OWL_DEFEND
>  #define NUM_ROUTINES    (MAX_ROUTINE+1)

It's necessary to also bump MAX_ROUTINE. Otherwise there may be
indexing out of bounds and noone knows what might happen. I've added
an assertion in hashtable_unlink_closed_results() to detect this
problem. It wouldn't surprise me if this was in fact the cause for the
crashes.

I've tested the patch below with reading.tst and owl.tst without
finding any problems. I'll let the whole regression suite run for a
while before I add it to CVS.

/Gunnar

Index: engine/cache.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.c,v
retrieving revision 1.7
diff -u -r1.7 cache.c
--- engine/cache.c      15 Dec 2001 14:35:26 -0000      1.7
+++ engine/cache.c      26 Jan 2002 15:10:51 -0000
@@ -41,10 +41,10 @@
 static Hashnode *hashtable_search(Hashtable *table, Hash_data *hd);
 
 static Read_result *hashnode_search(Hashnode *node, int routine, int komaster,
-                                   int kom_pos, int str);
+                                   int kom_pos, int str1, int str2);
 static Read_result *hashnode_new_result(Hashtable *table, Hashnode *node, 
                                        int routine, int komaster,
-                                       int kom_pos, int move);
+                                       int kom_pos, int str1, int str2);
 
 static void hashtable_unlink_closed_results(Hashnode *node, 
                                            int exclusions, 
@@ -52,7 +52,7 @@
                                            int statistics[][20]);
 static void hashtable_partially_clear(Hashtable *table);
 static int do_get_read_result(int routine, int komaster, int kom_pos,
-                             int *str, Read_result **read_result);
+                             int str1, int str2, Read_result **read_result);
 
 /*
  * Dump an ASCII representation of the contents of a Read_result onto
@@ -281,7 +281,7 @@
 
   /* Mark all read_results as free. */
   for (i = 0; i < table->num_results; i++)
-    table->all_results[i].result_ri_rj = 0;
+    table->all_results[i].data2 = 0;
   
   /* Mark all nodes as free. */
   for (i = 0; i < table->num_nodes; i++)
@@ -306,11 +306,15 @@
   
   while (current_result != NULL) {
     int stackp;
+    int routine;
 
     stackp = rr_get_stackp(*current_result);
     if (stackp > 19)
       stackp = 19;
-    statistics[rr_get_routine(*current_result)][stackp]++;
+
+    routine = rr_get_routine(*current_result);
+    gg_assert(routine >= 0 && routine < NUM_ROUTINES);
+    statistics[routine][stackp]++;
 
     if (rr_get_status(*current_result) == 2
        && ((1 << rr_get_routine(*current_result)) & exclusions) == 0
@@ -319,7 +323,7 @@
        node->results = current_result->next;
       else
        previous_result->next = current_result->next;
-      current_result->result_ri_rj = 0;
+      current_result->data2 = 0;
     }
     else
       previous_result = current_result;
@@ -509,15 +513,18 @@
 
 static Read_result *
 hashnode_search(Hashnode *node, int routine, int komaster, int kom_pos,
-               int str)
+               int str1, int str2)
 {
   Read_result *result;
-  unsigned int search_for;
+  unsigned int search_for1;
+  unsigned int search_for2;
 
-  search_for = rr_compress_data(rr, routine, komaster, kom_pos, str, stackp);
+  search_for1 = rr_input_data1(routine, komaster, kom_pos, str1, stackp);
+  search_for2 = rr_input_data2(str2);
 
   for (result = node->results; result != NULL; result = result->next) {
-    if (result->compressed_data == search_for)
+    if (result->data1 == search_for1
+       && (result->data2 & RR_INPUT_DATA2) == search_for2)
       break;
     }
 
@@ -534,7 +541,7 @@
 
 static Read_result *
 hashnode_new_result(Hashtable *table, Hashnode *node, int routine, 
-                   int komaster, int kom_pos, int str)
+                   int komaster, int kom_pos, int str1, int str2)
 {
   Read_result *result;
 
@@ -554,13 +561,9 @@
   result->next = node->results;
   node->results = result;
 
-  /* Now, put the routine number into it. */
-  result->compressed_data = rr_compress_data(rr, routine, komaster,
-                                            kom_pos, str, stackp);
+  /* Now, put the input data into it. This also sets status to open. */
+  rr_set_input_data2(*result, routine, komaster, kom_pos, str1, str2, stackp);
 
-  /* And set the status to open. */
-  result->result_ri_rj = 1 << 24;
-  
   stats.read_result_entered++;
   return result;
 
@@ -628,18 +631,20 @@
    */
   *str = find_origin(*str);
   
-  result = do_get_read_result(routine, komaster, kom_pos, str, read_result);
+  result = do_get_read_result(routine, komaster, kom_pos, *str, NO_MOVE,
+                             read_result);
   if (*read_result == NULL) {
     /* Clean up the hashtable and try once more. */
     hashtable_partially_clear(movehash);
-    result = do_get_read_result(routine, komaster, kom_pos, str, read_result);
+    result = do_get_read_result(routine, komaster, kom_pos, *str, NO_MOVE,
+                               read_result);
   }
   return result;
 }
 
 static int
 do_get_read_result(int routine, int komaster, int kom_pos,
-                  int *str, Read_result **read_result)
+                  int str1, int str2, Read_result **read_result)
 {
   Hashnode *hashnode;
   int retval;
@@ -690,7 +695,7 @@
 
     /* We found it!  Now see if we can find a previous result. */
     *read_result = hashnode_search(hashnode, routine, komaster, kom_pos,
-                                  *str);
+                                  str1, str2);
 
     if (*read_result != NULL) {
       stats.read_result_hits++;
@@ -698,11 +703,11 @@
     }
     else {
       DEBUG(DEBUG_READING_CACHE,
-           "...but no previous result for routine %d and (%1m)...",
-           routine, *str);
+           "...but no previous result for routine %d and (%1m, %1m)...",
+           routine, str1, str2);
 
       *read_result = hashnode_new_result(movehash, hashnode, routine,
-                                        komaster, kom_pos, *str);
+                                        komaster, kom_pos, str1, str2);
       
       if (*read_result == NULL)
        DEBUG(DEBUG_READING_CACHE,
Index: engine/cache.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.h,v
retrieving revision 1.6
diff -u -r1.6 cache.h
--- engine/cache.h      11 Oct 2001 15:39:37 -0000      1.6
+++ engine/cache.h      26 Jan 2002 15:10:51 -0000
@@ -51,55 +51,83 @@
  * identify repeated positions in the reading, in particular local
  * double or triple kos.
  *
- * The compressed_data field packs into 32 bits the following
+ * The data1 field packs into 32 bits the following
  * fields:
  *
- * komaster: 2 bits (EMPTY, BLACK, WHITE, or GRAY)
+ * komaster:  2 bits (EMPTY, BLACK, WHITE, or GRAY)
  * kom_pos : 10 bits (allows MAX_BOARD up to 31)
- * routine : 4 bits (currently 10 different choices)
- * str     : 10 bits
- * stackp  : 5 bits
+ * routine :  4 bits (currently 10 different choices)
+ * str1    : 10 bits
+ * stackp  :  5 bits
+ *
+ * The data2 field packs into 32 bits the following
+ * fields:
+ *
+ * status :   2 bits (0 free, 1 open, 2 closed)
+ * result1:   4 bits
+ * result2:   4 bits
+ * move   :  10 bits
+ * str2   :  10 bits
  */
 
 typedef struct read_result_t {
-  unsigned int compressed_data;        
-
-  int result_ri_rj;            /* ...then this was the result. */
-  /*
-  status:  8 bits        // 0 free, 1 open, 2 closed
-  result:  8 bits
-  move  : 16 bits
-  */
+  unsigned int data1;  
+  unsigned int data2;
 
   struct read_result_t *next;
 } Read_result;
 
+/* Bit mask for the input bits in the data2 field. */
+#define RR_INPUT_DATA2 0x3ff
 
-/* Get parts of a Read_result identifying the routine and position. */
-#define rr_get_komaster(rr)   (((rr).compressed_data  >> 29) & 0x03)
-#define rr_get_kom_pos(rr)    (((rr).compressed_data  >> 19) & 0x2ff)
-#define rr_get_routine(rr)    (((rr).compressed_data  >> 15) & 0x0f)
-#define rr_get_str(rr)        (((rr).compressed_data  >>  5) & 0x2ff)
-#define rr_get_stackp(rr)     (((rr).compressed_data  >>  0) & 0x1f)
+/* Get parts of a Read_result identifying the input data. */
+#define rr_get_komaster(rr)   (((rr).data1  >> 29) & 0x03)
+#define rr_get_kom_pos(rr)    (((rr).data1  >> 19) & 0x3ff)
+#define rr_get_routine(rr)    (((rr).data1  >> 15) & 0x0f)
+#define rr_get_str1(rr)       (((rr).data1  >>  5) & 0x3ff)
+#define rr_get_stackp(rr)     (((rr).data1  >>  0) & 0x1f)
+#define rr_get_str2(rr)       (((rr).data2  >>  0) & 0x3ff)
+#define rr_get_str(rr)        rr_get_str1(rr)
 
 /* Set corresponding parts. */
-#define rr_compress_data(rr, routine, komaster, kom_pos, str, stackp) \
+#define rr_input_data1(routine, komaster, kom_pos, str1, stackp) \
        (((((((((komaster) << 10) | (kom_pos)) << 4) \
-         | (routine)) << 10) | (str)) << 5) | stackp);
+         | (routine)) << 10) | (str1)) << 5) | stackp);
+#define rr_input_data2(str2) (str2) \
 
-#define rr_set_compressed_data(rr, routine, komaster, kom_pos, str, stackp) \
-       (rr).compressed_data \
-       = rr_compress_data(rr, routine, komaster, kom_pos, str, stackp)
+/* Set input data fields and at the same time set status to open. */
+#define rr_set_input_data(rr, routine, komaster, kom_pos, str, stackp) \
+       do { \
+         (rr).data1 = rr_input_data1(routine, komaster, kom_pos, str, stackp);\
+         (rr).data2 = (((rr).data2 & ~0x300003ff) | (1 << 28));\
+       } while (0)
+
+/* Variation for two distinct strings. */
+#define rr_set_input_data2(rr, routine, komaster, kom_pos, str1, str2, stackp)\
+       do { \
+         (rr).data1 = rr_input_data1(routine, komaster, kom_pos, \
+                                     str1, stackp); \
+         (rr).data2 = (((rr).data2 & ~0x3ff) | (1 << 28) \
+                       | rr_input_data2(str2)); \
+       } while (0)
 
 /* Get parts of a Read_result constituting the result of a search. */
-#define rr_get_status(rr)      (((rr).result_ri_rj >> 24) & 0xff)
-#define rr_get_result(rr)      (((rr).result_ri_rj >> 16) & 0xff)
-#define rr_get_move(rr)        (((rr).result_ri_rj >>  0) & 0xffff)
+#define rr_get_status(rr)      (((rr).data2 >> 28) & 0x03)
+#define rr_get_result1(rr)     (((rr).data2 >> 24) & 0x0f)
+#define rr_get_result2(rr)     (((rr).data2 >> 20) & 0x0f)
+#define rr_get_move(rr)        (((rr).data2 >> 10) & 0x3ff)
+#define rr_get_result(rr)      rr_get_result1(rr)
 
 /* Set corresponding parts. */
-#define rr_set_result_ri_rj(rr, result, move) \
-       (rr).result_ri_rj \
-           = (2 << 24 | (((result) & 0xff) << 16) | ((move) & 0xffff))
+#define rr_set_result_move(rr, result, move) \
+       (rr).data2 = (((rr).data2 & 0x3ff) \
+          | (2 << 28) | (((result) & 0x0f) << 24) | (((move) & 0x3ff) << 10))
+
+/* Variation with two results. */
+#define rr_set_result_move2(rr, result1, result2, move) \
+       (rr).data2 = (((rr).data2 & 0x3ff) \
+          | (2 << 28) | (((result) & 0x0f) << 24) | (((move) & 0x3ff) << 10))
+
 
 /*
  * The hash table consists of hash nodes.  Each hash node consists of
@@ -229,7 +257,7 @@
 #define READ_RETURN0(read_result) \
   do { \
     if (read_result) { \
-      rr_set_result_ri_rj(*(read_result), 0, 0); \
+      rr_set_result_move(*(read_result), 0, 0); \
     } \
     return 0; \
   } while (0)
@@ -238,7 +266,7 @@
   do { \
     if ((value) != 0 && (point) != 0) *(point) = (move); \
     if (read_result) { \
-      rr_set_result_ri_rj(*(read_result), (value), (move)); \
+      rr_set_result_move(*(read_result), (value), (move)); \
     } \
     return (value); \
   } while (0)
@@ -248,7 +276,7 @@
 #define READ_RETURN0(read_result) \
   do { \
     if (read_result) { \
-      rr_set_result_ri_rj(*(read_result), 0, 0); \
+      rr_set_result_move(*(read_result), 0, 0); \
     } \
     gprintf("%o%s %1m %d 0 0 0 ", read_function_name, q, stackp); \
     dump_stack(); \
@@ -259,7 +287,7 @@
   do { \
     if ((value) != 0 && (point) != 0) *(point) = (move); \
     if (read_result) { \
-      rr_set_result_ri_rj(*(read_result), (value), (move)); \
+      rr_set_result_move(*(read_result), (value), (move)); \
     } \
     gprintf("%o%s %1m %d %d %d ", read_function_name, q, stackp, \
            (value), (move)); \
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.52
diff -u -r1.52 owl.c
--- engine/owl.c        20 Jan 2002 15:08:06 -0000      1.52
+++ engine/owl.c        26 Jan 2002 15:10:53 -0000
@@ -1051,7 +1051,7 @@
   int move_cutoff;
   int dcode;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
   int this_variation_number = count_variations - 1;
   
   SETUP_TRACE_INFO("owl_attack", str);
@@ -1075,15 +1075,7 @@
               "cached");
       return rr_get_result(*read_result);
     }
-
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, OWL_ATTACK, komaster, kom_pos,
-                            str, stackp);
-    }
   }
-  else
-    read_result = NULL;
 
   /* If we're deeper than owl_reading_depth, assume the dragon has
    * managed to escape.
@@ -1641,7 +1633,7 @@
   int move_cutoff;
   int acode;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
   int this_variation_number = count_variations - 1;
   
   SETUP_TRACE_INFO("owl_defend", str);
@@ -1665,14 +1657,7 @@
               "cached");
       return rr_get_result(*read_result);
     }
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, OWL_DEFEND, 
-                            komaster, kom_pos, str, stackp);
-    }
   }
-  else
-    read_result = NULL;
 
   /* In order to get a defense move even if we seem to already have
    * escaped and to reduce the impact of overestimated escape
Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.44
diff -u -r1.44 reading.c
--- engine/reading.c    10 Jan 2002 08:14:31 -0000      1.44
+++ engine/reading.c    26 Jan 2002 15:10:55 -0000
@@ -962,7 +962,7 @@
   int dcode = 0;
   int liberties;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
   
   SETUP_TRACE_INFO("find_defense", str);
   
@@ -998,15 +998,7 @@
               rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
-
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, FIND_DEFENSE, 
-                            komaster, kom_pos, str, stackp);
-    }
   }
-  else
-    read_result = NULL;
 
   if (liberties == 1)
     dcode = defend1(str, &xpos, komaster, kom_pos);
@@ -1059,7 +1051,7 @@
   int liberties;
   int k;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
 
   SETUP_TRACE_INFO("defend1", str);
   reading_node_counter++;
@@ -1081,15 +1073,7 @@
               rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
-
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, DEFEND1, komaster, kom_pos,
-                            str, stackp);
-    }
   }
-  else
-    read_result = NULL;
 
   /* lib will be the liberty of the string. */
   liberties = findlib(str, 1, &lib);
@@ -1207,7 +1191,7 @@
   int r;
   int s;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
 
   SETUP_TRACE_INFO("defend2", str);
   reading_node_counter++;
@@ -1232,15 +1216,7 @@
               rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
-
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, DEFEND2, komaster, kom_pos,
-                            str, stackp);
-    }
   }
-  else
-    read_result = NULL;
 
   liberties = findlib(str, 2, libs);
   ASSERT1(liberties == 2, str);
@@ -1525,7 +1501,7 @@
   int bc;
   int k;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
 
   SETUP_TRACE_INFO("defend3", str);
   reading_node_counter++;
@@ -1549,15 +1525,7 @@
               rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
-
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, DEFEND3, komaster, kom_pos, 
-                            str, stackp);
-    }
   }
-  else
-    read_result = NULL;
 
   liberties = findlib(str, 3, libs);
   ASSERT1(liberties == 3, str);
@@ -1869,7 +1837,7 @@
   int savecode = 0;
   int k;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
   
   SETUP_TRACE_INFO("defend4", str);
   reading_node_counter++;
@@ -1893,15 +1861,7 @@
               rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
-
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, DEFEND4, komaster, kom_pos, 
-                            str, stackp);
-    }
   }
-  else
-    read_result = NULL;
 
   liberties = findlib(str, 4, libs);
   ASSERT1(liberties == 4, str);
@@ -2671,7 +2631,7 @@
   int libs;
   int result = 0;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
 
   SETUP_TRACE_INFO("attack", str);
 
@@ -2702,15 +2662,7 @@
               rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
-
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, ATTACK, komaster, kom_pos, 
-                            str, stackp);
-    }
   }
-  else
-    read_result = NULL;
 
   /* Treat the attack differently depending on how many liberties the 
      string at (str) has. */
@@ -2925,7 +2877,7 @@
   int num_moves = 0;
   int adjacent_liberties = 0;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
 
   SETUP_TRACE_INFO("attack2", str);
   reading_node_counter++;
@@ -2949,15 +2901,7 @@
               rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
-
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, ATTACK2, komaster, kom_pos, 
-                            str, stackp);
-    }
   }
-  else
-    read_result = NULL;
 
   /* The attack may fail if a boundary string is in atari and cannot 
    * be defended.  First we must try defending such a string. 
@@ -3222,7 +3166,7 @@
   int savemove = 0;
   int savecode = 0;
   int found_read_result;
-  Read_result *read_result;
+  Read_result *read_result = NULL;
   
   SETUP_TRACE_INFO("attack3", str);
   reading_node_counter++;
@@ -3241,15 +3185,7 @@
               rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
-    
-    /* This data should always be recorded. */
-    if (read_result) {
-      rr_set_compressed_data(*read_result, ATTACK3, komaster, kom_pos, 
-                            str, stackp);
-    }
   }
-  else
-    read_result = NULL;
   
   if (stackp > depth) {
     SGFTRACE(0, 0, "stackp > depth");