1 /* trans.cpp
2
3 GNU Chess engine
4
5 Copyright (C) 2001-2011 Free Software Foundation, Inc.
6
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
19 */
20
21
22 // trans.cpp
23
24 // includes
25
26 #include "hash.h"
27 #include "move.h"
28 #include "option.h"
29 #include "protocol.h"
30 #include "trans.h"
31 #include "util.h"
32 #include "value.h"
33
34 // macros
35
36 #define MIN(a,b) ((a)<=(b)?(a):(b))
37 #define MAX(a,b) ((a)>=(b)?(a):(b))
38
39 namespace engine {
40
41 // constants
42
43 static const bool UseModulo = false;
44
45 static const int DateSize = 16;
46
47 static const int ClusterSize = 4; // TODO: unsigned?
48
49 static const int DepthNone = -128;
50
51 // types
52
53 struct entry_t {
54 uint32 lock;
55 uint16 move;
56 sint8 depth;
57 uint8 date;
58 sint8 move_depth;
59 uint8 flags;
60 sint8 min_depth;
61 sint8 max_depth;
62 sint16 min_value;
63 sint16 max_value;
64 };
65
66 struct trans { // HACK: typedef'ed in trans.h
67 entry_t * table;
68 uint32 size;
69 uint32 mask;
70 int date;
71 int age[DateSize];
72 uint32 used;
73 sint64 read_nb;
74 sint64 read_hit;
75 sint64 write_nb;
76 sint64 write_hit;
77 sint64 write_collision;
78 };
79
80 // variables
81
82 trans_t Trans[1];
83
84 // prototypes
85
86 static void trans_set_date (trans_t * trans, int date);
87 static int trans_age (const trans_t * trans, int date);
88
89 static entry_t * trans_entry (trans_t * trans, uint64 key);
90
91 static bool entry_is_ok (const entry_t * entry);
92
93 // functions
94
95 // trans_is_ok()
96
trans_is_ok(const trans_t * trans)97 bool trans_is_ok(const trans_t * trans) {
98
99 int date;
100
101 if (trans == NULL) return false;
102
103 if (trans->table == NULL) return false;
104 if (trans->size == 0) return false;
105 if (trans->mask == 0 || trans->mask >= trans->size) return false;
106 if (trans->date >= DateSize) return false;
107
108 for (date = 0; date < DateSize; date++) {
109 if (trans->age[date] != trans_age(trans,date)) return false;
110 }
111
112 return true;
113 }
114
115 // trans_init()
116
trans_init(trans_t * trans)117 void trans_init(trans_t * trans) {
118
119 ASSERT(trans!=NULL);
120
121 ASSERT(sizeof(entry_t)==16);
122
123 trans->size = 0;
124 trans->mask = 0;
125 trans->table = NULL;
126
127 trans_set_date(trans,0);
128
129 trans_clear(trans);
130
131 // ASSERT(trans_is_ok(trans));
132 }
133
134 // trans_alloc()
135
trans_alloc(trans_t * trans)136 void trans_alloc(trans_t * trans) {
137
138 uint32 size, target;
139
140 ASSERT(trans!=NULL);
141
142 // calculate size
143
144 target = option_get_int("Hash");
145 if (target < 4) target = 16;
146 target *= 1024 * 1024;
147
148 for (size = 1; size != 0 && size <= target; size *= 2)
149 ;
150
151 size /= 2;
152 ASSERT(size>0&&size<=target);
153
154 // allocate table
155
156 size /= sizeof(entry_t);
157 ASSERT(size!=0&&(size&(size-1))==0); // power of 2
158
159 trans->size = size + (ClusterSize - 1); // HACK to avoid testing for end of table
160 trans->mask = size - 1;
161
162 trans->table = (entry_t *) my_malloc(trans->size*sizeof(entry_t));
163
164 trans_clear(trans);
165
166 ASSERT(trans_is_ok(trans));
167 }
168
169 // trans_free()
170
trans_free(trans_t * trans)171 void trans_free(trans_t * trans) {
172
173 ASSERT(trans_is_ok(trans));
174
175 my_free(trans->table);
176
177 trans->table = NULL;
178 trans->size = 0;
179 trans->mask = 0;
180 }
181
182 // trans_clear()
183
trans_clear(trans_t * trans)184 void trans_clear(trans_t * trans) {
185
186 entry_t clear_entry[1];
187 entry_t * entry;
188 uint32 index;
189
190 ASSERT(trans!=NULL);
191
192 trans_set_date(trans,0);
193
194 clear_entry->lock = 0;
195 clear_entry->move = MoveNone;
196 clear_entry->depth = DepthNone;
197 clear_entry->date = trans->date;
198 clear_entry->move_depth = DepthNone;
199 clear_entry->flags = 0;
200 clear_entry->min_depth = DepthNone;
201 clear_entry->max_depth = DepthNone;
202 clear_entry->min_value = -ValueInf;
203 clear_entry->max_value = +ValueInf;
204
205 ASSERT(entry_is_ok(clear_entry));
206
207 entry = trans->table;
208
209 for (index = 0; index < trans->size; index++) {
210 *entry++ = *clear_entry;
211 }
212 }
213
214 // trans_inc_date()
215
trans_inc_date(trans_t * trans)216 void trans_inc_date(trans_t * trans) {
217
218 ASSERT(trans!=NULL);
219
220 trans_set_date(trans,(trans->date+1)%DateSize);
221 }
222
223 // trans_set_date()
224
trans_set_date(trans_t * trans,int date)225 static void trans_set_date(trans_t * trans, int date) {
226
227 ASSERT(trans!=NULL);
228 ASSERT(date>=0&&date<DateSize);
229
230 trans->date = date;
231
232 for (date = 0; date < DateSize; date++) {
233 trans->age[date] = trans_age(trans,date);
234 }
235
236 trans->used = 0;
237 trans->read_nb = 0;
238 trans->read_hit = 0;
239 trans->write_nb = 0;
240 trans->write_hit = 0;
241 trans->write_collision = 0;
242 }
243
244 // trans_age()
245
trans_age(const trans_t * trans,int date)246 static int trans_age(const trans_t * trans, int date) {
247
248 int age;
249
250 ASSERT(trans!=NULL);
251 ASSERT(date>=0&&date<DateSize);
252
253 age = trans->date - date;
254 if (age < 0) age += DateSize;
255
256 ASSERT(age>=0&&age<DateSize);
257
258 return age;
259 }
260
261 // trans_store()
262
trans_store(trans_t * trans,uint64 key,int move,int depth,int min_value,int max_value)263 void trans_store(trans_t * trans, uint64 key, int move, int depth, int min_value, int max_value) {
264
265 entry_t * entry, * best_entry;
266 int score, best_score;
267 int i;
268
269 ASSERT(trans_is_ok(trans));
270 ASSERT(move>=0&&move<65536);
271 ASSERT(depth>=-127&&depth<=+127);
272 ASSERT(min_value>=-ValueInf&&min_value<=+ValueInf);
273 ASSERT(max_value>=-ValueInf&&max_value<=+ValueInf);
274 ASSERT(min_value<=max_value);
275
276 // init
277
278 trans->write_nb++;
279
280 // probe
281
282 best_entry = NULL;
283 best_score = -32767;
284
285 entry = trans_entry(trans,key);
286
287 for (i = 0; i < ClusterSize; i++, entry++) {
288
289 if (entry->lock == KEY_LOCK(key)) {
290
291 // hash hit => update existing entry
292
293 trans->write_hit++;
294 if (entry->date != trans->date) trans->used++;
295
296 entry->date = trans->date;
297
298 if (depth > entry->depth) entry->depth = depth; // for replacement scheme
299
300 if (move != MoveNone && depth >= entry->move_depth) {
301 entry->move_depth = depth;
302 entry->move = move;
303 }
304
305 if (min_value > -ValueInf && depth >= entry->min_depth) {
306 entry->min_depth = depth;
307 entry->min_value = min_value;
308 }
309
310 if (max_value < +ValueInf && depth >= entry->max_depth) {
311 entry->max_depth = depth;
312 entry->max_value = max_value;
313 }
314
315 ASSERT(entry_is_ok(entry));
316
317 return;
318 }
319
320 // evaluate replacement score
321
322 score = trans->age[entry->date] * 256 - entry->depth;
323 ASSERT(score>-32767);
324
325 if (score > best_score) {
326 best_entry = entry;
327 best_score = score;
328 }
329 }
330
331 // "best" entry found
332
333 entry = best_entry;
334 ASSERT(entry!=NULL);
335 ASSERT(entry->lock!=KEY_LOCK(key));
336
337 if (entry->date == trans->date) {
338 trans->write_collision++;
339 } else {
340 trans->used++;
341 }
342
343 // store
344
345 ASSERT(entry!=NULL);
346
347 entry->lock = KEY_LOCK(key);
348 entry->date = trans->date;
349
350 entry->depth = depth;
351
352 entry->move_depth = (move != MoveNone) ? depth : DepthNone;
353 entry->move = move;
354
355 entry->min_depth = (min_value > -ValueInf) ? depth : DepthNone;
356 entry->max_depth = (max_value < +ValueInf) ? depth : DepthNone;
357 entry->min_value = min_value;
358 entry->max_value = max_value;
359
360 ASSERT(entry_is_ok(entry));
361 }
362
363 // trans_retrieve()
364
trans_retrieve(trans_t * trans,uint64 key,int * move,int * min_depth,int * max_depth,int * min_value,int * max_value)365 bool trans_retrieve(trans_t * trans, uint64 key, int * move, int * min_depth, int * max_depth, int * min_value, int * max_value) {
366
367 entry_t * entry;
368 int i;
369
370 ASSERT(trans_is_ok(trans));
371 ASSERT(move!=NULL);
372 ASSERT(min_depth!=NULL);
373 ASSERT(max_depth!=NULL);
374 ASSERT(min_value!=NULL);
375 ASSERT(max_value!=NULL);
376
377 // init
378
379 trans->read_nb++;
380
381 // probe
382
383 entry = trans_entry(trans,key);
384
385 for (i = 0; i < ClusterSize; i++, entry++) {
386
387 if (entry->lock == KEY_LOCK(key)) {
388
389 // found
390
391 trans->read_hit++;
392 if (entry->date != trans->date) entry->date = trans->date;
393
394 *move = entry->move;
395
396 *min_depth = entry->min_depth;
397 *max_depth = entry->max_depth;
398 *min_value = entry->min_value;
399 *max_value = entry->max_value;
400
401 return true;
402 }
403 }
404
405 // not found
406
407 return false;
408 }
409
410 // trans_stats()
411
trans_stats(const trans_t * trans)412 void trans_stats(const trans_t * trans) {
413
414 double full;
415 // double hit, collision;
416
417 ASSERT(trans_is_ok(trans));
418
419 full = double(trans->used) / double(trans->size);
420 // hit = double(trans->read_hit) / double(trans->read_nb);
421 // collision = double(trans->write_collision) / double(trans->write_nb);
422
423 send("info hashfull %.0f",full*1000.0);
424 }
425
426 // trans_entry()
427
trans_entry(trans_t * trans,uint64 key)428 static entry_t * trans_entry(trans_t * trans, uint64 key) {
429
430 uint32 index;
431
432 ASSERT(trans_is_ok(trans));
433
434 if (UseModulo) {
435 index = KEY_INDEX(key) % (trans->mask + 1);
436 } else {
437 index = KEY_INDEX(key) & trans->mask;
438 }
439
440 ASSERT(index<=trans->mask);
441
442 return &trans->table[index];
443 }
444
445 // entry_is_ok()
446
entry_is_ok(const entry_t * entry)447 static bool entry_is_ok(const entry_t * entry) {
448
449 if (entry == NULL) return false;
450
451 if (entry->date >= DateSize) return false;
452
453 if (entry->move == MoveNone && entry->move_depth != DepthNone) return false;
454 if (entry->move != MoveNone && entry->move_depth == DepthNone) return false;
455
456 if (entry->min_value == -ValueInf && entry->min_depth != DepthNone) return false;
457 if (entry->min_value > -ValueInf && entry->min_depth == DepthNone) return false;
458
459 if (entry->max_value == +ValueInf && entry->max_depth != DepthNone) return false;
460 if (entry->max_value < +ValueInf && entry->max_depth == DepthNone) return false;
461
462 return true;
463 }
464
465 } // namespace engine
466
467 // end of trans.cpp
468
469