4

I was hoping to parallelize the chess engine I was currently working on. I have done some research on some of the various types of algorithms such as YBWC, ABDADA, and LazySMP which is currently used in stockfish. I was hoping to implement LazySMP into my engine and I have since taken a look at some sites such as https://www.chessprogramming.org/Lazy_SMP as well as https://www.duo.uio.no/bitstream/handle/10852/53769/1/master.pdf. As of now I am unsure of my understanding which is the following...

Each iteration, during iterative deepening, you initialize N threads to search from the root to the same depth for that iteration. During their search, they use the same transposition table and it is a race to see which of those threads are the "first to complete". Each thread mantain's its own AB values, PV, heuristics, etc...

I want to know if this is correct. If it is correct, I am also curious in knowing how/why it improves search speed. It seems like a lot of redundant searching of nodes.

Improve this question
6
  • Your text above seems to contradict what it says in your first link where it says "Multiple processes or threads search the same root position, but are launched with different depths, and/or varying move ordering at the root node" (emphasis mine). Now I know nothing about chess programming (but do know a lot about parallel programming for scientific computing) so I could be wrong, but it seems you are just using lots of threads with different initial conditions, and hoping that is enough to improve significantly the search of the space.
    – Ian Bush
    Commented Jun 6, 2021 at 16:17
  • Each thread can have a completely independent iterative deepening loop.
    – Sopel
    Commented Jun 7, 2021 at 22:32
  • 1
    @IanBush I'm not an expert on LazySMP, but chess engines have a transposition table, which is basically a giant lookup table that stores information about a position that can be reused if the position is encountered again. The tt is what causes the speedup, since if a thread searches a position and another thread encounters that position, it can reuse information in the transposition table and avoid a complete research of the position.
    – AspectOfTheNoob
    Commented Aug 20, 2023 at 19:59
  • @AspectOfTheNoob Might cause a speed up. Your threads are no longer independent, and it may be that the overhead due to thread synchronization is significant. I'm well aware of tts but it's not my coding area, so I can't say more.
    – Ian Bush
    Commented Aug 20, 2023 at 20:39
  • @IanBush AFAIK, most strong engines don't synchronize access to the transposition table. Robert Hyatt, the creator of Crafty, has already shown that hash collisions don't affect the search significantly until the conditions are far outside the realm of practical limits. craftychess.com/hyatt/collisions.html. Because race conditions in thread access to a large hash table are also extremely rare, engines like Stockfish and Ethereal accept the low but not impossible chances of a race condition in order to increase the search speed. chess.stackexchange.com/a/35131/34660
    – AspectOfTheNoob
    Commented Aug 22, 2023 at 14:52

1 Answer 1

Reset to default
2

Yes, it's true... :)

There can be a lot of redundant search, but Lazy SMP works. Currently, it is a mystery why, but it has been verified with any engines that the simple, basic implementation works, regardless of how counter-intuitive this seems...

To clarify a little bit, you don't need to setup different initial conditions (like different depth, etc.); what makes threads de-synchronize is a history table used for move ordering.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.