| 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 | #ifndef _CACHE_H_ |
| 25 | #define _CACHE_H_ |
| 26 | |
| 27 | #include <stdio.h> |
| 28 | #include "hash.h" |
| 29 | |
| 30 | /* |
| 31 | * This file, together with engine/hash.c implements hashing of go positions |
| 32 | * using a method known as Zobrist hashing. See the Texinfo documentation |
| 33 | * (Reading/Hashing) for more information. |
| 34 | */ |
| 35 | |
| 36 | |
| 37 | /* Hashnode: a node stored in the transposition table. |
| 38 | * |
| 39 | * In addition to the position, the hash lock encodes the following data, |
| 40 | * all hashed: |
| 41 | * komaster |
| 42 | * kom_pos |
| 43 | * routine |
| 44 | * str1 |
| 45 | * str2 |
| 46 | * extra hashvalue, optional (e.g. encoding a goal array) |
| 47 | * |
| 48 | * The data field packs into 32 bits the following |
| 49 | * fields: |
| 50 | * |
| 51 | * RESERVED : 5 bits |
| 52 | * value1 : 4 bits |
| 53 | * value2 : 4 bits |
| 54 | * move : 10 bits |
| 55 | * cost : 4 bits |
| 56 | * remaining_depth: 5 bits (depth - stackp) NOTE: HN_MAX_REMAINING_DEPTH |
| 57 | * |
| 58 | * The last 9 bits together give an index for the total costs. |
| 59 | */ |
| 60 | typedef struct { |
| 61 | Hash_data key; |
| 62 | unsigned int data; /* Should be 32 bits, but only wastes 25% if 64 bits. */ |
| 63 | } Hashnode; |
| 64 | |
| 65 | #define HN_MAX_REMAINING_DEPTH 31 |
| 66 | |
| 67 | |
| 68 | /* Hashentry: an entry, with two nodes of the hash_table |
| 69 | */ |
| 70 | typedef struct { |
| 71 | Hashnode deepest; |
| 72 | Hashnode newest; |
| 73 | } Hashentry; |
| 74 | |
| 75 | /* Hn is for hash node. */ |
| 76 | #define hn_get_value1(hn) ((hn >> 23) & 0x0f) |
| 77 | #define hn_get_value2(hn) ((hn >> 19) & 0x0f) |
| 78 | #define hn_get_move(hn) ((hn >> 9) & 0x3ff) |
| 79 | #define hn_get_cost(hn) ((hn >> 5) & 0x0f) |
| 80 | #define hn_get_remaining_depth(hn) ((hn >> 0) & 0x1f) |
| 81 | #define hn_get_total_cost(hn) ((hn >> 0) & 0x1ff) |
| 82 | |
| 83 | #define hn_create_data(remaining_depth, value1, value2, move, cost) \ |
| 84 | ((((value1) & 0x0f) << 23) \ |
| 85 | | (((value2) & 0x0f) << 19) \ |
| 86 | | (((move) & 0x3ff) << 9) \ |
| 87 | | (((cost) & 0x0f) << 5) \ |
| 88 | | (((remaining_depth & 0x1f) << 0))) |
| 89 | |
| 90 | |
| 91 | /* Transposition_table: transposition table used for caching. */ |
| 92 | typedef struct { |
| 93 | unsigned int num_entries; |
| 94 | Hashentry *entries; |
| 95 | int is_clean; |
| 96 | } Transposition_table; |
| 97 | |
| 98 | extern Transposition_table ttable; |
| 99 | |
| 100 | /* Number of cache entries to use by default if no cache memory usage |
| 101 | * has been set explicitly. |
| 102 | */ |
| 103 | #define DEFAULT_NUMBER_OF_CACHE_ENTRIES 350000 |
| 104 | |
| 105 | void tt_free(Transposition_table *table); |
| 106 | int tt_get(Transposition_table *table, enum routine_id routine, |
| 107 | int target1, int target2, int remaining_depth, |
| 108 | Hash_data *extra_hash, |
| 109 | int *value1, int *value2, int *move); |
| 110 | void tt_update(Transposition_table *table, enum routine_id routine, |
| 111 | int target, int target2, int remaining_depth, |
| 112 | Hash_data *extra_hash, |
| 113 | int value1, int value2, int move); |
| 114 | |
| 115 | |
| 116 | /* ================================================================ */ |
| 117 | |
| 118 | |
| 119 | /* Macros used from reading.c, readconnect.c, and owl.c to store and |
| 120 | * retrieve read results. |
| 121 | */ |
| 122 | |
| 123 | #if TRACE_READ_RESULTS |
| 124 | |
| 125 | #define TRACE_CACHED_RESULT(result, move) \ |
| 126 | gprintf("%o%s %1m %d %d %1m (cached) ", read_function_name, \ |
| 127 | q, stackp, result, move); \ |
| 128 | dump_stack(); |
| 129 | |
| 130 | #define TRACE_CACHED_RESULT2(result1, result2, move) \ |
| 131 | gprintf("%o%s %1m %1m %d %d %d %1m (cached) ", read_function_name, \ |
| 132 | q1, q2, stackp, result1, result2, move); \ |
| 133 | dump_stack(); |
| 134 | |
| 135 | |
| 136 | #define SETUP_TRACE_INFO(name, str) \ |
| 137 | const char *read_function_name = name; \ |
| 138 | int q = find_origin(str); |
| 139 | |
| 140 | #define SETUP_TRACE_INFO2(name, str1, str2) \ |
| 141 | const char *read_function_name = name; \ |
| 142 | int q1 = board[str1] == EMPTY ? str1 : find_origin(str1); \ |
| 143 | int q2 = board[str2] == EMPTY ? str2 : find_origin(str2); |
| 144 | |
| 145 | #else |
| 146 | |
| 147 | #define TRACE_CACHED_RESULT(result, move) |
| 148 | #define TRACE_CACHED_RESULT2(result1, result2, move) |
| 149 | |
| 150 | #define SETUP_TRACE_INFO(name, str) \ |
| 151 | const char *read_function_name = name; \ |
| 152 | int q = str; |
| 153 | |
| 154 | #define SETUP_TRACE_INFO2(name, str1, str2) \ |
| 155 | const char *read_function_name = name; \ |
| 156 | int q1 = str1; \ |
| 157 | int q2 = str2; |
| 158 | |
| 159 | #endif |
| 160 | |
| 161 | /* Trace messages in decidestring/decidedragon sgf file. */ |
| 162 | void sgf_trace(const char *func, int str, int move, int result, |
| 163 | const char *message); |
| 164 | /* Trace messages in decideconnection sgf file. */ |
| 165 | void sgf_trace2(const char *func, int str1, int str2, int move, |
| 166 | const char *result, const char *message); |
| 167 | /* Trace messages in decidesemeai sgf file. */ |
| 168 | void sgf_trace_semeai(const char *func, int str1, int str2, int move, |
| 169 | int result1, int result2, const char *message); |
| 170 | |
| 171 | /* Macro to hide the call to sgf_trace(). Notice that a little black |
| 172 | * magic is going on here. Before using this macro, SETUP_TRACE_INFO |
| 173 | * must have been called to provide the variables read_function_name |
| 174 | * and q. These must of course not be used for anything else in |
| 175 | * the function. |
| 176 | */ |
| 177 | #define SGFTRACE(move, result, message) \ |
| 178 | if (sgf_dumptree) \ |
| 179 | sgf_trace(read_function_name, q, move, result, message) |
| 180 | |
| 181 | /* Corresponding macro for use in connection or semeai reading, where |
| 182 | * two groups are involved. |
| 183 | */ |
| 184 | #define SGFTRACE2(move, result, message) \ |
| 185 | if (sgf_dumptree) \ |
| 186 | sgf_trace2(read_function_name, q1, q2, move, \ |
| 187 | result_to_string(result), message) |
| 188 | |
| 189 | #define SGFTRACE_SEMEAI(move, result1, result2, message) \ |
| 190 | if (sgf_dumptree) \ |
| 191 | sgf_trace_semeai(read_function_name, q1, q2, move, \ |
| 192 | result1, result2, message) |
| 193 | |
| 194 | |
| 195 | /* ================================================================ */ |
| 196 | |
| 197 | /* |
| 198 | * These macros should be used in all the places where we want to |
| 199 | * return a result from a reading function and where we want to |
| 200 | * store the result in the hash table at the same time. |
| 201 | */ |
| 202 | |
| 203 | #if !TRACE_READ_RESULTS |
| 204 | |
| 205 | #define READ_RETURN0(routine, str, remaining_depth) \ |
| 206 | do { \ |
| 207 | tt_update(&ttable, routine, str, NO_MOVE, remaining_depth, NULL,\ |
| 208 | 0, 0, NO_MOVE);\ |
| 209 | return 0; \ |
| 210 | } while (0) |
| 211 | |
| 212 | #define READ_RETURN(routine, str, remaining_depth, point, move, value) \ |
| 213 | do { \ |
| 214 | tt_update(&ttable, routine, str, NO_MOVE, remaining_depth, NULL,\ |
| 215 | value, 0, move);\ |
| 216 | if ((value) != 0 && (point) != 0) *(point) = (move); \ |
| 217 | return (value); \ |
| 218 | } while (0) |
| 219 | |
| 220 | #define READ_RETURN_SEMEAI(routine, str1, str2, remaining_depth, point, move, value1, value2) \ |
| 221 | do { \ |
| 222 | tt_update(&ttable, routine, str1, str2, remaining_depth, NULL, \ |
| 223 | value1, value2, move); \ |
| 224 | if ((value1) != 0 && (point) != 0) *(point) = (move); \ |
| 225 | return; \ |
| 226 | } while (0) |
| 227 | |
| 228 | #define READ_RETURN_CONN(routine, str1, str2, remaining_depth, point, move, value) \ |
| 229 | do { \ |
| 230 | tt_update(&ttable, routine, str1, str2, remaining_depth, NULL,\ |
| 231 | value, 0, move);\ |
| 232 | if ((value) != 0 && (point) != 0) *(point) = (move); \ |
| 233 | return (value); \ |
| 234 | } while (0) |
| 235 | |
| 236 | #define READ_RETURN_HASH(routine, str, remaining_depth, hash, point, move, value) \ |
| 237 | do { \ |
| 238 | tt_update(&ttable, routine, str, NO_MOVE, remaining_depth, hash,\ |
| 239 | value, 0, move);\ |
| 240 | if ((value) != 0 && (point) != 0) *(point) = (move); \ |
| 241 | return (value); \ |
| 242 | } while (0) |
| 243 | |
| 244 | #define READ_RETURN2(routine, str, remaining_depth, point, move, value1, value2) \ |
| 245 | do { \ |
| 246 | tt_update(&ttable, routine, str, NO_MOVE, remaining_depth, NULL,\ |
| 247 | value1, value2, move);\ |
| 248 | if ((value1) != 0 && (point) != 0) *(point) = (move); \ |
| 249 | return (value1); \ |
| 250 | } while (0) |
| 251 | |
| 252 | #else /* !TRACE_READ_RESULTS */ |
| 253 | |
| 254 | #define READ_RETURN0(routine, str, remaining_depth) \ |
| 255 | do { \ |
| 256 | tt_update(&ttable, routine, str, NO_MOVE, remaining_depth, NULL,\ |
| 257 | 0, 0, NO_MOVE);\ |
| 258 | gprintf("%o%s %1m %d 0 0 ", read_function_name, q, stackp); \ |
| 259 | dump_stack(); \ |
| 260 | return 0; \ |
| 261 | } while (0) |
| 262 | |
| 263 | #define READ_RETURN(routine, str, remaining_depth, point, move, value) \ |
| 264 | do { \ |
| 265 | tt_update(&ttable, routine, str, NO_MOVE, remaining_depth, NULL,\ |
| 266 | value, 0, move);\ |
| 267 | if ((value) != 0 && (point) != 0) *(point) = (move); \ |
| 268 | gprintf("%o%s %1m %d %d %1m ", read_function_name, q, stackp, \ |
| 269 | (value), (move)); \ |
| 270 | dump_stack(); \ |
| 271 | return (value); \ |
| 272 | } while (0) |
| 273 | |
| 274 | #define READ_RETURN_SEMEAI(routine, str1, str2, remaining_depth, point, move, value1, value2) \ |
| 275 | do { \ |
| 276 | tt_update(&ttable, routine, str1, str2, remaining_depth, NULL, \ |
| 277 | value1, value2, move); \ |
| 278 | if ((value1) != 0 && (point) != 0) *(point) = (move); \ |
| 279 | gprintf("%o%s %1m %1m %d %d %d %1m ", read_function_name, q1, q2, stackp, \ |
| 280 | (value1), (value2), (move)); \ |
| 281 | dump_stack(); \ |
| 282 | return; \ |
| 283 | } while (0) |
| 284 | |
| 285 | #define READ_RETURN_CONN(routine, str1, str2, remaining_depth, point, move, value) \ |
| 286 | do { \ |
| 287 | tt_update(&ttable, routine, str1, str2, remaining_depth, NULL,\ |
| 288 | value, 0, move);\ |
| 289 | if ((value) != 0 && (point) != 0) *(point) = (move); \ |
| 290 | gprintf("%o%s %1m %1m %d %d %1m ", read_function_name, q1, q2, stackp, \ |
| 291 | (value), (move)); \ |
| 292 | dump_stack(); \ |
| 293 | return (value); \ |
| 294 | } while (0) |
| 295 | |
| 296 | #define READ_RETURN_HASH(routine, str, remaining_depth, hash, point, move, value) \ |
| 297 | do { \ |
| 298 | tt_update(&ttable, routine, str, NO_MOVE, remaining_depth, hash,\ |
| 299 | value, 0, move);\ |
| 300 | if ((value) != 0 && (point) != 0) *(point) = (move); \ |
| 301 | gprintf("%o%s %1m %d %d %1m ", read_function_name, q, stackp, \ |
| 302 | (value), (move)); \ |
| 303 | dump_stack(); \ |
| 304 | return (value); \ |
| 305 | } while (0) |
| 306 | |
| 307 | #define READ_RETURN2(routine, str, remaining_depth, point, move, value1, value2) \ |
| 308 | do { \ |
| 309 | tt_update(&ttable, routine, str, NO_MOVE, remaining_depth, NULL,\ |
| 310 | value1, value2, move);\ |
| 311 | if ((value1) != 0 && (point) != 0) *(point) = (move); \ |
| 312 | gprintf("%o%s %1m %d %d %1m ", read_function_name, q, stackp, \ |
| 313 | (value1), (move)); \ |
| 314 | dump_stack(); \ |
| 315 | return (value1); \ |
| 316 | } while (0) |
| 317 | |
| 318 | #endif |
| 319 | |
| 320 | |
| 321 | /* ================================================================ */ |
| 322 | /* This has actually nothing to do with caching, but is useful in |
| 323 | * the same places where the caching is. |
| 324 | */ |
| 325 | |
| 326 | /* Macro to use when saving ko results while continuing to look for an |
| 327 | * unconditional result. It's assumed that we have tried the move at |
| 328 | * (move) and then called an attack or defense function giving the |
| 329 | * result passed in the code parameter. |
| 330 | * |
| 331 | * In general we prefer not to have to do the first ko threat. Thus a |
| 332 | * savecode KO_A is always better than a savecode KO_B. Also we always |
| 333 | * prefer to keep the old move if we get the same savecode once more, |
| 334 | * on the assumption that the moves have been ordered with the |
| 335 | * presumably best one first. |
| 336 | * |
| 337 | * Notice that the savecode may be either 0 (nothing found so far), KO_B |
| 338 | * or KO_A. Occasionally savecode WIN is also used, indicating an effective |
| 339 | * but not preferred move, typically because it's either a sacrifice |
| 340 | * or a backfilling move. If possible, we prefer making non-sacrifice |
| 341 | * and direct moves. Of course savecode WIN is better than KO_A or KO_B. |
| 342 | */ |
| 343 | |
| 344 | #define UPDATE_SAVED_KO_RESULT(savecode, save, code, move) \ |
| 345 | if (code != 0 && REVERSE_RESULT(code) > savecode) { \ |
| 346 | save = move; \ |
| 347 | savecode = REVERSE_RESULT(code); \ |
| 348 | } \ |
| 349 | |
| 350 | /* Same as above, except this should be used when there's no |
| 351 | * intervening trymove(). Thus we shouldn't reverse the save code. |
| 352 | */ |
| 353 | #define UPDATE_SAVED_KO_RESULT_UNREVERSED(savecode, save, code, move) \ |
| 354 | if (code != WIN && code > savecode) { \ |
| 355 | save = move; \ |
| 356 | savecode = code; \ |
| 357 | } |
| 358 | |
| 359 | |
| 360 | /* This too isn't really related to caching but is convenient to have here. |
| 361 | * (Needs to be available in reading.c and persistent.c.) |
| 362 | * |
| 363 | * Minimum number of nodes for which DEBUG_READING_PERFORMANCE reports |
| 364 | * anything. |
| 365 | */ |
| 366 | #define MIN_READING_NODES_TO_REPORT 1000 |
| 367 | |
| 368 | |
| 369 | #endif /* _CACHE_H_ */ |
| 370 | |
| 371 | |
| 372 | /* |
| 373 | * Local Variables: |
| 374 | * tab-width: 8 |
| 375 | * c-basic-offset: 2 |
| 376 | * End: |
| 377 | */ |