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