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
Size of Transposition Table Entry
Moderators: hgm, Rebel, chrisw
-
- Posts: 12
- Joined: Mon Aug 07, 2017 5:24 pm
- Location: Los Angeles
-
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Size of Transposition Table Entry
Let the users choose.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
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.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Size of Transposition Table Entry
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.
-
- Posts: 12
- Joined: Mon Aug 07, 2017 5:24 pm
- Location: Los Angeles
Re: Size of Transposition Table Entry
Mine is 32 bytes per entry, although I'm sure I can get it smaller
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Size of Transposition Table Entry
That's big. I think 16 bytes should do. In RuyDos I havejfern2011 wrote:Mine is 32 bytes per entry, although I'm sure I can get it smaller
Code: Select all
struct HashEntry {
u64 lock;
i16 score_and_bound;
u16 move;
u8 depth;
u8 period;
};
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Size of Transposition Table Entry
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.
-
- Posts: 268
- Joined: Sun Apr 24, 2011 12:33 am
Re: Size of Transposition Table Entry
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
Some SMP engine uses two uint64 members, key and data, where data is packed
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;
Skiull http://skiull.blogspot.com
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Size of Transposition Table Entry
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.
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.)
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
*/
}
}
}
Last edited by hgm on Fri Sep 29, 2017 11:48 pm, edited 6 times in total.
-
- Posts: 105
- Joined: Mon Jun 09, 2014 12:22 am
- Full name: James Swafford
Re: Size of Transposition Table Entry
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.
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.
-
- Posts: 2204
- Joined: Sat Jan 18, 2014 10:24 am
- Location: Andorra
Re: Size of Transposition Table Entry
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;
Daniel José - http://www.andscacs.com