home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 6 / FreshFish_September1994.bin / bbs / game / uchess-2.89.lha / UChess / src / TTABLE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1994-06-13  |  18.0 KB  |  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.             printf(" %d:%ld/%ld", ii, ttdepthin[ii], ttdepthout[ii]);
  323.     printf("\nRehash: ");
  324.     for(ii=0;ii<=MAXrehash;ii++)
  325.         printf(" %ld", ttrehash[ii]);
  326.     printf("\n");
  327.     printf (CP[71],
  328.         HashAdd, HashCnt, THashCol, HashCol,FHashCnt, FHashAdd);
  329. #ifdef CACHE
  330.     printf ("cache in/out: %ld/%ld\n", EADD, EGET);
  331. #endif
  332.   }
  333. #endif
  334.  
  335. /************************* Hash File Stuf ****************************/
  336. #ifdef HASHFILE
  337. #define frehash 6
  338.  
  339.      struct fileentry
  340.      {
  341.        UCHAR bd[32];
  342.        UCHAR f, t, flags, depth, sh, sl;
  343.      };
  344.  
  345. FILE *hashfile = NULL;
  346. unsigned long HFileSize;        /* Nunber of fileentry records in hash file */
  347.  
  348. void 
  349. CreateHashFile(long sz)
  350. /* NOTE: If sz is Odd the black and white positions will be
  351.    scrambled (Is this good or bad?) */
  352.   {
  353.     if (hashfile = fopen (HASHFILE, RWA_ACC))    /* old file */
  354.       {    /* chech size, warn if shrinking? */
  355.         fseek (hashfile, 0L, SEEK_END);
  356.         HFileSize = ftell (hashfile) / sizeof (struct fileentry);
  357.         if (sz < HFileSize) sz = HFileSize;
  358.         fseek (hashfile, 0L, SEEK_SET);
  359.       }
  360.     else if (sz)
  361.       {    /* create new file only if we have a size */
  362.         hashfile = fopen (HASHFILE, WA_ACC);
  363.       }
  364.     if (hashfile != NULL)
  365.       {
  366.         long j;
  367.         struct fileentry n[64]; /* Write a bunch at a time */
  368.         
  369.         printf (CP[66]);
  370.         memset ((CHAR *) n, 0, sizeof (n));
  371. /*        n.f = n.t = 0; */
  372. /*        n.flags = 0; */
  373. /*        n.depth = 0; */
  374. /*        n.sh = n.sl = 0; */
  375.         for (j = 0; j < sz; j += 64)
  376.             fwrite (&n, sizeof (struct fileentry), sz-j<64 ? sz-j: 64, hashfile);
  377.         fclose (hashfile);
  378.         hashfile = NULL;
  379.       }
  380.     else
  381.         printf (CP[50], HASHFILE);
  382.   }
  383.   
  384. void 
  385. OpenHashFile() /* try to open hash file */
  386.   {
  387.     hashfile = fopen (HASHFILE, RWA_ACC);
  388.     if (hashfile)
  389.       {
  390.         fseek (hashfile, 0L, SEEK_END);
  391.         HFileSize = ftell (hashfile) / sizeof (struct fileentry);
  392.       }
  393. #if !defined CHESSTOOL && !defined XBOARD
  394.     else
  395.         ShowMessage (CP[98]);
  396. #endif
  397.   }
  398.  
  399. void
  400. CloseHashFile()
  401.   {
  402.       /* remember to write accumulated statistics if we keep such */
  403.     if (hashfile)
  404.         fclose (hashfile);
  405.     hashfile = NULL;
  406.   }
  407.   
  408. void 
  409. TestHashFile()
  410.   {
  411.     int iopendit = false;
  412.     if (!hashfile)
  413.       {
  414.         OpenHashFile();
  415.         iopendit = (hashfile != NULL);
  416.       }
  417.     if (hashfile)
  418.       {
  419.         int i; 
  420.         long j;
  421.         long nr[MAXDEPTH+1];
  422.         struct fileentry n;
  423.         
  424.         printf (CP[49]);
  425.         for (i = 0; i < MAXDEPTH; i++)
  426.             nr[i] = 0;
  427.         fseek (hashfile, 0L, SEEK_SET);
  428.         for (j = 0; j < HFileSize; j++)
  429.           {
  430.             fread (&n, sizeof (struct fileentry), 1, hashfile);
  431.             if (n.depth > MAXDEPTH){printf("ERROR\n");exit(1);}
  432.             if (n.depth)
  433.               {
  434.                 nr[n.depth]++;
  435.                 nr[0]++;
  436.               }
  437.           }
  438.         printf (CP[109], nr[0], HFileSize);
  439.         for (i = 1; i <= MAXDEPTH; i++)
  440.             if (nr[i])
  441.                 printf (" %d:%ld", i,nr[i]);
  442.         printf ("\n");
  443.         if (iopendit)
  444.             CloseHashFile();
  445.       }
  446.   }
  447.  
  448. int 
  449. Fbdcmp(UCHAR *a,UCHAR *b)
  450.   {
  451.     register int i;
  452.     for(i = 0;i<32;i++)
  453.         if(a[i] != b[i])
  454.             return false;
  455.     return true;
  456.   }
  457.  
  458. int
  459. ProbeFTable (SHORT side,
  460.         SHORT depth,
  461.         SHORT ply,
  462.         SHORT *alpha,
  463.         SHORT *beta,
  464.         SHORT *score)
  465.  
  466. /*
  467. * Look for the current board position in the persistent transposition table.
  468. */
  469.  
  470.   {
  471.     register SHORT i;
  472.     register unsigned long hashix;
  473.     struct fileentry new, t;
  474.     
  475.     hashix = ((side == white) ? (hashkey & 0xFFFFFFFE) : (hashkey | 1)) % HFileSize;
  476.     
  477.     for (i = 0; i < 32; i++)
  478.         new.bd[i] = CB (i);
  479.     new.flags = 0;
  480.     if (Mvboard[kingP[side]] == 0)
  481.       {
  482.         if (Mvboard[qrook[side]] == 0)
  483.             new.flags |= queencastle;
  484.         if (Mvboard[krook[side]] == 0)
  485.         new.flags |= kingcastle;
  486.       }
  487.     for (i = 0; i < frehash; i++)
  488.       {
  489.         fseek (hashfile,
  490.             sizeof (struct fileentry) * ((hashix + 2 * i) % (HFileSize)),
  491.             SEEK_SET);
  492.         fread (&t, sizeof (struct fileentry), 1, hashfile);
  493.         if (!t.depth) break;
  494.         if(!Fbdcmp(t.bd, new.bd)) continue;
  495.         if (((SHORT) t.depth >= depth) 
  496.             && (new.flags == (UTSHORT)(t.flags & (kingcastle | queencastle))))
  497.           {
  498. #ifdef HASHSTATS
  499.             FHashCnt++;
  500. #endif
  501.             PV = (t.f << 8) | t.t;
  502.             *score = (t.sh << 8) | t.sl;
  503.             /* adjust *score so moves to mate is from root */
  504.             if (*score > 9000)
  505.                 *score -= ply;
  506.             else if (*score < -9000)
  507.                 *score += ply;
  508.             if (t.flags & truescore)
  509.               {
  510.                 *beta = -20000;
  511.               }
  512.             else if (t.flags & lowerbound)
  513.               {
  514.                 if (*score > *alpha)
  515.                     *alpha = *score - 1;
  516.               }
  517.             else if (t.flags & upperbound)
  518.               {
  519.                 if (*score < *beta)
  520.                     *beta = *score + 1;
  521.               }
  522.             return (true);
  523.           }
  524.       }
  525.     return (false);
  526.   }
  527.  
  528. void
  529. PutInFTable (SHORT side,
  530.         SHORT score,
  531.         SHORT depth,
  532.         SHORT ply,
  533.         SHORT alpha,
  534.         SHORT beta,
  535.         UTSHORT f,
  536.         UTSHORT t)
  537.  
  538. /*
  539. * Store the current board position in the persistent transposition table.
  540. */
  541.  
  542.   {
  543.     register UTSHORT i;
  544.     register unsigned long hashix;
  545.     struct fileentry new, tmp;
  546.     
  547.     hashix = ((side == white) ? (hashkey & 0xFFFFFFFE) : (hashkey | 1)) % HFileSize;
  548.     for (i = 0; i < 32; i++) new.bd[i] = CB (i);
  549.     new.f = (UCHAR) f;
  550.     new.t = (UCHAR) t;
  551.     if (score < alpha)
  552.         new.flags = upperbound;
  553.     else
  554.         new.flags = ((score > beta) ? lowerbound : truescore);
  555.     if (Mvboard[kingP[side]] == 0)
  556.       {
  557.         if (Mvboard[qrook[side]] == 0)
  558.             new.flags |= queencastle;
  559.         if (Mvboard[krook[side]] == 0)
  560.             new.flags |= kingcastle;
  561.       }
  562.     new.depth = (UCHAR) depth;
  563.     /* adjust *score so moves to mate is from root */
  564.     if (score > 9000)
  565.         score += ply;
  566.     else if (score < -9000)
  567.         score -= ply;
  568.  
  569.     new.sh = (UCHAR) (score >> 8);
  570.     new.sl = (UCHAR) (score & 0xFF);
  571.     
  572.     for (i = 0; i < frehash; i++)
  573.       {
  574.         fseek (hashfile,
  575.             sizeof (struct fileentry) * ((hashix + 2 * i) % (HFileSize)),
  576.             SEEK_SET);
  577.         if(fread (&tmp, sizeof (struct fileentry), 1, hashfile) == 0){perror("hashfile");exit(1);}
  578.         if (tmp.depth && !Fbdcmp(tmp.bd,new.bd))continue;
  579.         if ((SHORT) tmp.depth < new.depth)
  580.           {
  581.             fseek (hashfile,
  582.                 sizeof (struct fileentry) * ((hashix + 2 * i) % (HFileSize)),
  583.                 SEEK_SET);
  584.             fwrite (&new, sizeof (struct fileentry), 1, hashfile);
  585. #ifdef HASHSTATS
  586.             FHashAdd++;
  587. #endif
  588.           }
  589.         break;
  590.       }
  591.   }
  592.  
  593. #endif /* HASHFILE */
  594.  
  595. /********************** Repitition cache ***********************/
  596. extern SHORT rpthash[2][256];
  597. extern SHORT ISZERO;
  598.  
  599. void
  600. ZeroRPT (void)
  601. {
  602. #ifdef AMIGA
  603.    if(ISZERO){ClearMem(rpthash, sizeof (rpthash));ISZERO=0;}
  604. #else
  605.    if(ISZERO){memset ((CHAR *) rpthash, 0, sizeof (rpthash));ISZERO=0;}
  606. #endif
  607. }
  608. /********************** Hash code stuff ***********************/
  609. /*
  610.  * In a networked enviroment gnuchess might be compiled on different hosts
  611.  * with different random number generators, that is not acceptable if they
  612.  * are going to share the same transposition table.
  613.  */
  614. extern unsigned long int next;
  615.  
  616. #if defined NEWURAND
  617. /*
  618. This code copied from:
  619.  
  620. G. Wiesenekker. ZZZZZZ a chess program.
  621. Copyright (C) 1993  G. Wiesenekker
  622. E-mail: wiesenecker@sara.nl
  623.  
  624. A 32 bit random number generator. An implementation in C of the algorithm given by
  625. Knuth, the art of computer programming, vol. 2, pp. 26-27. We use e=32, so 
  626. we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which is implicitly
  627. done by unsigned arithmetic.
  628. */
  629.  
  630. unsigned int urand(void)
  631. {
  632.     /*
  633.     random numbers from Mathematica 2.0.
  634.     SeedRandom = 1;
  635.     Table[Random[Integer, {0, 2^32 - 1}]
  636.     */
  637.     static unsigned long x[55] =
  638.     {
  639.         1410651636UL,
  640.         3012776752UL,
  641.         3497475623UL,
  642.         2892145026UL,
  643.         1571949714UL,
  644.         3253082284UL,
  645.         3489895018UL,
  646.         387949491UL, 
  647.         2597396737UL,
  648.         1981903553UL,
  649.         3160251843UL,
  650.         129444464UL, 
  651.         1851443344UL,
  652.         4156445905UL,
  653.         224604922UL,
  654.         1455067070UL, 
  655.         3953493484UL,
  656.         1460937157UL,
  657.         2528362617UL,
  658.         317430674UL, 
  659.         3229354360UL,
  660.         117491133UL,
  661.         832845075UL,
  662.         1961600170UL, 
  663.         1321557429UL,
  664.         747750121UL,
  665.         545747446UL,
  666.         810476036UL,
  667.         503334515UL, 
  668.         4088144633UL,
  669.         2824216555UL,
  670.         3738252341UL,
  671.         3493754131UL, 
  672.         3672533954UL,
  673.         29494241UL,
  674.         1180928407UL,
  675.         4213624418UL,
  676.         33062851UL, 
  677.         3221315737UL,
  678.         1145213552UL,
  679.         2957984897UL,
  680.         4078668503UL, 
  681.         2262661702UL,
  682.         65478801UL,
  683.         2527208841UL,
  684.         1960622036UL,
  685.         315685891UL, 
  686.         1196037864UL,
  687.         804614524UL,
  688.         1421733266UL,
  689.         2017105031UL, 
  690.         3882325900UL,
  691.         810735053UL,
  692.         384606609UL,
  693.         2393861397UL
  694.     };
  695.     static int init = TRUE;
  696.     static unsigned long y[55];
  697.     static int j, k;
  698.     unsigned long ul;
  699.     
  700.     if (init)
  701.     {
  702.         int i;
  703.         
  704.         init = FALSE;
  705.         for (i = 0; i < 55; i++)
  706.             y[i] = x[i];
  707.         j = 24 - 1;
  708.         k = 55 - 1;
  709.     }
  710.     
  711.     ul = (y[k] += y[j]);
  712.     if (--j < 0) j = 55 - 1;
  713.     if (--k < 0) k = 55 - 1;
  714.     return((unsigned int)ul);
  715. }
  716.  
  717. #else
  718. unsigned int
  719. urand (void)
  720. {
  721.   next *= 1103515245;
  722.   next += 12345;
  723.   return ((unsigned int) (next >> 16) & 0xFFFF);
  724. }
  725. #endif
  726.  
  727. void
  728. gsrand (unsigned int seed)
  729. {
  730.   next = seed;
  731. }
  732.  
  733. extern unsigned long hashkey, hashbd;
  734. extern struct hashval hashcode[2][7][64];
  735.  
  736. #if !defined NOXRAND
  737. unsigned int
  738. xrand (int a, unsigned int b[])
  739. {
  740.   unsigned int i, r, loop;
  741.   unsigned int j, c;
  742.   unsigned int msk;
  743.   if (!a)
  744.     {
  745.       for (i = 0; i < 4000; i++)
  746.     b[i] = 0;
  747.       return 0;
  748.     }
  749.   loop = true;
  750.   while (loop)
  751.     {
  752.       r = urand ();
  753.       msk = 1;
  754.       c = 0;
  755.       for (j = 0; j < 16; j++)
  756.     {
  757.       if (r & msk)
  758.         c++;
  759.       msk = msk << 1;
  760.     }
  761.       if (c < 8)
  762.     continue;
  763.       loop = false;
  764.       for (i = 0; i < a; i++)
  765.     if (r == b[i])
  766.       {
  767.         loop = true;
  768.         break;
  769.       }
  770.       if (!loop)
  771.     {
  772.       b[a] = r;
  773.       return r;
  774.     }
  775.     }
  776.   return 0;
  777. }
  778. #else
  779. #define xrand(a,b) urand()
  780. #endif
  781.  
  782. void
  783. InitHashCode(unsigned int seed)
  784.   {
  785.     SHORT l, c, p;
  786. //    unsigned int t[4000];
  787.     unsigned int *t;
  788.     int cnt = 0;
  789.  
  790.         ShowMessage("Hashcode init");
  791.         ShowMessage("Please wait..");
  792.     t = AllocMem(sizeof(int)*4000,MEMF_CLEAR);
  793.         if (!t)
  794.          {
  795.        DisplayError("Cannot init hashtable");
  796.       return;
  797.      }
  798.     xrand(cnt++,t);
  799.     gsrand (seed);    /* idealy we would preserve the old seed but... */
  800.     for (c = white; c <= black; c++)
  801.       for (p = pawn; p <= king; p++)
  802.         for (l = 0; l < 64; l++)
  803.           {
  804.             hashcode[c][p][l].key = (((unsigned long) xrand (cnt++,t)));
  805.             hashcode[c][p][l].key += (((unsigned long) xrand (cnt++,t)) << 16);
  806.             hashcode[c][p][l].bd = (((unsigned long) xrand (cnt++,t)));
  807.             hashcode[c][p][l].bd += (((unsigned long) xrand (cnt++,t)) << 16);
  808. #ifdef LONG64
  809.             hashcode[c][p][l].key += (((unsigned long) xrand (cnt++,t)) << 32);
  810.             hashcode[c][p][l].key += (((unsigned long) xrand (cnt++,t)) << 48);
  811.             hashcode[c][p][l].bd += (((unsigned long) xrand (cnt++,t)) << 32);
  812.             hashcode[c][p][l].bd += (((unsigned long) xrand (cnt++,t)) << 48);
  813. #endif
  814.           }
  815.     FreeMem(t,sizeof(int)*4000);
  816.   }
  817.  
  818.