ttable.c

GNU国际象棋C++源代码Windows版的

/* ttable.c -- Transposition table code to be included in search.c */
/* #include "gnuchess.h"  already included, see search.c */
/* #include "ttable.h"  dito */
/* NOTE: The static evaluation cache "EETable" belongs to eval.c and cannot*/
/*       be moved to ttable.c */
/* Privae types and data */

struct hashentry
     {
       unsigned long hashbd;
       UCHAR flags, depth;      /* CHAR saves some space */
       tshort score;
       utshort mv;
#ifdef HASHTEST
       UCHAR bd[32];
#endif /* HASHTEST */
#ifdef NEWAGE
   utshort age;        /* age of last use */
#endif
     };
struct hashentry *ttable[2];

unsigned long ttblsize;
SHORT rehash;  /* -1 is used as a flag --tpm */
#ifdef NEWAGE
        utshort TTage;        /* Current ttable age */
        UTSHORT TTageClock,    /* Count till next age tick */
                TTageRate;      /* new entry counts per age tick */
        UTSHORT TTdepthage[MAXDEPTH+1];    /* Depth bonus for aging*/
        UTSHORT newage = NEWAGE;    /* Initialization tuning parameter */
#else
unsigned int ttbllimit;
unsigned int TTadd = 1;
#endif

#ifdef HASHSTATS
unsigned long ttdepthin[MAXDEPTH+1], ttdepthout[MAXDEPTH+1];
unsigned long ttrehash[MAXrehash+1];
unsigned long ttprobe[MAXDEPTH+1];
unsigned long HashCnt, HashAdd, FHashCnt, FHashAdd, HashCol, THashCol;
#endif

/* hashtable flags */
#define truescore 0x0001
#define lowerbound 0x0002
#define upperbound 0x0004
#define kingcastle 0x0008
#define queencastle 0x0010
#define evalflag 0x0020

void
Initialize_ttable ()
{
  int doit = true;
  if (rehash < 0) rehash = MAXrehash;
while(doit && ttblsize > MINTTABLE){
  ttable[0] = (struct hashentry *)malloc(sizeof(struct hashentry)*(ttblsize+rehash));
  ttable[1] = (struct hashentry *)malloc(sizeof(struct hashentry)*(ttblsize+rehash));
  if(ttable[0] == NULL || ttable[1] == NULL){
  if(ttable[0] != NULL)free(ttable[0]);
  ttblsize = ttblsize>>1;
  } else doit = false;
}
  if(ttable[0] == NULL || ttable[1] == NULL){ ShowMessage(CP[70]);Exit(1);}
  else {
   int j;
#ifdef notdef
  printf("transposition table is %ld\n",ttblsize);
#endif
#ifdef NEWAGE
        TTageRate = ttblsize / 1024;
        TTdepthage[0] = TTdepthage[1] = newage;
        for (j=2; j<=MAXDEPTH; j++)
            TTdepthage[j] = TTdepthage[j-1]/2;
/*    ZeroTTable(0); -- called in NewGame() */
#else
   ttbllimit = ttblsize<<1 - ttblsize>>2;
#endif
  }
}

#define CB(i) (UCHAR) ((color[2 * (i)] ? 0x80 : 0)\
   | (board[2 * (i)] << 4)\
   | (color[2 * (i) + 1] ? 0x8 : 0)\
   | (board[2 * (i) + 1]))

inline
int
ProbeTTable (SHORT side,
        SHORT depth,
        SHORT ply,
        SHORT *alpha,
        SHORT *beta,
        SHORT *score)

/*
 * Look for the current board position in the transposition table.
 */

