gnushogi/util.c

   1 /*
   2  * FILE: util.c
   3  *
   4  * ----------------------------------------------------------------------
   5  * Copyright (c) 1993, 1994, 1995 Matthias Mutz
   6  * Copyright (c) 1999 Michael Vanier and the Free Software Foundation
   7  * Copyright (c) 2008, 2013, 2014 Yann Dirson and the Free Software Foundation
   8  *
   9  * GNU SHOGI is based on GNU CHESS
  10  *
  11  * Copyright (c) 1988, 1989, 1990 John Stanback
  12  * Copyright (c) 1992 Free Software Foundation
  13  *
  14  * This file is part of GNU SHOGI.
  15  *
  16  * GNU Shogi is free software; you can redistribute it and/or modify it
  17  * under the terms of the GNU General Public License as published by the
  18  * Free Software Foundation; either version 3 of the License,
  19  * or (at your option) any later version.
  20  *
  21  * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
  22  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  23  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  24  * for more details.
  25  *
  26  * You should have received a copy of the GNU General Public License along
  27  * with GNU Shogi; see the file COPYING. If not, see
  28  * <http://www.gnu.org/licenses/>.
  29  * ----------------------------------------------------------------------
  30  *
  31  */
  32
  33 #include "gnushogi.h"
  34
  35 unsigned int TTadd = 0;
  36 short recycle;
  37 short ISZERO = 1;
  38
  39 #if 0
  40 int
  41 parse(FILE * fd, unsigned short *mv, char *opening)
  42 {
  43     int c, i, r1, r2, c1, c2;
  44     char s[128];
  45     char *p;
  46
  47     while (((c = getc(fd)) == ' ') || (c == '\n'));
  48
  49     i = 0;
  50     s[0] = (char) c;
  51
  52     if (c == '!')
  53     {
  54         p = opening;
  55         do
  56         {
  57             *p++ = c;
  58             c = getc(fd);
  59
  60             if ((c == '\n') || (c == EOF))
  61             {
  62                 *p = '\0';
  63                 return 0;
  64             }
  65         }
  66         while (true);
  67     }
  68
  69     while ((c != '?') && (c != ' ')
  70            && (c != '\t') && (c != '\n') && (c != EOF))
  71     {
  72         s[++i] = (char) (c = getc(fd));
  73     }
  74
  75     s[++i] = '\0';
  76
  77     if (c == EOF)
  78         return (-1);
  79
  80     if ((s[0] == '!') || (s[0] == ';') || (i < 3))
  81     {
  82         while ((c != '\n') && (c != EOF))
  83             c = getc(fd);
  84
  85         return 0;
  86     }
  87
  88     c1 = COL_NUM(s[0]);
  89     r1 = ROW_NUM(s[1]);
  90     c2 = COL_NUM(s[2]);
  91     r2 = ROW_NUM(s[3]);
  92     *mv = (locn(r1, c1) << 8) | locn(r2, c2);
  93
  94     if (c == '?')
  95     {
  96         /* Bad move, not for the program to play */
  97         *mv |= 0x8000;      /* Flag it ! */
  98         c = getc(fd);
  99     }
 100
 101     return 1;
 102 }
 103 #endif
 104
 105 /*
 106  * The field of a hashtable is computed as follows:
 107  *   if sq is on board (< NO_SQUARES) the field gets the value
 108  *     of the piece on the square sq;
 109  *   if sq is off board (>= NO_SQUARES) it is a catched figure,
 110  *     and the field gets the number of catched pieces for
 111  *     each side.
 112  */
 113
 114 inline unsigned char
 115 CB(short sq)
 116 {
 117     short i = sq;
 118
 119     if (i < NO_SQUARES)
 120     {
 121         return ((color[i] == white) ? (0x80 | board[i]) : board[i]);
 122     }
 123     else
 124     {
 125         i -= NO_SQUARES;
 126         return ((Captured[black][i] << 4) | Captured[white][i]);
 127     }
 128 }
 129
 130
 131
 132
 133 #if ttblsz
 134
 135 /*
 136  * Look for the current board position in the transposition table.
 137  */
 138
 139 int
 140 ProbeTTable (short side,
 141              short depth,
 142              short ply,
 143              short *alpha,
 144              short *beta,
 145              short *score)
 146 {
 147     struct hashentry  *ptbl;
 148     /*unsigned*/ short i = 0;  /* to match new type of rehash --tpm */
 149
 150     ptbl = &ttable[side][hashkey % ttblsize];
 151
 152     while (true)
 153     {
 154         if ((ptbl->depth) == 0)
 155             return false;
 156
 157         if (ptbl->hashbd == hashbd)
 158             break;
 159
 160         if (++i > rehash)
 161             return false;
 162
 163         ptbl++;
 164     }
 165
 166     /* rehash max rehash times */
 167
 168     if (((short)(ptbl->depth) >= (short) depth))
 169     {
 170 #ifdef HASHTEST
 171         for (i = 0; i < PTBLBDSIZE; i++)
 172         {
 173             if (ptbl->bd[i] != CB(i))
 174             {
 175                 HashCol++;
 176
 177                 if (!XSHOGI)
 178                 {
 179                     ShowMessage("ttable collision detected");
 180                     ShowBD(ptbl->bd);
 181                     printf("hashkey = 0x%x, hashbd = 0x%x\n",
 182                            hashkey, hashbd);
 183                 }
 184
 185                 break;
 186             }
 187         }
 188 #endif /* HASHTEST */
 189
 190
 191         PV = SwagHt = ptbl->mv;
 192
 193         HashCnt++;
 194
 195         if (ptbl->flags & truescore)
 196         {
 197             *score = ptbl->score;
 198             /* adjust *score so moves to mate is from root */
 199
 200             if (*score > SCORE_LIMIT)
 201                 *score -= ply;
 202             else if (*score < -SCORE_LIMIT)
 203                 *score += ply;
 204
 205             *beta = -2 * (SCORE_LIMIT + 1000);
 206         }
 207         else if (ptbl->flags & lowerbound)
 208         {
 209             if (ptbl->score > *alpha)
 210                 *alpha = ptbl->score - 1;
 211         }
 212
 213         return true;
 214     }
 215
 216     return false;
 217 }
 218
 219
 220
 221 /*
 222  * Store the current board position in the transposition table.
 223  */
 224
 225 int
 226 PutInTTable(short side,
 227             short score,
 228             short depth,
 229             short ply,
 230             short beta,
 231             unsigned short mv)
 232 {
 233     struct hashentry  *ptbl;
 234     /*unsigned*/ short i = 0;  /* to match new type of rehash --tpm */
 235
 236     ptbl = &ttable[side][hashkey % ttblsize];
 237
 238     while (true)
 239     {
 240         if ((ptbl->depth) == 0 || ptbl->hashbd == hashbd)
 241             break;
 242
 243         if (++i > rehash)
 244         {
 245             THashCol++;
 246             ptbl += recycle;
 247
 248             break;
 249         }
 250
 251         ptbl++;
 252     }
 253
 254     TTadd++;
 255     HashAdd++;
 256
 257     /* adjust score so moves to mate is from this ply */
 258
 259     if (score > SCORE_LIMIT)
 260         score += ply;
 261     else if (score < -SCORE_LIMIT)
 262         score -= ply;
 263
 264     ptbl->hashbd = hashbd;
 265     ptbl->depth = (unsigned char) depth;
 266     ptbl->score = score;
 267     ptbl->mv = mv;
 268
 269     if (score > beta)
 270     {
 271         ptbl->flags = lowerbound;
 272         ptbl->score = beta + 1;
 273     }
 274     else
 275     {
 276         ptbl->flags = truescore;
 277     }
 278
 279 #if defined HASHTEST
 280     for (i = 0; i < PTBLBDSIZE; i++)
 281         ptbl->bd[i] = CB(i);
 282 #endif /* HASHTEST */
 283
 284     return true;
 285 }
 286
 287
 288
 289 void
 290 ZeroTTable(void)
 291 {
 292     array_zero(ttable[black], (ttblsize + rehash));
 293     array_zero(ttable[white], (ttblsize + rehash));
 294
 295 #ifdef CACHE
 296     array_zero(etab[0], sizeof(struct etable)*(size_t)ETABLE);
 297     array_zero(etab[1], sizeof(struct etable)*(size_t)ETABLE);
 298 #endif
 299
 300     TTadd = 0;
 301 }
 302
 303
 304
 305
 306 #ifdef HASHFILE
 307 int
 308 Fbdcmp(unsigned char *a, unsigned char *b)
 309 {
 310     int i;
 311
 312     for (i = 0; i < PTBLBDSIZE; i++)
 313     {
 314         if (a[i] != b[i])
 315             return false;
 316     }
 317
 318     return true;
 319 }
 320
 321
 322
 323 /*
 324  * Look for the current board position in the persistent transposition table.
 325  */
 326
 327 int
 328 ProbeFTable(short side,
 329             short depth,
 330             short ply,
 331             short *alpha,
 332             short *beta,
 333             short *score)
 334 {
 335     short i;
 336     unsigned long hashix;
 337     struct fileentry new, t;
 338
 339     hashix = ((side == black) ? (hashkey & 0xFFFFFFFE)
 340               : (hashkey | 1)) % filesz;
 341
 342     for (i = 0; i < PTBLBDSIZE; i++)
 343         new.bd[i] = CB(i);
 344
 345     new.flags = 0;
 346
 347     for (i = 0; i < frehash; i++)
 348     {
 349         fseek(hashfile,
 350               sizeof(struct fileentry) * ((hashix + 2 * i) % (filesz)),
 351               SEEK_SET);
 352         fread(&t, sizeof(struct fileentry), 1, hashfile);
 353
 354         if (!t.depth)
 355             break;
 356
 357         if (!Fbdcmp(t.bd, new.bd))
 358             continue;
 359
 360         if (((short) t.depth >= depth)
 361             && (new.flags == (unsigned short)(t.flags
 362                                               & (kingcastle | queencastle))))
 363         {
 364             FHashCnt++;
 365
 366             PV = (t.f << 8) | t.t;
 367             *score = (t.sh << 8) | t.sl;
 368
 369             /* adjust *score so moves to mate is from root */
 370             if (*score > SCORE_LIMIT)
 371                 *score -= ply;
 372             else if (*score < -SCORE_LIMIT)
 373                 *score += ply;
 374
 375             if (t.flags & truescore)
 376             {
 377                 *beta = -((SCORE_LIMIT + 1000)*2);
 378             }
 379             else if (t.flags & lowerbound)
 380             {
 381                 if (*score > *alpha)
 382                     *alpha = *score - 1;
 383             }
 384             else if (t.flags & upperbound)
 385             {
 386                 if (*score < *beta)
 387                     *beta = *score + 1;
 388             }
 389
 390             return (true);
 391         }
 392     }
 393
 394     return (false);
 395 }
 396
 397
 398
 399 /*
 400  * Store the current board position in the persistent transposition table.
 401  */
 402
 403 void
 404 PutInFTable(short side,
 405             short score,
 406             short depth,
 407             short ply,
 408             short alpha,
 409             short beta,
 410             unsigned short f,
 411             unsigned short t)
 412 {
 413     unsigned short i;
 414     unsigned long hashix;
 415     struct fileentry new, tmp;
 416
 417     hashix = ((side == black) ? (hashkey & 0xFFFFFFFE)
 418               : (hashkey | 1)) % filesz;
 419
 420     for (i = 0; i < PTBLBDSIZE; i++)
 421         new.bd[i] = CB(i);
 422
 423     new.f = (unsigned char) f;
 424     new.t = (unsigned char) t;
 425
 426     if (score < alpha)
 427         new.flags = upperbound;
 428     else
 429         new.flags = ((score > beta) ? lowerbound : truescore);
 430
 431     new.depth = (unsigned char) depth;
 432
 433     /* adjust *score so moves to mate is from root */
 434     if (score > SCORE_LIMIT)
 435         score += ply;
 436     else if (score < -SCORE_LIMIT)
 437         score -= ply;
 438
 439
 440     new.sh = (unsigned char) (score >> 8);
 441     new.sl = (unsigned char) (score & 0xFF);
 442
 443     for (i = 0; i < frehash; i++)
 444     {
 445         fseek(hashfile,
 446               sizeof(struct fileentry) * ((hashix + 2 * i) % (filesz)),
 447               SEEK_SET);
 448
 449         if (!fread(&tmp, sizeof(struct fileentry), 1, hashfile) )
 450         {
 451             perror("hashfile");
 452             exit(1);
 453         }
 454
 455         if (tmp.depth && !Fbdcmp(tmp.bd, new.bd))
 456             continue;
 457
 458         if (tmp.depth == depth)
 459             break;
 460
 461         if (!tmp.depth || ((short) tmp.depth < depth))
 462         {
 463             fseek(hashfile,
 464                   sizeof(struct fileentry) * ((hashix + 2 * i) % (filesz)),
 465                   SEEK_SET);
 466
 467             fwrite(&new, sizeof(struct fileentry), 1, hashfile);
 468             FHashAdd++;
 469
 470             break;
 471         }
 472     }
 473 }
 474
 475 #endif /* HASHFILE */
 476 #endif /* ttblsz */
 477
 478
 479
 480 void
 481 ZeroRPT(void)
 482 {
 483     if (ISZERO )
 484     {
 485         array_zero(rpthash, sizeof(rpthash));
 486         ISZERO = 0;
 487     }
 488 }
 489
 490
 491
 492 #if defined CACHE
 493
 494 /*
 495  * Store the current eval position in the transposition table.
 496  */
 497
 498 void
 499 PutInEETable(short side, int score)
 500 {
 501     struct etable  *ptbl;
 502
 503     ptbl = &(*etab[side])[hashkey % (ETABLE)];
 504     ptbl->ehashbd = hashbd;
 505     ptbl->escore[black] = pscore[black];
 506     ptbl->escore[white] = pscore[white];
 507     ptbl->hung[black] = hung[black];
 508     ptbl->hung[white] = hung[white];
 509     ptbl->score = score;
 510
 511 #if !defined SAVE_SSCORE
 512     array_copy(svalue, &(ptbl->sscore), sizeof(svalue));
 513 #endif
 514
 515     EADD++;
 516
 517     return;
 518 }
 519
 520
 521
 522 /* Get an evaluation from the transposition table */
 523
 524 int
 525 CheckEETable(short side)
 526 {
 527     struct etable  *ptbl;
 528
 529     ptbl = &(*etab[side])[hashkey % (ETABLE)];
 530
 531     if (hashbd == ptbl->ehashbd)
 532         return true;
 533
 534     return false;
 535 }
 536
 537
 538
 539 /* Get an evaluation from the transposition table */
 540
 541 int
 542 ProbeEETable(short side, short *score)
 543 {
 544     struct etable  *ptbl;
 545
 546     ptbl = &(*etab[side])[hashkey % (ETABLE)];
 547
 548     if (hashbd == ptbl->ehashbd)
 549     {
 550         pscore[black] = ptbl->escore[black];
 551         pscore[white] = ptbl->escore[white];
 552
 553 #if defined SAVE_SSCORE
 554         array_zero(svalue, sizeof(svalue));
 555 #else
 556         array_copy(&(ptbl->sscore), svalue, sizeof(svalue));
 557 #endif
 558
 559         *score = ptbl->score;
 560         hung[black] = ptbl->hung[black];
 561         hung[white] = ptbl->hung[white];
 562
 563         EGET++;
 564
 565         return true;
 566     }
 567
 568     return false;
 569 }
 570
 571 #endif /* CACHE */
 572
 573
 574
 575