CPW-Engine transposition

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * CPW-Engine * Transposition

For definitions, see CPW-Engine_transposition_h

#include "stdafx.h"
#include "transposition.h"


extern bool time_over;

szobrist zobrist;

stt_entry * tt;
spawntt_entry * ptt;
sevaltt_entry * ett;

int tt_size = 0;
int ptt_size = 0;
int ett_size = 0;

/* function taken from Sungorus chess engine */
U64 rand64() {
  static U64 next = 1;

  next = next * 1103515245 + 12345;
  return next;
}

int tt_init() {

  /* fill the zobrist struct with random numbers */

  for (int pnr = 0; pnr <= 5; pnr++) {
    for (int cnr = 0; cnr <= 1; cnr++) {
      for (int snr = 0; snr <= 127; snr++) {
        zobrist.piecesquare[pnr][cnr][snr] = rand64();
      }
    }
  }

  zobrist.color = rand64();

  for (int castling = 0; castling <= 15; castling++) {
    zobrist.castling[castling] = rand64();
  }

  for (int ep = 0; ep <= 127; ep++) {
    zobrist.ep[ep] = rand64();
  }

  return 0;
}

int tt_setsize(int size) {

  /* check if size is a power of 2
  if not, make it the next lower power of 2
  this allows for a faster access of the entry needed:

  as sizeof(stt_entry) in our case is 16 Bytes long (see definition of stt_entry),
  we are creating size / 16 tt entries. The idea of making the size a power of 2
  is important when accessing the table. By 'anding' the hash value and the number
  of entries -1 (tt_size), we get a number in the range of 0 and the number of
  entries very quickly, this is used to index the entry.
  */

  free(tt);

  if (size & (size - 1)) {

    size--;
    for (int i = 1; i<32; i = i * 2)
      size |= size >> i;
    size++;
    size >>= 1;

  }

  if (size < 16) {
    tt_size = 0;
    return 0;
  }

  tt_size = (size / sizeof(stt_entry)) - 1;
  tt = (stt_entry *)malloc(size);

  return 0;
}

int tt_probe(U8 depth, int alpha, int beta, char * best) {

  if (!tt_size) return INVALID;

  /**************************************************************************
  *   Before  searching  a certain position, look whether we have  done  so *
  *   before. This is done by comparing the hashkey of the current position *
  *   to the hashkey of the specific tt entry. If they are the same, we may *
  *   use the move stored in the hash table to enhance move ordering.  When *
  *   the previous search was not shallower then the one needed now, we may *
  *   use  the  information present in the transposition table  to  replace *
  *   search altogether. We do it only if the value found is in the  proper *
  *   relation  to alpha and beta, i.e. when it would cause a cutoff.  Some *
  *   programs  do  use these informations to narrow the window,  but  then *
  *   you have to be extra careful to avoid search instability.             *
  **************************************************************************/

  stt_entry * phashe = &tt[b.hash & tt_size];

  if (phashe->hash == b.hash) {

    /***************************************************
    *   The  position  matches, so  we  may  retrieve  *
    *   a move that will be used for sorting purposes  *
    ***************************************************/

    *best = phashe->bestmove;

    /***************************************************
    *   Now test if we can retrieve position value     *
    *  ( saved depth greater than current depth )      *
    ***************************************************/

    if (phashe->depth >= depth) {

      if (phashe->flags == TT_EXACT)
        return phashe->val;

      if ((phashe->flags == TT_ALPHA) && (phashe->val <= alpha))
        return alpha;

      if ((phashe->flags == TT_BETA) && (phashe->val >= beta))
        return beta;

    }

  }

  return INVALID;

}

void tt_save(U8 depth, int val, char flags, char best) {

  if (!tt_size) return;
  if (time_over) return;

  stt_entry * phashe = &tt[b.hash & tt_size];

  if ((phashe->hash == b.hash) && (phashe->depth > depth)) return;

  phashe->hash = b.hash;
  phashe->val = val;
  phashe->flags = flags;
  phashe->depth = depth;
  phashe->bestmove = best;
}

int ttpawn_setsize(int size) {

  /* see tt_setsize for more details */

  free(ptt);

  if (size & (size - 1)) {

    size--;
    for (int i = 1; i<32; i = i * 2)
      size |= size >> i;
    size++;
    size >>= 1;

  }

  if (size < 8) {
    ptt_size = 0;
    return 0;
  }

  ptt_size = (size / sizeof(spawntt_entry)) - 1;
  ptt = (spawntt_entry *)malloc(size);

  return 0;
}

int ttpawn_probe() {

  if (!ptt_size) return INVALID;

  spawntt_entry * phashe = &ptt[b.phash & ptt_size];

  if (phashe->hash == b.phash) return phashe->val;

  return INVALID;

}

void ttpawn_save(int val) {

  if (!ptt_size) return;

  spawntt_entry * phashe = &ptt[b.phash & ptt_size];

  phashe->hash = b.phash;
  phashe->val = val;
}

int tteval_setsize(int size) {

  /* see tt_setsize for more details */

  free(ett);

  if (size & (size - 1)) {

    size--;
    for (int i = 1; i<32; i = i * 2)
      size |= size >> i;
    size++;
    size >>= 1;

  }

  if (size < 16) {
    ett_size = 0;
    return 0;
  }

  ett_size = (size / sizeof(sevaltt_entry)) - 1;
  ett = (sevaltt_entry *)malloc(size);

  return 0;
}

int tteval_probe() {

  if (!ett_size) return INVALID;

  sevaltt_entry * phashe = &ett[b.hash & ett_size];

  if (phashe->hash == b.hash) return phashe->val;

  return INVALID;

}

void tteval_save(int val) {

  if (!ett_size) return;

  sevaltt_entry * phashe = &ett[b.hash & ett_size];

  phashe->hash = b.hash;
  phashe->val = val;
}

Up one Level