{
    register struct hashentry *ptbl;
    register SHORT i = 0;

#ifdef DEBUG
    if(flag.nott)return false;
#endif
#ifdef HASHSTATS
    ttprobe[depth]++;
#endif
#ifdef NEWAGE
     /* Find entry within rehash window or return failure */
     for (i=rehash, ptbl = &ttable[side][hashkey % ttblsize];
          ptbl->hashbd != hashbd; ptbl++)
       if (--i == 0) return false;
     /* Update age of rediscovered node */
          ptbl->age = TTage - TTdepthage[ptbl->depth];
#else
    ptbl = &ttable[side][hashkey % ttblsize];
    while (true)
      {
     if (ptbl->depth == 0) return false;
     if (ptbl->hashbd == hashbd) break;
     if (++i > rehash) return false;
     ptbl++;
      }
#endif

    PV = SwagHt = ptbl->mv;
    if ((ptbl->depth >= (SHORT) depth) || abs(ptbl->score)>9000)
      {
#ifdef HASHTEST
     for (i = 0; i < 32; i++)
       {
      if (ptbl->bd[i] != CB (i))
        {
#ifdef HASHSTATS
            HashCol++;
            ShowMessage (CP[51]); /*ttable collision detected*/
#endif
            break;
        }
       }
#endif /* HASHTEST */

#ifdef HASHSTATS
     ttdepthout[ptbl->depth]++;
     HashCnt++;
#endif

     if (ptbl->flags & truescore)
       {
      *score = ptbl->score;
      /* adjust *score so moves to mate is from root */
      if (*score > 9000) *score -= ply;
      else if (*score < -9000) *score += ply;
      *beta = -20000;
       }
     else if (ptbl->flags & lowerbound)
       {
      if (ptbl->score > *alpha)
#ifdef notdef
        *alpha = ptbl->score - 1;
#endif
      *alpha = ptbl->score;
       }
#ifdef DEBUG
     if (debuglevel & 32)
       {
      algbr (PV >> 8, PV & 0xff, 0);
      printf ("-get-> h=%lx d=%d s=%d p=%d a=%d b=%d %s\n", hashbd, depth, *score, ply, *alpha, *beta, mvstr);
       }
#endif
     return (true);
      }
    return (false);
}

inline
int
PutInTTable 
      (SHORT side,
        SHORT score,
        SHORT depth,
        SHORT ply,
        SHORT alpha,
        SHORT beta,
        UTSHORT mv)

/*
 * Store the current board position in the transposition table.
 */

  {
   register struct hashentry *ptbl;
   register SHORT i = 0;
#ifndef NEWAGE

   ptbl = &ttable[side][hashkey % ttblsize];
   while (true)
     {
      if (ptbl->depth == 0) break;
      if ((ptbl->hashbd) == hashbd) {
          if (ptbl->depth > (UCHAR)depth) return false; else break;
      }
      if (++i > rehash)
        {
#ifdef HASHSTATS
         THashCol++;
#endif
         ptbl -= rehash; /* Hey! it's already randomized. use the original location. */
                     /* There is some discussion about thrashing.... */
         break;
        }
      ptbl++;
     }
   TTadd++;
   if (ptbl->depth > (UCHAR)depth) return false;

#else /* NEWAGE */
   utshort old;
        struct hashentry *oldest;

        /* Look for match or oldest entry to reuse */
   /* Note that arithmetic on ages is intentionally modulo 65536 */
        i = rehash;
   oldest = ptbl = &ttable[side][hashkey % ttblsize];
        old = TTage - ptbl->age;
   while (ptbl->hashbd != hashbd) {
       if (--i == 0) break;
       ptbl++;
       if ((TTage - ptbl->age) > old) {
      old = TTage - ptbl->age;
      oldest = ptbl;
       }
   }
        if (i == 0) {
            ptbl = oldest; /* reuse oldest entry */
#ifdef HASHSTATS
       THashCol++;
#endif
            if (--TTageClock == 0) {
                TTageClock = TTageRate;
                TTage++;        /* Everyone is now just a little older */
       }
   } else {
/*!!!     if (ptbl->depth > (UCHAR)depth) return false;*/
   }
/*!!!*/      if (ptbl->depth > (UCHAR)depth) return false;
        ptbl->age = TTage - TTdepthage[depth]; /* Set age of this node */

#endif /* NEWAGE */
#ifdef HASHSTATS
   HashAdd++;
#endif
   ptbl->hashbd = hashbd;
   ptbl->depth = (UCHAR) depth;
   ptbl->score = score;
   ptbl->mv = mv;
#ifdef DEBUG
   if (debuglevel & 32)
     {
      algbr (mv >> 8, mv & 0xff, 0);
      printf ("-add-> h=%lx d=%d s=%d p=%d a=%d b=%d %s\n", hashbd, depth, score, ply, alpha, beta, mvstr);
     }
#endif
   if (score > beta)
     {
      ptbl->flags = lowerbound;
      ptbl->score = beta + 1;
     }
   else
          {
      /* adjust score so moves to mate is from this ply */
      if (score > 9000) score += ply;
      else if (score < -9000) score -= ply;
      ptbl->score = score;
      ptbl->flags = truescore;
     }

#ifdef HASHSTATS
   ttdepthin[ptbl->depth]++;
   ttrehash[i]++;
#endif
#ifdef HASHTEST
   for (i = 0; i < 32; i++)
     {
      ptbl->bd[i] = CB (i);
     }
#endif /* HASHTEST */
   return true;
  }

