gnushogi/util.c

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