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