Lazy SMP and shared hash table

[amanjpro]

What I did recently is change my buckets to three elements stored in 4 uint64. The first uint64 is just a directory containing 21 bits of metadata per entry like age, depth, type and however many bits of signature fit after that. The remaining three entries then contain the rest of the signature as well as score and move. The idea being that you only need to inspect that metadata to find an entry to replace instead of the entries themselves.

So to fully update an entry technically i'd have to atomically write both the metadata uint64 as well as the entry uint64. Which I don't do. The justification being that if there is a race condition in the worst case you see mismatched metadata and entry. However since both contain part of the signature the chance of mistaking a partial entry as a real one is very small. So if you multiply out the chances of there being a data race in the first place, that race not resulting in a signature mismatch AND that entry being critical for the search result the risk is low enough. Probably lower than the chance of a key collision which is a risk we already accept in the TT.

That is an interesting use of buckets! Unfortunately I am not using buckets in my TT, so changing to this representation is a big change, as I am already introducing a whole new world of changes with Lazy SMP... but will see what happens, as I am still exploring

[amanjpro]

Actually, thinking about it. The Xor approach won't work on 32-bit architecture. Which is a bummer really.

As that excludes all Android and my own Raspberry Pi from benefiting from multithreading

[AndrewGrant]

Actually, thinking about it. The Xor approach won't work on 32-bit architecture. Which is a bummer really.

As that excludes all Android and my own Raspberry Pi from benefiting from multithreading

I feel there is very little reason to be concerned about lockless hashing or not. So long as your engine won't crap itself upon getting a bad value (Which should already be true, since you only store so much of the Zobrist), then all is well.

[Ronald]

There was a topic on the same subject half a year ago:

http://talkchess.com/forum3/viewtopic.p ... 34#p881317

[amanjpro]

Actually, thinking about it. The Xor approach won't work on 32-bit architecture. Which is a bummer really.

As that excludes all Android and my own Raspberry Pi from benefiting from multithreading

I feel there is very little reason to be concerned about lockless hashing or not. So long as your engine won't crap itself upon getting a bad value (Which should already be true, since you only store so much of the Zobrist), then all is well.

I agree with you, relying on zoibrist key alone for hashmove legality is somewhat risky. But I have been using hash moves without any checks for pseudo legality, and I have never had issues with that. The risk might be just too small to bother, at least for now.

There was a topic on the same subject half a year ago:

http://talkchess.com/forum3/viewtopic.p ... 34#p881317

That's a nice one, thank you. How did you end up addressing this in 32-bit architecture? I might just disable multi threading in these builds, but I'm willing to learn, if there is a trick

[AndrewGrant]

I agree with you, relying on zoibrist key alone for hashmove legality is somewhat risky. But I have been using hash moves without any checks for pseudo legality, and I have never had issues with that. The risk might be just too small to bother, at least for now.

If you are blindly taking the move from the TT, and applying it to the current board state, I highly suggest you implement a pseudo legality check immediately. Your engine will almost certainly crash given the right series of unfortunate events, which is extremely common with smaller key sizes, and still not out of the realm of possibility with 64bit keys.

[amanjpro]

I agree with you, relying on zoibrist key alone for hashmove legality is somewhat risky. But I have been using hash moves without any checks for pseudo legality, and I have never had issues with that. The risk might be just too small to bother, at least for now.

If you are blindly taking the move from the TT, and applying it to the current board state, I highly suggest you implement a pseudo legality check immediately. Your engine will almost certainly crash given the right series of unfortunate events, which is extremely common with smaller key sizes, and still not out of the realm of possibility with 64bit keys.

So far, I was using the full 64 bit Zoibrist key the table. So, I was reasonably confident that the hash move belongs to a position that produces the same key. I know, it is risky, but the risk is small enough, that I am not really too worried about it.

I intend to add move pseudo legality check later, so I can use killer moves before generating quiet moves, but I feel like introducing LazySMP and the check at the same time is too much, to debug/test

The question, that I should ask is: using the Xor approach, I'll be storing checksums not keys, does this mean the chance of pseudo illegal moves go higher? I have no idea

[amanjpro]

Read a few older posts, and that is what I will do:

- Xor to make sure that the data read is not corrupt
- Test the hell out of SMP on my machine and merge it

Another PR (follows immediately):
- Test pseudo-legality for hash moves (as well as killers)
- Use killers before generating quiet moves (if possible)

Thanks everyone for your contribution in the subject, it really means a lot to me!

[connor_mcmonigle]

Read a few older posts, and that is what I will do:

- Xor to make sure that the data read is not corrupt
- Test the hell out of SMP on my machine and merge it

Another PR (follows immediately):
- Test pseudo-legality for hash moves (as well as killers)
- Use killers before generating quiet moves (if possible)

Thanks everyone for your contribution in the subject, it really means a lot to me!

I've found the XOR "trick" to be useless. On x86, you have certain aligned write atomicity guarantees which just make it pointless. Perhaps, on other platforms, it holds some value, though I'm still doubtful. Regardless, you'll still need resiliency to incorrect TT data due to the possibility of zobrist collisions. Therefore, the best solution is to just insure your engine doesn't crash even when faced with a TT full of junk. I would recommend experimenting the XOR trick only after you have such an implementation.

[amanjpro]

Read a few older posts, and that is what I will do:

- Xor to make sure that the data read is not corrupt
- Test the hell out of SMP on my machine and merge it

Another PR (follows immediately):
- Test pseudo-legality for hash moves (as well as killers)
- Use killers before generating quiet moves (if possible)

Thanks everyone for your contribution in the subject, it really means a lot to me!

I've found the XOR "trick" to be useless. On x86, you have certain aligned write atomicity guarantees which just make it pointless. Perhaps, on other platforms, it holds some value, though I'm still doubtful. Regardless, you'll still need resiliency to incorrect TT data due to the possibility of zobrist collisions. Therefore, the best solution is to just insure your engine doesn't crash even when faced with a TT full of junk. I would recommend experimenting the XOR trick only after you have such an implementation.

The XOR trick, only improves the chance that the key (checksum) belongs to the data... which agreed, won't protect the engine from crashing, but protects it from reading bad data... so yeah, I agree with you, move pseudo-legality (or make-move protection really) is a must, but the XOR is only a cheap bonus, that I don't think it is going to hurt, but can only add value...

The atomicity guarantee, only guarantees that each single word is written atomically, not that the key and the data together are written atomically