I have seen it suggested in various places (e.g., on Stack Overflow posts) that alpha-beta pruning cannot be "naively" parallelized. To me, an intuitive parallelization of alpha-beta with n
threads would be to assign each a thread to process the subtree defined by each child of the root node of the search tree. For example, in the tree below, if we had n >= 3
threads, we would assign one to process the left subtree (with root b), one to process the middle (root c) and one to process the right subtree (root d).
I understand that we will not be able to prune as many nodes with this approach, since sometimes pruning occurs based on the alpha-beta value of a previously processed subtree. However, won't we have the wait for the left subtree to finish being processed anyway if we run alpha-beta sequentially? By the time the sequential version knew it could prune part of the c and d subtrees, the parallel version will already be done processing them, right? While running alpha-beta on each subtree, we can still get the benefits of pruning for that subtree.
Even if the number of children of the root is greater than n
, the number of processors, why not just run alpha-beta on the leftmost n
subtrees and then use the results to define alpha and beta for the next n
subtrees until you have processed the whole tree?
Perhaps this approach is so simple/trivial that no one discusses it, but I am confused why so many resources I have seen seem to suggest that parallelizing alpha-beta is extremely complicated or leads to worse performance.