gnugo-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[gnugo-devel] caching for break-in reading


From: Arend Bayer
Subject: [gnugo-devel] caching for break-in reading
Date: Tue, 3 Jun 2003 18:13:28 +0200 (CEST)


- new helper functions goal_to_hashvalue(), xor_hashvalues()
- new function get_read_result_hash_modified to enable calling functions
  to use a modified hash value
- results for recursive_break() and recursive_block() now get cached

The tricky part is that the fields str1 and str2 in the read result do
not suffice to store the goal[] array. However, as the likelyhood of
hash collisions is extremely small for these functions (as they are by some
magnitudes less frequent than do_attack etc.), I decided to store this
information in the hash value instead. So at the beginning, the goal[]
array gets assigned a hash value, and this is persistenly used throughout
the search tree to modify the hash value (with an xor).

In principle, this machinery could also be used by owl to store the goal,
etc.

Arend

Index: engine/cache.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.c,v
retrieving revision 1.23
diff -u -p -r1.23 cache.c
--- engine/cache.c      22 Apr 2003 02:48:04 -0000      1.23
+++ engine/cache.c      3 Jun 2003 16:09:07 -0000
@@ -56,7 +56,8 @@ static void hashnode_unlink_closed_resul
                                           int statistics[][20]);
 static void hashtable_partially_clear(Hashtable *table);
 static int do_get_read_result(int routine, int komaster, int kom_pos,
-                             int str1, int str2, Read_result **read_result);
+                             int str1, int str2, Read_result **read_result,
+                             Hash_data *hashmodifier);


 /*
@@ -662,6 +663,27 @@ reading_cache_clear()
   hashtable_clear(movehash);
 }

+int
+get_read_result_hash_modified(int routine, int komaster, int kom_pos,
+                             int *str, Hash_data *hashmodifier,
+                             Read_result **read_result)
+{
+  /* Only store the result if stackp <= depth. Above that, there
+   * is no branching, so we won't gain anything.
+   */
+  if (stackp > depth) {
+    *read_result = NULL;
+    return 0;
+  }
+
+  /* Find the origin of the string in order to make the caching of read
+   * results work better.
+   */
+  *str = find_origin(*str);
+
+  return do_get_read_result(routine, komaster, kom_pos, *str, NO_MOVE,
+                           read_result, hashmodifier);
+}

 /*
  * Return a Read_result for the current position, routine and location.
@@ -685,7 +707,7 @@ get_read_result(int routine, int komaste
   *str = find_origin(*str);

   return do_get_read_result(routine, komaster, kom_pos, *str, NO_MOVE,
-                           read_result);
+                           read_result, NULL);
 }


@@ -711,18 +733,20 @@ get_read_result2(int routine, int komast
   *str2 = find_origin(*str2);

   return do_get_read_result(routine, komaster, kom_pos, *str1, *str2,
-                           read_result);
+                           read_result, NULL);
 }


 static int
 do_get_read_result(int routine, int komaster, int kom_pos,
-                  int str1, int str2, Read_result **read_result)
+                  int str1, int str2, Read_result **read_result,
+                  Hash_data *hashmodifier)
 {
   Hashnode *node;
   unsigned int data1 = rr_input_data1(routine, komaster, kom_pos,
                                      str1, depth - stackp);
   unsigned int data2 = rr_input_data2(str2);
+  Hash_data modified_hash;

 #if CHECK_HASHING
   Hash_data    key;
@@ -737,8 +761,13 @@ do_get_read_result(int routine, int koma

 #endif /* CHECK_HASHING */

+  if (hashmodifier)
+    modified_hash = xor_hashvalues(&hashdata, hashmodifier);
+  else
+    modified_hash = hashdata;
+
   /* First try to look this position up in the table. */
