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