/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
* http://www.gnu.org/software/gnugo/ for more information. *
* Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
* 2008 and 2009 by the Free Software Foundation. *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as *
* published by the Free Software Foundation - version 3 or *
* (at your option) any later version. *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License in file COPYING for more details. *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
* Boston, MA 02111, USA. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* ================================================================ */
/* The transposition table */
/* ---------------------------------------------------------------- */
static void tt_init(Transposition_table
*table
, int memsize
);
static void tt_clear(Transposition_table
*table
);
/* The transposition table itself. */
Transposition_table ttable
;
/* Arrays with random numbers for Zobrist hashing of input data (other
* than the board position). If you add an array here, do not forget
* to also initialize it in keyhash_init() below.
static Hash_data target1_hash
[BOARDMAX
];
static Hash_data target2_hash
[BOARDMAX
];
static Hash_data routine_hash
[NUM_CACHE_ROUTINES
];
static int is_initialized
= 0;
INIT_ZOBRIST_ARRAY(target1_hash
);
INIT_ZOBRIST_ARRAY(target2_hash
);
INIT_ZOBRIST_ARRAY(routine_hash
);
calculate_hashval_for_tt(Hash_data
*hashdata
, int routine
, int target1
,
int target2
, Hash_data
*extra_hash
)
*hashdata
= board_hash
; /* from globals.c */
hashdata_xor(*hashdata
, routine_hash
[routine
]);
hashdata_xor(*hashdata
, target1_hash
[target1
]);
hashdata_xor(*hashdata
, target2_hash
[target2
]);
hashdata_xor(*hashdata
, *extra_hash
);
/* Initialize the transposition table. Non-positive memsize means use
* the default size of DEFAULT_NUMBER_OF_CACHE_ENTRIES entries.
tt_init(Transposition_table
*table
, int memsize
)
/* Make sure the hash system is initialized. */
num_entries
= memsize
/ sizeof(table
->entries
[0]);
num_entries
= DEFAULT_NUMBER_OF_CACHE_ENTRIES
;
table
->num_entries
= num_entries
;
table
->entries
= malloc(num_entries
* sizeof(table
->entries
[0]));
if (table
->entries
== NULL
) {
perror("Couldn't allocate memory for transposition table. \n");
/* Clear the transposition table. */
tt_clear(Transposition_table
*table
)
memset(table
->entries
, 0, table
->num_entries
* sizeof(table
->entries
[0]));
/* Free the transposition table. */
tt_free(Transposition_table
*table
)
/* Get result and move. Return value:
* 1 if found, but depth too 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.
tt_get(Transposition_table
*table
,
int target1
, int target2
, int remaining_depth
,
int *value1
, int *value2
, int *move
)
if (remaining_depth
< 0 || remaining_depth
> HN_MAX_REMAINING_DEPTH
)
/* Get the combined hash value. */
calculate_hashval_for_tt(&hashval
, routine
, target1
, target2
, extra_hash
);
/* Get the correct entry and node. */
entry
= &table
->entries
[hashdata_remainder(hashval
, table
->num_entries
)];
if (hashdata_is_equal(hashval
, entry
->deepest
.key
))
else if (hashdata_is_equal(hashval
, entry
->newest
.key
))
stats
.read_result_hits
++;
/* 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.
*move
= hn_get_move(node
->data
);
if (remaining_depth
<= (int) hn_get_remaining_depth(node
->data
)) {
*value1
= hn_get_value1(node
->data
);
*value2
= hn_get_value2(node
->data
);
stats
.trusted_read_result_hits
++;
/* Update a transposition table entry.
tt_update(Transposition_table
*table
,
enum routine_id routine
, int target1
, int target2
,
int remaining_depth
, Hash_data
*extra_hash
,
int value1
, int value2
, int move
)
/* Get routine costs definitions from liberty.h. */
static const int routine_costs
[] = { ROUTINE_COSTS
};
gg_assert(routine_costs
[NUM_CACHE_ROUTINES
] == -1);
if (remaining_depth
< 0 || remaining_depth
> HN_MAX_REMAINING_DEPTH
)
/* Get the combined hash value. */
calculate_hashval_for_tt(&hashval
, routine
, target1
, target2
, extra_hash
);
data
= hn_create_data(remaining_depth
, value1
, value2
, move
,
/* Get the entry and nodes. */
entry
= &table
->entries
[hashdata_remainder(hashval
, table
->num_entries
)];
deepest
= &entry
->deepest
;
/* See if we found an already existing node. */
if (hashdata_is_equal(hashval
, deepest
->key
)
&& remaining_depth
>= (int) hn_get_remaining_depth(deepest
->data
)) {
else if (hashdata_is_equal(hashval
, newest
->key
)
&& remaining_depth
>= (int) hn_get_remaining_depth(newest
->data
)) {
/* If newest has become deeper than deepest, then switch them. */
if (hn_get_remaining_depth(newest
->data
)
> hn_get_remaining_depth(deepest
->data
)) {
else if (hn_get_total_cost(data
) > hn_get_total_cost(deepest
->data
)) {
if (hn_get_total_cost(newest
->data
) < hn_get_total_cost(deepest
->data
))
stats
.read_result_entered
++;
static const char *routine_names
[] = {
/* Convert a routine as used in the cache table to a string. */
routine_id_to_string(enum routine_id routine
)
return routine_names
[(int) routine
];
/* Initialize the cache for read results, using at most the given
* number of bytes of memory. If the memory isn't sufficient to
* allocate a single node or if the allocation fails, the caching is
reading_cache_init(int bytes
)
/* Clear the cache for read results. */
reading_cache_default_size()
return DEFAULT_NUMBER_OF_CACHE_ENTRIES
* sizeof(Hashentry
) / 1024.0 / 1024.0;
/* Write reading trace data to an SGF file. Normally called through the
* macro SGFTRACE in cache.h.
sgf_trace(const char *func
, int str
, int move
, int result
,
sprintf(buf
, "%s %c%d: ", func
, J(str
) + 'A' + (J(str
) >= 8),
sprintf(buf
+ strlen(buf
), "0");
sprintf(buf
+ strlen(buf
), "%s %c%d", result_to_string(result
),
J(move
) + 'A' + (J(move
) >= 8),
sprintf(buf
+ strlen(buf
), "%s PASS", result_to_string(result
));
sprintf(buf
+ strlen(buf
), "%s [%d]", result_to_string(result
), move
);
sprintf(buf
+ strlen(buf
), " (%s)", message
);
sgftreeAddComment(sgf_dumptree
, buf
);
/* Write two group reading (connection) trace data to an SGF file.
* Normally called through the macro SGFTRACE2 in cache.h.
sgf_trace2(const char *func
, int str1
, int str2
, int move
,
const char *result
, const char *message
)
sprintf(buf
, "%s %c%d %c%d: ", func
,
J(str1
) + 'A' + (J(str1
) >= 8), board_size
- I(str1
),
J(str2
) + 'A' + (J(str2
) >= 8), board_size
- I(str2
));
sprintf(buf
+ strlen(buf
), "%s %c%d", result
,
J(move
) + 'A' + (J(move
) >= 8),
sprintf(buf
+ strlen(buf
), "%s PASS", result
);
sprintf(buf
+ strlen(buf
), "%s [%d]", result
, move
);
sprintf(buf
+ strlen(buf
), " (%s)", message
);
sgftreeAddComment(sgf_dumptree
, buf
);
/* Write semeai reading trace data to an SGF file. Normally called
* through the macro SGFTRACE_SEMEAI in cache.h.
sgf_trace_semeai(const char *func
, int str1
, int str2
, int move
,
int result1
, int result2
, const char *message
)
sprintf(buf
, "%s %c%d %c%d: ", func
,
J(str1
) + 'A' + (J(str1
) >= 8), board_size
- I(str1
),
J(str2
) + 'A' + (J(str2
) >= 8), board_size
- I(str2
));
sprintf(buf
+ strlen(buf
), "%s %s %c%d",
result_to_string(result1
), result_to_string(result2
),
J(move
) + 'A' + (J(move
) >= 8), board_size
- I(move
));
sprintf(buf
+ strlen(buf
), "%s %s PASS",
result_to_string(result1
), result_to_string(result2
));
sprintf(buf
+ strlen(buf
), "%s %s [%d]",
result_to_string(result1
), result_to_string(result2
),
sprintf(buf
+ strlen(buf
), " (%s)", message
);
sgftreeAddComment(sgf_dumptree
, buf
);