Index: engine/board.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v retrieving revision 1.81 diff -u -r1.81 board.c --- engine/board.c 18 Jul 2003 18:59:21 -0000 1.81 +++ engine/board.c 3 Aug 2003 12:23:34 -0000 @@ -270,12 +270,14 @@ PUSH_VERTEX(board[pos]);\ board[pos] = color;\ hashdata_invert_stone(&hashdata, pos, color);\ + hashval_ng = hashvalue_ng_invert_stone(hashval_ng, pos, color);\ } while (0) #define DO_REMOVE_STONE(pos)\ do {\ PUSH_VERTEX(board[pos]);\ hashdata_invert_stone(&hashdata, pos, board[pos]);\ + hashval_ng = hashvalue_ng_invert_stone(hashval_ng, pos, board[pos]);\ board[pos] = EMPTY;\ } while (0) @@ -394,6 +396,7 @@ movenum = state->move_number; hashdata_recalc(&hashdata, board, board_ko_pos); + hashval_ng = hashvalue_ng_recalc(board, board_ko_pos); new_position(); } @@ -430,6 +433,7 @@ movenum = 0; hashdata_recalc(&hashdata, board, board_ko_pos); + hashval_ng = hashvalue_ng_recalc(board, board_ko_pos); new_position(); } @@ -463,6 +467,7 @@ static int move_color[MAXSTACK]; static Hash_data hashdata_stack[MAXSTACK]; +static Hashvalue_ng hashval_ng_stack[MAXSTACK]; /* KOMASTER_SCHEME 4 handles empty case differently from other schemes */ @@ -528,25 +533,25 @@ if (str == NO_MOVE) { if (!komaster_is_empty(komaster, kom_pos)) gg_snprintf(buf, 100, "%s (variation %d, hash %lx, komaster %s:%s)", - message, count_variations, hashdata.hashval[0], + message, count_variations, hashval_ng, komaster_to_string(komaster, kom_pos), location_to_string(kom_pos)); else gg_snprintf(buf, 100, "%s (variation %d, hash %lx)", - message, count_variations, hashdata.hashval[0]); + message, count_variations, hashval_ng); } else { if (!komaster_is_empty(komaster, kom_pos)) gg_snprintf(buf, 100, "%s at %s (variation %d, hash %lx, komaster %s:%s)", message, location_to_string(str), count_variations, - hashdata.hashval[0], + hashval_ng, komaster_to_string(komaster, kom_pos), location_to_string(kom_pos)); else gg_snprintf(buf, 100, "%s at %s (variation %d, hash %lx)", message, location_to_string(str), count_variations, - hashdata.hashval[0]); + hashval_ng); } sgftreeAddPlayLast(sgf_dumptree, color, I(pos), J(pos)); sgftreeAddComment(sgf_dumptree, buf); @@ -584,12 +589,12 @@ message = "UNKNOWN"; if (!komaster_is_empty(komaster, kom_pos)) gg_snprintf(buf, 100, "tryko: %s (variation %d, %lx, komaster %s:%s)", - message, count_variations, hashdata.hashval[0], + message, count_variations, hashval_ng, komaster_to_string(komaster, kom_pos), location_to_string(kom_pos)); else gg_snprintf(buf, 100, "tryko: %s (variation %d, %lx)", - message, count_variations, hashdata.hashval[0]); + message, count_variations, hashval_ng); /* Add two pass moves to the SGF output to simulate the ko threat * and the answer. @@ -704,9 +709,12 @@ BEGIN_CHANGE_RECORD(); PUSH_VALUE(board_ko_pos); memcpy(&hashdata_stack[stackp], &hashdata, sizeof(hashdata)); + hashval_ng_stack[stackp] = hashval_ng; - if (board_ko_pos != NO_MOVE) + if (board_ko_pos != NO_MOVE) { hashdata_invert_ko(&hashdata, board_ko_pos); + hashval_ng = hashvalue_ng_invert_ko(hashval_ng, board_ko_pos); + } board_ko_pos = NO_MOVE; PUSH_VALUE(black_captured); @@ -735,6 +743,8 @@ undo_trymove(); memcpy(&hashdata, &(hashdata_stack[stackp]), sizeof(hashdata)); + hashval_ng = hashval_ng_stack[stackp]; + if (sgf_dumptree) { char buf[100]; gg_snprintf(buf, 100, "(next variation: %d)", count_variations); @@ -761,6 +771,7 @@ stackp--; undo_trymove(); memcpy(&hashdata, &(hashdata_stack[stackp]), sizeof(hashdata)); + hashval_ng = hashval_ng_stack[stackp]; } #endif @@ -810,7 +821,7 @@ if (count_variations) gprintf("%o (variation %d)", count_variations-1); #else - gprintf("%o (%d)", hashdata.hashval[0]); + gprintf("%o (%d)", hashval_ng); #endif gprintf("%o\n"); @@ -846,6 +857,7 @@ board[pos] = color; hashdata_invert_stone(&hashdata, pos, color); + hashval_ng = hashvalue_ng_invert_stone(hashval_ng, pos, color); reset_move_history(); new_position(); } @@ -863,6 +875,7 @@ ASSERT1(IS_STONE(board[pos]), pos); hashdata_invert_stone(&hashdata, pos, board[pos]); + hashval_ng = hashvalue_ng_invert_stone(hashval_ng, pos, board[pos]); board[pos] = EMPTY; reset_move_history(); new_position(); @@ -881,9 +894,11 @@ { #if CHECK_HASHING Hash_data oldkey; + Hashvalue_ng oldhashval_ng; /* Check the hash table to see if it corresponds to the cumulative one. */ hashdata_recalc(&oldkey, board, board_ko_pos); + old_hashval_ng = hashvalue_ng_recalc(board, board_ko_pos); #if FULL_POSITION_IN_HASH gg_assert(hashdata_diff_dump(&oldkey, &hashdata) == 0); #else @@ -891,8 +906,10 @@ #endif #endif - if (board_ko_pos != NO_MOVE) + if (board_ko_pos != NO_MOVE) { hashdata_invert_ko(&hashdata, board_ko_pos); + hashval_ng = hashvalue_ng_invert_ko(hashval_ng, board_ko_pos); + } board_ko_pos = NO_MOVE; /* If the move is a pass, we can skip some steps. */ @@ -909,6 +926,7 @@ #if CHECK_HASHING /* Check the hash table to see if it equals the previous one. */ hashdata_recalc(&oldkey, board, board_ko_pos); + oldhashval_ng = hashvalue_ng_recalc(board, board_ko_pos); #if FULL_POSITION_IN_HASH gg_assert(hashdata_diff_dump(&oldkey, &hashdata) == 0); #else @@ -2195,6 +2213,7 @@ int threshold; int liberties; Hash_data position_hash; + Hashvalue_ng position_hash_ng; }; @@ -2242,19 +2261,9 @@ if (!libs) { /* First see if this result is cached. */ - if (hashdata.hashval[0] == entry->position_hash.hashval[0] + if (hashdata_is_equal(hashval_ng, entry->position_hash_ng) && maxlib <= entry->threshold) { - int k; - for (k = 1; k < NUM_HASHVALUES; k++) { - if (hashdata.hashval[k] != entry->position_hash.hashval[k]) - break; - } - - /* If position hash values match and `maxlib' is not greater than - * the threshold, we already know the result. - */ - if (k == NUM_HASHVALUES) - return entry->liberties; + return entry->liberties; } liberties = fastlib(pos, color, 1); @@ -2266,6 +2275,7 @@ entry->threshold = MAXLIBS; entry->liberties = liberties; entry->position_hash = hashdata; + entry->position_hash_ng = hashval_ng; return liberties; } @@ -2285,6 +2295,7 @@ entry->liberties = liberties; entry->position_hash = hashdata; + entry->position_hash_ng = hashval_ng; #else /* not USE_BOARD_CACHES */ @@ -2550,19 +2561,9 @@ if (!libs) { /* First see if this result is cached. */ - if (hashdata.hashval[0] == entry->position_hash.hashval[0] + if (hashdata_is_equal(hashval_ng, entry->position_hash_ng) && maxlib <= entry->threshold) { - int k; - for (k = 1; k < NUM_HASHVALUES; k++) { - if (hashdata.hashval[k] != entry->position_hash.hashval[k]) - break; - } - - /* If position hash values match and `maxlib' is not greater than - * the threshold, we already know the result. - */ - if (k == NUM_HASHVALUES) - return entry->liberties; + return entry->liberties; } liberties = fastlib(pos, color, 0); @@ -2574,6 +2575,7 @@ entry->threshold = MAXLIBS; entry->liberties = liberties; entry->position_hash = hashdata; + entry->position_hash_ng = hashval_ng; return liberties; } @@ -2588,6 +2590,7 @@ entry->threshold = liberties < maxlib ? MAXLIBS : maxlib; entry->liberties = liberties; entry->position_hash = hashdata; + entry->position_hash_ng = hashval_ng; #else /* not USE_BOARD_CACHES */ @@ -4485,10 +4488,13 @@ && string[s].size == 1 && captured_stones == 1) { /* In case of a double ko: clear old ko position first. */ - if (board_ko_pos != NO_MOVE) + if (board_ko_pos != NO_MOVE) { hashdata_invert_ko(&hashdata, board_ko_pos); + hashval_ng = hashvalue_ng_invert_ko(hashval_ng, board_ko_pos); + } board_ko_pos = string[s].libs[0]; hashdata_invert_ko(&hashdata, board_ko_pos); + hashval_ng = hashvalue_ng_invert_ko(hashval_ng, board_ko_pos); } } Index: engine/cache.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/cache.c,v retrieving revision 1.26 diff -u -r1.26 cache.c --- engine/cache.c 18 Jul 2003 18:59:21 -0000 1.26 +++ engine/cache.c 3 Aug 2003 12:23:38 -0000 @@ -21,6 +21,7 @@ \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ +#include "random.h" #include "gnugo.h" #include @@ -33,6 +34,197 @@ #include "cache.h" #include "sgftree.h" + +/* ================================================================ */ +/* The new transposition table */ + + + +/* ---------------------------------------------------------------- */ + + +/* Initialize the transposition table. + */ + +void +tt_init(Transposition_table *table, int memsize) +{ + int num_entries; + + /* Make sure the hash system is initialized. */ + hash_ng_init(); + + num_entries = memsize / sizeof(Hashentry_ng); + +#if 0 + printf("Creating hash table of size double entries (%d bytes)\n", + bits, size); +#endif + + table->num_entries = num_entries; + table->entries = (Hashentry_ng *) malloc(num_entries + * sizeof(Hashentry_ng)); + + if (table->entries == NULL) { + perror("Couldn't allocate memory for transposition table. \n"); + exit(1); + } + + table->is_clean = 0; + tt_clear(table); +} + + +/* Clear the transposition table. + */ + +void +tt_clear(Transposition_table *table) +{ + Hashentry_ng hash_null = {{hashdata_NULL, 0}, {hashdata_NULL, 0}}; + unsigned i; + + if (table->is_clean) + return; + + for (i = 0; i < table->num_entries; i++) + table->entries[i] = hash_null; + + table->is_clean = 1; +} + + +/* Free the transposition table. + */ + +void +tt_free(Transposition_table *table) +{ + free(table->entries); +} + + +/* Set result and move. Return value: + * 0 if not found + * 1 if found, but depth to small to be trusted. In this case the move + * can be used for move ordering. + * 2 if found and depth is enough so that the result can be trusted. + */ + +int +tt_get(Transposition_table *table, + int komaster, int kom_pos, int routine, int target, + int remaining_depth, + int *result, int *move) +{ + Hashvalue_ng hashval; + Hashentry_ng *entry; + Hashnode_ng *node; + + hashval = calculate_hashval_ng(komaster, kom_pos, routine, target); + + /* Sanity check. */ + if (remaining_depth < 0) + remaining_depth = 0; + if (remaining_depth > HN_MAX_REMAINING_DEPTH) + remaining_depth = HN_MAX_REMAINING_DEPTH; + + /* Get the correct entry and node. */ + entry = &table->entries[hashdata_remainder(hashval, table->num_entries)]; + if (hashdata_is_equal(hashval, entry->deepest.key)) + node = &entry->deepest; + else if (hashdata_is_equal(hashval, entry->newest.key)) + node = &entry->newest; + else + return 0; + + /* Return data. Only set the result if remaining depth in the table + * is big enough to be trusted. The move can always be used for move + * ordering if nothing else. + */ + if (move) + *move = hn_get_move(*node); + if ((unsigned) remaining_depth <= hn_get_remaining_depth(*node)) { + if (result) + *result = hn_get_result1(*node); + return 2; + } + + return 1; +} + + +/* Update a transposition table entry. + */ + +void +tt_update(Transposition_table *table, + int komaster, int kom_pos, int routine, int target, + int remaining_depth, + int result, int move) +{ + Hashvalue_ng hashval; + Hashentry_ng *entry; + Hashnode_ng *deepest; + Hashnode_ng *newest; + uint32_t data; + + /* Calculate the hash value. */ + hashval = calculate_hashval_ng(komaster, kom_pos, routine, target); + data = hn_create_data(remaining_depth, result, 0, move, 0); + + /* Get the entry and nodes. */ + entry = &table->entries[hashdata_remainder(hashval, table->num_entries)]; + deepest = &entry->deepest; + newest = &entry->newest; + + /* See if we found an already existing node. */ + if (hashdata_is_equal(hashval, deepest->key) + && (unsigned) remaining_depth >= hn_get_remaining_depth(*deepest)) { + + /* Found deepest */ + deepest->data = data; + + } + else if (hashdata_is_equal(hashval, newest->key) + && (unsigned) remaining_depth >= hn_get_remaining_depth(*newest)) { + + /* Found newest */ + newest->data = data; + + /* If newest has become deeper than deepest, then switch them. */ + if (hn_get_remaining_depth(*newest) > hn_get_remaining_depth(*deepest)) { + Hashnode_ng temp; + + temp = *deepest; + *deepest = *newest; + *newest = temp; + } + + } + else if ((unsigned) remaining_depth > hn_get_remaining_depth(*deepest)) { + + /* This can only happen if newest is empty. */ + if (hn_get_remaining_depth(*newest) < hn_get_remaining_depth(*deepest)) + *newest = *deepest; + + deepest->key = hashval; + deepest->data = data; + } + else { + /* Replace newest. */ + newest->key = hashval; + newest->data = data; + } + + table->is_clean = 0; +} + + +/* ================================================================ */ +/* The old transposition table */ + + static Hashtable *movehash; static int hashtable_init(Hashtable *table, int tablesize, int num_nodes, @@ -630,16 +822,41 @@ void reading_cache_init(int bytes) { + float nodes; + +#ifdef USE_HASHTABLE_NG + + /* Use a majority of the memory for the transposition table because + * that one is used for the tactical reading. Tests reveal that we + * use approximately 500 tactical reading nodes for each owl node. + * This would point to 99.8%, but it is better to have a bit too + * many owl nodes in the cache than too few. + * + * Using 5% for the owl nodes and 95% for the transposition table + * seems to give a 2% speedup, but this should be better once the + * owl table is gone and everything is in the new transposition + * table. + */ +#define NG_PERCENTAGE 95 + tt_init(&ttable, bytes * NG_PERCENTAGE / 100); + + /* Use the rest of the available memory for the old cache where + * still owl, semeai and readconnect caching takes place. + */ + bytes = bytes * (100 - NG_PERCENTAGE) / 100; +#endif + + /* Initialize hash table. * * The number 1.4 below is the quotient between the number of nodes * and the number of read results. It was found in a test that this * number varies between 1.15 and 1.4. Thus we use 1.4. */ - float nodes = ((float) bytes - / (1.5 * sizeof(Hashnode *) - + sizeof(Hashnode) - + 1.4 * sizeof(Read_result))); + nodes = ((float) bytes + / (1.5 * sizeof(Hashnode *) + + sizeof(Hashnode) + + 1.4 * sizeof(Read_result))); if (0) gprintf("Allocated memory for %d hash nodes. \n", (int) nodes); /* If we get a zero size hash table, disable hashing completely. */ @@ -662,6 +879,7 @@ reading_cache_clear() { hashtable_clear(movehash); + tt_clear(&ttable); } int Index: engine/cache.h =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/cache.h,v retrieving revision 1.31 diff -u -r1.31 cache.h --- engine/cache.h 2 Aug 2003 14:17:52 -0000 1.31 +++ engine/cache.h 3 Aug 2003 12:23:41 -0000 @@ -32,6 +32,85 @@ #ifndef _CACHE_H_ #define _CACHE_H_ + +/* Hashnode: a node stored in the transposition table. + * + * In addition to the position, the hash lock encodes the following data, + * all hashed: + * komaster + * kom_pos + * routine + * str1 + * str2 + * + * The data field packs into 32 bits the following + * fields: + * + * RESERVED : 5 bits + * remaining_depth: 5 bits (depth - stackp) NOTE: HN_MAX_REMAINING_DEPTH + * result1 : 4 bits + * result2 : 4 bits + * move : 10 bits + * flags : 4 bits + */ +typedef struct { + Hashvalue_ng key; + uint32_t data; +} Hashnode_ng; + +#define HN_MAX_REMAINING_DEPTH 31 + + +/* Hashentry: an entry, with two nodes of the hash_table + */ +typedef struct { + Hashnode_ng deepest; + Hashnode_ng newest; +} Hashentry_ng; + +/* Hn is for hash node. */ +#define hn_get_remaining_depth(hn) (((hn).data >> 22) & 0x1f) +#define hn_get_result1(hn) (((hn).data >> 18) & 0x0f) +#define hn_get_result2(hn) (((hn).data >> 14) & 0x0f) +#define hn_get_move(hn) (((hn).data >> 4) & 0x3ff) +#define hn_get_flags(hn) (((hn).data >> 0) & 0x0f) + +#define hn_create_data(remaining_depth, result1, result2, move, flags) \ + (((remaining_depth & 0x1f) << 22) \ + | (((result1) & 0x0f) << 18) \ + | (((result2) & 0x0f) << 14) \ + | (((move) & 0x3ff) << 4) \ + | (((flags) & 0x0f) << 0)) + + +/* Transposition_table: transposition table used for caching. */ +typedef struct { + unsigned int num_entries; + Hashentry_ng *entries; + int is_clean; +} Transposition_table; + + +extern void tt_init(Transposition_table *table, int memsize); +extern void tt_clear(Transposition_table *table); +extern void tt_free(Transposition_table *table); +extern int tt_get(Transposition_table *table, + int komaster, int kom_pos, int routine, int target, + int remaining_depth, + int *result, int *move); +extern void tt_update(Transposition_table *table, + int komaster, int kom_pos, int routine, int target, + int remaining_depth, + int result, int move); + + +/* ================================================================ */ +/* The old transposition table */ + + +/* Dump (almost) all read results. */ +#define TRACE_READ_RESULTS 0 + /* * This struct contains the attack / defense point and the result. * It is kept in a linked list, and each position has a list of @@ -168,8 +247,10 @@ void hashtable_dump(Hashtable *table, FILE *outfile); void hashnode_dump(Hashnode *node, FILE *outfile); + /* ================================================================ */ + /* Macros used from reading.c and owl.c to store and retrieve read * results. */ @@ -268,6 +349,19 @@ */ #if !TRACE_READ_RESULTS +#define READ_RETURN0_NG(komaster, kom_pos, routine, str, remaining_depth) \ + do { \ + tt_update(&ttable, komaster, kom_pos, routine, str, remaining_depth, 0, 0);\ + return 0; \ + } while (0) + +#define READ_RETURN_NG(komaster, kom_pos, routine, str, remaining_depth, point, move, value) \ + do { \ + tt_update(&ttable, komaster, kom_pos, routine, str, remaining_depth, value, move);\ + if ((value) != 0 && (point) != 0) *(point) = (move); \ + return (value); \ + } while (0) + #define READ_RETURN0(read_result) \ do { \ if (read_result) { \ @@ -284,6 +378,7 @@ } \ return (value); \ } while (0) + #define READ_RETURN_SEMEAI(read_result, point, move, value_a, value_b) \ do { \ Index: engine/genmove.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v retrieving revision 1.80 diff -u -r1.80 genmove.c --- engine/genmove.c 3 Aug 2003 08:03:12 -0000 1.80 +++ engine/genmove.c 3 Aug 2003 12:23:44 -0000 @@ -77,7 +77,9 @@ /* Initialize things for hashing of positions. */ reading_cache_clear(); + hashdata_recalc(&hashdata, board, board_ko_pos); + hashval_ng = hashvalue_ng_recalc(board, board_ko_pos); worms_examined = -1; initial_influence_examined = -1; Index: engine/globals.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v retrieving revision 1.55 diff -u -r1.55 globals.c --- engine/globals.c 3 Aug 2003 08:03:12 -0000 1.55 +++ engine/globals.c 3 Aug 2003 12:23:45 -0000 @@ -58,7 +58,9 @@ Intersection shadow[BOARDMAX]; /* Hashing of positions. */ -Hash_data hashdata; +Hash_data hashdata; +Hashvalue_ng hashval_ng; +Transposition_table ttable; int hashflags = HASH_DEFAULT; Index: engine/hash.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/hash.c,v retrieving revision 1.17 diff -u -r1.17 hash.c --- engine/hash.c 18 Jul 2003 18:59:21 -0000 1.17 +++ engine/hash.c 3 Aug 2003 12:23:47 -0000 @@ -38,6 +38,154 @@ */ +/* Random values for the hash function. */ +static Hashvalue_ng white_hash_ng[BOARDMAX]; +static Hashvalue_ng black_hash_ng[BOARDMAX]; +static Hashvalue_ng ko_hash_ng[BOARDMAX]; + +static Hashvalue_ng komaster_hash[4]; /* EMPTY, BLACK, WHITE, GRAY */ +static Hashvalue_ng kom_pos_hash[BOARDMAX]; +static Hashvalue_ng target1_hash[BOARDMAX]; +static Hashvalue_ng target2_hash[BOARDMAX]; +static Hashvalue_ng routine_hash[NUM_ROUTINES]; + +static struct init_struct { + Hashvalue_ng *array; + int array_size; +} hash_init_values[] = { + {white_hash_ng, BOARDMAX}, + {black_hash_ng, BOARDMAX}, + {ko_hash_ng, BOARDMAX}, + {komaster_hash, 4}, + {kom_pos_hash, BOARDMAX}, + {target1_hash, BOARDMAX}, + {target2_hash, BOARDMAX}, + {routine_hash, NUM_ROUTINES}, +}; + + +/* + * Initialize the entire hash and transposition table system. + * + * This should only be called once, and before calling any other + * functions in this file. + */ + +void +hash_ng_init(void) +{ + static int is_initialized = 0; + Hashvalue_ng *array; + int size; + unsigned i; + int j; + + + if (is_initialized) + return; + +#if TRACE_READ_RESULTS + /* We need consistent hash values when this option is enabled. */ + gg_srand(1); +#endif + + for (i = 0; + i < sizeof(hash_init_values) / sizeof(struct init_struct); + i++) { + array = hash_init_values[i].array; + size = hash_init_values[i].array_size; + + for (j = 0; j < size; j++) + hashdata_init(array[j], gg_urand(), gg_urand()); + } + + is_initialized = 1; +} + + +/* Calculate the hashvalue for a position. + */ + +Hashvalue_ng +hashvalue_ng_recalc(Intersection *p, int ko_pos) +{ + Hashvalue_ng hashval; + int pos; + + hashdata_clear(hashval); + for (pos = BOARDMIN; pos < BOARDMAX; pos++) { + if (!ON_BOARD(pos)) + continue; + + switch (p[pos]) { + default: + case EMPTY: + break; + + case WHITE: + hashdata_xor(hashval, white_hash_ng[pos]); + break; + + case BLACK: + hashdata_xor(hashval, black_hash_ng[pos]); + break; + } + } + + if (ko_pos != NO_MOVE) + hashdata_xor(hashval, ko_hash_ng[ko_pos]); + + return hashval; +} + + +Hashvalue_ng +calculate_hashval_ng(int komaster, int kom_pos, int routine, int target) +{ + Hashvalue_ng hashval; + + hashval = hashval_ng; /* from globals.c */ + hashdata_xor(hashval, komaster_hash[komaster]); + hashdata_xor(hashval, kom_pos_hash[kom_pos]); + hashdata_xor(hashval, routine_hash[routine]); + hashdata_xor(hashval, target1_hash[target]); + + return hashval; +} + + +/* + * Set or remove ko in the hash value. + */ + +Hashvalue_ng +hashvalue_ng_invert_ko(Hashvalue_ng hashval, int ko_pos) +{ + hashdata_xor(hashval, ko_hash_ng[ko_pos]); + return hashval; +} + + + +/* + * Set or remove a stone of COLOR at pos in a Hash_data. + */ + +Hashvalue_ng +hashvalue_ng_invert_stone(Hashvalue_ng hashval, int pos, int color) +{ + if (color == BLACK) + hashdata_xor(hashval, black_hash_ng[pos]); + else if (color == WHITE) + hashdata_xor(hashval, white_hash_ng[pos]); + + return hashval; +} + + +/* ================================================================ */ + + static int is_initialized = 0; Index: engine/hash.h =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/hash.h,v retrieving revision 1.13 diff -u -r1.13 hash.h --- engine/hash.h 2 Aug 2003 14:17:52 -0000 1.13 +++ engine/hash.h 3 Aug 2003 12:23:48 -0000 @@ -21,6 +21,7 @@ \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ #include +#include #include "gnugo.h" /* @@ -56,6 +57,7 @@ typedef unsigned long Hashvalue; typedef unsigned long Compacttype; + /* for testing: Enables a lot of checks. */ #define CHECK_HASHING 0 @@ -151,6 +153,66 @@ void hashdata_set_tomove(Hash_data *hd, int to_move); int hashdata_diff_dump(Hash_data *key1, Hash_data *key2); + + +/* ---------------------------------------------------------------- */ + + +/* Next generation hash implementation. + * + * FIXME: Once this is the standard, remove all the _ng suffixes + * and clean it up. + */ +#if 0 +typedef uint64_t Hashvalue_ng; + +#define hashdata_init(hd, uint1, uint2) \ + (hd) = ((uint64_t) (uint1) << 32) | ((uint64_t) (uint2)) + +#else + +#define Hashvalue_ng Hash_data + +#define hashdata_NULL {{0, 0}} +#define hashdata_clear(hd) \ + do { \ + (hd).hashval[0] = 0; \ + (hd).hashval[1] = 0; \ + } while (0) +#define hashdata_init(hd, uint1, uint2) \ + do { \ + (hd).hashval[0] = (uint1); \ + (hd).hashval[1] = (uint2); \ + } while (0) + +#define hashdata_is_equal(hd1, hd2) \ + ((hd1).hashval[0] == (hd2).hashval[0] \ + && (hd1).hashval[1] == (hd2).hashval[1]) +#define hashdata_xor(hd1, hd2) \ + do { \ + (hd1).hashval[0] ^= (hd2).hashval[0]; \ + (hd1).hashval[1] ^= (hd2).hashval[1]; \ + } while (0) + +/* FIXME: This is only an approximation. + * The real remainder can be calculated by + * (ax+y)%z = (a%z)(x%z)+(y%z) + * but this probably is good enough for the cache. + */ +#define hashdata_remainder(hd, num) \ + (((hd).hashval[0] + (hd).hashval[1]) % (num)) + +#endif + + +extern void hash_ng_init(void); +extern Hashvalue_ng calculate_hashval_ng(int komaster, int kom_pos, + int routine, int target); +extern Hashvalue_ng hashvalue_ng_recalc(Intersection *p, int ko_pos); +extern Hashvalue_ng hashvalue_ng_invert_ko(Hashvalue_ng hashval, int ko_pos); +extern Hashvalue_ng hashvalue_ng_invert_stone(Hashvalue_ng hashval, + int pos, int color); + #endif Index: engine/influence.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v retrieving revision 1.92 diff -u -r1.92 influence.c --- engine/influence.c 3 Aug 2003 08:03:12 -0000 1.92 +++ engine/influence.c 3 Aug 2003 12:23:57 -0000 @@ -1944,9 +1944,10 @@ const struct influence_data *base, Hash_data safety_hash) { + int i; + ASSERT_ON_BOARD1(pos); ASSERT1(IS_STONE(color), pos); - int i; if (territory_cache_position_number != position_number || territory_cache_color != color Index: engine/liberty.h =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v retrieving revision 1.191 diff -u -r1.191 liberty.h --- engine/liberty.h 3 Aug 2003 08:03:12 -0000 1.191 +++ engine/liberty.h 3 Aug 2003 12:24:03 -0000 @@ -42,10 +42,15 @@ /* We need the defintion of type Hash_data here. */ #include "hash.h" +#include "cache.h" /* Other modules get read-only access to this variable. */ -extern Hash_data hashdata; +extern Hash_data hashdata; +extern Hashvalue_ng hashval_ng; +extern Transposition_table ttable; +/* Define if you want the new transposition table. */ +#define USE_HASHTABLE_NG /* ================================================================ */ Index: engine/reading.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v retrieving revision 1.120 diff -u -r1.120 reading.c --- engine/reading.c 18 Jul 2003 18:59:21 -0000 1.120 +++ engine/reading.c 3 Aug 2003 12:24:25 -0000 @@ -1058,6 +1058,7 @@ int liberties; int found_read_result; Read_result *read_result = NULL; + int retval; SETUP_TRACE_INFO("find_defense", str); @@ -1069,6 +1070,7 @@ * storing the position in the hash table, we must do this test * before we look for cached results. */ + str = find_origin(str); liberties = countlib(str); if (liberties > 4 @@ -1081,6 +1083,17 @@ return WIN; } +#ifdef USE_HASHTABLE_NG + + if ((stackp <= depth) && (hashflags & HASH_FIND_DEFENSE) + && tt_get(&ttable, komaster, kom_pos, FIND_DEFENSE, str, + depth - stackp, + &retval, move) == 2) + /* FIXME: Use move for move ordering if tt_get() returned 1 */ + return retval; + +#else + if ((stackp <= depth) && (hashflags & HASH_FIND_DEFENSE)) { found_read_result = get_read_result(FIND_DEFENSE, komaster, kom_pos, &str, &read_result); @@ -1096,6 +1109,8 @@ } } +#endif + #if EXPERIMENTAL_READING if (defend_by_pattern) { dcode = do_defend_pat(str, &xpos, komaster, kom_pos); @@ -1114,10 +1129,19 @@ dcode = defend4(str, &xpos, komaster, kom_pos); if (dcode) { +#ifdef USE_HASHTABLE_NG + READ_RETURN_NG(komaster, kom_pos, FIND_DEFENSE, str, depth - stackp, + move, xpos, dcode); +#else READ_RETURN(read_result, move, xpos, dcode); +#endif } +#ifdef USE_HASHTABLE_NG + READ_RETURN0_NG(komaster, kom_pos, FIND_DEFENSE, str, depth - stackp); +#else READ_RETURN0(read_result); +#endif } @@ -2945,6 +2969,7 @@ int result = 0; int found_read_result; Read_result *read_result = NULL; + int retval; SETUP_TRACE_INFO("attack", str); @@ -2956,6 +2981,7 @@ if (color == 0) /* if assertions are turned off, silently fails */ return 0; + str = find_origin(str); libs = countlib(str); if (libs > 4 @@ -2970,6 +2996,17 @@ return 0; } +#ifdef USE_HASHTABLE_NG + + if ((stackp <= depth) && (hashflags & HASH_ATTACK) + && tt_get(&ttable, komaster, kom_pos, ATTACK, str, + depth - stackp, + &retval, move) == 2) + /* FIXME: Use move for move ordering if tt_get() returned 1 */ + return retval; + +#else + if ((stackp <= depth) && (hashflags & HASH_ATTACK)) { found_read_result = get_read_result(ATTACK, komaster, kom_pos, &str, &read_result); @@ -2985,6 +3022,8 @@ } } +#endif + #if EXPERIMENTAL_READING if (attack_by_pattern) { result = do_attack_pat(str, &xpos, komaster, kom_pos); @@ -3012,9 +3051,18 @@ ASSERT1(result >= 0 && result <= WIN, str); if (result) +#ifdef USE_HASHTABLE_NG + READ_RETURN_NG(komaster, kom_pos, ATTACK, str, depth - stackp, + move, xpos, result); +#else READ_RETURN(read_result, move, xpos, result); +#endif +#ifdef USE_HASHTABLE_NG + READ_RETURN0_NG(komaster, kom_pos, ATTACK, str, depth - stackp); +#else READ_RETURN0(read_result); +#endif }