TalkChess.com

In parallel search transposition table could be corrupted by simultaneous read/write in a tt element. I have been using simple testing of legality of move to avoid crashing problems. Now that I am doing other games too, this has become difficult mostly because MOVE is not a simple int. It could be 14 ints in checkers f.i and any of the bytes could get corrupted.

Can lock-less hashing be used for hash_entry size != 128-bit ? The information I store is different for each game. Can I do the test only on part of the data (f.i first 128 bits) and be guaranteed a safe data ? Most of the time I need only the best move to be safe. I can read the whole paper and try to get it but I am too lazy right now.

It will work for any size. Just XOR the hash signature with (parts from) all other words. So with a 256-bit entry (four 64-bit memory words) and a 32-bits ignature, you can do

signature ^= (word1 ^ word2 ^ word3) & 0xFFFFFFFF;

(assuming the signature is in word0), both before storing and before probing. Even safer would be toXOR with all other seven 32-bit units, to catch mixups that happen to have the same low 32-bits but different high bits.

Oh great! I was getting tired of writing game specific code. This is a clean and hassle free way if I managed to implement it.
Thanks.

Daniel Shawul wrote:In parallel search transposition table could be corrupted by simultaneous read/write in a tt element. I have been using simple testing of legality of move to avoid crashing problems. Now that I am doing other games too, this has become difficult mostly because MOVE is not a simple int. It could be 14 ints in checkers f.i and any of the bytes could get corrupted.

Can lock-less hashing be used for hash_entry size != 128-bit ? The information I store is different for each game. Can I do the test only on part of the data (f.i first 128 bits) and be guaranteed a safe data ? Most of the time I need only the best move to be safe. I can read the whole paper and try to get it but I am too lazy right now.

Certainly. I use it on my pawn hash as well, where an entry is 24 bytes if I recall. You just xor them all together and store that as the signature...

I was misguided by the 128 bit description given there but now I remember it was used also in pawn tt. The way HG described it sounds like a CRC check for data integrity in a way every data stored contributes to the key ?
How about hash collisions i.e the real ones where two different positions map to the same hash_key ? We still need to check for legality of move. I know it shouldn't happen but I am not sure since my pseudo-random numbers are generated with a different seed each time using a rather weak rand(). Just a thought.

Hash collisions happen. Here, however, they are not an issue in that if two different positions have the same signature, and the same score and such, they will collide. If they have the same sig, but different scoring info, they won't because the XOR changes the stored key. The final choice is two different positions, with different everything, but they end up matching because of all the XORing...

In short, it is not worth worrying about. It is much more likely to have out-of-order writes produce corrupted entries when doing an SMP search, and those happen often enough to become problematic at times... Lockless hashing at least solves that (as much as it can be solved, anyway).