home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnuch40.zip / gnuchess-4.0.pl79 / src / ttable.c < prev    next >
C/C++ Source or Header  |  1998-09-28  |  19KB  |  861 lines
  1. /*
  2.  * ttable.c - Transposition Table Code for GNU Chess
  3.  *
  4.  * Copyright (c) 1985-1996 Stuart Cracraft, John Stanback,
  5.  *                         Daryl Baker, Conor McCarthy,
  6.  *                         Mike McGann, Chua Kong Sian
  7.  * Copyright (c) 1985-1996 Free Software Foundation
  8.  *
  9.  * This file is part of GNU CHESS.
  10.  *
  11.  * GNU Chess is free software; you can redistribute it and/or modify
  12.  * it under the terms of the GNU General Public License as published by
  13.  * the Free Software Foundation; either version 2, or (at your option)
  14.  * any later version.
  15.  *
  16.  * GNU Chess is distributed in the hope that it will be useful,
  17.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19.  * GNU General Public License for more details.
  20.  *
  21.  * You should have received a copy of the GNU General Public License
  22.  * along with GNU Chess; see the file COPYING.  If not, write to
  23.  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  24.  */
  25. /* ttable.c -- Transposition table code to be included in search.c */
  26. /* #include "gnuchess.h"  already included, see search.c */
  27. /* #include "ttable.h"  dito */
  28. /* NOTE: The static evaluation cache "EETable" belongs to eval.c and cannot*/
  29. /*       be moved to ttable.c */
  30. /* Privae types and data */
  31.  
  32. struct hashentry
  33.      {
  34.        unsigned long hashbd;
  35.        UCHAR flags, depth;      /* CHAR saves some space */
  36.        tshort score;
  37.        utshort mv;
  38. #ifdef HASHTEST
  39.        UCHAR bd[32];
  40. #endif /* HASHTEST */
  41. #ifdef NEWAGE
  42.     utshort age;        /* age of last use */
  43. #endif
  44.      };
  45. struct hashentry *ttable[2];
  46.  
  47. unsigned long ttblsize;
  48. SHORT rehash;  /* -1 is used as a flag --tpm */
  49. #ifdef NEWAGE
  50.         utshort TTage;        /* Current ttable age */
  51.         UTSHORT TTageClock,    /* Count till next age tick */
  52.                 TTageRate;      /* new entry counts per age tick */
  53.         UTSHORT TTdepthage[MAXDEPTH+1];    /* Depth bonus for aging*/
  54.         UTSHORT newage = NEWAGE;    /* Initialization tuning parameter */
  55. #else
  56. unsigned int ttbllimit;
  57. unsigned int TTadd = 1;
  58. #endif
  59.  
  60. #ifdef HASHSTATS
  61. unsigned long ttdepthin[MAXDEPTH+1], ttdepthout[MAXDEPTH+1];
  62. unsigned long ttrehash[MAXrehash+1];
  63. unsigned long ttprobe[MAXDEPTH+1];
  64. unsigned long HashCnt, HashAdd, FHashCnt, FHashAdd, HashCol, THashCol;
  65. #endif
  66.  
  67. /* hashtable flags */
  68. #define truescore 0x0001
  69. #define lowerbound 0x0002
  70. #define upperbound 0x0004
  71. #define kingcastle 0x0008
  72. #define queencastle 0x0010
  73. #define evalflag 0x0020
  74.  
  75. void
  76. Initialize_ttable ()
  77. {
  78.   int doit = true;
  79.   if (rehash < 0) rehash = MAXrehash;
  80. while(doit && ttblsize > MINTTABLE){
  81.   ttable[0] = (struct hashentry *)malloc(sizeof(struct hashentry)*(ttblsize+rehash));
  82.   ttable[1] = (struct hashentry *)malloc(sizeof(struct hashentry)*(ttblsize+rehash));
  83.   if(ttable[0] == NULL || ttable[1] == NULL){
  84.   if(ttable[0] != NULL)free(ttable[0]);
  85.   ttblsize = ttblsize>>1;
  86.   } else doit = false;
  87. }
  88.   if(ttable[0] == NULL || ttable[1] == NULL){ perror("can't alloc ttable");exit(1);}
  89.   else {
  90.     int j;
  91. #ifdef notdef
  92.   printf("transposition table is %ld\n",ttblsize);
  93. #endif
  94. #ifdef NEWAGE
  95.         TTageRate = ttblsize / 1024;
  96.         TTdepthage[0] = TTdepthage[1] = newage;
  97.         for (j=2; j<=MAXDEPTH; j++)
  98.             TTdepthage[j] = TTdepthage[j-1]/2;
  99. /*     ZeroTTable(0); -- called in NewGame() */
  100. #else
  101.     ttbllimit = ttblsize<<1 - ttblsize>>2;
  102. #endif
  103.   }
  104. }
  105.  
  106. #define CB(i) (UCHAR) ((color[2 * (i)] ? 0x80 : 0)\
  107.     | (board[2 * (i)] << 4)\
  108.     | (color[2 * (i) + 1] ? 0x8 : 0)\
  109.     | (board[2 * (i) + 1]))
  110.  
  111. inline
  112. int
  113. ProbeTTable (SHORT side,
  114.          SHORT depth,
  115.          SHORT ply,
  116.          SHORT *alpha,
  117.          SHORT *beta,
  118.          SHORT *score)
  119.  
  120. /*
  121.  * Look for the current board position in the transposition table.
  122.  */
  123.  
  124. {
  125.     register struct hashentry *ptbl;
  126.     register SHORT i = 0;
  127.  
  128. #ifdef DEBUG
  129.     if(flag.nott)return false;
  130. #endif
  131. #ifdef HASHSTATS
  132.     ttprobe[depth]++;
  133. #endif
  134. #ifdef NEWAGE
  135.       /* Find entry within rehash window or return failure */
  136.       for (i=rehash, ptbl = &ttable[side][hashkey % ttblsize];
  137.            ptbl->hashbd != hashbd; ptbl++)
  138.         if (--i == 0) return false;
  139.       /* Update age of rediscovered node */
  140.           ptbl->age = TTage - TTdepthage[ptbl->depth];
  141. #else
  142.     ptbl = &ttable[side][hashkey % ttblsize];
  143.     while (true)
  144.       {
  145.       if (ptbl->depth == 0) return false;
  146.       if (ptbl->hashbd == hashbd) break;
  147.       if (++i > rehash) return false;
  148.       ptbl++;
  149.       }
  150. #endif
  151.  
  152.     PV = SwagHt = ptbl->mv;
  153.     if ((ptbl->depth >= (SHORT) depth) || abs(ptbl->score)>9000)
  154.       {
  155. #ifdef HASHTEST
  156.       for (i = 0; i < 32; i++)
  157.         {
  158.         if (ptbl->bd[i] != CB (i))
  159.           {
  160. #ifdef HASHSTATS
  161.               HashCol++;
  162.               ShowMessage (CP[199]); /*ttable collision detected*/
  163. #endif
  164.               break;
  165.           }
  166.         }
  167. #endif /* HASHTEST */
  168.  
  169. #ifdef HASHSTATS
  170.       ttdepthout[ptbl->depth]++;
  171.       HashCnt++;
  172. #endif
  173.  
  174.       if (ptbl->flags & truescore)
  175.         {
  176.         *score = ptbl->score;
  177.         /* adjust *score so moves to mate is from root */
  178.         if (*score > 9000) *score -= ply;
  179.         else if (*score < -9000) *score += ply;
  180.         *beta = -20000;
  181.         }
  182.       else if (ptbl->flags & lowerbound)
  183.         {
  184.         if (ptbl->score > *alpha)
  185. #ifdef notdef
  186.           *alpha = ptbl->score - 1;
  187. #endif
  188.         *alpha = ptbl->score;
  189.         }
  190. #ifdef DEBUG
  191.       if (debuglevel & 32)
  192.         {
  193.         algbr (PV >> 8, PV & 0xff, 0);
  194.         printf ("-get-> h=%lx d=%d s=%d p=%d a=%d b=%d %s\n", hashbd, depth, *score, ply, *alpha, *beta, mvstr);
  195.         }
  196. #endif
  197.       return (true);
  198.       }
  199.     return (false);
  200. }
  201.  
  202. inline
  203. int
  204. PutInTTable 
  205.         (SHORT side,
  206.          SHORT score,
  207.          SHORT depth,
  208.          SHORT ply,
  209.          SHORT alpha,
  210.          SHORT beta,
  211.          UTSHORT mv)
  212.  
  213. /*
  214.  * Store the current board position in the transposition table.
  215.  */
  216.  
  217.   {
  218.     register struct hashentry *ptbl;
  219.     register SHORT i = 0;
  220. #ifndef NEWAGE
  221.  
  222.     ptbl = &ttable[side][hashkey % ttblsize];
  223.     while (true)
  224.       {
  225.         if (ptbl->depth == 0) break;
  226.         if ((ptbl->hashbd) == hashbd) {
  227.             if (ptbl->depth > (UCHAR)depth) return false; else break;
  228.         }
  229.         if (++i > rehash)
  230.           {
  231. #ifdef HASHSTATS
  232.             THashCol++;
  233. #endif
  234.             ptbl -= rehash; /* Hey! it's already randomized. use the original location. */
  235.                             /* There is some discussion about thrashing.... */
  236.             break;
  237.           }
  238.         ptbl++;
  239.       }
  240.     TTadd++;
  241.     if (ptbl->depth > (UCHAR)depth) return false;
  242.  
  243. #else /* NEWAGE */
  244.     utshort old;
  245.         struct hashentry *oldest;
  246.  
  247.         /* Look for match or oldest entry to reuse */
  248.     /* Note that arithmetic on ages is intentionally modulo 65536 */
  249.         i = rehash;
  250.     oldest = ptbl = &ttable[side][hashkey % ttblsize];
  251.         old = TTage - ptbl->age;
  252.     while (ptbl->hashbd != hashbd) {
  253.         if (--i == 0) break;
  254.         ptbl++;
  255.         if ((TTage - ptbl->age) > old) {
  256.         old = TTage - ptbl->age;
  257.         oldest = ptbl;
  258.         }
  259.     }
  260.         if (i == 0) {
  261.             ptbl = oldest; /* reuse oldest entry */
  262. #ifdef HASHSTATS
  263.         THashCol++;
  264. #endif
  265.             if (--TTageClock == 0) {
  266.                 TTageClock = TTageRate;
  267.                 TTage++;        /* Everyone is now just a little older */
  268.         }
  269.     } else {
  270. /*!!!        if (ptbl->depth > (UCHAR)depth) return false;*/
  271.     }
  272. /*!!!*/        if (ptbl->depth > (UCHAR)depth) return false;
  273.         ptbl->age = TTage - TTdepthage[depth]; /* Set age of this node */
  274.  
  275. #endif /* NEWAGE */
  276. #ifdef HASHSTATS
  277.     HashAdd++;
  278. #endif
  279.     ptbl->hashbd = hashbd;
  280.     ptbl->depth = (UCHAR) depth;
  281.     ptbl->score = score;
  282.     ptbl->mv = mv;
  283. #ifdef DEBUG
  284.     if (debuglevel & 32)
  285.       {
  286.         algbr (mv >> 8, mv & 0xff, 0);
  287.         printf ("-add-> h=%lx d=%d s=%d p=%d a=%d b=%d %s\n", hashbd, depth, score, ply, alpha, beta, mvstr);
  288.       }
  289. #endif
  290.     if (score > beta)
  291.       {
  292.         ptbl->flags = lowerbound;
  293.         ptbl->score = beta + 1;
  294.       }
  295.     else
  296.           {
  297.           /* adjust score so moves to mate is from this ply */
  298.         if (score > 9000) score += ply;
  299.         else if (score < -9000) score -= ply;
  300.         ptbl->score = score;
  301.         ptbl->flags = truescore;
  302.       }
  303.  
  304. #ifdef HASHSTATS
  305.     ttdepthin[ptbl->depth]++;
  306.     ttrehash[i]++;
  307. #endif
  308. #ifdef HASHTEST
  309.     for (i = 0; i < 32; i++)
  310.       {
  311.         ptbl->bd[i] = CB (i);
  312.       }
  313. #endif /* HASHTEST */
  314.     return true;
  315.   }
  316.  
  317. void
  318. ZeroTTable (int iop) /* iop: 0= clear any, 1= clear agged */
  319.   {
  320. #ifdef NEWAGE
  321.     if(iop==0)
  322.       {
  323.         TTageClock = TTageRate;
  324.         TTage = newage+1; /* Zero entries are pre-expired. */
  325.         /* zero the age of all ttable entries */
  326.         memset(ttable[white],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
  327.         memset(ttable[black],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
  328.       }
  329.     else
  330.         /* Just add a major increment to TTage */
  331.         TTage += newage/5;  /* Just a guess */
  332. #else /* not NEWAGE */
  333.     if ((iop==0 && TTadd) || TTadd > ttbllimit)
  334.       {
  335.         memset(ttable[white],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
  336.         memset(ttable[black],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
  337.         TTadd = 0;
  338.       }
  339. #endif /* NEWAGE */
  340.  
  341. }
  342.  
  343. /************************* Hash table statistics ****************************/
  344.  
  345. #ifdef HASHSTATS
  346. long EADD,EGET;    /* Eval cache stats */
  347.  
  348. void
  349. ClearHashStats()    /* initialize the stats */
  350.   {
  351.     memset ((CHAR *) ttdepthin, 0, sizeof (ttdepthin));
  352.     memset ((CHAR *) ttdepthout, 0, sizeof (ttdepthout));
  353.     memset ((CHAR *) ttrehash, 0, sizeof (ttrehash));
  354.     memset ((CHAR *) ttprobe, 0, sizeof (ttprobe));
  355.     HashAdd = HashCnt = THashCol = HashCol = FHashCnt = FHashAdd = 0;
  356.     EADD = EGET = 0;
  357.   }
  358.  
  359. void
  360. ShowHashStats()    /* print the stats */
  361.   {
  362.     int ii;
  363.     printf("Probe: ");
  364.     for(ii=0;ii<MAXDEPTH;ii++)
  365.         if (ttprobe[ii])
  366.             printf(" %d:%ld", ii, ttprobe[ii]);
  367.     printf("\nIn/Out: ");
  368.     for(ii=0;ii<MAXDEPTH;ii++)
  369.         if (ttdepthin[ii] || ttdepthout[ii])
  370.             printf(" %d:%ld/%ld", ii, ttdepthin[ii], ttdepthout[ii]);
  371.     printf("\nRehash: ");
  372.     for(ii=0;ii<=MAXrehash;ii++)
  373.         printf(" %ld", ttrehash[ii]);
  374.     printf("\n");
  375.     printf (CP[71],
  376.         HashAdd, HashCnt, THashCol, HashCol,FHashCnt, FHashAdd);
  377. #ifdef CACHE
  378.     printf ("cache in/out: %ld/%ld\n", EADD, EGET);
  379. #endif
  380.   }
  381. #endif
  382.  
  383. /************************* Hash File Stuf ****************************/
  384. #ifdef HASHFILE
  385. #define frehash 6
  386.  
  387.      struct fileentry
  388.      {
  389.        UCHAR bd[32];
  390.        UCHAR f, t, flags, depth, sh, sl;
  391.      };
  392.  
  393. FILE *hashfile = NULL;
  394. unsigned long HFileSize;        /* Nunber of fileentry records in hash file */
  395.  
  396. void 
  397. CreateHashFile(long sz)
  398. /* NOTE: If sz is Odd the black and white positions will be
  399.    scrambled (Is this good or bad?) */
  400.   {
  401.     if ((hashfile = fopen (HASHFILE, RWA_ACC)))    /* old file */
  402.       {    /* chech size, warn if shrinking? */
  403.         fseek (hashfile, 0L, SEEK_END);
  404.         HFileSize = ftell (hashfile) / sizeof (struct fileentry);
  405.         if (sz < HFileSize) sz = HFileSize;
  406.         fseek (hashfile, 0L, SEEK_SET);
  407.       }
  408.     else if (sz)
  409.       {    /* create new file only if we have a size */
  410.         hashfile = fopen (HASHFILE, WA_ACC);
  411.       }
  412.     if (hashfile != NULL)
  413.       {
  414.         long j;
  415.         struct fileentry n[64]; /* Write a bunch at a time */
  416.         
  417.         printf (CP[66]);
  418.         memset ((CHAR *) n, 0, sizeof (n));
  419. /*        n.f = n.t = 0; */
  420. /*        n.flags = 0; */
  421. /*        n.depth = 0; */
  422. /*        n.sh = n.sl = 0; */
  423.         for (j = 0; j < sz; j += 64)
  424.             fwrite (&n, sizeof (struct fileentry), sz-j<64 ? sz-j: 64, hashfile);
  425.         fclose (hashfile);
  426.         hashfile = NULL;
  427.       }
  428.     else
  429.         printf (CP[50], HASHFILE);
  430.   }
  431.   
  432. void 
  433. OpenHashFile() /* try to open hash file */
  434.   {
  435.     hashfile = fopen (HASHFILE, RWA_ACC);
  436.     if (hashfile)
  437.       {
  438.         fseek (hashfile, 0L, SEEK_END);
  439.         HFileSize = ftell (hashfile) / sizeof (struct fileentry);
  440.       }
  441. #if !defined CHESSTOOL && !defined XBOARD
  442.     else
  443.         ShowMessage (CP[98]);
  444. #endif
  445.   }
  446.  
  447. void
  448. CloseHashFile()
  449.   {
  450.       /* remember to write accumulated statistics if we keep such */
  451.     if (hashfile)
  452.         fclose (hashfile);
  453.     hashfile = NULL;
  454.   }
  455.   
  456. void 
  457. TestHashFile()
  458.   {
  459.     int iopendit = false;
  460.     if (!hashfile)
  461.       {
  462.         OpenHashFile();
  463.         iopendit = (hashfile != NULL);
  464.       }
  465.     if (hashfile)
  466.       {
  467.         int i; 
  468.         long j;
  469.         long nr[MAXDEPTH+1];
  470.         struct fileentry n;
  471.         
  472.         printf (CP[49]);
  473.         for (i = 0; i < MAXDEPTH; i++)
  474.             nr[i] = 0;
  475.         fseek (hashfile, 0L, SEEK_SET);
  476.         for (j = 0; j < HFileSize; j++)
  477.           {
  478.             fread (&n, sizeof (struct fileentry), 1, hashfile);
  479.             if (n.depth > MAXDEPTH){printf("ERROR\n");exit(1);}
  480.             if (n.depth)
  481.               {
  482.                 nr[n.depth]++;
  483.                 nr[0]++;
  484.               }
  485.           }
  486.         printf (CP[109], nr[0], HFileSize);
  487.         for (i = 1; i <= MAXDEPTH; i++)
  488.             if (nr[i])
  489.                 printf (" %d:%ld", i,nr[i]);
  490.         printf ("\n");
  491.         if (iopendit)
  492.             CloseHashFile();
  493.       }
  494.   }
  495.  
  496. int 
  497. Fbdcmp(UCHAR *a,UCHAR *b)
  498.   {
  499.     register int i;
  500.     for(i = 0;i<32;i++)
  501.         if(a[i] != b[i])
  502.             return false;
  503.     return true;
  504.   }
  505.  
  506. int
  507. ProbeFTable (SHORT side,
  508.         SHORT depth,
  509.         SHORT ply,
  510.         SHORT *alpha,
  511.         SHORT *beta,
  512.         SHORT *score)
  513.  
  514. /*
  515. * Look for the current board position in the persistent transposition table.
  516. */
  517.  
  518.   {
  519.     register SHORT i;
  520.     register unsigned long hashix;
  521.     struct fileentry new, t;
  522. #ifdef DEBUG
  523.     if(flag.noft)return false;
  524. #endif
  525.     
  526.     hashix = ((side == white) ? (hashkey & 0xFFFFFFFE) : (hashkey | 1)) % HFileSize;
  527.     
  528.     for (i = 0; i < 32; i++)
  529.         new.bd[i] = CB (i);
  530.     new.flags = 0;
  531.     if (Mvboard[kingP[side]] == 0)
  532.       {
  533.         if (Mvboard[qrook[side]] == 0)
  534.             new.flags |= queencastle;
  535.         if (Mvboard[krook[side]] == 0)
  536.         new.flags |= kingcastle;
  537.       }
  538.     for (i = 0; i < frehash; i++)
  539.       {
  540.         fseek (hashfile,
  541.             sizeof (struct fileentry) * ((hashix + 2 * i) % (HFileSize)),
  542.             SEEK_SET);
  543.         fread (&t, sizeof (struct fileentry), 1, hashfile);
  544.         if (!t.depth) break;
  545.         if(!Fbdcmp(t.bd, new.bd)) continue;
  546.         if (((SHORT) t.depth >= depth) 
  547.             && (new.flags == (UTSHORT)(t.flags & (kingcastle | queencastle))))
  548.           {
  549. #ifdef HASHSTATS
  550.             FHashCnt++;
  551. #endif
  552.             PV = (t.f << 8) | t.t;
  553.             *score = (t.sh << 8) | t.sl;
  554.             /* adjust *score so moves to mate is from root */
  555.             if (*score > 9000)
  556.                 *score -= ply;
  557.             else if (*score < -9000)
  558.                 *score += ply;
  559.             if (t.flags & truescore)
  560.               {
  561.                 *beta = -20000;
  562.               }
  563.             else if (t.flags & lowerbound)
  564.               {
  565.                 if (*score > *alpha)
  566.                     *alpha = *score - 1;
  567.               }
  568.             else if (t.flags & upperbound)
  569.               {
  570.                 if (*score < *beta)
  571.                     *beta = *score + 1;
  572.               }
  573.             return (true);
  574.           }
  575.       }
  576.     return (false);
  577.   }
  578.  
  579. void
  580. PutInFTable (SHORT side,
  581.         SHORT score,
  582.         SHORT depth,
  583.         SHORT ply,
  584.         SHORT alpha,
  585.         SHORT beta,
  586.         UTSHORT f,
  587.         UTSHORT t)
  588.  
  589. /*
  590. * Store the current board position in the persistent transposition table.
  591. */
  592.  
  593.   {
  594.     register UTSHORT i;
  595.     register unsigned long hashix;
  596.     struct fileentry new, tmp;
  597.     
  598.     hashix = ((side == white) ? (hashkey & 0xFFFFFFFE) : (hashkey | 1)) % HFileSize;
  599.     for (i = 0; i < 32; i++) new.bd[i] = CB (i);
  600.     new.f = (UCHAR) f;
  601.     new.t = (UCHAR) t;
  602.     if (score < alpha)
  603.         new.flags = upperbound;
  604.     else
  605.         new.flags = ((score > beta) ? lowerbound : truescore);
  606.     if (Mvboard[kingP[side]] == 0)
  607.       {
  608.         if (Mvboard[qrook[side]] == 0)
  609.             new.flags |= queencastle;
  610.         if (Mvboard[krook[side]] == 0)
  611.             new.flags |= kingcastle;
  612.       }
  613.     new.depth = (UCHAR) depth;
  614.     /* adjust *score so moves to mate is from root */
  615.     if (score > 9000)
  616.         score += ply;
  617.     else if (score < -9000)
  618.         score -= ply;
  619.  
  620.     new.sh = (UCHAR) (score >> 8);
  621.     new.sl = (UCHAR) (score & 0xFF);
  622.     
  623.     for (i = 0; i < frehash; i++)
  624.       {
  625.         fseek (hashfile,
  626.             sizeof (struct fileentry) * ((hashix + 2 * i) % (HFileSize)),
  627.             SEEK_SET);
  628.         if(fread (&tmp, sizeof (struct fileentry), 1, hashfile) == 0){perror("hashfile");exit(1);}
  629.         if (tmp.depth && !Fbdcmp(tmp.bd,new.bd))continue;
  630.         if ((SHORT) tmp.depth < new.depth)
  631.           {
  632.             fseek (hashfile,
  633.                 sizeof (struct fileentry) * ((hashix + 2 * i) % (HFileSize)),
  634.                 SEEK_SET);
  635.             fwrite (&new, sizeof (struct fileentry), 1, hashfile);
  636. #ifdef HASHSTATS
  637.             FHashAdd++;
  638. #endif
  639.           }
  640.         break;
  641.       }
  642.   }
  643.  
  644. #endif /* HASHFILE */
  645. /********************** Repitition cache ***********************/
  646. SHORT rpthash[2][256];
  647.  
  648. void
  649. ZeroRPT (void)
  650. {
  651.    memset ((CHAR *) rpthash, 0, sizeof (rpthash));
  652. }
  653. /********************** Hash code stuff ***********************/
  654. /*
  655.  * In a networked enviroment gnuchess might be compiled on different hosts
  656.  * with different random number generators, that is not acceptable if they
  657.  * are going to share the same transposition table.
  658.  */
  659. unsigned long int next = 1;
  660.  
  661. #if defined NEWURAND
  662. /*
  663. This code copied from:
  664.  
  665. G. Wiesenekker. ZZZZZZ a chess program.
  666. Copyright (C) 1993  G. Wiesenekker
  667. E-mail: wiesenecker@sara.nl
  668.  
  669. A 32 bit random number generator. An implementation in C of the algorithm given by
  670. Knuth, the art of computer programming, vol. 2, pp. 26-27. We use e=32, so 
  671. we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which is implicitly
  672. done by unsigned arithmetic.
  673. */
  674.  
  675. unsigned int urand(void)
  676. {
  677.     /*
  678.     random numbers from Mathematica 2.0.
  679.     SeedRandom = 1;
  680.     Table[Random[Integer, {0, 2^32 - 1}]
  681.     */
  682.     static unsigned long x[55] =
  683.     {
  684.         1410651636UL,
  685.         3012776752UL,
  686.         3497475623UL,
  687.         2892145026UL,
  688.         1571949714UL,
  689.         3253082284UL,
  690.         3489895018UL,
  691.         387949491UL, 
  692.         2597396737UL,
  693.         1981903553UL,
  694.         3160251843UL,
  695.         129444464UL, 
  696.         1851443344UL,
  697.         4156445905UL,
  698.         224604922UL,
  699.         1455067070UL, 
  700.         3953493484UL,
  701.         1460937157UL,
  702.         2528362617UL,
  703.         317430674UL, 
  704.         3229354360UL,
  705.         117491133UL,
  706.         832845075UL,
  707.         1961600170UL, 
  708.         1321557429UL,
  709.         747750121UL,
  710.         545747446UL,
  711.         810476036UL,
  712.         503334515UL, 
  713.         4088144633UL,
  714.         2824216555UL,
  715.         3738252341UL,
  716.         3493754131UL, 
  717.         3672533954UL,
  718.         29494241UL,
  719.         1180928407UL,
  720.         4213624418UL,
  721.         33062851UL, 
  722.         3221315737UL,
  723.         1145213552UL,
  724.         2957984897UL,
  725.         4078668503UL, 
  726.         2262661702UL,
  727.         65478801UL,
  728.         2527208841UL,
  729.         1960622036UL,
  730.         315685891UL, 
  731.         1196037864UL,
  732.         804614524UL,
  733.         1421733266UL,
  734.         2017105031UL, 
  735.         3882325900UL,
  736.         810735053UL,
  737.         384606609UL,
  738.         2393861397UL
  739.     };
  740.     static int init = TRUE;
  741.     static unsigned long y[55];
  742.     static int j, k;
  743.     unsigned long ul;
  744.     
  745.     if (init)
  746.     {
  747.         int i;
  748.         
  749.         init = FALSE;
  750.         for (i = 0; i < 55; i++)
  751.             y[i] = x[i];
  752.         j = 24 - 1;
  753.         k = 55 - 1;
  754.     }
  755.     
  756.     ul = (y[k] += y[j]);
  757.     if (--j < 0) j = 55 - 1;
  758.     if (--k < 0) k = 55 - 1;
  759.     return((unsigned int)ul);
  760. }
  761.  
  762. #else
  763. unsigned int
  764. urand (void)
  765. {
  766.   next *= 1103515245;
  767.   next += 12345;
  768.   return ((unsigned int) (next >> 16) & 0xFFFF);
  769. }
  770. #endif
  771.  
  772. void
  773. gsrand (unsigned int seed)
  774. {
  775.   next = seed;
  776. }
  777.  
  778. unsigned long hashkey, hashbd;
  779. struct hashval hashcode[2][7][64];
  780. #ifdef LONG64
  781. #define XRANDTSIZE 8000
  782. #else
  783. #define XRANDTSIZE 4000
  784. #endif
  785.  
  786. #if !defined NOXRAND
  787. unsigned int
  788. xrand (int a, unsigned int b[])
  789. {
  790.   unsigned int i, r, loop;
  791.   unsigned int j, c;
  792.   unsigned int msk;
  793.   if (!a)
  794.     {
  795.       for (i = 0; i < XRANDTSIZE; i++)
  796.     b[i] = 0;
  797.       return 0;
  798.     }
  799.   loop = true;
  800.   while (loop)
  801.     {
  802.       r = urand ();
  803.       msk = 1;
  804.       c = 0;
  805.       for (j = 0; j < 16; j++)
  806.     {
  807.       if (r & msk)
  808.         c++;
  809.       msk = msk << 1;
  810.     }
  811.       if (c < 8)
  812.     continue;
  813.       loop = false;
  814.       for (i = 0; i < a; i++)
  815.     if (r == b[i])
  816.       {
  817.         loop = true;
  818.         break;
  819.       }
  820.       if (!loop)
  821.     {
  822.       b[a] = r;
  823.       return r;
  824.     }
  825.     }
  826.   return 0;
  827. }
  828. #else
  829. #define xrand(a,b) urand()
  830. #endif
  831.  
  832. void
  833. InitHashCode(unsigned int seed)
  834.   {
  835.     SHORT l, c, p;
  836.     unsigned int t[XRANDTSIZE];
  837.     int cnt = 0;
  838.  
  839.     xrand(cnt++,t);
  840.     gsrand (seed);    /* idealy we would preserve the old seed but... */
  841.     for (c = white; c <= black; c++)
  842.       for (p = pawn; p <= king; p++)
  843.         for (l = 0; l < 64; l++)
  844.           {
  845.             hashcode[c][p][l].key = (((unsigned long) xrand (cnt++,t)));
  846.             hashcode[c][p][l].key += (((unsigned long) xrand (cnt++,t)) << 16);
  847.             hashcode[c][p][l].bd = (((unsigned long) xrand (cnt++,t)));
  848.             hashcode[c][p][l].bd += (((unsigned long) xrand (cnt++,t)) << 16);
  849. #ifdef LONG64
  850.             hashcode[c][p][l].key += (((unsigned long) xrand (cnt++,t)) << 32);
  851.             hashcode[c][p][l].key += (((unsigned long) xrand (cnt++,t)) << 48);
  852.             hashcode[c][p][l].bd += (((unsigned long) xrand (cnt++,t)) << 32);
  853.             hashcode[c][p][l].bd += (((unsigned long) xrand (cnt++,t)) << 48);
  854. #endif
  855.           }
  856.   }
  857.  
  858.  
  859.  
  860.  
  861.