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