void
ZeroTTable (int iop) /* iop: 0= clear any, 1= clear agged */
  {
#ifdef NEWAGE
   if(iop==0)
     {
      TTageClock = TTageRate;
      TTage = newage+1; /* Zero entries are pre-expired. */
      /* zero the age of all ttable entries */
      memset(ttable[white],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
      memset(ttable[black],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
     }
   else
      /* Just add a major increment to TTage */
      TTage += newage/5;  /* Just a guess */
#else /* not NEWAGE */
   if ((iop==0 && TTadd) || TTadd > ttbllimit)
     {
      memset(ttable[white],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
      memset(ttable[black],0,sizeof(struct hashentry)*(unsigned)(ttblsize+rehash));
       TTadd = 0;
      }
#endif /* NEWAGE */

}

/************************* Hash table statistics ****************************/

#ifdef HASHSTATS
long EADD,EGET;   /* Eval cache stats */

void
ClearHashStats()  /* initialize the stats */
  {
   memset ((CHAR *) ttdepthin, 0, sizeof (ttdepthin));
   memset ((CHAR *) ttdepthout, 0, sizeof (ttdepthout));
   memset ((CHAR *) ttrehash, 0, sizeof (ttrehash));
   memset ((CHAR *) ttprobe, 0, sizeof (ttprobe));
   HashAdd = HashCnt = THashCol = HashCol = FHashCnt = FHashAdd = 0;
   EADD = EGET = 0;
  }

void
ShowHashStats()   /* print the stats */
  {
   int ii;
   printf("Probe: ");
   for(ii=0;ii<MAXDEPTH;ii++)
      if (ttprobe[ii])
         printf(" %d:%ld", ii, ttprobe[ii]);
   printf("\nIn/Out: ");
   for(ii=0;ii<MAXDEPTH;ii++)
      if (ttdepthin[ii] || ttdepthout[ii])
         printf(" %d:%ld/%ld", ii, ttdepthin[ii], ttdepthout[ii]);
   printf("\nRehash: ");
   for(ii=0;ii<=MAXrehash;ii++)
      printf(" %ld", ttrehash[ii]);
   printf("\n");
   printf (CP[71],
      HashAdd, HashCnt, THashCol, HashCol,FHashCnt, FHashAdd);
#ifdef CACHE
   printf ("cache in/out: %ld/%ld\n", EADD, EGET);
#endif
  }
#endif

/************************* Hash File Stuf ****************************/
#ifdef HASHFILE
#define frehash 6

     struct fileentry
     {
       UCHAR bd[32];
       UCHAR f, t, flags, depth, sh, sl;
     };

FILE *hashfile = NULL;
unsigned long HFileSize;      /* Nunber of fileentry records in hash file */

void 
CreateHashFile(long sz)
/* NOTE: If sz is Odd the black and white positions will be
   scrambled (Is this good or bad?) */
  {
   if ((hashfile = fopen (HASHFILE, RWA_ACC)))  /* old file */
     {   /* chech size, warn if shrinking? */
      fseek (hashfile, 0L, SEEK_END);
      HFileSize = ftell (hashfile) / sizeof (struct fileentry);
      if (sz < HFileSize) sz = HFileSize;
      fseek (hashfile, 0L, SEEK_SET);
     }
   else if (sz)
     {   /* create new file only if we have a size */
      hashfile = fopen (HASHFILE, WA_ACC);
     }
   if (hashfile != NULL)
     {
      long j;
      struct fileentry n[64]; /* Write a bunch at a time */
      
      memset ((CHAR *) n, 0, sizeof (n));
/*    n.f = n.t = 0; */
/*    n.flags = 0; */
/*    n.depth = 0; */
/*    n.sh = n.sl = 0; */
      for (j = 0; j < sz; j += 64)
         fwrite (&n, sizeof (struct fileentry), sz-j<64 ? sz-j: 64, hashfile);
      fclose (hashfile);
      hashfile = NULL;
     }
   else
     {
      sprintf (msg,CP[79], HASHFILE);
      ShowMessage(msg);
     }
  }
  
void 
OpenHashFile() /* try to open hash file */
  {
   hashfile = fopen (HASHFILE, RWA_ACC);
   if (hashfile)
     {
      fseek (hashfile, 0L, SEEK_END);