[gnugo-devel] remove FULL_POSITION_IN_HASH

[Arend Bayer]

While I was trying to convert the break-in reading to the new cache
implementation, I realized just how annoying that would be with the
two competing hash implementations.

To make them more compatible, so that one of them can be easily removed,
I'd suggest to start by removing FULL_POSITION_IN_HASH. I don't think
this switch has ever been enabled since I introduced it 1.5 years ago,
and instead I think it is sufficient if we can easily increase the
number of bits per hash value from 64 to 96 or 128.

Arend


- remove FULL_POSITION_IN_HASH


Index: config.vcin
===================================================================
RCS file: /cvsroot/gnugo/gnugo/config.vcin,v
retrieving revision 1.27
diff -u -p -r1.27 config.vcin
--- config.vcin 27 Jun 2003 04:34:31 -0000      1.27
+++ config.vcin 29 Sep 2003 13:41:25 -0000
@@ -37,9 +37,6 @@
    */
 #define GRID_OPT 1

-/* Hashing scheme. Default scheme 2 (new). */
-#define HASHING_SCHEME 2
-
 /* Oracle. Default not enabled. */
 #define ORACLE 0

@@ -55,7 +52,7 @@
 /* Semeai Variations. 500 default */
 #define SEMEAI_NODE_LIMIT 500

-/* Break-in module. Default not enabled. */
+/* Break-in module. Enabled by default. */
 #define USE_BREAK_IN 1


Index: configure.in
===================================================================
RCS file: /cvsroot/gnugo/gnugo/configure.in,v
retrieving revision 1.94
diff -u -p -r1.94 configure.in
--- configure.in        5 Sep 2003 13:35:23 -0000       1.94
+++ configure.in        29 Sep 2003 13:41:31 -0000
@@ -493,17 +493,6 @@ else
    AC_DEFINE(OWL_THREATS, 0)
 fi

