I am trying to implement LazySMP into Zahak, and it is going very well... I have some elo gain and things seem to be working, that is how I guarantee atomicity when updating the hashtable:
- find hash entry at index i
- use compare-and-swap to flip a bit in the entry from 0 to 1
- read or update the entry
- atomically flip the bit from 1 to 0, to unlock it for other readers
Since, I essentially had to grow the size of the entry by int32 (that is the smallest size that I can use it in compare-and-swap in golang), I decided to only store 32-bit of the hash in the entry. This proves to be good except Zahak plays an illegal move every 1600 games or so (I do not validate the legality of hash moves).
That encouraged me to search other engines, and see how they implement atomicity in their engines, and they DO NOT! I saw some top engiens like Weiss for example even plays hash moves without checking their legality first! Stockfish even admits that neither probing, nor storing are atomic! Not sure how this works, can somone enlighten me
Lazy SMP and shared hash table
Moderators: hgm, Rebel, chrisw
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
-
- Posts: 2709
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: Lazy SMP and shared hash table
Not sure if this is what you mean, TT lockless:
https://www.chessprogramming.org/Shared ... #Lock-less
I use the xor trick for lockless TT, my tt move is picked from a prev generated move list, dunno how other engines check tt move, maybe to just check if the move is valid (piece/sq from/to) but not legal is already enough.
--
Srdja
https://www.chessprogramming.org/Shared ... #Lock-less
I use the xor trick for lockless TT, my tt move is picked from a prev generated move list, dunno how other engines check tt move, maybe to just check if the move is valid (piece/sq from/to) but not legal is already enough.
--
Srdja
-
- Posts: 347
- Joined: Tue Nov 19, 2019 4:34 am
- Location: https://github.com/TerjeKir/weiss
- Full name: Terje Kirstihagen
Re: Lazy SMP and shared hash table
Weiss doesn't check move legality before playing it? When did it stop?
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Lazy SMP and shared hash table
Not move legality, but pseudo legality.... For killers you make sure the move is pseudo legal, for hash moves you don't ... Or probably I read it wrong?
-
- Posts: 347
- Joined: Tue Nov 19, 2019 4:34 am
- Location: https://github.com/TerjeKir/weiss
- Full name: Terje Kirstihagen
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
Can you point me to where you do the check, I completely fail to find it:
https://github.com/TerjeKir/weiss/searc ... egal&type=
What is more amazing, you read the entry here:
https://github.com/TerjeKir/weiss/blob/ ... rch.c#L179
Then use it here:
https://github.com/TerjeKir/weiss/blob/ ... rch.c#L181
The issue is that, your probe function returns the reference of the entry, not a copy of it. That means in the meantime another thread could have easily written a different value there, unless I'm missing something obvious. Can you elaborate a bit?
I'm sure whatever you do works, as your engine is way stronger than mine, it is just that I do not understand
Last edited by amanjpro on Tue Aug 10, 2021 2:02 pm, edited 1 time in total.
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Lazy SMP and shared hash table
I haven't tried this, but found the crafty source and Bob's article about it. Will read it.smatovic wrote: ↑Tue Aug 10, 2021 8:38 am Not sure if this is what you mean, TT lockless:
https://www.chessprogramming.org/Shared ... #Lock-less
I use the xor trick for lockless TT, my tt move is picked from a prev generated move list, dunno how other engines check tt move, maybe to just check if the move is valid (piece/sq from/to) but not legal is already enough.
--
Srdja
My data is more than 64 bytes, but I can probably fix that
-
- Posts: 40
- Joined: Fri Apr 16, 2021 4:44 pm
- Full name: Jakob Progsch
Re: Lazy SMP and shared hash table
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.
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.
-
- Posts: 1788
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Re: Lazy SMP and shared hash table
https://github.com/TerjeKir/weiss/blob/ ... ker.c#L151amanjpro wrote: ↑Tue Aug 10, 2021 1:51 pmCan you point me to where you do the check, I completely fail to find it:
https://github.com/TerjeKir/weiss/searc ... egal&type=
What is more amazing, you read the entry here:
https://github.com/TerjeKir/weiss/blob/ ... rch.c#L179
Then use it here:
https://github.com/TerjeKir/weiss/blob/ ... rch.c#L181
The issue is that, your probe function returns the reference of the entry, not a copy of it. That means in the meantime another thread could have easily written a different value there, unless I'm missing something obvious. Can you elaborate a bit?
I'm sure whatever you do works, as your engine is way stronger than mine, it is just that I do not understand
#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
Oh! I totally missed that. Thank youAndrewGrant wrote: ↑Tue Aug 10, 2021 3:23 pmhttps://github.com/TerjeKir/weiss/blob/ ... ker.c#L151amanjpro wrote: ↑Tue Aug 10, 2021 1:51 pmCan you point me to where you do the check, I completely fail to find it:
https://github.com/TerjeKir/weiss/searc ... egal&type=
What is more amazing, you read the entry here:
https://github.com/TerjeKir/weiss/blob/ ... rch.c#L179
Then use it here:
https://github.com/TerjeKir/weiss/blob/ ... rch.c#L181
The issue is that, your probe function returns the reference of the entry, not a copy of it. That means in the meantime another thread could have easily written a different value there, unless I'm missing something obvious. Can you elaborate a bit?
I'm sure whatever you do works, as your engine is way stronger than mine, it is just that I do not understand
I'll give Bob's approach a try, if it wasn't good then I'll give this a try, and see
Bob's approach is I believe the safest non-atomic/non-locking solution, as you will almost never have corrupt data. The way Weiss is doing, is slightly riskier, as you can have score+move mismatch, and possibly play bad moves, but that is not as sever as playing illegal move