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.