Alternate Implementation of Parallel Search Strategy

[sfleischman105]

Currently, all the parallel algorithms implement Principal Variation Splitting (See section on ChessProgramming Wiki) to utilize mutli-core processing. PVS works by searching a set amount of moves sequentially to find an alpha cut-off, and then the remaining nodes are searched in parallel with that alpha cutoff. Can this be done better?

[sfleischman105]

Parallel Search Strategies

Here I'm going to outline the Pros and Cons of various Parallel Search Strategies.

1) Young Brothers Wait Concept (YBWC) / Jamboree

Link HERE and HERE for further information.

Pros

• Easily implemented with Fork-Join parallelism. Specifically, the Rayon crate makes this an absolute breeze to implement.
• ThreadPool which guarantees all threads are utilized.

Cons

• Harder to share global state between threads. The biggest downside associated with this is the difficulties in using a Transposition Table easily.
• Local Thread storage is nearly impossible. Examples where this impediments searching is in utilizing tools like Butterfly Tables && Killer Moves, detecting repetitions, etc... Forces reliance on global state, which could easily create cache misse and synchronization errors.

2) Lazy SMP

Link HERE for further information.

Pros

• Threads run independently of each other, with the exception of communication via Transposition Table. This allows for straightforward searching, as each thread simply worries about its own work.
• Local Stack variables can easily be used when searching.

Cons

• Harder to Synchronize work done between threads.
• Must utilize a [CondVar] or otherwise synchronizing structure to start and stop all threads at once.

[AnshulMalik]

Aren't there any other strategies?

[sfleischman105]

@AnshulMalik Yes, quite a few actually!

The two examples listed above are actually referring to broader, over-arching parallel search implementations rather than specific algorithms. Both the YBWC and Lazy SMP have multiple possible implementation strategies for each.

The main difference between the two (to my knowledge!) is that in a YBWC-like algorithm, threads divide and conquer the possible moves in a list of moves, while in a Lazy SMP implementation the main source of communication / work sharing between threads is through a shared Transposition Table.

These are the two most "popular" strategies for parallel searching, due to decent scalability when the thread count is increased. Obviously some other implementations exist, such as Dynamic Tree Splitting, which could be worth looking into.

There is a fair amount of information available at with ChessWiki page on Parallel Search Strategies.

[AnshulMalik]

Great! @sfleischman105. I'll be doing more research on them.

[sfleischman105]

As of #57, this library is split into pleco (core functionality) and pleco_engine (the uci searcher).

Currently, we are using the Lazy SMP approach, similar to stockfish. There is a non-negligible startup time for the searcher, but the multi-threading speedup far surpases anything before. Furthermore, we can write "sequential-esq" code with relative ease, allowing stuff like local variables and tables for each thread.