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
29uint32_t zobrist[17][144];
30
31uint32_t hash;
32
33uint32_t TTProbes;
34uint32_t TTHits;
35uint32_t TTStores;
36
37typedef 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  uint32_t Hash;
44  uint32_t Hold_hash;
45  int32_t Bound;
46}
47TType;
48
49typedef struct
50{
51  unsigned short Bestmove;
52  unsigned OnMove:1, Type:2;
53  uint32_t Hash;
54  uint32_t Hold_hash;
55  int32_t Bound;
56}
57QTType;
58
59/*TType DP_TTable[TTSIZE];
60TType AS_TTable[TTSIZE];
61*/
62
63TType *DP_TTable;
64TType *AS_TTable;
65QTType *QS_TTable;
66
67void clear_tt(void)
68{
69  memset(DP_TTable, 0, sizeof(TType) * TTSize);
70  memset(AS_TTable, 0, sizeof(TType) * TTSize);
71  memset(QS_TTable, 0, sizeof(QTType) * TTSize);
72};
73
74void clear_dp_tt(void)
75{
76  memset(DP_TTable, 0, sizeof(TType) * TTSize);
77};
78
79void initialize_zobrist(void)
80{
81  int p, q;
82
83  seedMT(31657);
84
85  for(p = 0; p < 17; p++)
86  {
87    for(q = 0; q < 144; q++)
88      {
89	zobrist[p][q] = randomMT();
90      }
91  }
92  /* our magic number */
93
94  hash = 0xDEADBEEF;
95}
96
97void initialize_hash(void)
98{
99  int p;
100
101  hash = 0xDEADBEEF;
102
103  for(p = 0; p < 144; p++)
104    {
105      if (board[p] != npiece && board[p] != frame)
106	hash = hash ^ zobrist[board[p]][p];
107    }
108
109  hold_hash = 0xC0FFEE00;
110  /* we need to set up hold_hash here, rely on ProcessHolding for now */
111
112}
113
114void QStoreTT(int score, int alpha, int beta, int best)
115{
116  uint32_t index;
117
118  TTStores++;
119
120  index = hash % TTSize;
121
122  if (score <= alpha)
123    QS_TTable[index].Type = UPPER;
124  else if(score >= beta)
125    QS_TTable[index].Type = LOWER;
126  else
127    QS_TTable[index].Type = EXACT;
128
129  QS_TTable[index].Hash = hash;
130  QS_TTable[index].Hold_hash = hold_hash;
131  QS_TTable[index].Bestmove = best;
132  QS_TTable[index].Bound = score;
133  QS_TTable[index].OnMove = ToMove;
134
135  return;
136}
137
138void StoreTT(int score, int alpha, int beta, int best, int threat, int depth)
139{
140  uint32_t index;
141
142  TTStores++;
143
144  index = hash % TTSize;
145
146  /* Prefer storing entries with more information */
147  if ((      (DP_TTable[index].Depth < depth)
148        ||  ((DP_TTable[index].Depth == depth) &&
149	        (    ((DP_TTable[index].Type == UPPER) && (score > alpha))
150		 ||  ((score > alpha) && (score < beta))
151		)
152	    )
153      )
154      && !is_pondering)
155    {
156      if (score <= alpha)
157      {
158	DP_TTable[index].Type = UPPER;
159	if (score < -INF+500) score = -INF+500;
160      }
161      else if(score >= beta)
162      {
163	DP_TTable[index].Type = LOWER;
164	if (score > INF-500) score = INF-500;
165      }
166      else
167      {
168	DP_TTable[index].Type = EXACT;
169
170	/* normalize mate scores */
171       if (score > (+INF-500))
172	  score += ply;
173        else if (score < (-INF+500))
174	  score -= ply;
175      }
176
177      DP_TTable[index].Hash = hash;
178      DP_TTable[index].Hold_hash = hold_hash;
179      DP_TTable[index].Depth = depth;
180      DP_TTable[index].Bestmove = best;
181      DP_TTable[index].Bound = score;
182      DP_TTable[index].OnMove = ToMove;
183      DP_TTable[index].Threat = threat;
184    }
185  else
186    {
187      if (score <= alpha)
188      {
189	AS_TTable[index].Type = UPPER;
190	if (score < -INF+500) score = -INF+500;
191      }
192      else if(score >= beta)
193      {
194	AS_TTable[index].Type = LOWER;
195	if (score > INF-500) score = INF-500;
196      }
197      else
198      {
199	AS_TTable[index].Type = EXACT;
200
201	/* normalize mate scores */
202       if (score > (+INF-500))
203	  score += ply;
204        else if (score < (-INF+500))
205	  score -= ply;
206      }
207
208      AS_TTable[index].Hash = hash;
209      AS_TTable[index].Hold_hash = hold_hash;
210      AS_TTable[index].Depth = depth;
211      AS_TTable[index].Bestmove = best;
212      AS_TTable[index].Bound = score;
213      AS_TTable[index].OnMove = ToMove;
214      AS_TTable[index].Threat = threat;
215    };
216
217  return;
218}
219
220void LearnStoreTT(int score, unsigned nhash, unsigned hhash, int tomove, int best, int depth)
221{
222  uint32_t index;
223
224  index = nhash % TTSize;
225
226  AS_TTable[index].Depth = depth;
227
228  if (Variant != Suicide && Variant != Losers)
229  {
230    AS_TTable[index].Type = EXACT;
231  }
232  else
233  {
234    AS_TTable[index].Type = UPPER;
235  }
236
237  AS_TTable[index].Hash = nhash;
238  AS_TTable[index].Hold_hash = hhash;
239  AS_TTable[index].Bestmove = best;
240  AS_TTable[index].Bound = score;
241  AS_TTable[index].OnMove = tomove;
242  AS_TTable[index].Threat = 0;
243
244}
245
246int ProbeTT(int *score, int alpha, int beta, int *best, int *threat, int *donull, int depth)
247{
248
249  uint32_t index;
250
251  *donull = TRUE;
252
253  TTProbes++;
254
255  index = hash % TTSize;
256
257  if ((DP_TTable[index].Hash == hash)
258      && (DP_TTable[index].Hold_hash == hold_hash)
259      && (DP_TTable[index].OnMove == ToMove))
260    {
261      TTHits++;
262
263      if ((DP_TTable[index].Type == UPPER)
264      	   && ((depth-2-1) <= DP_TTable[index].Depth)
265      	   && (DP_TTable[index].Bound < beta))
266      	  *donull = FALSE;
267
268      if (DP_TTable[index].Threat) depth++;
269
270      if (DP_TTable[index].Depth >= depth)
271	{
272	  *score = DP_TTable[index].Bound;
273
274	  if (*score > (+INF-500))
275	   *score -= ply;
276	  else if (*score < (-INF+500))
277	    *score += ply;
278
279	  *best = DP_TTable[index].Bestmove;
280	  *threat = DP_TTable[index].Threat;
281
282	  return DP_TTable[index].Type;
283	}
284      else
285	{
286	  *best = DP_TTable[index].Bestmove;
287	  *threat = DP_TTable[index].Threat;
288
289	  return DUMMY;
290	}
291    }
292  else if ((AS_TTable[index].Hash == hash)
293      && (AS_TTable[index].Hold_hash == hold_hash)
294      && (AS_TTable[index].OnMove == ToMove))
295    {
296      TTHits++;
297
298      if ((AS_TTable[index].Type == UPPER)
299      	   && ((depth-2-1) <= AS_TTable[index].Depth)
300      	   && (AS_TTable[index].Bound < beta))
301      	  *donull = FALSE;
302
303      if (AS_TTable[index].Threat) depth++;
304
305      if (AS_TTable[index].Depth >= depth)
306	{
307	  *score = AS_TTable[index].Bound;
308
309	  if (*score > (+INF-500))
310	   *score -= ply;
311	  else if (*score < (-INF+500))
312	    *score += ply;
313
314	  *best = AS_TTable[index].Bestmove;
315	  *threat = AS_TTable[index].Threat;
316
317	  return AS_TTable[index].Type;
318	}
319      else
320	{
321	  *best = AS_TTable[index].Bestmove;
322	  *threat = AS_TTable[index].Threat;
323
324	  return DUMMY;
325	}
326    }
327  else
328    return HMISS;
329
330}
331
332int QProbeTT(int *score, int alpha, int beta, int *best)
333{
334
335  uint32_t index;
336
337  TTProbes++;
338
339  index = hash % TTSize;
340
341  if ((QS_TTable[index].Hash == hash)
342      && (QS_TTable[index].Hold_hash == hold_hash)
343      && (QS_TTable[index].OnMove == ToMove))
344    {
345      TTHits++;
346
347      *score = QS_TTable[index].Bound;
348
349      *best = QS_TTable[index].Bestmove;
350
351      return QS_TTable[index].Type;
352    }
353  else
354    return HMISS;
355
356}
357
358
359void alloc_hash(void)
360{
361  AS_TTable = (TType *) malloc(sizeof(TType) * TTSize);
362  DP_TTable = (TType *) malloc(sizeof(TType) * TTSize);
363  QS_TTable = (QTType *) malloc(sizeof(QTType) * TTSize);
364
365  if (AS_TTable == NULL || DP_TTable == NULL || QS_TTable == NULL)
366  {
367    printf("Out of memory allocating hashtables.\n");
368    exit(EXIT_FAILURE);
369  }
370
371  printf("Allocated 2*%d hash entries, totalling %u bytes.\n",
372          TTSize, (uint32_t)(2*sizeof(TType)*TTSize));
373  printf("Allocated %d quiescenthash entries, totalling %u bytes.\n",
374          TTSize, (uint32_t)(sizeof(QTType)*TTSize));
375  return;
376}
377
378void free_hash(void)
379{
380  free(AS_TTable);
381  free(DP_TTable);
382  free(QS_TTable);
383  return;
384}
385