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 #if 0
  39 int
  40 parse(FILE * fd, unsigned short *mv, 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 #endif
 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 beta,
 230             unsigned short mv)
 231 {
 232     struct hashentry  *ptbl;
 233     /*unsigned*/ short i = 0;  /* to match new type of rehash --tpm */
 234
 235     ptbl = &ttable[side][hashkey % ttblsize];
 236
 237     while (true)
 238     {
 239         if ((ptbl->depth) == 0 || ptbl->hashbd == hashbd)
 240             break;
 241
 242         if (++i > rehash)
 243         {
 244             THashCol++;
 245             ptbl += recycle;
 246
 247             break;
 248         }
 249
 250         ptbl++;
 251     }
 252
 253     TTadd++;
 254     HashAdd++;
 255
 256     /* adjust score so moves to mate is from this ply */
 257
 258     if (score > SCORE_LIMIT)
 259         score += ply;
 260     else if (score < -SCORE_LIMIT)
 261         score -= ply;
 262
 263     ptbl->hashbd = hashbd;
 264     ptbl->depth = (unsigned char) depth;
 265     ptbl->score = score;
 266     ptbl->mv = mv;
 267
 268     if (score > beta)
 269     {
 270         ptbl->flags = lowerbound;
 271         ptbl->score = beta + 1;
 272     }
 273     else
 274     {
 275         ptbl->flags = truescore;
 276     }
 277
 278 #if defined HASHTEST
 279     for (i = 0; i < PTBLBDSIZE; i++)
 280         ptbl->bd[i] = CB(i);
 281 #endif /* HASHTEST */
 282
 283     return true;
 284 }
 285
 286
 287
 288 void
 289 ZeroTTable(void)
 290 {
 291     array_zero(ttable[black], (ttblsize + rehash));
 292     array_zero(ttable[white], (ttblsize + rehash));
 293
 294 #ifdef CACHE
 295     array_zero(etab[0], sizeof(struct etable)*(size_t)ETABLE);
 296     array_zero(etab[1], sizeof(struct etable)*(size_t)ETABLE);
 297 #endif
 298
 299     TTadd = 0;
 300 }
 301
 302
 303
 304
 305 #ifdef HASHFILE
 306 int
 307 Fbdcmp(unsigned char *a, unsigned char *b)
 308 {
 309     int i;
 310
 311     for (i = 0; i < PTBLBDSIZE; i++)
 312     {
 313         if (a[i] != b[i])
 314             return false;
 315     }
 316
 317     return true;
 318 }
 319
 320
 321
 322 /*
 323  * Look for the current board position in the persistent transposition table.
 324  */
 325
 326 int
 327 ProbeFTable(short side,
 328             short depth,
 329             short ply,
 330             short *alpha,
 331             short *beta,
 332             short *score)
 333 {
 334     short i;
 335     unsigned long hashix;
 336     struct fileentry new, t;
 337
 338     hashix = ((side == black) ? (hashkey & 0xFFFFFFFE)
 339               : (hashkey | 1)) % filesz;
 340
 341     for (i = 0; i < PTBLBDSIZE; i++)
 342         new.bd[i] = CB(i);
 343
 344     new.flags = 0;
 345
 346     for (i = 0; i < frehash; i++)
 347     {
 348         fseek(hashfile,
 349               sizeof(struct fileentry) * ((hashix + 2 * i) % (filesz)),
 350               SEEK_SET);
 351         fread(&t, sizeof(struct fileentry), 1, hashfile);
 352
 353         if (!t.depth)
 354             break;
 355
 356         if (!Fbdcmp(t.bd, new.bd))
 357             continue;
 358
 359         if (((short) t.depth >= depth)
 360             && (new.flags == (unsigned short)(t.flags
 361                                               & (kingcastle | queencastle))))
 362         {
 363             FHashCnt++;
 364
 365             PV = (t.f << 8) | t.t;
 366             *score = (t.sh << 8) | t.sl;
 367
 368             /* adjust *score so moves to mate is from root */
 369             if (*score > SCORE_LIMIT)
 370                 *score -= ply;
 371             else if (*score < -SCORE_LIMIT)
 372                 *score += ply;
 373
 374             if (t.flags & truescore)
 375             {
 376                 *beta = -((SCORE_LIMIT + 1000)*2);
 377             }
 378             else if (t.flags & lowerbound)
 379             {
 380                 if (*score > *alpha)
 381                     *alpha = *score - 1;
 382             }
 383             else if (t.flags & upperbound)
 384             {
 385                 if (*score < *beta)
 386                     *beta = *score + 1;
 387             }
 388
 389             return (true);
 390         }
 391     }
 392
 393     return (false);
 394 }
 395
 396
 397
 398 /*
 399  * Store the current board position in the persistent transposition table.
 400  */
 401
 402 void
 403 PutInFTable(short side,
 404             short score,
 405             short depth,
 406             short ply,
 407             short alpha,
 408             short beta,
 409             unsigned short f,
 410             unsigned short t)
 411 {
 412     unsigned short i;
 413     unsigned long hashix;
 414     struct fileentry new, tmp;
 415
 416     hashix = ((side == black) ? (hashkey & 0xFFFFFFFE)
 417               : (hashkey | 1)) % filesz;
 418
 419     for (i = 0; i < PTBLBDSIZE; i++)
 420         new.bd[i] = CB(i);
 421
 422     new.f = (unsigned char) f;
 423     new.t = (unsigned char) t;
 424
 425     if (score < alpha)
 426         new.flags = upperbound;
 427     else
 428         new.flags = ((score > beta) ? lowerbound : truescore);
 429
 430     new.depth = (unsigned char) depth;
 431
 432     /* adjust *score so moves to mate is from root */
 433     if (score > SCORE_LIMIT)
 434         score += ply;
 435     else if (score < -SCORE_LIMIT)
 436         score -= ply;
 437
 438
 439     new.sh = (unsigned char) (score >> 8);
 440     new.sl = (unsigned char) (score & 0xFF);
 441
 442     for (i = 0; i < frehash; i++)
 443     {
 444         fseek(hashfile,
 445               sizeof(struct fileentry) * ((hashix + 2 * i) % (filesz)),
 446               SEEK_SET);
 447
 448         if (!fread(&tmp, sizeof(struct fileentry), 1, hashfile) )
 449         {
 450             perror("hashfile");
 451             exit(1);
 452         }
 453
 454         if (tmp.depth && !Fbdcmp(tmp.bd, new.bd))
 455             continue;
 456
 457         if (tmp.depth == depth)
 458             break;
 459
 460         if (!tmp.depth || ((short) tmp.depth < depth))
 461         {
 462             fseek(hashfile,
 463                   sizeof(struct fileentry) * ((hashix + 2 * i) % (filesz)),
 464                   SEEK_SET);
 465
 466             fwrite(&new, sizeof(struct fileentry), 1, hashfile);
 467             FHashAdd++;
 468
 469             break;
 470         }
 471     }
 472 }
 473
 474 #endif /* HASHFILE */
 475 #endif /* ttblsz */
 476
 477
 478
 479 void
 480 ZeroRPT(void)
 481 {
 482     if (ISZERO )
 483     {
 484         array_zero(rpthash, sizeof(rpthash));
 485         ISZERO = 0;
 486     }
 487 }
 488
 489
 490
 491 #if defined CACHE
 492
 493 /*
 494  * Store the current eval position in the transposition table.
 495  */
 496
 497 void
 498 PutInEETable(short side, int score)
 499 {
 500     struct etable  *ptbl;
 501
 502     ptbl = &(*etab[side])[hashkey % (ETABLE)];
 503     ptbl->ehashbd = hashbd;
 504     ptbl->escore[black] = pscore[black];
 505     ptbl->escore[white] = pscore[white];
 506     ptbl->hung[black] = hung[black];
 507     ptbl->hung[white] = hung[white];
 508     ptbl->score = score;
 509
 510 #if !defined SAVE_SSCORE
 511     array_copy(svalue, &(ptbl->sscore), sizeof(svalue));
 512 #endif
 513
 514     EADD++;
 515
 516     return;
 517 }
 518
 519
 520
 521 /* Get an evaluation from the transposition table */
 522
 523 int
 524 CheckEETable(short side)
 525 {
 526     struct etable  *ptbl;
 527
 528     ptbl = &(*etab[side])[hashkey % (ETABLE)];
 529
 530     if (hashbd == ptbl->ehashbd)
 531         return true;
 532
 533     return false;
 534 }
 535
 536
 537
 538 /* Get an evaluation from the transposition table */
 539
 540 int
 541 ProbeEETable(short side, short *score)
 542 {
 543     struct etable  *ptbl;
 544
 545     ptbl = &(*etab[side])[hashkey % (ETABLE)];
 546
 547     if (hashbd == ptbl->ehashbd)
 548     {
 549         pscore[black] = ptbl->escore[black];
 550         pscore[white] = ptbl->escore[white];
 551
 552 #if defined SAVE_SSCORE
 553         array_zero(svalue, sizeof(svalue));
 554 #else
 555         array_copy(&(ptbl->sscore), svalue, sizeof(svalue));
 556 #endif
 557
 558         *score = ptbl->score;
 559         hung[black] = ptbl->hung[black];
 560         hung[white] = ptbl->hung[white];
 561
 562         EGET++;
 563
 564         return true;
 565     }
 566
 567     return false;
 568 }
 569
 570 #endif /* CACHE */
 571
 572
 573
 574