home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 8 / FreshFishVol8-CD1.bin / useful / game / think / uchess / src / ttable.c < prev    next >
C/C++ Source or Header  |  1994-06-12  |  18KB  |  818 lines
  1. /* ttable.c -- Transposition table code to be included in search.c */
  2. /* #include "gnuchess.h" /* already included, see search.c */
  3. /* #include "ttable.h" /* dito */
  4. /* NOTE: The static evaluation cache "EETable" belongs to eval.c and cannot*/
  5. /*       be moved to ttable.c */
  6. /* Privae types and data */
  7.  
  8. #include <proto/exec.h>
  9. #include <exec/memory.h>
  10. #include <proto/dos.h>
  11.  
  12. //#define TT_EXPIRATION 40000 // nominal exp node value
  13.  
  14. #ifndef AMIGA
  15. struct hashentry
  16.      {
  17.        unsigned long hashbd;
  18.        UCHAR flags, depth;      /* CHAR saves some space */
  19.        tshort score;
  20.        utshort mv;
  21. #ifdef HASHTEST
  22.        UCHAR bd[32];
  23. #endif /* HASHTEST */
  24. #ifdef NEWAGE
  25.     utshort age;        /* age of last use */
  26. #endif
  27.      };
  28. unsigned long ttblsize;
  29. #endif // AMIGA
  30.  
  31. extern struct hashentry huge __aligned *ttable[2];
  32.  
  33. /* unsigned */ extern SHORT __aligned rehash;  /* -1 is used as a flag --tpm */
  34. #ifdef NEWAGE
  35.         utshort TTage;        /* Current ttable age */
  36.         UTSHORT TTageClock,    /* Count till next age tick */
  37.                 TTageRate;      /* new entry counts per age tick */
  38.         UTSHORT TTdepthage[MAXDEPTH+1];    /* Depth bonus for aging*/
  39.         UTSHORT newage = NEWAGE;    /* Initialization tuning parameter */
  40.         extern unsigned int __aligned TTadd;
  41. #else
  42. unsigned int ttbllimit;
  43. extern unsigned int TTadd;
  44. #endif
  45.  
  46. #ifdef HASHSTATS
  47. unsigned long ttdepthin[MAXDEPTH+1], ttdepthout[MAXDEPTH+1];
  48. unsigned long ttrehash[MAXrehash+1];
  49. unsigned long ttprobe[MAXDEPTH+1];
  50. unsigned long HashCnt, HashAdd, FHashCnt, FHashAdd, HashCol, THashCol;
  51. #endif
  52.  
  53. /* hashtable flags */
  54. #define truescore 0x0001
  55. #define lowerbound 0x0002
  56. #define upperbound 0x0004
  57. #define kingcastle 0x0008
  58. #define queencastle 0x0010
  59. #define evalflag 0x0020
  60.  
  61.  
  62. void
  63. Initialize_ttable ()
  64. {
  65.   char astr[32];
  66.   int doit = true;
  67.  
  68.   if (rehash < 0) rehash = MAXrehash;
  69. while(doit && ttblsize >= (1<<13)){
  70.   ttable[0] = (struct hashentry *)malloc(sizeof(struct hashentry)*(ttblsize+rehash));
  71.   ttable[1] = (struct hashentry *)malloc(sizeof(struct hashentry)*(ttblsize+rehash));
  72.   if(ttable[0] == NULL || ttable[1] == NULL){
  73.   if(ttable[0] != NULL)free(ttable[0]);
  74.   ttblsize = ttblsize>>1;
  75.   } else doit = false;
  76. }
  77.   if(ttable[0] == NULL || ttable[1] == NULL)
  78.    {
  79.     ShowMessage("Critical Mem Failure");
  80.     Delay(100L);
  81.     AmigaShutDown();
  82.     exit(1);
  83.    }
  84.   else {
  85. #ifdef NEWAGE
  86.     int j;
  87.         unsigned long k;
  88. #endif
  89.         sprintf(astr,"transposition tbl is %d\n",ttblsize);
  90.         ShowMessage(astr);
  91. #ifdef NEWAGE
  92.     /* WARNING: Bogus parameters ahead!
  93.      * The numbers that follow are based on pure fiction
  94.      * and are not contaminated with facts
  95.      */
  96.     TTageRate = ttblsize/3000 + 1; // try 3k, 1500 and 5000 and see
  97.                     // which gives lowest node cnts
  98.     TTdepthage[0] = 32768;
  99.     for (j=1, k = 50; j<=MAXDEPTH; j++, k *= (13-j))
  100.       {
  101.         /* Maximum k = 50 * 11! ~= 2^31 (this is a fact) */
  102.         TTdepthage[j] = (TTdepthage[j-1] > k/TTageRate) ?
  103.         TTdepthage[j-1] - k/TTageRate : 0;
  104.       }
  105. #else
  106.     ttbllimit = ttblsize<<1 - ttblsize>>2;
  107. #endif
  108.   }
  109. }
  110.  
  111. #define CB(i) (UCHAR) ((color[2 * (i)] ? 0x80 : 0)\
  112.     | (board[2 * (i)] << 4)\
  113.     | (color[2 * (i) + 1] ? 0x8 : 0)\
  114.     | (board[2 * (i) + 1]))
  115.  
  116. int __inline
  117. ProbeTTable (int side,
  118.          int depth,
  119.          int ply,
  120.          SHORT *alpha,
  121.          SHORT *beta,
  122.          SHORT *score)
  123.  
  124. /*
  125.  * Look for the current board position in the transposition table.
  126.  */
  127.  
  128. {
  129.   register struct hashentry *ptbl;
  130.   register /*unsigned*/ SHORT i = 0;    /*to match new type of rehash --tpm*/
  131.  
  132. #ifndef NEWAGE
  133.   ptbl = &ttable[side][hashkey % ttblsize];
  134.   while (true)
  135.     {
  136.       if (ptbl->depth == 0) return false;
  137.       if (ptbl->hashbd == hashbd) break;
  138.       if (++i > rehash) return false;
  139.       ptbl++;
  140.     }
  141. #else
  142.   for (i=rehash, ptbl = &ttable[side][hashkey % ttblsize];
  143.         ptbl->hashbd != hashbd; ptbl++)
  144.     if (--i == 0) return false;
  145.   /* Update age of rediscovered node */
  146.   ptbl->age = TTage - TTdepthage[ptbl->depth];
  147. #endif
  148.  
  149.   PV = SwagHt = ptbl->mv;
  150.   if ((ptbl->depth >= (short) depth))
  151.     {
  152.       if (ptbl->flags & truescore)
  153.     {
  154.       *score = ptbl->score;
  155.       /* adjust *score so moves to mate is from root */
  156.       if (*score > 9000) *score -= ply;
  157.       else if (*score < -9000) *score += ply;
  158.       *beta = -20000;
  159.     }
  160.       else if (ptbl->flags & lowerbound)
  161.     {
  162.       if (ptbl->score > *alpha)
  163.         *alpha = ptbl->score;
  164.     }
  165.       return (true);
  166.     }
  167.   return (false);
  168. }
  169.  
  170. int __inline
  171. PutInTTable 
  172.         (int side,
  173.          int score,
  174.          int depth,
  175.          int ply,
  176.          //int alpha,
  177.          int beta,
  178.          unsigned int mv)
  179.  
  180. /*
  181.  * Store the current board position in the transposition table.
  182.  */
  183.  
  184.   {
  185.     register struct hashentry *ptbl,*oldest;
  186.         unsigned short old;
  187.     register /*unsigned*/ SHORT i = 0;    /*to match new type of rehash --tpm*/
  188.  
  189. #ifdef NEWAGE
  190.     i=rehash;
  191.     old = 0;
  192.     ptbl = &ttable[side][hashkey % ttblsize];
  193.     while (true)
  194.       {
  195.         if (ptbl->hashbd == hashbd)
  196.           {
  197.             if(ptbl->depth > (UCHAR)depth) return false;
  198.             else break;
  199.           }
  200.          if (((TTage - ptbl->age) /*& 0xFFFF*/) > old) 
  201.           {
  202.             old = (TTage - ptbl->age)/* & 0xFFFF*/;
  203.             //if (old > TT_EXPIRATION) break; /* Use this expired entry */
  204.             oldest = ptbl;
  205.           }
  206.         if (--i == 0)
  207.           {
  208.             ptbl = oldest;
  209.             break;
  210.           }
  211.         ptbl++;
  212.       }
  213.  
  214.     if (--TTageClock == 0)
  215.       {
  216.         TTageClock = TTageRate;
  217.         TTage++;  /* Everyone is now just a little older */
  218.       }
  219.         TTadd++;
  220.     /* Update age of this node */
  221.     ptbl->age = TTage - TTdepthage[ptbl->depth];
  222. #else
  223.     TTadd++;
  224. #endif
  225. #ifdef HASHSTATS
  226.     HashAdd++;
  227. #endif
  228.     if(ptbl->depth > (UCHAR)depth) return false;
  229.     ptbl->hashbd = hashbd;
  230.     ptbl->depth = (UCHAR) depth;
  231.     ptbl->score = score;
  232.     ptbl->mv = mv;
  233.     if (score > beta)
  234.       {
  235.         ptbl->flags = lowerbound;
  236.         ptbl->score = beta + 1;
  237.       }
  238.     else
  239.        {
  240.                 /* adjust score so moves to mate is from this ply */
  241.              if (score > 9000) score += ply;
  242.              else if (score < -9000 && score != -9999) score -= ply;
  243.                 ptbl->score = score;
  244.           ptbl->flags = truescore;
  245.        }
  246.  
  247.     return true;
  248.   }
  249.  
  250. void
  251. ZeroTTable (int iop) /* iop: 0= clear any, 1= clear agged */
  252.   {
  253. #ifdef NEWAGE
  254.     if(iop==0)
  255.       {
  256.         TTageClock = TTageRate;
  257.         TTage = TTdepthage[0]+1; /* used to be newage + 1Zero entries are pre-expired. */
  258.                 //TTage = TT_EXPIRATION + 1;
  259.         //TTageRate = ttblsize/(newage/2); /* Average 1/2 of table will be expired */
  260.         /* zero the age of all ttable entries */
  261.             if (!TTadd)
  262.              return;
  263. #ifdef AMIGA
  264.   ClearMem(ttable[0],sizeof(struct hashentry)*(ttblsize+rehash));
  265.   ClearMem(ttable[1],sizeof(struct hashentry)*(ttblsize+rehash));
  266. #else
  267.   memset(ttable[white],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
  268.   memset(ttable[black],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
  269. #endif
  270.            TTadd = 0;
  271.       }
  272. #ifdef ZERO_1_DOES
  273.     else
  274.           {
  275.         /* Just add a major increment to TTage */
  276.         TTage += (TTdepthage[0] - TTdepthage[MAXDEPTH-1]);  /* Just a guess */
  277.           }
  278. #endif
  279. #else /* not NEWAGE */
  280.     if ((iop==0 && TTadd) || TTadd > ttbllimit)
  281.       {
  282. #ifdef AMIGA
  283.   ClearMem(ttable[0],sizeof(struct hashentry)*(ttblsize+rehash));
  284.   ClearMem(ttable[1],sizeof(struct hashentry)*(ttblsize+rehash));
  285. #else
  286.   memset(ttable[white],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
  287.   memset(ttable[black],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
  288. #endif
  289.         TTadd = 0;
  290.       }
  291. #endif /* NEWAGE */
  292.  
  293. }
  294.  
  295. /************************* Hash table statistics ****************************/
  296.  
  297. #ifdef HASHSTATS
  298. long EADD,EGET;    /* Eval cache stats */
  299.  
  300. void
  301. ClearHashStats()    /* initialize the stats */
  302.   {
  303.     memset ((CHAR *) ttdepthin, 0, sizeof (ttdepthin));
  304.     memset ((CHAR *) ttdepthout, 0, sizeof (ttdepthout));
  305.     memset ((CHAR *) ttrehash, 0, sizeof (ttrehash));
  306.     memset ((CHAR *) ttprobe, 0, sizeof (ttprobe));
  307.     HashAdd = HashCnt = THashCol = HashCol = FHashCnt = FHashAdd = 0;
  308.     EADD = EGET = 0;
  309.   }
  310.  
  311. void
  312. ShowHashStats()    /* print the stats */
  313.   {
  314.     int ii;
  315.     printf("Probe: ");
  316.     for(ii=0;ii<MAXDEPTH;ii++)
  317.         if (ttprobe[ii])
  318.             printf(" %d:%ld", ii, ttprobe[ii]);
  319.     printf("\nIn/Out: ");
  320.     for(ii=0;ii<MAXDEPTH;ii++)
  321.         if (ttdepthin[ii] || ttdepthout[ii])
  322.