-dnl ------------ Influence -------------------
-
-AH_TEMPLATE([HASHING_SCHEME],
-[Hashing scheme. Default scheme 2 (new).])
-
-if test "$enable_experimental_hashing" = "no" ; then
-   AC_DEFINE(HASHING_SCHEME, 1)
-else
-   AC_DEFINE(HASHING_SCHEME, 2)
-fi
-
 dnl  ----------- special-case use of gcc ---------

 dnl Not sure if we are supposed to be accessing this variable, but...
Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.86
diff -u -p -r1.86 board.c
--- engine/board.c      15 Aug 2003 07:21:22 -0000      1.86
+++ engine/board.c      29 Sep 2003 13:41:34 -0000
@@ -831,12 +831,8 @@ play_move_no_history(int pos, int color,

   /* Check the hash table to see if it corresponds to the cumulative one. */
   hashdata_recalc(&oldkey, board, board_ko_pos);
-#if FULL_POSITION_IN_HASH
-  gg_assert(hashdata_diff_dump(&oldkey, &hashdata) == 0);
-#else
   gg_assert(hashdata_compare(&oldkey, &hashdata) == 0);
 #endif
-#endif

   if (board_ko_pos != NO_MOVE)
     hashdata_invert_ko(&hashdata, board_ko_pos);
@@ -856,12 +852,8 @@ play_move_no_history(int pos, int color,
 #if CHECK_HASHING
     /* Check the hash table to see if it equals the previous one. */
     hashdata_recalc(&oldkey, board, board_ko_pos);
-#if FULL_POSITION_IN_HASH
-    gg_assert(hashdata_diff_dump(&oldkey, &hashdata) == 0);
-#else
     gg_assert(hashdata_compare(&oldkey, &hashdata) == 0);
 #endif
-#endif
   }

   if (update_internals || next_string == MAX_STRINGS)
@@ -1583,7 +1575,7 @@ fastlib(int pos, int color, int ignore_c


 /* Effectively true unless we store full position in hash. */
-#define USE_BOARD_CACHES       (NUM_HASHVALUES <= 4 && !FULL_POSITION_IN_HASH)
+#define USE_BOARD_CACHES       (NUM_HASHVALUES <= 4)

 struct board_cache_entry {
   int threshold;
Index: engine/cache.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.c,v
retrieving revision 1.31
diff -u -p -r1.31 cache.c
--- engine/cache.c      12 Aug 2003 09:15:20 -0000      1.31
+++ engine/cache.c      29 Sep 2003 13:41:35 -0000
@@ -362,9 +362,6 @@ hashnode_dump(Hashnode *node, FILE *outf

   /* Data about the node itself. */
   fprintf(outfile, "Hash value: %lx\n", (unsigned long) node->key.hashval);
-#if FULL_POSITION_IN_HASH
-  hashposition_dump(&(node->key.hashpos), outfile);
-#endif

   for (result = node->results; result != NULL; result = result->next) {
     read_result_dump(result, outfile);
@@ -802,12 +799,7 @@ hashtable_search(Hashtable *table, Hash_
        break;
       }
     if (i >= NUM_HASHVALUES)
-#if FULL_POSITION_IN_HASH
-      if (hashposition_compare(&hd->hashpos, &node->key.hashpos) == 0)
-       break;
-#else
       break;
-#endif
   }

   return node;
@@ -1047,11 +1039,7 @@ do_get_read_result(enum routine_id routi

   /* Assert that hash data really corresponds to the state of the board. */
   hashdata_recalc(&key, board, board_ko_pos);
-#if FULL_POSITION_IN_HASH
-  gg_assert(hashdata_diff_dump(&key, &hashdata) == 0);
-#else
   gg_assert(hashdata_compare(&key, &hashdata) == 0);
-#endif

 #endif /* CHECK_HASHING */

Index: engine/hash.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.c,v
retrieving revision 1.20
diff -u -p -r1.20 hash.c
--- engine/hash.c       10 Aug 2003 17:56:50 -0000      1.20
+++ engine/hash.c       29 Sep 2003 13:41:35 -0000
@@ -102,11 +102,6 @@ static Hashvalue white_hash[BOARDMAX][NU
 static Hashvalue black_hash[BOARDMAX][NUM_HASHVALUES];
 static Hashvalue ko_hash[BOARDMAX][NUM_HASHVALUES];

-#if FULL_POSITION_IN_HASH
-static Compacttype white_patterns[4 * sizeof(Compacttype)];
-static Compacttype black_patterns[4 * sizeof(Compacttype)];
-#endif
-

 /* Get a random Hashvalue, where all bits are used. */
 static Hashvalue
@@ -132,9 +127,6 @@ hash_init(void)
   int pos;
   int i;
   struct gg_rand_state state;
-#if FULL_POSITION_IN_HASH
-  int x;
-#endif

   if (is_initialized)
     return;
@@ -162,76 +154,12 @@ hash_init(void)

   gg_set_rand_state(&state);

-#if FULL_POSITION_IN_HASH
-  {
-    Compacttype mask;
-
-    for (x = 0, mask = 1; mask; x++, mask <<= 2) {
-      white_patterns[x] = mask;
-      black_patterns[x] = mask << 1;
-    }
-  }
-#endif
-
   is_initialized = 1;
 }


 /* ---------------------------------------------------------------- */

-
-/* Return 0 if *pos1 == *pos2, otherwise return 1.
- * This adheres (almost) to the standard compare function semantics
- * which are used e.g. by the comparison functions used in qsort().
- */
-
-#if FULL_POSITION_IN_HASH
-int
-hashposition_compare(Hashposition *pos1, Hashposition *pos2)
-{
-  int i;
-
-  /* We need only compare to board_size.  MAX_BOARD is not necessary. */
-  for (i = 0; i < (int) (board_size * board_size / POINTSPERCOMPACT + 1); i++)
-    if (pos1->board[i] != pos2->board[i]) {
-      stats.hash_collisions++;
-      return 1;
-    }
-
-  if (pos1->ko_pos != pos2->ko_pos) {
-    stats.hash_collisions++;
-    return 1;
-  }
-
-  return 0;
-}
-
-
-/*
- * Dump an ASCII representation of the contents of a Hashposition onto
- * the FILE outfile.
- */
-
-void
-hashposition_dump(Hashposition *pos, FILE *outfile)
-{
-  int i;
-
-  gfprintf(outfile, "Board:  ");
-  for (i = 0; i < (int) COMPACT_BOARD_SIZE; ++i)
-    gfprintf(outfile, " %lx", (unsigned long) pos->board[i]);
-
-  if (pos->ko_pos == 0)
-    gfprintf(outfile, "  No ko");
-  else
-    gfprintf(outfile, "  Ko position: %1m", pos->ko_pos);
-}
-#endif                 /* FULL_POSITION_IN_HASH */
-
-
-/* ---------------------------------------------------------------- */
-
-
 /* Calculate the compactboard and the hashvalues in one function.
  * They are always used together and it saves us a loop and a function
  * call.
@@ -240,75 +168,33 @@ hashposition_dump(Hashposition *pos, FIL
 void
 hashdata_recalc(Hash_data *target, Intersection *p, int ko_pos)
 {
-#if FULL_POSITION_IN_HASH
-  unsigned int index;
-  Compacttype bits;
-#endif
   int pos;
   int i;

   for (i = 0; i < NUM_HASHVALUES; i++)
     target->hashval[i] = 0;
-#if FULL_POSITION_IN_HASH
-  bits = 1;
-  index = 0;
-  target->hashpos.board[index] = 0;
-#endif
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
     if (!ON_BOARD(pos))
       continue;
     switch (p[pos]) {
       default:
       case EMPTY:
-#if FULL_POSITION_IN_HASH
-       bits <<= 2;
-#endif
        break;
       case WHITE:
         for (i = 0; i < NUM_HASHVALUES; i++)
          target->hashval[i] ^= white_hash[pos][i];
-#if FULL_POSITION_IN_HASH
-       target->hashpos.board[index] |= bits;
-       bits <<= 2;
-#endif
        break;
       case BLACK:
         for (i = 0; i < NUM_HASHVALUES; i++)
          target->hashval[i] ^= black_hash[pos][i];
-#if FULL_POSITION_IN_HASH
-       bits <<= 1;
-       target->hashpos.board[index] |= bits;
-       bits <<= 1;
-#endif
        break;
     }

-#if FULL_POSITION_IN_HASH
-    if (!bits) {
-      /* This means the bit fell off the left side. */
-      bits = 1;
-      index++;
-      if (index < COMPACT_BOARD_SIZE)
-       target->hashpos.board[index] = 0;
-    }
-#endif
   }

-  /* This cleans up garbage bits at the (unused) end of the array.
-   * It probably should not really be necessary.
-   */
-#if FULL_POSITION_IN_HASH
-  while (++index < COMPACT_BOARD_SIZE)
-    target->hashpos.board[index] = 0;
-#endif
-
   if (ko_pos != 0)
     for (i = 0; i < NUM_HASHVALUES; i++)
       target->hashval[i] ^= ko_hash[ko_pos][i];
-
-#if FULL_POSITION_IN_HASH
-  target->hashpos.ko_pos = ko_pos;
-#endif
 }


@@ -322,9 +208,6 @@ hashdata_invert_ko(Hash_data *hd, int po
   int i;
   for (i = 0; i < NUM_HASHVALUES; i++)
     hd->hashval[i] ^= ko_hash[pos][i];
-#if FULL_POSITION_IN_HASH
-  hd->hashpos.ko_pos = pos;
-#endif
 }


@@ -336,100 +219,19 @@ hashdata_invert_ko(Hash_data *hd, int po
 void
 hashdata_invert_stone(Hash_data *hd, int pos, int color)
 {
-#if FULL_POSITION_IN_HASH
-  int i = I(pos);
-  int j = J(pos);
-  int index = (i * board_size + j) / POINTSPERCOMPACT;
-  int subindex = (i * board_size + j) % POINTSPERCOMPACT;
-#endif
   int k;

   if (color == BLACK) {
     for (k = 0; k < NUM_HASHVALUES; k++)
       hd->hashval[k] ^= black_hash[pos][k];
-#if FULL_POSITION_IN_HASH
-    hd->hashpos.board[index] ^= black_patterns[subindex];
-#endif
   }
   else if (color == WHITE) {
     for (k = 0; k < NUM_HASHVALUES; k++)
       hd->hashval[k] ^= white_hash[pos][k];
-#if FULL_POSITION_IN_HASH
-    hd->hashpos.board[index] ^= white_patterns[subindex];
-#endif
   }
 }


-/*
- * Compare two Hash_data, if different: dump an ASCII representation
- * of the differences to stderr.
- * return is the same as for hashposition_compare()
- */
-
-#if FULL_POSITION_IN_HASH
-int
-hashdata_diff_dump(Hash_data *hd1, Hash_data *hd2)
-{
-  int retval;
-  int pos, i;
-  int count1[4], count2[4];
-  static const char letter[] = "abcdefghjklmnopqrstuvwxyz";
-  static const char *hashcolors[] = {"Empty", "White", "Black", "Grey!"};
-
-  retval = hashdata_compare(hd1, hd2);
-  if (retval == 0)
-    return retval;
-
-  for (i = 0; i < 4; i++) {
-    count1[i] = 0;
-    count2[i] = 0;
-  }
-
-  fprintf(stderr, "Differences: ");
-  for (i = 0; i < COMPACT_BOARD_SIZE; i++) {
-    if (hd1->hashpos.board[i] != hd2->hashpos.board[i])
-      fprintf(stderr, "\nSlot %d: (%lx <==> %lx)" , i,
-             (unsigned long) hd1->hashpos.board[i],
-             (unsigned long) hd2->hashpos.board[i]);
-
-    for (pos = 0; pos < POINTSPERCOMPACT; pos++) {
-      unsigned int u1, u2;
-      int xx, yy, zz;
-
-      u1 = (hd1->hashpos.board[i] >> (2*pos)) & 3;
-      u2 = (hd2->hashpos.board[i] >> (2*pos)) & 3;
-      count1[u1]++;
-      count2[u2]++;
-      if (u1 == u2)
-       continue;
-
-      zz = (i * POINTSPERCOMPACT) + pos;
-      xx = zz / MAX_BOARD;
-      yy = zz % MAX_BOARD;
-      fprintf(stderr, "\n#%2d: [%c%d] %s<==>%s", pos, letter[xx], yy,
-             hashcolors[u1], hashcolors[u2]);
-    }
-  }
-
-  if (hd1->hashpos.ko_pos == 0 && hd2->hashpos.ko_pos == 0)
-    fprintf(stderr, "\nNo ko\n");
-  else if (hd1->hashpos.ko_pos == hd2->hashpos.ko_pos)
-    gfprintf(stderr, "\nEqual Ko position:[%1m]\n", hd1->hashpos.ko_pos);
-  else
-    gfprintf(stderr, "\nDifferent Ko position:[%1m] <==> [%1m]\n",
-           hd1->hashpos.ko_pos, hd2->hashpos.ko_pos);
-
-  fprintf(stderr, "Total [%d,%d,%d,%d]",
-         count1[0], count1[1], count1[2], count1[3]);
-  fprintf(stderr, " <==> [%d,%d,%d,%d]\n",
-         count2[0], count2[1], count2[2], count2[3]);
-
-  return retval;
-}
-#endif
-
-
 int
 hashdata_compare(Hash_data *hd1, Hash_data *hd2)
 {
@@ -442,11 +244,6 @@ hashdata_compare(Hash_data *hd1, Hash_da
   if (rc == 2 && i > 0)
     stats.hash_collisions++;

-#if FULL_POSITION_IN_HASH
-  if (rc == 0)
-    rc = hashposition_compare(&hd1->hashpos, &hd2->hashpos);
-#endif
-
   return rc;
 }

@@ -465,9 +262,7 @@ goal_to_hashvalue(const char *goal)
   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.
- */
+/* Returns an XOR of the two hash values. */
 Hash_data
 xor_hashvalues(Hash_data *hash1, Hash_data *hash2)
 {
@@ -476,9 +271,6 @@ xor_hashvalues(Hash_data *hash1, Hash_da

   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.18
diff -u -p -r1.18 hash.h
--- engine/hash.h       15 Aug 2003 07:21:22 -0000      1.18
+++ engine/hash.h       29 Sep 2003 13:41:35 -0000
@@ -61,15 +61,6 @@ typedef unsigned long Compacttype;
 /* for testing: Enables a lot of checks. */
 #define CHECK_HASHING 0

-/* Old hashing. */
-#if (HASHING_SCHEME==1)
-#define NUM_HASHVALUES                 1
-#define FULL_POSITION_IN_HASH  1
-#endif
-
-/* Proposed new hashing. */
-#if (HASHING_SCHEME==2)
-
 /* How many bits should be used at least for hashing? Set this to 32 for
  * some memory save and speedup, at the cost of occasional irreproducable
  * mistakes (and possibly assertion failures).
@@ -79,51 +70,6 @@ typedef unsigned long Compacttype;
 #define MIN_HASHBITS           64

 #define NUM_HASHVALUES                 (MIN_HASHBITS / ( 8 * SIZEOF_LONG))
-#define FULL_POSITION_IN_HASH  0       /* Set this to 1 for debugging. */
-#endif
-
-/* Use this for self-defined values. */
-#if (HASHING_SCHEME==3)
-#define NUM_HASHVALUES                 ?
-#define FULL_POSITION_IN_HASH  ?
-#endif
-
-
-/*
- * We define a special compact representation of the board for the
- * positions, used if FULL_POSITION_IN_HASH is set. In this representation
- * each location is represented by 2 bits with 0 meaning EMPTY, 1 meaning
- * WHITE and 2 meaning BLACK as defined in gnugo.h.
- * COMPACT_BOARD_SIZE is the size of such a compact representation
- * for the maximum board size allowed.
- *
- * POINTSPERCOMPACT is the number of intersections that fits into a
- * Compacttype. COMPACT_BOARD_SIZE contains the number of Compacttype
- * that is needed to contain a board of size MAX_BOARD. We would like
- * to have this as a variable instead of a macro since the macro could
- * waste one word, but it is used in the sizeing of Hashposition.
- *
- * A go position consists of the board, possibly a ko point but NOT the
- * player to move.  This will not let us handle the super ko rule, but
- * we deem this sufficient for now.
- *
- * The ko point is defined as the point where, on the last move, one
- * stone was captured.  It is illegal for the player to move to place
- * a stone on this point.  To do so would either be suicide, which is
- * illegal anyhow, or a violation of the ko rule.  If there is no ko
- * going on, ko_pos == -1;
- */
-
-#define POINTSPERCOMPACT    ((int) sizeof(Compacttype) * 4)
-#define COMPACT_BOARD_SIZE  ((MAX_BOARD) * (MAX_BOARD) / POINTSPERCOMPACT + 1)
-
-#if FULL_POSITION_IN_HASH
-typedef struct hashposition_t {
-  Compacttype  board[COMPACT_BOARD_SIZE];
-  int          ko_pos;
-} Hashposition;
-#endif
-

 /*
  * This struct is maintained by the machinery that updates the board
@@ -132,9 +78,6 @@ typedef struct hashposition_t {

 typedef struct {
   Hashvalue     hashval[NUM_HASHVALUES];
-#if FULL_POSITION_IN_HASH
-  Hashposition  hashpos;
-#endif
 } Hash_data;

 extern Hash_data hashdata;
@@ -143,10 +86,6 @@ Hash_data xor_hashvalues(Hash_data *key1
 Hash_data goal_to_hashvalue(const char *goal);

 void hash_init(void);
-#if FULL_POSITION_IN_HASH
-int  hashposition_compare(Hashposition *pos1, Hashposition *pos2);
-void hashposition_dump(Hashposition *pos, FILE *outfile);
-#endif

 void hashdata_recalc(Hash_data *hd, Intersection *board, int ko_pos);
 int  hashdata_compare(Hash_data *hd1, Hash_data *hd2);
Index: interface/main.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/main.c,v
retrieving revision 1.85
diff -u -p -r1.85 main.c
--- interface/main.c    7 Sep 2003 23:02:45 -0000       1.85
+++ interface/main.c    29 Sep 2003 13:41:37 -0000
@@ -474,8 +474,6 @@ main(int argc, char *argv[])
        if (EXPERIMENTAL_READING)
          fprintf(stderr,
                  "configure option enabled: experimental reading\n");
-       if (HASHING_SCHEME != 2)
-         fprintf(stderr, "hash scheme %d\n", HASHING_SCHEME);
        if (OWL_THREATS)
          fprintf(stderr,
                  "configure option enabled: owl threats\n");