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  *
   8  * GNU SHOGI is based on GNU CHESS
   9  *
  10  * Copyright (c) 1988, 1989, 1990 John Stanback
  11  * Copyright (c) 1992 Free Software Foundation
  12  *
  13  * This file is part of GNU SHOGI.
  14  *
  15  * GNU Shogi is free software; you can redistribute it and/or modify it
  16  * under the terms of the GNU General Public License as published by the
  17  * Free Software Foundation; either version 3 of the License,
  18  * or (at your option) any later version.
  19  *
  20  * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
  21  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  22  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  23  * for more details.
  24  *
  25  * You should have received a copy of the GNU General Public License along
  26  * with GNU Shogi; see the file COPYING. If not, see
  27  * <http://www.gnu.org/licenses/>.
  28  * ----------------------------------------------------------------------
  29  *
  30  */
  31
  32 #include "gnushogi.h"
  33
  34 unsigned int TTadd = 0;
  35 short recycle;
  36 short ISZERO = 1;
  37
  38
  39 int
  40 parse(FILE * fd, unsigned short *mv, short side, char *opening)
  41 {
  42     int c, i, r1, r2, c1, c2;
  43     char s[128];
  44     char *p;
  45
  46     while (((c = getc(fd)) == ' ') || (c == '\n'));
  47
  48     i = 0;
  49     s[0] = (char) c;
  50
  51     if (c == '!')
  52     {
  53         p = opening;
  54         do
  55         {
  56             *p++ = c;
  57             c = getc(fd);
  58
  59             if ((c == '\n') || (c == EOF))
  60             {
  61                 *p = '\0';
  62                 return 0;
  63             }
  64         }
  65         while (true);
  66     }
  67
  68     while ((c != '?') && (c != ' ')
  69            && (c != '\t') && (c != '\n') && (c != EOF))
  70     {
  71         s[++i] = (char) (c = getc(fd));
  72     }
  73
  74     s[++i] = '\0';
  75
  76     if (c == EOF)
  77         return (-1);
  78
  79     if ((s[0] == '!') || (s[0] == ';') || (i < 3))
  80     {
  81         while ((c != '\n') && (c != EOF))
  82             c = getc(fd);
  83
  84         return 0;
  85     }
  86
  87     c1 = COL_NAME(s[0]);
  88     r1 = ROW_NAME(s[1]);
  89     c2 = COL_NAME(s[2]);
  90     r2 = ROW_NAME(s[3]);
  91     *mv = (locn(r1, c1) << 8) | locn(r2, c2);
  92
  93     if (c == '?')
  94     {
  95         /* Bad move, not for the program to play */
  96         *mv |= 0x8000;      /* Flag it ! */
  97         c = getc(fd);
  98     }
  99
 100     return 1;
 101 }
 102
 103
 104 /*
 105  * The field of a hashtable is computed as follows:
 106  *   if sq is on board (< NO_SQUARES) the field gets the value
 107  *     of the piece on the square sq;
 108  *   if sq is off board (>= NO_SQUARES) it is a catched figure,
 109  *     and the field gets the number of catched pieces for
 110  *     each side.
 111  */
 112
 113 inline unsigned char
 114 CB(short sq)
 115 {
 116     short i = sq;
 117
 118     if (i < NO_SQUARES)
 119     {
 120         return ((color[i] == white) ? (0x80 | board[i]) : board[i]);
 121     }
 122     else
 123     {
 124         i -= NO_SQUARES;
 125         return ((Captured[black][i] << 4) | Captured[white][i]);
 126     }
 127 }
 128
 129
 130
 131
 132 #if ttblsz
 133
 134 /*
 135  * Look for the current board position in the transposition table.
 136  */
 137
 138 int
 139 ProbeTTable (short side,
 140              short depth,
 141              short ply,
 142              short *alpha,
 143              short *beta,
 144              short *score)
 145 {
 146     struct hashentry  *ptbl;
 147     /*unsigned*/ short i = 0;  /* to match new type of rehash --tpm */
 148
 149     ptbl = &ttable[side][hashkey % ttblsize];
 150
 151     while (true)
 152     {
 153         if ((ptbl->depth) == 0)
 154             return false;
 155
 156         if (ptbl->hashbd == hashbd)
 157             break;
 158
 159         if (++i > rehash)
 160             return false;
 161
 162         ptbl++;
 163     }
 164
 165     /* rehash max rehash times */
 166
 167     if (((short)(ptbl->depth) >= (short) depth))
 168     {
 169 #ifdef HASHTEST
 170         for (i = 0; i < PTBLBDSIZE; i++)
 171         {
 172             if (ptbl->bd[i] != CB(i))
 173             {
 174                 HashCol++;
 175
 176                 if (!barebones)
 177                 {
 178                     ShowMessage("ttable collision detected");
 179                     ShowBD(ptbl->bd);
 180                     printf("hashkey = 0x%x, hashbd = 0x%x\n",
 181                            hashkey, hashbd);
 182                 }
 183
 184                 break;
 185             }
 186         }
 187 #endif /* HASHTEST */
 188
 189
 190         PV = SwagHt = ptbl->mv;
 191
 192         HashCnt++;
 193
 194         if (ptbl->flags & truescore)
 195         {
 196             *score = ptbl->score;
 197             /* adjust *score so moves to mate is from root */
 198
 199             if (*score > SCORE_LIMIT)
 200                 *score -= ply;
 201             else if (*score < -SCORE_LIMIT)
 202                 *score += ply;
 203
 204             *beta = -2 * (SCORE_LIMIT + 1000);
 205         }
 206         else if (ptbl->flags & lowerbound)
 207         {
 208             if (ptbl->score > *alpha)
 209                 *alpha = ptbl->score - 1;
 210         }
 211
 212         return true;
 213     }
 214
 215     return false;
 216 }
 217
 218
 219
 220 /*
 221  * Store the current board position in the transposition table.
 222  */
 223
 224 int
 225 PutInTTable(short side,
 226             short score,
 227             short depth,
 228             short ply,
 229             short alpha,
 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