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 exploringJakob Progsch wrote: ↑Tue Aug 10, 2021 3:02 pm 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.
Lazy SMP and shared hash table
Moderators: hgm, Rebel, chrisw
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Lazy SMP and shared hash table
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Lazy SMP and shared hash table
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
As that excludes all Android and my own Raspberry Pi from benefiting from multithreading
-
- Posts: 1754
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Re: Lazy SMP and shared hash table
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.
#WeAreAllDraude #JusticeForDraude #RememberDraude #LeptirBigUltra
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
-
- Posts: 160
- Joined: Tue Jan 23, 2018 10:18 am
- Location: Rotterdam
- Full name: Ronald Friederich
Re: Lazy SMP and shared hash table
There was a topic on the same subject half a year ago:
http://talkchess.com/forum3/viewtopic.p ... 34#p881317
http://talkchess.com/forum3/viewtopic.p ... 34#p881317
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Lazy SMP and shared hash table
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.AndrewGrant wrote: ↑Tue Aug 10, 2021 5:12 pmI 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.
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 trickRonald wrote: ↑Tue Aug 10, 2021 5:36 pm There was a topic on the same subject half a year ago:
http://talkchess.com/forum3/viewtopic.p ... 34#p881317
-
- Posts: 1754
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Re: Lazy SMP and shared hash table
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 wrote: ↑Tue Aug 10, 2021 6:29 pm 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.
#WeAreAllDraude #JusticeForDraude #RememberDraude #LeptirBigUltra
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Lazy SMP and shared hash table
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.AndrewGrant wrote: ↑Tue Aug 10, 2021 6:37 pmIf 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 wrote: ↑Tue Aug 10, 2021 6:29 pm 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.
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
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Lazy SMP and shared hash table
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!
- 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!
-
- Posts: 530
- Joined: Sun Sep 06, 2020 4:40 am
- Full name: Connor McMonigle
Re: Lazy SMP and shared hash table
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 wrote: ↑Tue Aug 10, 2021 11:26 pm 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!
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Lazy SMP and shared hash table
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...connor_mcmonigle wrote: ↑Tue Aug 10, 2021 11:47 pmI'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 wrote: ↑Tue Aug 10, 2021 11:26 pm 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!
The atomicity guarantee, only guarantees that each single word is written atomically, not that the key and the data together are written atomically