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 "board.h" | |
26 | #include "hash.h" | |
27 | #include "random.h" | |
28 | ||
29 | #include <stdio.h> | |
30 | #include <stdlib.h> | |
31 | #include <limits.h> | |
32 | ||
33 | ||
34 | ||
35 | /* | |
36 | * This file, together with engine/hash.h implements hashing of go positions | |
37 | * using a method known as Zobrist hashing. See the Texinfo documentation | |
38 | * (Reading/Hashing) for more information. | |
39 | */ | |
40 | ||
41 | ||
42 | /* ================================================================ */ | |
43 | ||
44 | ||
45 | ||
46 | ||
47 | /* Random values for the board hash function. For stones and ko position. */ | |
48 | static Hash_data white_hash[BOARDMAX]; | |
49 | static Hash_data black_hash[BOARDMAX]; | |
50 | static Hash_data ko_hash[BOARDMAX]; | |
51 | static Hash_data komaster_hash[NUM_KOMASTER_STATES]; | |
52 | static Hash_data kom_pos_hash[BOARDMAX]; | |
53 | static Hash_data goal_hash[BOARDMAX]; | |
54 | ||
55 | ||
56 | /* Get a random Hashvalue, where all bits are used. */ | |
57 | static Hashvalue | |
58 | hash_rand(void) | |
59 | { | |
60 | int i; | |
61 | Hashvalue h = 0; | |
62 | ||
63 | for (i = 0; 32*i < (int) (CHAR_BIT*sizeof(Hashvalue)); i++) | |
64 | h |= (Hashvalue) gg_urand() << 32*i; | |
65 | ||
66 | return h; | |
67 | } | |
68 | ||
69 | /* Fill an array with random numbers for Zobrist hashing. */ | |
70 | void | |
71 | hash_init_zobrist_array(Hash_data *array, int size) | |
72 | { | |
73 | int i, j; | |
74 | for (i = 0; i < size; i++) | |
75 | for (j = 0; j < NUM_HASHVALUES; j++) | |
76 | array[i].hashval[j] = hash_rand(); | |
77 | } | |
78 | ||
79 | /* | |
80 | * Initialize the board hash system. | |
81 | */ | |
82 | ||
83 | void | |
84 | hash_init(void) | |
85 | { | |
86 | static int is_initialized = 0; | |
87 | if (is_initialized) | |
88 | return; | |
89 | ||
90 | INIT_ZOBRIST_ARRAY(black_hash); | |
91 | INIT_ZOBRIST_ARRAY(white_hash); | |
92 | INIT_ZOBRIST_ARRAY(ko_hash); | |
93 | INIT_ZOBRIST_ARRAY(komaster_hash); | |
94 | INIT_ZOBRIST_ARRAY(kom_pos_hash); | |
95 | INIT_ZOBRIST_ARRAY(goal_hash); | |
96 | ||
97 | is_initialized = 1; | |
98 | } | |
99 | ||
100 | ||
101 | /* ---------------------------------------------------------------- */ | |
102 | ||
103 | /* Calculate the hashvalue from scratch. */ | |
104 | void | |
105 | hashdata_recalc(Hash_data *hd, Intersection *p, int ko_pos) | |
106 | { | |
107 | int pos; | |
108 | ||
109 | hashdata_clear(hd); | |
110 | ||
111 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
112 | if (p[pos] == WHITE) | |
113 | hashdata_xor(*hd, white_hash[pos]); | |
114 | else if (p[pos] == BLACK) | |
115 | hashdata_xor(*hd, black_hash[pos]); | |
116 | } | |
117 | ||
118 | if (ko_pos != 0) | |
119 | hashdata_xor(*hd, ko_hash[ko_pos]); | |
120 | } | |
121 | ||
122 | /* Clear hashdata. */ | |
123 | void | |
124 | hashdata_clear(Hash_data *hd) | |
125 | { | |
126 | int i; | |
127 | for (i = 0; i < NUM_HASHVALUES; i++) | |
128 | hd->hashval[i] = 0; | |
129 | } | |
130 | ||
131 | /* Set or remove ko in the hash value and hash position. */ | |
132 | void | |
133 | hashdata_invert_ko(Hash_data *hd, int pos) | |
134 | { | |
135 | hashdata_xor(*hd, ko_hash[pos]); | |
136 | } | |
137 | ||
138 | ||
139 | /* Set or remove a stone of COLOR at pos in a Hash_data. */ | |
140 | void | |
141 | hashdata_invert_stone(Hash_data *hd, int pos, int color) | |
142 | { | |
143 | if (color == BLACK) | |
144 | hashdata_xor(*hd, black_hash[pos]); | |
145 | else if (color == WHITE) | |
146 | hashdata_xor(*hd, white_hash[pos]); | |
147 | } | |
148 | ||
149 | ||
150 | /* Set or remove the komaster value in the hash data. */ | |
151 | void | |
152 | hashdata_invert_komaster(Hash_data *hd, int komaster) | |
153 | { | |
154 | hashdata_xor(*hd, komaster_hash[komaster]); | |
155 | } | |
156 | ||
157 | /* Set or remove the komaster position in the hash data. */ | |
158 | void | |
159 | hashdata_invert_kom_pos(Hash_data *hd, int kom_pos) | |
160 | { | |
161 | hashdata_xor(*hd, kom_pos_hash[kom_pos]); | |
162 | } | |
163 | ||
164 | /* Calculate a transformation invariant hashvalue. */ | |
165 | void | |
166 | hashdata_calc_orientation_invariant(Hash_data *hd, Intersection *p, int ko_pos) | |
167 | { | |
168 | int pos; | |
169 | int rot; | |
170 | Hash_data hd_rot; | |
171 | ||
172 | for (rot = 0; rot < 8; rot++) { | |
173 | hashdata_clear(&hd_rot); | |
174 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
175 | if (p[pos] == WHITE) | |
176 | hashdata_xor(hd_rot, white_hash[rotate1(pos, rot)]); | |
177 | else if (p[pos] == BLACK) | |
178 | hashdata_xor(hd_rot, black_hash[rotate1(pos, rot)]); | |
179 | } | |
180 | ||
181 | if (ko_pos != NO_MOVE) | |
182 | hashdata_xor(hd_rot, ko_hash[rotate1(ko_pos, rot)]); | |
183 | ||
184 | if (rot == 0 || hashdata_is_smaller(hd_rot, *hd)) | |
185 | *hd = hd_rot; | |
186 | } | |
187 | } | |
188 | ||
189 | /* Compute hash value to identify the goal area. */ | |
190 | Hash_data | |
191 | goal_to_hashvalue(const signed char *goal) | |
192 | { | |
193 | int pos; | |
194 | Hash_data return_value; | |
195 | ||
196 | hashdata_clear(&return_value); | |
197 | ||
198 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
199 | if (ON_BOARD(pos) && goal[pos]) | |
200 | hashdata_xor(return_value, goal_hash[pos]); | |
201 | ||
202 | return return_value; | |
203 | } | |
204 | ||
205 | ||
206 | #define HASHVALUE_NUM_DIGITS (1 + (CHAR_BIT * SIZEOF_HASHVALUE - 1) / 4) | |
207 | #define BUFFER_SIZE (1 + NUM_HASHVALUES * HASHVALUE_NUM_DIGITS) | |
208 | char * | |
209 | hashdata_to_string(Hash_data *hashdata) | |
210 | { | |
211 | static char buffer[BUFFER_SIZE]; | |
212 | int n = 0; | |
213 | int k; | |
214 | ||
215 | /* Loop backwards for consistency between 32 and 64 bit platforms. */ | |
216 | for (k = NUM_HASHVALUES - 1; k >= 0; k--) { | |
217 | n += sprintf(buffer + n, HASHVALUE_PRINT_FORMAT, | |
218 | HASHVALUE_NUM_DIGITS, hashdata->hashval[k]); | |
219 | gg_assert(n < BUFFER_SIZE); | |
220 | } | |
221 | ||
222 | return buffer; | |
223 | } | |
224 | ||
225 | #if NUM_HASHVALUES > 2 | |
226 | int | |
227 | hashdata_is_equal_func(Hash_data *hd1, Hash_data *hd2) | |
228 | { | |
229 | int i; | |
230 | for (i = 0; i < NUM_HASHVALUES; i++) | |
231 | if (hd1->hashval[i] != hd2->hashval[i]) | |
232 | return 0; | |
233 | ||
234 | return 1; | |
235 | } | |
236 | ||
237 | int | |
238 | hashdata_is_smaller_func(Hash_data *hd1, Hash_data *hd2) | |
239 | { | |
240 | int i; | |
241 | for (i = 0; i < NUM_HASHVALUES; i++) | |
242 | if (hd1->hashval[i] < hd2->hashval[i]) | |
243 | return 1; | |
244 | else if (hd1->hashval[i] > hd2->hashval[i]) | |
245 | return 0; | |
246 | ||
247 | return 0; | |
248 | } | |
249 | #endif | |
250 | ||
251 | ||
252 | /* | |
253 | * Local Variables: | |
254 | * tab-width: 8 | |
255 | * c-basic-offset: 2 | |
256 | * End: | |
257 | */ |