Size of Transposition Table Entry

[jfern2011]

I was wondering what size people typically choose for their transposition tables. Right now I'm using 8 million entries, but the table fills up after searching only 15 plies from the starting position.

Thanks,
Jason

[Dann Corbit]

I was wondering what size people typically choose for their transposition tables. Right now I'm using 8 million entries, but the table fills up after searching only 15 plies from the starting position.

Thanks,
Jason

Let the users choose.
I do long analysis, and sometimes I need 16GB or more.
I find that with 60 cores, the transposition table fills up in a startling hurry.

I think that almost every program has an option to choose the transposition table size.

There is a secondary, related question, though.
What percentage should be for regular hash, pawn hash (if specialized pawn hash exists), and eval hash (if specialized eval hash exists)?

I think that the dependence is not linear.
The regular hash should be proportionally the largest and the proportion should grow as the hash table grows.
The pawn hash is second in memory need, and the eval hash is lowest.

Generally, you can get away with a fixed eval hash that is fairly small.

[hgm]

BTW, the size of a TT entry is just 16, 12 or even 9 byte. LArger size of the TT means you have more entries in it.

[jfern2011]

Mine is 32 bytes per entry, although I'm sure I can get it smaller

[AlvaroBegue]

Mine is 32 bytes per entry, although I'm sure I can get it smaller

That's big. I think 16 bytes should do. In RuyDos I have

Code: Select all

struct HashEntry {
  u64 lock;
  i16 score_and_bound;
  u16 move;
  u8 depth;
  u8 period;
};

The "period" field (I think others call it "age") could use fewer bits, and you may want to use more bits for evaluation (I only use 14). But something similar to this should do.

[hgm]

Nowadays I also store in-check info in the TT entry. That allows me to skip any in-check testing to determine if the hash move should be extended.

[tttony]

This is what I have in my engine, I tested 16 vs 32 bytes, the 16 bytes is faster, right now I'm not using the last two

Code: Select all

typedef struct hash_entry_s {
	uint64_t key;
	move_t move; //u16
	score_t score; //i16
	int8_t depth;
	int8_t flags;
	int8_t age;
	int8_t unused;
} hash_entry_s;

Some SMP engine uses two uint64 members, key and data, where data is packed

[hgm]

64-bit key is very generous, and for a large part redundant, as many bits are already implied by the index. And to get the remainder in 8 bytes, you hardly have to pack. Even with a 4-byte key Joker only needs 9 bytes for an entry. You could store a move and two scores as int16, and two depths as uint8, for a two-sided hash table.

For speed you could put one byte of the key of each entry in the first 8-byte word of a 64-byte hash bucket. You can then conclude with 97% reliability that you have a hash miss just from the first word, and would thus almost never have to wait until the other words are fetched from memory. The other 7 words could then each contain a hash entry consisting of 2 byte score, 2 byte move & flags, 1 byte depth and 3 byte key (for a total of 4 key bytes). You could put the always-replace entry (where the overwhelmingly large fraction of hits takes place) in the second in the second word of the bucket, so that even in case of a hit you would almost never have to look in (and thus wait for) the remaining 6 words.

Code: Select all

#define H_UPPER 0x8000
#define H_LOWER 0x0800
#define H_CHECK 0x0008
#define H_FLAGS (H_UPPER | H_LOWER | H_CHECK)

typedef struct {
  uint32 keyAndDepth;
  uint16 moveAndFlags;
  int16 score;
} HashEntry;

typedef struct {
  char quickKey[7];
  char spare;
  HashEntry e[7];
} HashBucket;

HashEntry *Probe(uint64 hashKey)
{
  int slot;
  int index = hashKey & hashMask;
  HashBucket *b = hashTable + index;
  uint32 signature = haskKey >> 32;
  char quick = signature;
  for&#40;slot=0; slot<7; slot++) &#123;
    if&#40;quickKey&#91;slot&#93; == quick && (&#40;signature ^ b->e&#91;slot&#93;.keyAndDepth&#41; & ~255&#41; == 0&#41; &#123;
      return &&#40;b->e&#91;slot&#93;);
      /* in caller&#58;
        char depth = b->e&#91;slot&#93;.keyAndDepth; // low order 8 bits
        int score =  b->e&#91;slot&#93;.score;
        int move =   b->e&#91;slot&#93;.moveAndFlags & ~H_FLAGS;
        int flags =  b->e&#91;slot&#93;.moveAndFlags & H_FLAGS; // actually you would test them individually as needed
      */
    &#125;
  &#125;
&#125;

The 'spare' byte could contain a 1-bit flag per entry, e.g. for age (current search or not), or for in-check. A Chess move would typically use only 13 out of the 16 bytes, so that it leaves 3 bits for flags. (e.g. upper bound, lower bound and in-check.)

[jswaff]

In my C engine Prophet, I use 16 bytes (8 for key and 8 for a packed val).

I also have a Java chess engine, chess4j, that uses some ridiculously large TT entry size due to storing objects in the table. I could add some method to encode those into 'long' primitives but I haven't done so yet.

[cdani]

Andscacs 16 bytes:

Code: Select all

	uint64_t w1; //uint32_t key, uint16_t move, int16_t evaluation
	int16_t score;
	uint16_t secondmove;
	uint8_t tipuspuntuaciohash;  //alpha,beta,exact
	uint8_t age;
	int8_t depth;