Hacker News Reader

Comment by agalunar | Hacker News Reader

True, although I'd say transposition tables are much, much easier in a crucial aspect – you deal with hash collisions by simply overwriting the current entry or nop'ing. There's no linear probing, no cuckoo hashing, &c; when you want to update an entry, you check whether you'd rather store the new thing or keep the old, and that's it.

View on HN

That's true in theory, but in the actual Stockfish implementation, a sort of mixed strategy is employed where entries are kept in clusters of 3. So there's a type of limited linear probing there too. Additionally, there's a lot of cleverness employed in how a position's hash is mapped to an individual cluster, and how collisions are avoided without storing a copy of the position or the full key(see the first_entry method in the header and the key16 field in the entry struct).

But indeed, it's not a large amount of code. But there's a lot of thought put into every aspect of how the data is laid out, and how the table is probed. It's a nice case study in domain specific optimisation.

That's not linear probing, though; that's having a 3-way associative cache.

Maybe that's how I should have phrased my comment: a transposition table is a cache, not a hash map,* because entries can be lost (overwritten). Furthermore, insertions may not succeed.

I know you know this; I mentioned it because I didn't want anyone to read Stockfish's source expecting an implementation of a hash map and then get confused.

Stockfish's source is well-written and incidentally didactic, so I'd definitely second the recommendation to read it.

*Or hash table, or dictionary; these are all synonyms, I just prefer "map" myself.

Reply on news.ycombinator.com