| 1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
| 2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * |
| 3 | * http://www.gnu.org/software/gnugo/ for more information. * |
| 4 | * * |
| 5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * |
| 6 | * 2008 and 2009 by the Free Software Foundation. * |
| 7 | * * |
| 8 | * This program is free software; you can redistribute it and/or * |
| 9 | * modify it under the terms of the GNU General Public License as * |
| 10 | * published by the Free Software Foundation - version 3 or * |
| 11 | * (at your option) any later version. * |
| 12 | * * |
| 13 | * This program is distributed in the hope that it will be useful, * |
| 14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * |
| 15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * |
| 16 | * GNU General Public License in file COPYING for more details. * |
| 17 | * * |
| 18 | * You should have received a copy of the GNU General Public * |
| 19 | * License along with this program; if not, write to the Free * |
| 20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * |
| 21 | * Boston, MA 02111, USA. * |
| 22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
| 23 | |
| 24 | |
| 25 | #include "random.h" |
| 26 | #include "gnugo.h" |
| 27 | |
| 28 | #include <stdio.h> |
| 29 | #include <stdlib.h> |
| 30 | #include <limits.h> |
| 31 | #include <string.h> |
| 32 | |
| 33 | #include "liberty.h" |
| 34 | #include "cache.h" |
| 35 | #include "sgftree.h" |
| 36 | |
| 37 | |
| 38 | /* ================================================================ */ |
| 39 | /* The transposition table */ |
| 40 | /* ---------------------------------------------------------------- */ |
| 41 | |
| 42 | static void tt_init(Transposition_table *table, int memsize); |
| 43 | static void tt_clear(Transposition_table *table); |
| 44 | |
| 45 | /* The transposition table itself. */ |
| 46 | Transposition_table ttable; |
| 47 | |
| 48 | |
| 49 | /* Arrays with random numbers for Zobrist hashing of input data (other |
| 50 | * than the board position). If you add an array here, do not forget |
| 51 | * to also initialize it in keyhash_init() below. |
| 52 | */ |
| 53 | static Hash_data target1_hash[BOARDMAX]; |
| 54 | static Hash_data target2_hash[BOARDMAX]; |
| 55 | static Hash_data routine_hash[NUM_CACHE_ROUTINES]; |
| 56 | |
| 57 | static void |
| 58 | keyhash_init(void) |
| 59 | { |
| 60 | static int is_initialized = 0; |
| 61 | |
| 62 | if (!is_initialized) { |
| 63 | |
| 64 | INIT_ZOBRIST_ARRAY(target1_hash); |
| 65 | INIT_ZOBRIST_ARRAY(target2_hash); |
| 66 | INIT_ZOBRIST_ARRAY(routine_hash); |
| 67 | |
| 68 | is_initialized = 1; |
| 69 | } |
| 70 | } |
| 71 | |
| 72 | static void |
| 73 | calculate_hashval_for_tt(Hash_data *hashdata, int routine, int target1, |
| 74 | int target2, Hash_data *extra_hash) |
| 75 | { |
| 76 | *hashdata = board_hash; /* from globals.c */ |
| 77 | hashdata_xor(*hashdata, routine_hash[routine]); |
| 78 | hashdata_xor(*hashdata, target1_hash[target1]); |
| 79 | if (target2 != NO_MOVE) |
| 80 | hashdata_xor(*hashdata, target2_hash[target2]); |
| 81 | if (extra_hash) |
| 82 | hashdata_xor(*hashdata, *extra_hash); |
| 83 | } |
| 84 | |
| 85 | |
| 86 | |
| 87 | /* Initialize the transposition table. Non-positive memsize means use |
| 88 | * the default size of DEFAULT_NUMBER_OF_CACHE_ENTRIES entries. |
| 89 | */ |
| 90 | |
| 91 | static void |
| 92 | tt_init(Transposition_table *table, int memsize) |
| 93 | { |
| 94 | int num_entries; |
| 95 | |
| 96 | /* Make sure the hash system is initialized. */ |
| 97 | hash_init(); |
| 98 | keyhash_init(); |
| 99 | |
| 100 | if (memsize > 0) |
| 101 | num_entries = memsize / sizeof(table->entries[0]); |
| 102 | else |
| 103 | num_entries = DEFAULT_NUMBER_OF_CACHE_ENTRIES; |
| 104 | |
| 105 | table->num_entries = num_entries; |
| 106 | table->entries = malloc(num_entries * sizeof(table->entries[0])); |
| 107 | |
| 108 | if (table->entries == NULL) { |
| 109 | perror("Couldn't allocate memory for transposition table. \n"); |
| 110 | exit(1); |
| 111 | } |
| 112 | |
| 113 | table->is_clean = 0; |
| 114 | tt_clear(table); |
| 115 | } |
| 116 | |
| 117 | |
| 118 | /* Clear the transposition table. */ |
| 119 | |
| 120 | static void |
| 121 | tt_clear(Transposition_table *table) |
| 122 | { |
| 123 | if (!table->is_clean) { |
| 124 | memset(table->entries, 0, table->num_entries * sizeof(table->entries[0])); |
| 125 | table->is_clean = 1; |
| 126 | } |
| 127 | } |
| 128 | |
| 129 | |
| 130 | /* Free the transposition table. */ |
| 131 | |
| 132 | void |
| 133 | tt_free(Transposition_table *table) |
| 134 | { |
| 135 | free(table->entries); |
| 136 | } |
| 137 | |
| 138 | |
| 139 | /* Get result and move. Return value: |
| 140 | * 0 if not found |
| 141 | * 1 if found, but depth too small to be trusted. In this case the move |
| 142 | * can be used for move ordering. |
| 143 | * 2 if found and depth is enough so that the result can be trusted. |
| 144 | */ |
| 145 | |
| 146 | int |
| 147 | tt_get(Transposition_table *table, |
| 148 | enum routine_id routine, |
| 149 | int target1, int target2, int remaining_depth, |
| 150 | Hash_data *extra_hash, |
| 151 | int *value1, int *value2, int *move) |
| 152 | { |
| 153 | Hash_data hashval; |
| 154 | Hashentry *entry; |
| 155 | Hashnode *node; |
| 156 | |
| 157 | /* Sanity check. */ |
| 158 | if (remaining_depth < 0 || remaining_depth > HN_MAX_REMAINING_DEPTH) |
| 159 | return 0; |
| 160 | |
| 161 | /* Get the combined hash value. */ |
| 162 | calculate_hashval_for_tt(&hashval, routine, target1, target2, extra_hash); |
| 163 | |
| 164 | /* Get the correct entry and node. */ |
| 165 | entry = &table->entries[hashdata_remainder(hashval, table->num_entries)]; |
| 166 | if (hashdata_is_equal(hashval, entry->deepest.key)) |
| 167 | node = &entry->deepest; |
| 168 | else if (hashdata_is_equal(hashval, entry->newest.key)) |
| 169 | node = &entry->newest; |
| 170 | else |
| 171 | return 0; |
| 172 | |
| 173 | stats.read_result_hits++; |
| 174 | |
| 175 | /* Return data. Only set the result if remaining depth in the table |
| 176 | * is big enough to be trusted. The move can always be used for move |
| 177 | * ordering if nothing else. |
| 178 | */ |
| 179 | if (move) |
| 180 | *move = hn_get_move(node->data); |
| 181 | if (remaining_depth <= (int) hn_get_remaining_depth(node->data)) { |
| 182 | if (value1) |
| 183 | *value1 = hn_get_value1(node->data); |
| 184 | if (value2) |
| 185 | *value2 = hn_get_value2(node->data); |
| 186 | stats.trusted_read_result_hits++; |
| 187 | return 2; |
| 188 | } |
| 189 | |
| 190 | return 1; |
| 191 | } |
| 192 | |
| 193 | |
| 194 | /* Update a transposition table entry. |
| 195 | */ |
| 196 | |
| 197 | void |
| 198 | tt_update(Transposition_table *table, |
| 199 | enum routine_id routine, int target1, int target2, |
| 200 | int remaining_depth, Hash_data *extra_hash, |
| 201 | int value1, int value2, int move) |
| 202 | { |
| 203 | Hash_data hashval; |
| 204 | Hashentry *entry; |
| 205 | Hashnode *deepest; |
| 206 | Hashnode *newest; |
| 207 | unsigned int data; |
| 208 | /* Get routine costs definitions from liberty.h. */ |
| 209 | static const int routine_costs[] = { ROUTINE_COSTS }; |
| 210 | gg_assert(routine_costs[NUM_CACHE_ROUTINES] == -1); |
| 211 | |
| 212 | /* Sanity check. */ |
| 213 | if (remaining_depth < 0 || remaining_depth > HN_MAX_REMAINING_DEPTH) |
| 214 | return; |
| 215 | |
| 216 | /* Get the combined hash value. */ |
| 217 | calculate_hashval_for_tt(&hashval, routine, target1, target2, extra_hash); |
| 218 | |
| 219 | data = hn_create_data(remaining_depth, value1, value2, move, |
| 220 | routine_costs[routine]); |
| 221 | |
| 222 | /* Get the entry and nodes. */ |
| 223 | entry = &table->entries[hashdata_remainder(hashval, table->num_entries)]; |
| 224 | deepest = &entry->deepest; |
| 225 | newest = &entry->newest; |
| 226 | |
| 227 | /* See if we found an already existing node. */ |
| 228 | if (hashdata_is_equal(hashval, deepest->key) |
| 229 | && remaining_depth >= (int) hn_get_remaining_depth(deepest->data)) { |
| 230 | |
| 231 | /* Found deepest */ |
| 232 | deepest->data = data; |
| 233 | |
| 234 | } |
| 235 | else if (hashdata_is_equal(hashval, newest->key) |
| 236 | && remaining_depth >= (int) hn_get_remaining_depth(newest->data)) { |
| 237 | |
| 238 | /* Found newest */ |
| 239 | newest->data = data; |
| 240 | |
| 241 | /* If newest has become deeper than deepest, then switch them. */ |
| 242 | if (hn_get_remaining_depth(newest->data) |
| 243 | > hn_get_remaining_depth(deepest->data)) { |
| 244 | Hashnode temp; |
| 245 | |
| 246 | temp = *deepest; |
| 247 | *deepest = *newest; |
| 248 | *newest = temp; |
| 249 | } |
| 250 | |
| 251 | } |
| 252 | else if (hn_get_total_cost(data) > hn_get_total_cost(deepest->data)) { |
| 253 | if (hn_get_total_cost(newest->data) < hn_get_total_cost(deepest->data)) |
| 254 | *newest = *deepest; |
| 255 | deepest->key = hashval; |
| 256 | deepest->data = data; |
| 257 | } |
| 258 | else { |
| 259 | /* Replace newest. */ |
| 260 | newest->key = hashval; |
| 261 | newest->data = data; |
| 262 | } |
| 263 | |
| 264 | stats.read_result_entered++; |
| 265 | table->is_clean = 0; |
| 266 | } |
| 267 | |
| 268 | |
| 269 | static const char *routine_names[] = { |
| 270 | ROUTINE_NAMES |
| 271 | }; |
| 272 | |
| 273 | /* Convert a routine as used in the cache table to a string. */ |
| 274 | const char * |
| 275 | routine_id_to_string(enum routine_id routine) |
| 276 | { |
| 277 | return routine_names[(int) routine]; |
| 278 | } |
| 279 | |
| 280 | |
| 281 | /* Initialize the cache for read results, using at most the given |
| 282 | * number of bytes of memory. If the memory isn't sufficient to |
| 283 | * allocate a single node or if the allocation fails, the caching is |
| 284 | * disabled. |
| 285 | */ |
| 286 | void |
| 287 | reading_cache_init(int bytes) |
| 288 | { |
| 289 | tt_init(&ttable, bytes); |
| 290 | } |
| 291 | |
| 292 | |
| 293 | /* Clear the cache for read results. */ |
| 294 | void |
| 295 | reading_cache_clear() |
| 296 | { |
| 297 | tt_clear(&ttable); |
| 298 | } |
| 299 | |
| 300 | float |
| 301 | reading_cache_default_size() |
| 302 | { |
| 303 | return DEFAULT_NUMBER_OF_CACHE_ENTRIES * sizeof(Hashentry) / 1024.0 / 1024.0; |
| 304 | } |
| 305 | |
| 306 | |
| 307 | /* Write reading trace data to an SGF file. Normally called through the |
| 308 | * macro SGFTRACE in cache.h. |
| 309 | */ |
| 310 | |
| 311 | void |
| 312 | sgf_trace(const char *func, int str, int move, int result, |
| 313 | const char *message) |
| 314 | { |
| 315 | char buf[100]; |
| 316 | |
| 317 | sprintf(buf, "%s %c%d: ", func, J(str) + 'A' + (J(str) >= 8), |
| 318 | board_size - I(str)); |
| 319 | |
| 320 | if (result == 0) |
| 321 | sprintf(buf + strlen(buf), "0"); |
| 322 | else if (ON_BOARD(move)) |
| 323 | sprintf(buf + strlen(buf), "%s %c%d", result_to_string(result), |
| 324 | J(move) + 'A' + (J(move) >= 8), |
| 325 | board_size - I(move)); |
| 326 | else if (is_pass(move)) |
| 327 | sprintf(buf + strlen(buf), "%s PASS", result_to_string(result)); |
| 328 | else |
| 329 | sprintf(buf + strlen(buf), "%s [%d]", result_to_string(result), move); |
| 330 | |
| 331 | if (message) |
| 332 | sprintf(buf + strlen(buf), " (%s)", message); |
| 333 | |
| 334 | sgftreeAddComment(sgf_dumptree, buf); |
| 335 | } |
| 336 | |
| 337 | /* Write two group reading (connection) trace data to an SGF file. |
| 338 | * Normally called through the macro SGFTRACE2 in cache.h. |
| 339 | */ |
| 340 | |
| 341 | void |
| 342 | sgf_trace2(const char *func, int str1, int str2, int move, |
| 343 | const char *result, const char *message) |
| 344 | { |
| 345 | char buf[100]; |
| 346 | |
| 347 | sprintf(buf, "%s %c%d %c%d: ", func, |
| 348 | J(str1) + 'A' + (J(str1) >= 8), board_size - I(str1), |
| 349 | J(str2) + 'A' + (J(str2) >= 8), board_size - I(str2)); |
| 350 | |
| 351 | if (ON_BOARD(move)) |
| 352 | sprintf(buf + strlen(buf), "%s %c%d", result, |
| 353 | J(move) + 'A' + (J(move) >= 8), |
| 354 | board_size - I(move)); |
| 355 | else if (is_pass(move)) |
| 356 | sprintf(buf + strlen(buf), "%s PASS", result); |
| 357 | else |
| 358 | sprintf(buf + strlen(buf), "%s [%d]", result, move); |
| 359 | |
| 360 | if (message) |
| 361 | sprintf(buf + strlen(buf), " (%s)", message); |
| 362 | |
| 363 | sgftreeAddComment(sgf_dumptree, buf); |
| 364 | } |
| 365 | |
| 366 | /* Write semeai reading trace data to an SGF file. Normally called |
| 367 | * through the macro SGFTRACE_SEMEAI in cache.h. |
| 368 | */ |
| 369 | |
| 370 | void |
| 371 | sgf_trace_semeai(const char *func, int str1, int str2, int move, |
| 372 | int result1, int result2, const char *message) |
| 373 | { |
| 374 | char buf[100]; |
| 375 | |
| 376 | sprintf(buf, "%s %c%d %c%d: ", func, |
| 377 | J(str1) + 'A' + (J(str1) >= 8), board_size - I(str1), |
| 378 | J(str2) + 'A' + (J(str2) >= 8), board_size - I(str2)); |
| 379 | |
| 380 | if (ON_BOARD(move)) |
| 381 | sprintf(buf + strlen(buf), "%s %s %c%d", |
| 382 | result_to_string(result1), result_to_string(result2), |
| 383 | J(move) + 'A' + (J(move) >= 8), board_size - I(move)); |
| 384 | else if (is_pass(move)) |
| 385 | sprintf(buf + strlen(buf), "%s %s PASS", |
| 386 | result_to_string(result1), result_to_string(result2)); |
| 387 | else |
| 388 | sprintf(buf + strlen(buf), "%s %s [%d]", |
| 389 | result_to_string(result1), result_to_string(result2), |
| 390 | move); |
| 391 | |
| 392 | if (message) |
| 393 | sprintf(buf + strlen(buf), " (%s)", message); |
| 394 | |
| 395 | sgftreeAddComment(sgf_dumptree, buf); |
| 396 | } |
| 397 | |
| 398 | /* |
| 399 | * Local Variables: |
| 400 | * tab-width: 8 |
| 401 | * c-basic-offset: 2 |
| 402 | * End: |
| 403 | */ |