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 */ 378