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