-  node = hashtable_search(movehash, &hashdata);
+  node = hashtable_search(movehash, &modified_hash);
   if (node != NULL) {
     Read_result *result;

@@ -758,10 +787,10 @@ do_get_read_result(int routine, int koma
          routine, str1, str2);
   }
   else {
-    node = hashtable_enter_position(movehash, &hashdata);
+    node = hashtable_enter_position(movehash, &modified_hash);
     if (node) {
       DEBUG(DEBUG_READING_CACHE, "Created position %H in the hash table...\n",
-           (unsigned long) hashdata.hashval);
+           (unsigned long) modified_hash.hashval);
     }
     else {
       DEBUG(DEBUG_READING_CACHE, "Unable to clean up the hash table!\n");
Index: engine/cache.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.h,v
retrieving revision 1.28
diff -u -p -r1.28 cache.h
--- engine/cache.h      22 Apr 2003 02:48:04 -0000      1.28
+++ engine/cache.h      3 Jun 2003 16:09:08 -0000
@@ -255,6 +255,9 @@ void sgf_trace_semeai(const char *func,

 int get_read_result(int routine, int komaster, int kom_pos,
                    int *str, Read_result **read_result);
+int get_read_result_hash_modified(int routine, int komaster, int kom_pos,
+                                 int *str, Hash_data *hash_modifier,
+                                 Read_result **read_result);
 int get_read_result2(int routine, int komaster, int kom_pos,
                     int *str1, int *str2, Read_result **read_result);

@@ -388,7 +391,10 @@ int get_read_result2(int routine, int ko
 #define CONNECT         5
 #define DISCONNECT      6

-#define MAX_ROUTINE     DISCONNECT
+#define BREAK_IN       7
+#define BLOCK_OFF      8
+
+#define MAX_ROUTINE     BLOCK_OFF
 #define NUM_ROUTINES    (MAX_ROUTINE + 1)


Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.95
diff -u -p -r1.95 gnugo.h
--- engine/gnugo.h      2 Jun 2003 23:49:47 -0000       1.95
+++ engine/gnugo.h      3 Jun 2003 16:09:09 -0000
@@ -255,11 +255,14 @@ extern int output_flags;       /* amount
 #define HASH_SEMEAI       0x0400
 #define HASH_CONNECT      0x0800
 #define HASH_DISCONNECT   0x1000
+#define HASH_BREAK_IN    0x2000
+#define HASH_BLOCK_OFF   0x4000
 #define HASH_NOTHING      0
 #define HASH_ALL          0xffff
 #define HASH_DEFAULT      (HASH_ATTACK | HASH_FIND_DEFENSE\
                           | HASH_OWL_ATTACK | HASH_OWL_DEFEND | HASH_SEMEAI\
-                           | HASH_CONNECT | HASH_DISCONNECT)
+                           | HASH_CONNECT | HASH_DISCONNECT\
+                          | HASH_BREAK_IN | HASH_BLOCK_OFF)

 extern int debug;              /* debug flags */
 extern int hashflags;          /* hash flags */
Index: engine/hash.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.c,v
retrieving revision 1.14
diff -u -p -r1.14 hash.c
--- engine/hash.c       2 Jan 2003 00:23:28 -0000       1.14
+++ engine/hash.c       3 Jun 2003 16:09:09 -0000
@@ -383,7 +383,7 @@ hashdata_compare(Hash_data *hd1, Hash_da
   for (i = 0; i < NUM_HASHVALUES; i++)
     if (hd1->hashval[i] != hd2->hashval[i])
       rc = 2;
-  if ( rc == 2 && i > 0)
+  if (rc == 2 && i > 0)
     stats.hash_collisions++;

 #if FULL_POSITION_IN_HASH
@@ -392,6 +392,38 @@ hashdata_compare(Hash_data *hd1, Hash_da
 #endif

   return rc;
+}
+
+/* Compute hash value to identify the goal area. */
+Hash_data
+goal_to_hashvalue(char *goal)
+{
+  int i, pos;
+  Hash_data return_value;
+  for (i = 0; i < NUM_HASHVALUES; i++)
+    return_value.hashval[i] = 0;
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+    if (ON_BOARD(pos) && goal[pos])
+      for (i = 0; i < NUM_HASHVALUES; i++)
+       return_value.hashval[i] += white_hash[pos][i] + black_hash[pos][i];
+  return return_value;
+}
+
+/* Returns an XOR of the two hash values. The full board position is copied
+ * over from hash1 if FULL_POSITION_IN_HASH is set.
+ */
+Hash_data
+xor_hashvalues(Hash_data *hash1, Hash_data *hash2)
+{
+  int i;
+  Hash_data return_value;
+
+  for (i = 0; i < NUM_HASHVALUES; i++)
+    return_value.hashval[i] = hash1->hashval[i] ^ hash2->hashval[i];
+#if FULL_POSITION_IN_HASH
+  return_value.hashpos = hash1->hashpos;
+#endif
+  return return_value;
 }


Index: engine/hash.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.h,v
retrieving revision 1.9
diff -u -p -r1.9 hash.h
--- engine/hash.h       2 Jan 2003 00:23:28 -0000       1.9
+++ engine/hash.h       3 Jun 2003 16:09:09 -0000
@@ -133,6 +133,8 @@ typedef struct {
 #endif
 } Hash_data;

+Hash_data xor_hashvalues(Hash_data *key1, Hash_data *key2);
+Hash_data goal_to_hashvalue(char *goal);

 void hash_init(void);
 #if FULL_POSITION_IN_HASH
@@ -147,6 +149,7 @@ void hashdata_invert_stone(Hash_data *hd
 void hashdata_set_tomove(Hash_data *hd, int to_move);

 int hashdata_diff_dump(Hash_data *key1, Hash_data *key2);
+

 #endif

Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.176
diff -u -p -r1.176 liberty.h
--- engine/liberty.h    2 Jun 2003 23:49:47 -0000       1.176
+++ engine/liberty.h    3 Jun 2003 16:09:11 -0000
@@ -40,7 +40,7 @@
 /* ================================================================ */


-/* A few variables below are of types defined in hash.h. */
+/* We need the defintion of type Hash_data here. */
 #include "hash.h"

 /* Other modules get read-only access to this variable. */
Index: engine/printutils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/printutils.c,v
retrieving revision 1.36
diff -u -p -r1.36 printutils.c
--- engine/printutils.c 27 May 2003 08:48:24 -0000      1.36
+++ engine/printutils.c 3 Jun 2003 16:09:11 -0000
@@ -419,6 +419,10 @@ routine_to_string(int routine)
     return "CONNECT";
   else if (routine == DISCONNECT)
     return "DISCONNECT";
+  else if (routine == BREAK_IN)
+    return "BREAK_IN";
+  else if (routine == BLOCK_OFF)
+    return "BLOCK_OFF";
   else
     return "ERROR";
 }
Index: engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.49
diff -u -p -r1.49 readconnect.c
--- engine/readconnect.c        2 Jun 2003 23:49:48 -0000       1.49
+++ engine/readconnect.c        3 Jun 2003 16:09:14 -0000
@@ -48,9 +48,11 @@ static int recursive_connect2(int str1,
 static int recursive_disconnect2(int str1, int str2, int *move,
                                 int komaster, int kom_pos, int has_passed);
 static int recursive_break(int str, char goal[BOARDMAX], int *move,
-                          int komaster, int kom_pos, int has_passed);
+                          int komaster, int kom_pos, int has_passed,
+                          Hash_data *goal_hash);
 static int recursive_block(int str, char goal[BOARDMAX], int *move,
-                          int komaster, int kom_pos, int has_passed);
+                          int komaster, int kom_pos, int has_passed,
+                          Hash_data *goal_hash);

 static int add_array(int *array, int elt);
 static int element_array(int *array,int elt);
@@ -2632,13 +2634,14 @@ find_break_moves(int str, char goal[BOAR
 /* These depth values are set relative to the standard readconnnect depth
  * limits at each call of break_in()/block_off().
  * */
-int break_in_node_limit;
-int break_in_depth;
+static int break_in_node_limit;
+static int break_in_depth;

 /* Can (str) connect to goal[] if the other color moves first? */
 static int
 recursive_break(int str, char goal[BOARDMAX], int *move,
-               int komaster, int kom_pos, int has_passed)
+               int komaster, int kom_pos, int has_passed,
+               Hash_data *goal_hash)
 {
   int color = board[str];
   int moves[MAX_MOVES];
@@ -2648,9 +2651,7 @@ recursive_break(int str, char goal[BOARD
   int xpos;
   int savemove = NO_MOVE;
   int savecode = 0;
-#if 0
   int found_read_result;
-#endif
   Read_result *read_result = NULL;

   SETUP_TRACE_INFO("recursive_break", str);
@@ -2676,24 +2677,23 @@ recursive_break(int str, char goal[BOARD
     return 0;
   }

-#if 0
   if (stackp <= depth
-      && (hashflags & HASH_CONNECT)
+      && (hashflags & HASH_BREAK_IN)
       && !has_passed) {
-    found_read_result = get_read_result2(CONNECT, komaster, kom_pos,
-                                        &str1, &str2, &read_result);
+    found_read_result
+      = get_read_result_hash_modified(BREAK_IN, komaster, kom_pos,
+                                     &str, goal_hash, &read_result);
     if (found_read_result) {
-      TRACE_CACHED_RESULT2(*read_result);
+      TRACE_CACHED_RESULT(*read_result);
       if (rr_get_result(*read_result) != 0)
        if (move)
          *move = rr_get_move(*read_result);

-      SGFTRACE2(rr_get_move(*read_result),
-               rr_get_result(*read_result), "cached");
+      SGFTRACE(rr_get_move(*read_result),
+              rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
   }
-#endif

 #if 0
   if (trivial_connection(str1, str2, &xpos) == WIN) {
@@ -2717,7 +2717,7 @@ recursive_break(int str, char goal[BOARD
       if (!ko_move) {
        int acode = recursive_block(str, goal, NULL,
                                    new_komaster, new_kom_pos,
-                                   has_passed);
+                                   has_passed, goal_hash);
        popgo();
        if (acode == 0) {
          SGFTRACE(xpos, WIN, "break effective");
@@ -2730,7 +2730,7 @@ recursive_break(int str, char goal[BOARD
       }
       else {
        if (recursive_block(str, goal, NULL, new_komaster, new_kom_pos,
-                           has_passed) != WIN) {
+                           has_passed, goal_hash) != WIN) {
          savemove = xpos;
          savecode = KO_B;
        }
@@ -2757,7 +2757,8 @@ recursive_break(int str, char goal[BOARD
 /* Can (str) connect to goal[] if the other color moves first? */
 static int
 recursive_block(int str, char goal[BOARDMAX], int *move,
-               int komaster, int kom_pos, int has_passed)
+               int komaster, int kom_pos, int has_passed,
+               Hash_data *goal_hash)
 {
   int color = board[str];
   int other = OTHER_COLOR(color);
@@ -2768,9 +2769,7 @@ recursive_block(int str, char goal[BOARD
   int xpos;
   int savemove = NO_MOVE;
   int savecode = 0;
-#if 0
   int found_read_result;
-#endif
   Read_result *read_result = NULL;
   SETUP_TRACE_INFO("recursive_block", str);

@@ -2802,22 +2801,21 @@ recursive_block(int str, char goal[BOARD
     return WIN;
   }

-#if 0
-  if ((stackp <= depth) && (hashflags & HASH_DISCONNECT)) {
-    found_read_result = get_read_result2(DISCONNECT, komaster, kom_pos,
-                                        &str1, &str2, &read_result);
+  if ((stackp <= depth) && (hashflags & HASH_BLOCK_OFF)) {
+    found_read_result
+      = get_read_result_hash_modified(BLOCK_OFF, komaster, kom_pos,
+                                     &str, goal_hash, &read_result);
     if (found_read_result) {
-      TRACE_CACHED_RESULT2(*read_result);
+      TRACE_CACHED_RESULT(*read_result);
       if (rr_get_result(*read_result) != 0)
        if (move)
          *move = rr_get_move(*read_result);

-      SGFTRACE2(rr_get_move(*read_result),
-               rr_get_result(*read_result), "cached");
+      SGFTRACE(rr_get_move(*read_result),
+              rr_get_result(*read_result), "cached");
       return rr_get_result(*read_result);
     }
   }
-#endif

   if (ladder_capture(str, &xpos) == WIN) {
     SGFTRACE(xpos, WIN, "string capturable");
@@ -2838,7 +2836,8 @@ recursive_block(int str, char goal[BOARD
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
       if (!ko_move) {
        int dcode = recursive_break(str, goal, NULL,
-                                   new_komaster, new_kom_pos, has_passed);
+                                   new_komaster, new_kom_pos, has_passed,
+                                   goal_hash);
        popgo();
        if (dcode == 0) {
          SGFTRACE(xpos, WIN, "block effective");
@@ -2851,7 +2850,7 @@ recursive_block(int str, char goal[BOARD
       }
       else {
        if (recursive_break(str, goal, NULL, new_komaster, new_kom_pos,
-                           has_passed) != WIN) {
+                           has_passed, goal_hash) != WIN) {
          savemove = xpos;
          savecode = KO_B;
        }
@@ -2863,7 +2862,8 @@ recursive_block(int str, char goal[BOARD
   if (num_moves == 0
       && distance >= 1.0
       && (has_passed
-         || !recursive_break(str, goal, NULL, komaster, kom_pos, 1))) {
+         || !recursive_break(str, goal, NULL, komaster, kom_pos, 1,
+                             goal_hash))) {
     SGFTRACE(NO_MOVE, WIN, "no move, probably disconnected");
     READ_RETURN(read_result, move, NO_MOVE, WIN);
   }
@@ -2884,7 +2884,7 @@ recursive_block(int str, char goal[BOARD
  * not contain stones), if he gets the first move.
  */
 int
-break_in(int str, char goal [BOARDMAX], int *move)
+break_in(int str, char goal[BOARDMAX], int *move)
 {
   int dummy_move;
   int save_verbose;
@@ -2892,6 +2892,7 @@ break_in(int str, char goal [BOARDMAX],
   int reading_nodes_when_called = get_reading_node_counter();
   double start = 0;
   int tactical_nodes;
+  Hash_data goal_hash = goal_to_hashvalue(goal);

   break_in_node_limit = connection_node_limit / 5;
   break_in_depth = connect_depth2 - 5;
@@ -2911,7 +2912,7 @@ break_in(int str, char goal [BOARDMAX],
     verbose--;
   start = gg_cputime();
   memset(connection_shadow, 0, sizeof(connection_shadow));
-  result = recursive_break(str, goal, move, EMPTY, NO_MOVE, 0);
+  result = recursive_break(str, goal, move, EMPTY, NO_MOVE, 0, &goal_hash);
   verbose = save_verbose;
   tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
   if (0) {
@@ -2943,6 +2944,7 @@ block_off(int str, char goal[BOARDMAX],
   int reading_nodes_when_called = get_reading_node_counter();
   double start = 0;
   int tactical_nodes;
+  Hash_data goal_hash = goal_to_hashvalue(goal);

   if (move == NULL)
     move = &dummy_move;
@@ -2957,7 +2959,8 @@ block_off(int str, char goal[BOARDMAX],
     verbose--;
   start = gg_cputime();
   memset(connection_shadow, 0, sizeof(connection_shadow));
-  result = recursive_block(str, goal, move, EMPTY, NO_MOVE, 0);
+  result = recursive_block(str, goal, move, EMPTY, NO_MOVE, 0,
+                          &goal_hash);
   verbose = save_verbose;
   tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;






reply via email to

[Prev in Thread] Current Thread [Next in Thread]