home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / gnushogi-1.1 / src / util.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-16  |  12.6 KB  |  595 lines
  1. /*
  2.  * util.c - C source for GNU SHOGI
  3.  *
  4.  * Copyright (c) 1993 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. #include "gnushogi.h"
  28. unsigned int TTadd = 0;
  29. short int recycle;
  30. extern char mvstr[4][6];
  31.  
  32. #ifdef THINK_C
  33. #include <string.h>
  34. #define bcopy(src,dst,len) memcpy(dst,src,len)
  35. #endif
  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.     i -= NO_SQUARES;
  105.     return ( (Captured[black][i] << 4) | Captured[white][i] );
  106.   }
  107. }
  108.  
  109.       
  110.  
  111. #if defined DEBUG && defined CACHE                
  112.                           
  113. inline
  114. char
  115. BDpiece(unsigned char p)
  116. {
  117.   unsigned short piece = p & 0x7f;
  118.   if ( piece == no_piece )
  119.     return '-';
  120.   else if ( p & 0x80 )
  121.     return qxx[piece];
  122.   else
  123.     return pxx[piece];
  124. }
  125.  
  126. inline
  127. char
  128. BDpromoted(unsigned char p)
  129. {
  130.   unsigned short piece = p & 0x7f;
  131.   if ( is_promoted[piece] )
  132.     return '+';
  133.   else
  134.     return ' ';
  135. }
  136.  
  137. void
  138. ShowBD(unsigned char bd[])
  139. {
  140.   register short i;
  141.   for ( i = 0; i < PTBLBDSIZE; i++) 
  142.     {                   
  143.     if ( i < NO_SQUARES )
  144.       { 
  145.             printf("%c%c(%c%c) ",
  146.                BDpromoted(bd[i]),BDpiece(bd[i]),
  147.                BDpromoted(CB(i)),BDpiece(CB(i)));
  148.           if ( i % NO_COLS == NO_COLS - 1 )
  149.           printf("\n");
  150.       }
  151.     else
  152.       printf("%2x(%2x) ",bd[i],CB(i));
  153.     };
  154.   printf("\n");
  155. }        
  156.  
  157. #endif
  158.  
  159.  
  160.  
  161. #if ttblsz
  162.  
  163.  
  164.  
  165. int
  166. ProbeTTable (short int side,
  167.          short int depth,
  168.          short int ply,
  169.          short int *alpha,
  170.          short int *beta,
  171.          short int *score)
  172.  
  173. /*
  174.  * Look for the current board position in the transposition table.
  175.  */
  176.  
  177. {
  178.   register struct hashentry *ptbl;
  179.   register /*unsigned*/ short i;  /*to match new type of rehash --tpm*/
  180.  
  181.   ptbl = &ttable[side][hashkey & (ttblsize - 1)];
  182.  
  183.   /* rehash max rehash times */
  184.   for (i = 0; (ptbl->depth) && (ptbl->hashbd != hashbd) && (i < rehash); i++) ptbl++;
  185.   if ((ptbl->depth) && (ptbl->hashbd == hashbd))
  186. /*     ^^^^^^^^^^^^   we can use some informations of the entry even
  187.                       the depth is not large enough */
  188.     {  
  189. #if defined HASHTEST
  190.       for (i = 0; i < PTBLBDSIZE; i++)
  191.     {
  192.       if (ptbl->bd[i] != CB (i))
  193.         {
  194.           HashCol++;
  195. #if defined DEBUG && !defined BAREBONES
  196.           ShowMessage (CP[199]);    /*ttable collision detected*/
  197. #endif
  198.           return(false);
  199.         }
  200.     }
  201. #endif /* HASHTEST */ 
  202.  
  203.  
  204.       PV = SwagHt = ptbl->mv;
  205.       if ((short) ptbl->depth >= depth)
  206.     {
  207. #if !defined BAREBONES
  208.           HashCnt++;
  209. #endif
  210.       if (ptbl->flags & truescore)
  211.         {
  212.           *score = ptbl->score;
  213.           /* adjust *score so moves to mate is from root */
  214.           if (*score > SCORE_LIMIT)
  215.         *score -= ply;
  216.           else if (*score < -SCORE_LIMIT)
  217.         *score += ply;
  218.           *beta = -((SCORE_LIMIT+1000)*2);
  219.         }
  220. #ifdef notdef            /* Never happens! see search */
  221.       else if (ptbl->flags & upperbound)
  222.         {
  223.           if (ptbl->score < *beta)
  224.         *beta = ptbl->score + 1;
  225.         }
  226. #endif
  227.       else if (ptbl->flags & lowerbound)
  228.         {
  229.           if (ptbl->score > *alpha)
  230.         *alpha = ptbl->score - 1;
  231.         }
  232.       return (true);
  233.     }
  234.     }
  235.   return (false);
  236. }
  237.  
  238.  
  239. int
  240. PutInTTable (short int side,
  241.          short int score,
  242.          short int depth,
  243.          short int ply,
  244.          short int alpha,
  245.          short int beta,
  246.          short unsigned int mv)
  247.  
  248. /*
  249.  * Store the current board position in the transposition table.
  250.  */
  251.  
  252. {
  253.   register struct hashentry *ptbl;
  254.   register /*unsigned*/ short i;  /*to match new type of rehash --tpm*/
  255.  
  256.   ptbl = &ttable[side][hashkey & (ttblsize - 1)];
  257.  
  258.   /* rehash max rehash times */
  259.   for (i = 0; ptbl->depth && ptbl->hashbd != hashbd && i < rehash; i++)
  260.     ptbl++;
  261.   if (i == rehash) {
  262. #if !defined BAREBONES
  263.     THashCol++;
  264. #endif
  265.     ptbl -= recycle;}
  266.   if (depth >= (short)ptbl->depth || ptbl->hashbd != hashbd)
  267.     {
  268. #if !defined BAREBONES
  269.       TTadd++;
  270.       HashAdd++; 
  271. #endif
  272.       ptbl->hashbd = hashbd;
  273.       ptbl->depth = (unsigned char) depth;
  274.       /* adjust score so moves to mate is from this ply */
  275.       if (score > SCORE_LIMIT)
  276.     score += ply;
  277.       else if (score < -SCORE_LIMIT)
  278.     score -= ply;
  279.       ptbl->score = score;
  280.       ptbl->mv = mv;
  281. #ifdef DEBUG4
  282.       if (debuglevel & 32)
  283.     {
  284.       algbr (mv >> 8, mv & 0xff, 0);
  285.       printf ("-add-> d=%d s=%d p=%d a=%d b=%d %s\n", depth, score, ply, alpha, beta, mvstr);
  286.     }
  287. #endif
  288. /*#ifdef notdef
  289.       if (score < alpha)
  290.     ptbl->flags = upperbound;
  291.       else
  292. /*#endif /* 0 */
  293.       if (score > beta)
  294.     {
  295.       ptbl->flags = lowerbound;
  296.       score = beta + 1;
  297.     }
  298.       else
  299.     ptbl->flags = truescore;
  300.        
  301. #if defined HASHTEST
  302.       for (i = 0; i < PTBLBDSIZE; i++)
  303.     {
  304.       ptbl->bd[i] = CB (i);
  305.     }
  306. #endif /* HASHTEST */
  307.       return true;
  308.     }
  309.   return false;
  310. }
  311.  
  312.    
  313. static struct hashentry *ttageb, *ttagew;
  314.  
  315. void
  316. ZeroTTable (void)
  317. {
  318.    register struct hashentry *w, *b;
  319.    for ( b=ttable[black], w=ttable[white]; b < &ttable[black][ttblsize]; w++, b++)
  320.      { 
  321.         w->depth = 0; 
  322.         b->depth = 0;
  323.      }
  324.    ttageb = ttable[black]; 
  325.    ttagew = ttable[white];
  326. #ifdef CACHE
  327.    memset ((char *) etab[0], 0, sizeof(struct etable)*(size_t)ETABLE);
  328.    memset ((char *) etab[1], 0, sizeof(struct etable)*(size_t)ETABLE);
  329. #endif
  330. #ifdef notdef
  331.    register unsigned int a;
  332.    for (a = 0; a < ttblsize + (unsigned int)rehash; a++)
  333.      {
  334.        ttable[black][a].depth = 0;
  335.        ttable[white][a].depth = 0;
  336.      }
  337. #endif
  338.     TTadd = 0; 
  339. }
  340.  
  341. #ifdef HASHFILE
  342. int Fbdcmp(unsigned char *a,unsigned char *b)
  343. {
  344.     register int i;
  345.     for(i = 0; i < PTBLBDSIZE; i++)
  346.         if(a[i] != b[i]) return false;
  347.     return true;
  348. }
  349. int
  350. ProbeFTable (short int side,
  351.          short int depth,
  352.          short int ply,
  353.          short int *alpha,
  354.          short int *beta,
  355.          short int *score)
  356.  
  357. /*
  358.  * Look for the current board position in the persistent transposition table.
  359.  */
  360.  
  361. {
  362.   register short int i;
  363.   register unsigned long hashix;
  364.   struct fileentry new, t;
  365.  
  366.   hashix = ((side == black) ? (hashkey & 0xFFFFFFFE) : (hashkey | 1)) & filesz;
  367.  
  368.   for (i = 0; i < PTBLBDSIZE; i++)
  369.     new.bd[i] = CB (i);
  370.   new.flags = 0;
  371.   for (i = 0; i < frehash; i++)
  372.     {
  373.       fseek (hashfile,
  374.          sizeof (struct fileentry) * ((hashix + 2 * i) & (filesz)),
  375.          SEEK_SET);
  376.       fread (&t, sizeof (struct fileentry), 1, hashfile);
  377.       if (!t.depth) break;
  378.        if(!Fbdcmp(t.bd, new.bd)) continue;
  379.       if (((short int) t.depth >= depth) 
  380.       && (new.flags == (unsigned short)(t.flags & (kingcastle | queencastle))))
  381.     {
  382. #if !defined BAREBONES
  383.       FHashCnt++;
  384. #endif
  385.       PV = (t.f << 8) | t.t;
  386.       *score = (t.sh << 8) | t.sl;
  387.       /* adjust *score so moves to mate is from root */
  388.       if (*score > SCORE_LIMIT)
  389.         *score -= ply;
  390.       else if (*score < -SCORE_LIMIT)
  391.         *score += ply;
  392.       if (t.flags & truescore)
  393.         {
  394.           *beta = -((SCORE_LIMIT+1000)*2);
  395.         }
  396.       else if (t.flags & lowerbound)
  397.         {
  398.           if (*score > *alpha)
  399.         *alpha = *score - 1;
  400.         }
  401.       else if (t.flags & upperbound)
  402.         {
  403.           if (*score < *beta)
  404.         *beta = *score + 1;
  405.         }
  406.       return (true);
  407.     }
  408.     }
  409.   return (false);
  410. }
  411.  
  412. void
  413. PutInFTable (short int side,
  414.          short int score,
  415.          short int depth,
  416.          short int ply,
  417.          short int alpha,
  418.          short int beta,
  419.          short unsigned int f,
  420.          short unsigned int t)
  421.  
  422. /*
  423.  * Store the current board position in the persistent transposition table.
  424.  */
  425.  
  426. {
  427.   register unsigned short i;
  428.   register unsigned long hashix;
  429.   struct fileentry new, tmp;
  430.  
  431.   hashix = ((side == black) ? (hashkey & 0xFFFFFFFE) : (hashkey | 1)) & filesz;
  432.   for (i = 0; i < PTBLBDSIZE; i++) 
  433.     new.bd[i] = CB (i);
  434.   new.f = (unsigned char) f;
  435.   new.t = (unsigned char) t;
  436.   if (score < alpha)
  437.     new.flags = upperbound;
  438.   else
  439.     new.flags = ((score > beta) ? lowerbound : truescore);
  440.   new.depth = (unsigned char) depth;
  441.   /* adjust *score so moves to mate is from root */
  442.   if (score > SCORE_LIMIT)
  443.     score += ply;
  444.   else if (score < -SCORE_LIMIT)
  445.     score -= ply;
  446.  
  447.  
  448.   new.sh = (unsigned char) (score >> 8);
  449.   new.sl = (unsigned char) (score & 0xFF);
  450.  
  451.   for (i = 0; i < frehash; i++)
  452.     {
  453.       fseek (hashfile,
  454.          sizeof (struct fileentry) * ((hashix + 2 * i) & (filesz)),
  455.          SEEK_SET);
  456.       if ( !fread (&tmp, sizeof (struct fileentry), 1, hashfile) )
  457.         {perror("hashfile");exit(1);}
  458.       if (tmp.depth && !Fbdcmp(tmp.bd,new.bd))continue;
  459.       if (tmp.depth == depth) break;
  460.       if (!tmp.depth || (short) tmp.depth < depth)
  461.     {
  462.       fseek (hashfile,
  463.          sizeof (struct fileentry) * ((hashix + 2 * i) & (filesz)),
  464.          SEEK_SET);
  465. #ifdef DEBUG4
  466.           if (debuglevel & 32)
  467.             {
  468.           printf ("-fadd\n");
  469.         }
  470. #endif
  471.       fwrite (&new, sizeof (struct fileentry), 1, hashfile);
  472. #if !defined BAREBONES
  473.           FHashAdd++;
  474. #endif
  475.       break;
  476.     }
  477.     }
  478. }
  479.  
  480. #endif /* HASHFILE */
  481. #endif /* ttblsz */
  482.  
  483. void
  484. ZeroRPT (void)
  485. {
  486. #ifdef NOMEMSET
  487.   register int side, i;
  488.   for (side = black; side <= white; side++)
  489.     for (i = 0; i < 256;)
  490.       rpthash[side][i++] = 0;
  491. #else
  492.    memset ((char *) rpthash, 0, sizeof (rpthash));
  493. #endif
  494. }
  495.  
  496.  
  497.  
  498.  
  499. #if defined CACHE
  500.  
  501. void
  502. PutInEETable (short int side,int score)
  503.  
  504. /*
  505.  * Store the current eval position in the transposition table.
  506.  */
  507.  
  508. {
  509.     register struct etable *ptbl;
  510.     ptbl = &(*etab[side])[hashkey & (ETABLE - 1)];
  511.     if (ptbl->ehashbd == hashbd) return;
  512. #if defined CACHETEST
  513.     { short i;
  514.       for (i = 0; i < PTBLBDSIZE; i++)
  515.     {
  516.       ptbl->bd[i] = CB (i);
  517.     }
  518.     }
  519. #endif /* CACHETEST */
  520.     ptbl->ehashbd = hashbd;
  521.     ptbl->escore[black] = pscore[black];
  522.     ptbl->escore[white] = pscore[white];
  523.     ptbl->hung[black] = hung[black];
  524.     ptbl->hung[white] = hung[white];
  525.     ptbl->score = score;
  526.     bcopy (svalue, &(ptbl->sscore), sizeof (svalue));
  527. #if !defined BAREBONES
  528.     EADD++;
  529. #endif
  530.     return;
  531. }
  532.  
  533.  
  534. int
  535. CheckEETable (short int side)
  536.  
  537. /* Get an evaluation from the transposition table */
  538. {
  539.     register struct etable *ptbl;
  540.     ptbl = &(*etab[side])[hashkey & (ETABLE - 1)];
  541.     if (hashbd == ptbl->ehashbd) 
  542.       {
  543.         return true;
  544.       }
  545.     return false;
  546. }
  547.  
  548.  
  549. int
  550. ProbeEETable (short int side, short int *score)
  551.  
  552. /* Get an evaluation from the transposition table */
  553. {
  554.     register struct etable *ptbl;
  555.     ptbl = &(*etab[side])[hashkey & (ETABLE - 1)];
  556.     if (hashbd == ptbl->ehashbd)
  557.       {
  558. #if defined CACHETEST
  559.     short i;
  560.         for (i = 0; i < PTBLBDSIZE; i++)
  561.       {
  562.         if (ptbl->bd[i] != CB (i))
  563.           {
  564. #if !defined BAREBONES
  565.             ShowMessage ("eetable probe collision detected");
  566. #endif
  567. #if DEBUG            
  568.         ShowBD(ptbl->bd);
  569. #endif
  570.             return false;
  571.           }
  572.       }
  573. #endif /* CACHETEST */ 
  574.       pscore[black] = ptbl->escore[black];
  575.       pscore[white] = ptbl->escore[white];
  576.       bcopy (&(ptbl->sscore), svalue, sizeof (svalue));
  577.       *score = ptbl->score;
  578.           hung[black] = ptbl->hung[black];
  579.           hung[white] = ptbl->hung[white];
  580. #if !defined BAREBONES
  581.       EGET++;
  582. #endif
  583.       return true;
  584.       }
  585.     return false;
  586.  
  587. }
  588.  
  589.  
  590. #endif /* CACHE */ 
  591.  
  592.  
  593.  
  594.  
  595.