This isn't about chess directly. but this new-today video looks directly applicable to hash tables as I've seen discussed here. For months I've wondered why those coding chess in C++ don't use unordered_set from the STL (maybe some do but I've seen no mention of it), but it's clear that optimizing for performance is a big deal. This video goes into it:
HashTable methods video
Moderator: Ras
-
hgm
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: HashTable methods video
It is also important to realize that Transposition Tables in chess engines are a special case of using hashing, which would disqualify it as a general purpose hash table. We accept that data stored in it can be lost by overwriting, or that probing it can return erroneous data. Both of these are absolute no-nos in a general hash table, like an 'unordered set'. Programmers who use hash tables in other contexts would consider this so crappy that they would not recognize the TT as a hash table at all. Their first instinct is be to 'improve' on it by storing the full position (e.g. in FEN form) as a signature, so that you never can get a key collision, and rehash new entries rather than overwriting existing ones that have not aged yet.
Of course that defeats the purpose, because we know a TT that can be hold in memory will not be large enough to store every node in the search tree, and swapping to disk slows down things by many orders of magnitude. So you kick out the less important data to make room for the more important data. And smaller signatures allows you to hold more data, which is far more important than preventing occasional return of erroneous data.
Of course chess engines use hashing for other cases than the TT, such as magic bitboards. The techniquest mentioned in the video could be useful to speed up the hashing there.
Of course that defeats the purpose, because we know a TT that can be hold in memory will not be large enough to store every node in the search tree, and swapping to disk slows down things by many orders of magnitude. So you kick out the less important data to make room for the more important data. And smaller signatures allows you to hold more data, which is far more important than preventing occasional return of erroneous data.
Of course chess engines use hashing for other cases than the TT, such as magic bitboards. The techniquest mentioned in the video could be useful to speed up the hashing there.