Page 1 of 3
Size of Transposition Table Entry
Posted: Fri Sep 29, 2017 6:24 am
by 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
Re: Size of Transposition Table Entry
Posted: Fri Sep 29, 2017 6:50 am
by Dann Corbit
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.
Re: Size of Transposition Table Entry
Posted: Fri Sep 29, 2017 8:01 am
by 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.
Re: Size of Transposition Table Entry
Posted: Fri Sep 29, 2017 6:01 pm
by jfern2011
Mine is 32 bytes per entry, although I'm sure I can get it smaller
Re: Size of Transposition Table Entry
Posted: Fri Sep 29, 2017 8:16 pm
by AlvaroBegue
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.
Re: Size of Transposition Table Entry
Posted: Fri Sep 29, 2017 9:17 pm
by 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.
Re: Size of Transposition Table Entry
Posted: Fri Sep 29, 2017 10:14 pm
by 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
Re: Size of Transposition Table Entry
Posted: Fri Sep 29, 2017 11:27 pm
by 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(slot=0; slot<7; slot++) {
if(quickKey[slot] == quick && ((signature ^ b->e[slot].keyAndDepth) & ~255) == 0) {
return &(b->e[slot]);
/* in caller:
char depth = b->e[slot].keyAndDepth; // low order 8 bits
int score = b->e[slot].score;
int move = b->e[slot].moveAndFlags & ~H_FLAGS;
int flags = b->e[slot].moveAndFlags & H_FLAGS; // actually you would test them individually as needed
*/
}
}
}
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.)
Re: Size of Transposition Table Entry
Posted: Fri Sep 29, 2017 11:27 pm
by 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.
Re: Size of Transposition Table Entry
Posted: Sat Sep 30, 2017 1:08 am
by 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;