Size of Transposition Table Entry

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jfern2011
Posts: 12
Joined: Mon Aug 07, 2017 3:24 pm
Location: Los Angeles

Size of Transposition Table Entry

Post by jfern2011 » Fri Sep 29, 2017 4:24 am

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
Posts: 10101
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Size of Transposition Table Entry

Post by Dann Corbit » Fri Sep 29, 2017 4:50 am

jfern2011 wrote: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.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Size of Transposition Table Entry

Post by hgm » Fri Sep 29, 2017 6:01 am

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
Posts: 12
Joined: Mon Aug 07, 2017 3:24 pm
Location: Los Angeles

Re: Size of Transposition Table Entry

Post by jfern2011 » Fri Sep 29, 2017 4:01 pm

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

AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Size of Transposition Table Entry

Post by AlvaroBegue » Fri Sep 29, 2017 6:16 pm

jfern2011 wrote: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.

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Size of Transposition Table Entry

Post by hgm » Fri Sep 29, 2017 7:17 pm

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
Posts: 259
Joined: Sat Apr 23, 2011 10:33 pm
Contact:

Re: Size of Transposition Table Entry

Post by tttony » Fri Sep 29, 2017 8:14 pm

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

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Size of Transposition Table Entry

Post by hgm » Fri Sep 29, 2017 9:27 pm

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.)
Last edited by hgm on Fri Sep 29, 2017 9:48 pm, edited 6 times in total.

jswaff
Posts: 50
Joined: Sun Jun 08, 2014 10:22 pm
Contact:

Re: Size of Transposition Table Entry

Post by jswaff » Fri Sep 29, 2017 9:27 pm

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.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Size of Transposition Table Entry

Post by cdani » Fri Sep 29, 2017 11:08 pm

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;

Post Reply