Home
Chess
Parallel Search
Cutoff Checks
How To
Simplified AB...
Stobor
TSCP
Misc
 Parallel Search

The alpha-beta search algorithm is inherently serial. Techniques to make it parallel are usually 1) difficult to imlpement and fast, or 2) easy to implement and slow.

I've developed a method that's very easy to implement and results in very competitive speedups. The method is described in this How-To guide.

Here are the average speedups I've measured with my own chess engine:

1 core 2 4 8 16 32
ECM 9, time-to-solution 1.00 1.60 2.93 5.41 8.73 13.15
ECM 9, time-to-ply 1.00 1.73 3.22 6.02 9.96 15.39
Hyatt 24, time-to-ply 1.00 1.92 3.59 6.44 10.88 16.75
Hyatt 24, DTS
(for comparison) 		1.0 2.0 3.7 6.6 11.1 N/A

Some explanation:

"ECM 9" is a set of 9 positions from the Encyclopedia of Chess Middlegames that my engine takes a long time to solve (between 1 and 2 minutes).

"Hyatt 24" is a sequence of 24 positions that Robert Hyatt used to measure the parallel speedup of his DTS algorithm. The positions were taken from an actual game, so they have better move ordering than chess problems, and thus benefit more from parallel search. That's why their speedup numbers are higher.

Dynamic Tree Splitting (DTS) is the gold standard in terms of parallel alpha-beta search speedup. These DTS speedup numbers are from the DTS paper, so they're for a different engine running on different hardware searching the positions to different depths. So it's not clear how comparable they are to my speedup numbers. That being said, there's reason to believe that the performance of my method is close to state-of-the-art.