src/util.c

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