Answers.Body: <p>Yes, it's true... :)</p>
  <p>There can be <em>a lot</em> of redundant search, but Lazy SMP works. Currently, it is a mystery why, but it has been verified with <em>any</em> engines that the simple, basic implementation works, regardless of how counter-intuitive this seems...</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-21T17:23:51.440Z
Answers.LastActivityDate: 2021-10-21T19:07:51.360Z
Answers.LastEditDate: 2021-10-21T19:07:51.360Z
Answers.UserDisplayName: Hrvoje Horvatic
Body: <p>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 <a href="https://www.chessprogramming.org/Lazy_SMP" rel="nofollow noreferrer">https://www.chessprogramming.org/Lazy_SMP</a> as well as <a href="https://www.duo.uio.no/bitstream/handle/10852/53769/1/master.pdf" rel="nofollow noreferrer">https://www.duo.uio.no/bitstream/handle/10852/53769/1/master.pdf</a>. As of now I am unsure of my understanding which is the following...</p>
  <blockquote>
  <p>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 &quot;first to complete&quot;. Each thread mantain's its own AB values, PV, heuristics, etc...</p>
  </blockquote>
  <p><strong>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.</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-06T16:17:47.090Z
Comments.Text: 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.
Comments.UserDisplayName: Ian Bush
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-06-07T22:32:44.900Z
Comments.Text: Each thread can have a completely independent iterative deepening loop.
Comments.UserDisplayName: Sopel
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-20T19:59:13.790Z
Comments.Text: @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.
Comments.UserDisplayName: AspectOfTheNoob
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-20T20:39:03.303Z
Comments.Text: @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.
Comments.UserDisplayName: Ian Bush
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-22T14:52:13.587Z
Comments.Text: @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. https://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. https://chess.stackexchange.com/a/35131/34660
Comments.UserDisplayName: AspectOfTheNoob
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-22T15:00:38.273Z
Comments.Text: @AspectOfTheNoob  "low but not impossible chances of a race condition". As I said not my area of programming. For me in my work such a possibility is totally unacceptable.
Comments.UserDisplayName: Ian Bush
Tags: <engines><software><programming><chess-algorithms>
Title: Chess Engine Using LazySMP
ThreadText: # Chess Engine Using LazySMP
  
  (Asked by: username_0 on 2021-06-05)
  
  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.**
  
  **Tags:** engines, software, programming, chess-algorithms
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_2**: Each thread can have a completely independent iterative deepening loop.  
  > **username_3**: @username_1 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.  
  > **username_1**: @username_3 *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.  
  > **username_3**: @username_1 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. https://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. https://chess.stackexchange.com/a/35131/34660  
  > **username_1**: @username_3  "low but not impossible chances of a race condition". As I said not my area of programming. For me in my work such a possibility is totally unacceptable.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_4 on 2021-10-21. Score: 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.
  
  
  ---
  
  