4

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.

enter image description here

Improve this question
3
  • Have you got that right? As far as you describe, it can be naively parallelized. Consider the situation in your example where the scoring of B depends on a position that D also has and that proc. 3 has flagged as 'I'm working on this'. Proc 1 then waits for that result. Then Proc 3 discovers that it needs the score of a position that proc. 1 has flagged as 'I'm working on this'. What does it do? Waiting means a deadlock. Breaking the deadlock -- by some kind of progress counter -- means double evaluation, and probably getting caught up in further locks later down.
    – user30536
    Nov 16, 2022 at 10:43
  • @user30536 Why would any procs need to flag any work as "I am working on this" when they are evaluating a position? The approach I am describing accepts that some duplicated work will occur between the different threads, but is okay with that since we will be able to do the duplicate work simultaneously, so it will not slow down the total time to choose a good move for the position. There will be no deadlock since threads process each subtree independently and do not share results. Is that an unfair assumption to make?
    – zack-overflow
    Nov 16, 2022 at 18:25
  • Apologies -- I over-interpreted your use of 'parallelize alpha-beta'. To me, that means reformulating the alpha-beta algorithm to work, in parallel, fully recursively, and nothing else. To you, it does mean something else, and something sufficiently different that answers to the first problem are meaningless to your problem.
    – user30536
    Nov 16, 2022 at 20:18

1 Answer 1

Reset to default
7

I think you underestimate just how much pruning gets done in modern chess engine. They do not only use alpha-beta pruning alone - they prune nodes that seem unpromising using a variety of heuristics, to the point that the effective branching factor in chess engine search is around 2, that is, depth 15 takes twice as long as depth 14. In addition, all modern chess engines use the results of previous searches to get an idea of what the next search will look like. In fact, it is estimated that over 50% of the effort of the engine is spent on the first move alone, and 90% on the first three or four moves. Naively parallelizing alpha-beta could technically work and may even produce small strength gains, but it leads to evaluating significantly more nodes than single threaded.

TL;DR: Alpha-beta requires a lot of enhancements to work well, and these enhancements do not work well with parallelization.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.