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