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
keyhash_init(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
calculate_hashval_for_tt(Hash_data * hashdata,int routine,int target1,int target2,Hash_data * extra_hash)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
tt_init(Transposition_table * table,int memsize)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
tt_clear(Transposition_table * table)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
tt_free(Transposition_table * table)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
tt_get(Transposition_table * table,enum routine_id routine,int target1,int target2,int remaining_depth,Hash_data * extra_hash,int * value1,int * value2,int * move)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
tt_update(Transposition_table * table,enum routine_id routine,int target1,int target2,int remaining_depth,Hash_data * extra_hash,int value1,int value2,int move)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 *
routine_id_to_string(enum routine_id routine)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
reading_cache_init(int bytes)287 reading_cache_init(int bytes)
288 {
289 tt_init(&ttable, bytes);
290 }
291
292
293 /* Clear the cache for read results. */
294 void
reading_cache_clear()295 reading_cache_clear()
296 {
297 tt_clear(&ttable);
298 }
299
300 float
reading_cache_default_size()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
sgf_trace(const char * func,int str,int move,int result,const char * message)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
sgf_trace2(const char * func,int str1,int str2,int move,const char * result,const char * message)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
sgf_trace_semeai(const char * func,int str1,int str2,int move,int result1,int result2,const char * message)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 */
404