1 /*
2 Sjeng - a chess variants playing program
3 Copyright (C) 2000-2001 Gian-Carlo Pascutto
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19 File: ttable.c
20 Purpose: handling of transposition tables and hashes
21
22 */
23
24 #include "sjeng.h"
25 #include "protos.h"
26 #include "extvars.h"
27 #include "limits.h"
28
29 unsigned long zobrist[17][144];
30
31 unsigned long hash;
32
33 unsigned long TTProbes;
34 unsigned long TTHits;
35 unsigned long TTStores;
36
37 typedef struct
38 {
39 signed char Depth;
40 /* unsigned char may be a bit small for bughouse/crazyhouse */
41 unsigned short Bestmove;
42 unsigned OnMove:1, Threat:1, Type:2;
43 unsigned long Hash;
44 unsigned long Hold_hash;
45 signed long Bound;
46 }
47 TType;
48
49 typedef struct
50 {
51 unsigned short Bestmove;
52 unsigned OnMove:1, Type:2;
53 unsigned long Hash;
54 unsigned long Hold_hash;
55 signed long Bound;
56 }
57 QTType;
58
59 /*TType DP_TTable[TTSIZE];
60 TType AS_TTable[TTSIZE];
61 */
62
63 TType *DP_TTable;
64 TType *AS_TTable;
65 QTType *QS_TTable;
66
clear_tt(void)67 void clear_tt(void)
68 {
69 memset(DP_TTable, 0, sizeof(TType) * TTSize);
70 memset(AS_TTable, 0, sizeof(TType) * TTSize);
71 };
72
clear_dp_tt(void)73 void clear_dp_tt(void)
74 {
75 memset(DP_TTable, 0, sizeof(TType) * TTSize);
76 };
77
initialize_zobrist(void)78 void initialize_zobrist(void)
79 {
80 int p, q;
81
82 seedMT(31657);
83
84 for(p = 0; p < 17; p++)
85 {
86 for(q = 0; q < 144; q++)
87 {
88 zobrist[p][q] = randomMT();
89 }
90 }
91 /* our magic number */
92
93 hash = 0xDEADBEEF;
94 }
95
initialize_hash(void)96 void initialize_hash(void)
97 {
98 int p;
99
100 hash = 0xDEADBEEF;
101
102 for(p = 0; p < 144; p++)
103 {
104 if (board[p] != npiece && board[p] != frame)
105 hash = hash ^ zobrist[board[p]][p];
106 }
107
108 hold_hash = 0xC0FFEE00;
109 /* we need to set up hold_hash here, rely on ProcessHolding for now */
110
111 }
112
QStoreTT(int score,int alpha,int beta,int best)113 void QStoreTT(int score, int alpha, int beta, int best)
114 {
115 unsigned long index;
116
117 TTStores++;
118
119 index = hash % TTSize;
120
121 if (score <= alpha)
122 QS_TTable[index].Type = UPPER;
123 else if(score >= beta)
124 QS_TTable[index].Type = LOWER;
125 else
126 QS_TTable[index].Type = EXACT;
127
128 QS_TTable[index].Hash = hash;
129 QS_TTable[index].Hold_hash = hold_hash;
130 QS_TTable[index].Bestmove = best;
131 QS_TTable[index].Bound = score;
132 QS_TTable[index].OnMove = ToMove;
133
134 return;
135 }
136
StoreTT(int score,int alpha,int beta,int best,int threat,int depth)137 void StoreTT(int score, int alpha, int beta, int best, int threat, int depth)
138 {
139 unsigned long index;
140
141 TTStores++;
142
143 index = hash % TTSize;
144
145 /* Prefer storing entries with more information */
146 if (( (DP_TTable[index].Depth < depth)
147 || ((DP_TTable[index].Depth == depth) &&
148 ( ((DP_TTable[index].Type == UPPER) && (score > alpha))
149 || ((score > alpha) && (score < beta))
150 )
151 )
152 )
153 && !is_pondering)
154 {
155 if (score <= alpha)
156 {
157 DP_TTable[index].Type = UPPER;
158 if (score < -INF+500) score = -INF+500;
159 }
160 else if(score >= beta)
161 {
162 DP_TTable[index].Type = LOWER;
163 if (score > INF-500) score = INF-500;
164 }
165 else
166 {
167 DP_TTable[index].Type = EXACT;
168
169 /* normalize mate scores */
170 if (score > (+INF-500))
171 score += ply;
172 else if (score < (-INF+500))
173 score -= ply;
174 }
175
176 DP_TTable[index].Hash = hash;
177 DP_TTable[index].Hold_hash = hold_hash;
178 DP_TTable[index].Depth = depth;
179 DP_TTable[index].Bestmove = best;
180 DP_TTable[index].Bound = score;
181 DP_TTable[index].OnMove = ToMove;
182 DP_TTable[index].Threat = threat;
183 }
184 else
185 {
186 if (score <= alpha)
187 {
188 AS_TTable[index].Type = UPPER;
189 if (score < -INF+500) score = -INF+500;
190 }
191 else if(score >= beta)
192 {
193 AS_TTable[index].Type = LOWER;
194 if (score > INF-500) score = INF-500;
195 }
196 else
197 {
198 AS_TTable[index].Type = EXACT;
199
200 /* normalize mate scores */
201 if (score > (+INF-500))
202 score += ply;
203 else if (score < (-INF+500))
204 score -= ply;
205 }
206
207 AS_TTable[index].Hash = hash;
208 AS_TTable[index].Hold_hash = hold_hash;
209 AS_TTable[index].Depth = depth;
210 AS_TTable[index].Bestmove = best;
211 AS_TTable[index].Bound = score;
212 AS_TTable[index].OnMove = ToMove;
213 AS_TTable[index].Threat = threat;
214 };
215
216 return;
217 }
218
LearnStoreTT(int score,unsigned nhash,unsigned hhash,int tomove,int best,int depth)219 void LearnStoreTT(int score, unsigned nhash, unsigned hhash, int tomove, int best, int depth)
220 {
221 unsigned long index;
222
223 index = nhash % TTSize;
224
225 AS_TTable[index].Depth = depth;
226
227 if (Variant != Suicide && Variant != Losers)
228 {
229 AS_TTable[index].Type = EXACT;
230 }
231 else
232 {
233 AS_TTable[index].Type = UPPER;
234 }
235
236 AS_TTable[index].Hash = nhash;
237 AS_TTable[index].Hold_hash = hhash;
238 AS_TTable[index].Bestmove = best;
239 AS_TTable[index].Bound = score;
240 AS_TTable[index].OnMove = tomove;
241 AS_TTable[index].Threat = 0;
242
243 }
244
ProbeTT(int * score,int alpha,int beta,int * best,int * threat,int * donull,int depth)245 int ProbeTT(int *score, int alpha, int beta, int *best, int *threat, int *donull, int depth)
246 {
247
248 unsigned long index;
249
250 *donull = TRUE;
251
252 TTProbes++;
253
254 index = hash % TTSize;
255
256 if ((DP_TTable[index].Hash == hash)
257 && (DP_TTable[index].Hold_hash == hold_hash)
258 && (DP_TTable[index].OnMove == ToMove))
259 {
260 TTHits++;
261
262 if ((DP_TTable[index].Type == UPPER)
263 && ((depth-2-1) <= DP_TTable[index].Depth)
264 && (DP_TTable[index].Bound < beta))
265 *donull = FALSE;
266
267 if (DP_TTable[index].Threat) depth++;
268
269 if (DP_TTable[index].Depth >= depth)
270 {
271 *score = DP_TTable[index].Bound;
272
273 if (*score > (+INF-500))
274 *score -= ply;
275 else if (*score < (-INF+500))
276 *score += ply;
277
278 *best = DP_TTable[index].Bestmove;
279 *threat = DP_TTable[index].Threat;
280
281 return DP_TTable[index].Type;
282 }
283 else
284 {
285 *best = DP_TTable[index].Bestmove;
286 *threat = DP_TTable[index].Threat;
287
288 return DUMMY;
289 }
290 }
291 else if ((AS_TTable[index].Hash == hash)
292 && (AS_TTable[index].Hold_hash == hold_hash)
293 && (AS_TTable[index].OnMove == ToMove))
294 {
295 TTHits++;
296
297 if ((AS_TTable[index].Type == UPPER)
298 && ((depth-2-1) <= AS_TTable[index].Depth)
299 && (AS_TTable[index].Bound < beta))
300 *donull = FALSE;
301
302 if (AS_TTable[index].Threat) depth++;
303
304 if (AS_TTable[index].Depth >= depth)
305 {
306 *score = AS_TTable[index].Bound;
307
308 if (*score > (+INF-500))
309 *score -= ply;
310 else if (*score < (-INF+500))
311 *score += ply;
312
313 *best = AS_TTable[index].Bestmove;
314 *threat = AS_TTable[index].Threat;
315
316 return AS_TTable[index].Type;
317 }
318 else
319 {
320 *best = AS_TTable[index].Bestmove;
321 *threat = AS_TTable[index].Threat;
322
323 return DUMMY;
324 }
325 }
326 else
327 return HMISS;
328
329 }
330
QProbeTT(int * score,int alpha,int beta,int * best)331 int QProbeTT(int *score, int alpha, int beta, int *best)
332 {
333
334 unsigned long index;
335
336 TTProbes++;
337
338 index = hash % TTSize;
339
340 if ((QS_TTable[index].Hash == hash)
341 && (QS_TTable[index].Hold_hash == hold_hash)
342 && (QS_TTable[index].OnMove == ToMove))
343 {
344 TTHits++;
345
346 *score = QS_TTable[index].Bound;
347
348 *best = QS_TTable[index].Bestmove;
349
350 return QS_TTable[index].Type;
351 }
352 else
353 return HMISS;
354
355 }
356
357
alloc_hash(void)358 void alloc_hash(void)
359 {
360 AS_TTable = (TType *) malloc(sizeof(TType) * TTSize);
361 DP_TTable = (TType *) malloc(sizeof(TType) * TTSize);
362 QS_TTable = (QTType *) malloc(sizeof(QTType) * TTSize);
363
364 if (AS_TTable == NULL || DP_TTable == NULL || QS_TTable == NULL)
365 {
366 printf("Out of memory allocating hashtables.\n");
367 exit(EXIT_FAILURE);
368 }
369
370 printf("Allocated 2*%d hash entries, totalling %lu bytes.\n",
371 TTSize, (unsigned long)(2*sizeof(TType)*TTSize));
372 printf("Allocated %d quiescenthash entries, totalling %lu bytes.\n",
373 TTSize, (unsigned long)(sizeof(QTType)*TTSize));
374 return;
375 }
376
free_hash(void)377 void free_hash(void)
378 {
379 free(AS_TTable);
380 free(DP_TTable);
381 free(QS_TTable);
382 return;
383 }
384