3

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.

2
  • 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
    Jun 6, 2021 at 16:17
  • Each thread can have a completely independent iterative deepening loop.
    – Sopel
    Jun 7, 2021 at 22:32

1 Answer 1

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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