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
hash_rand(void)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
hash_init_zobrist_array(Hash_data * array,int size)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
hash_init(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
hashdata_recalc(Hash_data * hd,Intersection * p,int ko_pos)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
hashdata_clear(Hash_data * hd)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
hashdata_invert_ko(Hash_data * hd,int pos)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
hashdata_invert_stone(Hash_data * hd,int pos,int color)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
hashdata_invert_komaster(Hash_data * hd,int komaster)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
hashdata_invert_kom_pos(Hash_data * hd,int kom_pos)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
hashdata_calc_orientation_invariant(Hash_data * hd,Intersection * p,int ko_pos)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
goal_to_hashvalue(const signed char * goal)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 *
hashdata_to_string(Hash_data * hashdata)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
hashdata_is_equal_func(Hash_data * hd1,Hash_data * hd2)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
hashdata_is_smaller_func(Hash_data * hd1,Hash_data * hd2)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  */
258