home *** CD-ROM | disk | FTP | other *** search
/ C!T ROM 5 / ctrom5b.zip / ctrom5b / OS2 / SPEL / UCHESS / UCHESSRC / TTABLE.C < prev    next >
Text File  |  1994-11-01  |  19KB  |  814 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. #ifdef AMIGA
  9. #include <proto/exec.h>
  10. #include <exec/memory.h>
  11. #include <proto/dos.h>
  12. #else
  13. #include <dos.h>
  14. #endif
  15.  
  16. //#define TT_EXPIRATION 40000 // nominal exp node value
  17.  
  18. //#ifndef AMIGA
  19. //struct hashentry
  20. //     {
  21. //       unsigned long hashbd;
  22. //       UCHAR flags, depth;      /* CHAR saves some space */
  23. //       tshort score;
  24. //       utshort mv;
  25. //#ifdef HASHTEST
  26. //       UCHAR bd[32];
  27. //#endif /* HASHTEST */
  28. //#ifdef NEWAGE
  29. //        utshort age;        /* age of last use */
  30. //#endif
  31. //     };
  32. //unsigned long ttblsize;
  33. //#endif // AMIGA
  34.  
  35. //extern struct etable etab[2][ETABLE];
  36. extern struct etable *etab[2];
  37. extern struct hashentry *ttable[2];
  38.  
  39. /* unsigned */ extern SHORT __aligned rehash;  /* -1 is used as a flag --tpm */
  40. #ifdef NEWAGE
  41.     utshort TTage;        /* Current ttable age */
  42.     UTSHORT TTageClock,    /* Count till next age tick */
  43.         TTageRate;      /* new entry counts per age tick */
  44.     UTSHORT TTdepthage[MAXDEPTH+1];    /* Depth bonus for aging*/
  45.     UTSHORT newage = NEWAGE;    /* Initialization tuning parameter */
  46.     extern unsigned int __aligned TTadd;
  47. #else
  48. unsigned int ttbllimit;
  49. extern unsigned int TTadd;
  50. #endif
  51.  
  52. #ifdef HASHSTATS
  53. unsigned long ttdepthin[MAXDEPTH+1], ttdepthout[MAXDEPTH+1];
  54. unsigned long ttrehash[MAXrehash+1];
  55. unsigned long ttprobe[MAXDEPTH+1];
  56. unsigned long HashCnt, HashAdd, FHashCnt, FHashAdd, HashCol, THashCol;
  57. #endif
  58.  
  59. /* hashtable flags */
  60. #define truescore 0x0001
  61. #define lowerbound 0x0002
  62. #define upperbound 0x0004
  63. #define kingcastle 0x0008
  64. #define queencastle 0x0010
  65. #define evalflag 0x0020
  66.  
  67.  
  68. void
  69. Initialize_ttable ()
  70. {
  71.   char astr[32];
  72.   int doit = true;
  73.  
  74.   if (rehash < 0) rehash = MAXrehash;
  75.   while(doit && ttblsize >= (1<<13)){
  76.   ttable[0] = (struct hashentry *)malloc(sizeof(struct hashentry)*(ttblsize+rehash));
  77.   ttable[1] = (struct hashentry *)malloc(sizeof(struct hashentry)*(ttblsize+rehash));
  78.   if(ttable[0] == NULL || ttable[1] == NULL){
  79.   if(ttable[0] != NULL)free(ttable[0]);
  80.   ttblsize = ttblsize>>1;
  81.   } else doit = false;
  82. }
  83.   if(ttable[0] == NULL || ttable[1] == NULL)
  84.    {
  85.     ShowMessage("Critical Mem Failure");
  86.     sleep(2);
  87.     PM_ShutDown();
  88.     exit(1);
  89.    }
  90.   else {
  91. #ifdef NEWAGE
  92.     int j;
  93.     unsigned long k;
  94. #endif
  95.     sprintf(astr,"transposition tbl is %d\n",ttblsize);
  96.     ShowMessage(astr);
  97. // TMP
  98. //        sprintf(astr,"%lu bytes for ttable %lu bytes for etab",sizeof(struct hashentry)*(ttblsize+rehash)*2,sizeof(etab));
  99. //        ShowMessage(astr);
  100. // TMP
  101. #ifdef NEWAGE
  102.     /* WARNING: Bogus parameters ahead!
  103.      * The numbers that follow are based on pure fiction
  104.      * and are not contaminated with facts
  105.      */
  106.     TTageRate = ttblsize/3000 + 1; // try 3k, 1500 and 5000 and see
  107.                     // which gives lowest node cnts
  108.     TTdepthage[0] = 32768;
  109.     for (j=1, k = 50; j<=MAXDEPTH; j++, k *= (13-j))
  110.       {
  111.         /* Maximum k = 50 * 11! ~= 2^31 (this is a fact) */
  112.         TTdepthage[j] = (TTdepthage[j-1] > k/TTageRate) ?
  113.         TTdepthage[j-1] - k/TTageRate : 0;
  114.       }
  115. #else
  116.     ttbllimit = ttblsize<<1 - ttblsize>>2;
  117. #endif
  118.   }
  119. }
  120.  
  121. #define CB(i) (UCHAR) ((color[2 * (i)] ? 0x80 : 0)\
  122.     | (board[2 * (i)] << 4)\
  123.     | (color[2 * (i) + 1] ? 0x8 : 0)\
  124.     | (board[2 * (i) + 1]))
  125.  
  126. int __inline
  127. ProbeTTable (int side,
  128.          int depth,
  129.          int ply,
  130.          SHORT *alpha,
  131.          SHORT *beta,
  132.          SHORT *score)
  133.  
  134. /*
  135.  * Look for the current board position in the transposition table.
  136.  */
  137.  
  138. {
  139.   register struct hashentry *ptbl;
  140.   register /*unsigned*/ SHORT i = 0;    /*to match new type of rehash --tpm*/
  141.  
  142. #ifndef NEWAGE
  143.   ptbl = &ttable[side][hashkey % ttblsize];
  144.   while (true)
  145.     {
  146.       if (ptbl->depth == 0) return false;
  147.       if (ptbl->hashbd == hashbd) break;
  148.       if (++i > rehash) return false;
  149.       ptbl++;
  150.     }
  151. #else
  152.   for (i=rehash, ptbl = &ttable[side][hashkey % ttblsize];
  153.         ptbl->hashbd != hashbd; ptbl++)
  154.     if (--i == 0) return false;
  155.   /* Update age of rediscovered node */
  156.   ptbl->age = TTage - TTdepthage[ptbl->depth];
  157. #endif
  158.  
  159.   PV = SwagHt = ptbl->mv;
  160.   if ((ptbl->depth >= (short) depth))
  161.     {
  162.       if (ptbl->flags & truescore)
  163.     {
  164.       *score = ptbl->score;
  165.       /* adjust *score so moves to mate is from root */
  166.       if (*score > 9000) *score -= ply;
  167.       else if (*score < -9000) *score += ply;
  168.       *beta = -20000;
  169.     }
  170.       else if (ptbl->flags & lowerbound)
  171.     {
  172.       if (ptbl->score > *alpha)
  173.         *alpha = ptbl->score;
  174.     }
  175.       return (true);
  176.     }
  177.   return (false);
  178. }
  179.  
  180. int __inline
  181. PutInTTable 
  182.         (int side,
  183.          int score,
  184.          int depth,
  185.          int ply,
  186.          //int alpha,
  187.          int beta,
  188.          unsigned int mv)
  189.  
  190. /*
  191.  * Store the current board position in the transposition table.
  192.  */
  193.  
  194.   {
  195.     register struct hashentry *ptbl,*oldest;
  196.     unsigned short old;
  197.     register /*unsigned*/ SHORT i = 0;      /*to match new type of rehash --tpm*/
  198.  
  199. #ifdef NEWAGE
  200.     i=rehash;
  201.     old = 0;
  202.     ptbl = &ttable[side][hashkey % ttblsize];
  203.     while (true)
  204.       {
  205.         if (ptbl->hashbd == hashbd)
  206.           {
  207.         if(ptbl->depth > (UCHAR)depth) return false;
  208.         else break;
  209.           }
  210.         if (((TTage - ptbl->age) /*& 0xFFFF*/) > old) 
  211.           {
  212.         old = (TTage - ptbl->age)/* & 0xFFFF*/;
  213.         //if (old > TT_EXPIRATION) break; /* Use this expired entry */
  214.         oldest = ptbl;
  215.           }
  216.         if (--i == 0)
  217.           {
  218.         ptbl = oldest;
  219.         break;
  220.           }
  221.         ptbl++;
  222.       }
  223.  
  224.     if (--TTageClock == 0)
  225.       {
  226.         TTageClock = TTageRate;
  227.         TTage++;  /* Everyone is now just a little older */
  228.       }
  229.     TTadd++;
  230.     /* Update age of this node */
  231.     ptbl->age = TTage - TTdepthage[ptbl->depth];
  232. #else
  233.     TTadd++;
  234. #endif
  235. #ifdef HASHSTATS
  236.     HashAdd++;
  237. #endif
  238.     if(ptbl->depth > (UCHAR)depth) return false;
  239.     ptbl->hashbd = hashbd;
  240.     ptbl->depth = (UCHAR) depth;
  241.     ptbl->score = score;
  242.     ptbl->mv = mv;
  243.     if (score > beta)
  244.       {
  245.         ptbl->flags = lowerbound;
  246.         ptbl->score = beta + 1;
  247.       }
  248.     else
  249.       {
  250.         /* adjust score so moves to mate is from this ply */
  251.         if (score > 9000) score += ply;
  252.         else if (score < -9000 && score != -9999) score -= ply;
  253.         ptbl->score = score;
  254.         ptbl->flags = truescore;
  255.       }
  256.  
  257.     return true;
  258.   }
  259.  
  260. void
  261. ZeroTTable (int iop) /* iop: 0= clear any, 1= clear agged */
  262.   {
  263. #ifdef NEWAGE
  264.     if(iop==0)
  265.       {
  266.         TTageClock = TTageRate;
  267.         TTage = TTdepthage[0]+1; /* used to be newage + 1Zero entries are pre-expired. */
  268.         //TTage = TT_EXPIRATION + 1;
  269.         //TTageRate = ttblsize/(newage/2); /* Average 1/2 of table will be expired */
  270.         /* zero the age of all ttable entries */
  271.         if (!TTadd)
  272.          return;
  273.         ClearMem(ttable[0],sizeof(struct hashentry)*(ttblsize+rehash));
  274.         ClearMem(ttable[1],sizeof(struct hashentry)*(ttblsize+rehash));
  275.         TTadd = 0;
  276.       }
  277. #ifdef ZERO_1_DOES
  278.     else
  279.       {
  280.         /* Just add a major increment to TTage */
  281.         TTage += (TTdepthage[0] - TTdepthage[MAXDEPTH-1]);  /* Just a guess */
  282.       }
  283. #endif
  284. #else /* not NEWAGE */
  285.     if ((iop==0 && TTadd) || TTadd > ttbllimit)
  286.       {
  287.   ClearMem(ttable[0],sizeof(struct hashentry)*(ttblsize+rehash));
  288.   ClearMem(ttable[1],sizeof(struct hashentry)*(ttblsize+rehash));
  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.    if(ISZERO){ClearMem(rpthash, sizeof (rpthash));ISZERO=0;}
  603. }
  604. /********************** Hash code stuff ***********************/
  605. /*
  606.  * In a networked enviroment gnuchess might be compiled on different hosts
  607.  * with different random number generators, that is not acceptable if they
  608.  * are going to share the same transposition table.
  609.  */
  610. extern unsigned long int next;
  611.  
  612. #if defined NEWURAND
  613. /*
  614. This code copied from:
  615.  
  616. G. Wiesenekker. ZZZZZZ a chess program.
  617. Copyright (C) 1993  G. Wiesenekker
  618. E-mail: wiesenecker@sara.nl
  619.  
  620. A 32 bit random number generator. An implementation in C of the algorithm given by
  621. Knuth, the art of computer programming, vol. 2, pp. 26-27. We use e=32, so 
  622. we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which is implicitly
  623. done by unsigned arithmetic.
  624. */
  625.  
  626. unsigned int urand(void)
  627. {
  628.     /*
  629.     random numbers from Mathematica 2.0.
  630.     SeedRandom = 1;
  631.     Table[Random[Integer, {0, 2^32 - 1}]
  632.     */
  633.     static unsigned long x[55] =
  634.     {
  635.         1410651636UL,
  636.         3012776752UL,
  637.         3497475623UL,
  638.         2892145026UL,
  639.         1571949714UL,
  640.         3253082284UL,
  641.         3489895018UL,
  642.         387949491UL, 
  643.         2597396737UL,
  644.         1981903553UL,
  645.         3160251843UL,
  646.         129444464UL, 
  647.         1851443344UL,
  648.         4156445905UL,
  649.         224604922UL,
  650.         1455067070UL, 
  651.         3953493484UL,
  652.         1460937157UL,
  653.         2528362617UL,
  654.         317430674UL, 
  655.         3229354360UL,
  656.         117491133UL,
  657.         832845075UL,
  658.         1961600170UL, 
  659.         1321557429UL,
  660.         747750121UL,
  661.         545747446UL,
  662.         810476036UL,
  663.         503334515UL, 
  664.         4088144633UL,
  665.         2824216555UL,
  666.         3738252341UL,
  667.         3493754131UL, 
  668.         3672533954UL,
  669.         29494241UL,
  670.         1180928407UL,
  671.         4213624418UL,
  672.         33062851UL, 
  673.         3221315737UL,
  674.         1145213552UL,
  675.         2957984897UL,
  676.         4078668503UL, 
  677.         2262661702UL,
  678.         65478801UL,
  679.         2527208841UL,
  680.         1960622036UL,
  681.         315685891UL, 
  682.         1196037864UL,
  683.         804614524UL,
  684.         1421733266UL,
  685.         2017105031UL, 
  686.         3882325900UL,
  687.         810735053UL,
  688.         384606609UL,
  689.         2393861397UL
  690.     };
  691.     static int init = TRUE;
  692.     static unsigned long y[55];
  693.     static int j, k;
  694.     unsigned long ul;
  695.     
  696.     if (init)
  697.     {
  698.         int i;
  699.         
  700.         init = FALSE;
  701.         for (i = 0; i < 55; i++)
  702.             y[i] = x[i];
  703.         j = 24 - 1;
  704.         k = 55 - 1;
  705.     }
  706.     
  707.     ul = (y[k] += y[j]);
  708.     if (--j < 0) j = 55 - 1;
  709.     if (--k < 0) k = 55 - 1;
  710.     return((unsigned int)ul);
  711. }
  712.  
  713. #else
  714. unsigned int
  715. urand (void)
  716. {
  717.   next *= 1103515245;
  718.   next += 12345;
  719.   return ((unsigned int) (next >> 16) & 0xFFFF);
  720. }
  721. #endif
  722.  
  723. void
  724. gsrand (unsigned int seed)
  725. {
  726.   next = seed;
  727. }
  728.  
  729. extern unsigned long hashkey, hashbd;
  730. extern struct hashval hashcode[2][7][64];
  731.  
  732. #if !defined NOXRAND
  733. unsigned int
  734. xrand (int a, unsigned int b[])
  735. {
  736.   unsigned int i, r, loop;
  737.   unsigned int j, c;
  738.   unsigned int msk;
  739.   if (!a)
  740.     {
  741.       for (i = 0; i < 4000; i++)
  742.     b[i] = 0;
  743.       return 0;
  744.     }
  745.   loop = true;
  746.   while (loop)
  747.     {
  748.       r = urand ();
  749.       msk = 1;
  750.       c = 0;
  751.       for (j = 0; j < 16; j++)
  752.     {
  753.       if (r & msk)
  754.         c++;
  755.       msk = msk << 1;
  756.     }
  757.       if (c < 8)
  758.     continue;
  759.       loop = false;
  760.       for (i = 0; i < a; i++)
  761.     if (r == b[i])
  762.       {
  763.         loop = true;
  764.         break;
  765.       }
  766.       if (!loop)
  767.     {
  768.       b[a] = r;
  769.       return r;
  770.     }
  771.     }
  772.   return 0;
  773. }
  774. #else
  775. #define xrand(a,b) urand()
  776. #endif
  777.  
  778. void
  779. InitHashCode(unsigned int seed)
  780.   {
  781.     SHORT l, c, p;
  782. //      unsigned int t[4000];
  783.     unsigned int *t;
  784.     int cnt = 0;
  785.  
  786.     ShowMessage("Hashcode init");
  787.     ShowMessage("Please wait..");
  788.     t = calloc(sizeof(int)*4000,1);
  789.     if (!t)
  790.      {
  791.       DisplayError("Cannot init hashtable");
  792.       return;
  793.      }
  794.     xrand(cnt++,t);
  795.     gsrand (seed);  /* idealy we would preserve the old seed but... */
  796.     for (c = white; c <= black; c++)
  797.       for (p = pawn; p <= king; p++)
  798.         for (l = 0; l < 64; l++)
  799.           {
  800.             hashcode[c][p][l].key = (((unsigned long) xrand (cnt++,t)));
  801.             hashcode[c][p][l].key += (((unsigned long) xrand (cnt++,t)) << 16);
  802.             hashcode[c][p][l].bd = (((unsigned long) xrand (cnt++,t)));
  803.             hashcode[c][p][l].bd += (((unsigned long) xrand (cnt++,t)) << 16);
  804. #ifdef LONG64
  805.             hashcode[c][p][l].key += (((unsigned long) xrand (cnt++,t)) << 32);
  806.             hashcode[c][p][l].key += (((unsigned long) xrand (cnt++,t)) << 48);
  807.             hashcode[c][p][l].bd += (((unsigned long) xrand (cnt++,t)) << 32);
  808.             hashcode[c][p][l].bd += (((unsigned long) xrand (cnt++,t)) << 48);
  809. #endif
  810.           }
  811.     free(t);
  812.   }
  813.  
  814.