Commit | Line | Data |
---|---|---|
7eeb782e AT |
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 | */ |