Daniel Shawul wrote: ↑Sun Oct 09, 2022 5:47 pm
Scorpio mcts is lockless. I use atomic operations and try_lock in places where you usually need locks.
[...]
I implemented locks with "atom_cmpxchg" on integers with thread id+1 and pre-zeroed values, not sure if we talk about the same thing here, so you can set and check the lock with one atomic memory operation.
Yes, atomic exchange is what i use for spinlocks too. But for a lockfree implementation, all threads should not waste time waiting on a lock so try_lock() is the most you can do. Atomic adds/subtracts are also used throught to update variables without a lock.
Note that MCTS is very resistant to a bit of randomization; a deterministic algortithm would try to equalize the urgency of treatment of all moves by reducing the urgency of the most urgent. So it would not be very critical which of the moves you follow to a leaf. Just perturb the urgency by a small random number, different for each thread, and you will keep the urgency equal to within the range of the random.
