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 _HASH_H_ | |
25 | #define _HASH_H_ | |
26 | ||
27 | #include "config.h" | |
28 | #include <limits.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 | /* Hash values and the compact board representation should use the | |
37 | * longest integer type that the platform can handle efficiently. | |
38 | * Typically this would be a 32 bit integer on a 32 bit platform and a | |
39 | * 64 bit integer on a 64 bit platform. | |
40 | * | |
41 | * Our current assumption is that unsigned long has this | |
42 | * characteristic. Should it turn out to be false for some platform | |
43 | * we'll add conditional code to choose some other type. | |
44 | * | |
45 | * At the few places in the code where the actual size of these types | |
46 | * matter, the code should use sizeof(type) to test for this. Notice | |
47 | * that ISO C guarantees a long to be at least 32 bits. | |
48 | * | |
49 | * On (future) platforms with word length 128 bits or more, it might | |
50 | * be a waste to use more than 64 bit hashvalues, since the decreased | |
51 | * risk for hash collisions probably isn't worth the increased storage | |
52 | * cost. | |
53 | */ | |
54 | typedef unsigned long Hashvalue; | |
55 | #define SIZEOF_HASHVALUE SIZEOF_LONG | |
56 | #define HASHVALUE_PRINT_FORMAT "%0*lx" | |
57 | ||
58 | /* for testing: Enables a lot of checks. */ | |
59 | #define CHECK_HASHING 0 | |
60 | ||
61 | /* Dump (almost) all read results. */ | |
62 | #define TRACE_READ_RESULTS 0 | |
63 | ||
64 | /* How many bits should be used at least for hashing? Set this to 32 for | |
65 | * some memory save and speedup, at the cost of occasional irreproducable | |
66 | * mistakes (and possibly assertion failures). | |
67 | * With 64 bits, there should be less than one such mistake in 10^9 games. | |
68 | * Set this to 96 if this is not safe enough for you. | |
69 | */ | |
70 | #define MIN_HASHBITS 64 | |
71 | ||
72 | #define NUM_HASHVALUES (1 + (MIN_HASHBITS - 1) / (CHAR_BIT * SIZEOF_HASHVALUE)) | |
73 | ||
74 | /* This struct is maintained by the machinery that updates the board | |
75 | * to provide incremental hashing. Examples: trymove(), play_move(), ... | |
76 | */ | |
77 | ||
78 | typedef struct { | |
79 | Hashvalue hashval[NUM_HASHVALUES]; | |
80 | } Hash_data; | |
81 | ||
82 | extern Hash_data board_hash; | |
83 | ||
84 | Hash_data goal_to_hashvalue(const signed char *goal); | |
85 | ||
86 | void hash_init_zobrist_array(Hash_data *array, int size); | |
87 | void hash_init(void); | |
88 | #define INIT_ZOBRIST_ARRAY(a) \ | |
89 | hash_init_zobrist_array(a, (int) (sizeof(a) / sizeof(a[0]))) | |
90 | ||
91 | void hashdata_clear(Hash_data *hd); | |
92 | void hashdata_recalc(Hash_data *hd, Intersection *board, int ko_pos); | |
93 | void hashdata_invert_ko(Hash_data *hd, int pos); | |
94 | void hashdata_invert_stone(Hash_data *hd, int pos, int color); | |
95 | void hashdata_invert_komaster(Hash_data *hd, int komaster); | |
96 | void hashdata_invert_kom_pos(Hash_data *hd, int kom_pos); | |
97 | void hashdata_calc_orientation_invariant(Hash_data *hd, Intersection *board, | |
98 | int ko_pos); | |
99 | ||
100 | char *hashdata_to_string(Hash_data *hashdata); | |
101 | ||
102 | ||
103 | ||
104 | /* ---------------------------------------------------------------- */ | |
105 | ||
106 | /* There is no need to involve all bits in the remainder computation | |
107 | * as long as we only use it to compute a key into a hash table. 32 | |
108 | * random bits are sufficient to get an even distribution within any | |
109 | * hashtable of reasonable size. By never using more than 32 bits we | |
110 | * also reduce the platform dependency of the GNU Go engine. | |
111 | */ | |
112 | #define hashdata_remainder(hd, num) \ | |
113 | (((hd).hashval[0] & 0xffffffffU) % (num)) | |
114 | ||
115 | #if NUM_HASHVALUES == 1 | |
116 | ||
117 | #define hashdata_is_equal(hd1, hd2) \ | |
118 | ((hd1).hashval[0] == (hd2).hashval[0]) | |
119 | ||
120 | #define hashdata_is_smaller(hd1, hd2) \ | |
121 | ((hd1).hashval[0] < (hd2).hashval[0]) | |
122 | ||
123 | #define hashdata_xor(hd1, hd2) \ | |
124 | (hd1).hashval[0] ^= (hd2).hashval[0] | |
125 | ||
126 | #elif NUM_HASHVALUES == 2 | |
127 | ||
128 | #define hashdata_is_equal(hd1, hd2) \ | |
129 | ((hd1).hashval[0] == (hd2).hashval[0] \ | |
130 | && (hd1).hashval[1] == (hd2).hashval[1]) | |
131 | ||
132 | #define hashdata_is_smaller(hd1, hd2) \ | |
133 | ((hd1).hashval[0] < (hd2).hashval[0] \ | |
134 | || ((hd1).hashval[0] == (hd2).hashval[0] \ | |
135 | && (hd1).hashval[1] < (hd2).hashval[1])) | |
136 | ||
137 | #define hashdata_xor(hd1, hd2) \ | |
138 | do { \ | |
139 | (hd1).hashval[0] ^= (hd2).hashval[0]; \ | |
140 | (hd1).hashval[1] ^= (hd2).hashval[1]; \ | |
141 | } while (0) | |
142 | ||
143 | #else | |
144 | ||
145 | int hashdata_is_equal_func(Hash_data *hd1, Hash_data *hd2); | |
146 | int hashdata_is_smaller_func(Hash_data *hd1, Hash_data *hd2); | |
147 | ||
148 | #define hashdata_is_equal(hd1, hd2) \ | |
149 | hashdata_is_equal_func(&(hd1), &(hd2)) | |
150 | ||
151 | #define hashdata_is_smaller(hd1, hd2) \ | |
152 | hashdata_is_smaller_func(&(hd1), &(hd2)) | |
153 | ||
154 | #define hashdata_xor(hd1, hd2) \ | |
155 | do { \ | |
156 | int i; \ | |
157 | for (i = 0; i < NUM_HASHVALUES; i++) \ | |
158 | (hd1).hashval[i] ^= (hd2).hashval[i]; \ | |
159 | } while (0) | |
160 | ||
161 | #endif | |
162 | ||
163 | #endif | |
164 | ||
165 | ||
166 | /* | |
167 | * Local Variables: | |
168 | * tab-width: 8 | |
169 | * c-basic-offset: 2 | |
170 | * End: | |
171 | */ |