Answers.Body: <p>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.</p>
  <p>TL;DR: Alpha-beta requires a lot of enhancements to work well, and these enhancements do not work well with parallelization.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-30T02:01:17.397Z
Answers.LastActivityDate: 2022-11-30T02:01:17.397Z
Answers.UserDisplayName: AAce3
Body: <p>I have seen it suggested in various places (e.g., on Stack Overflow <a href="https://stackoverflow.com/a/48976594/11800120">posts</a>) that alpha-beta pruning cannot be &quot;naively&quot; parallelized. To me, an intuitive parallelization of alpha-beta with <code>n</code> 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 <code>n &gt;= 3</code> 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).</p>
  <p>I understand that we will not be able to prune <em>as many</em> 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.</p>
  <p>Even if the number of children of the root is greater than <code>n</code>, the number of processors, why not just run alpha-beta on the leftmost <code>n</code> subtrees and then use the results to define alpha and beta for  the next <code>n</code> subtrees until you have processed the whole tree?</p>
  <p>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.</p>
  <p><a href="https://i.sstatic.net/kZoYO.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kZoYO.png" alt="enter image description here" /></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-16T18:25:50.293Z
Comments.Text: @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?
Comments.UserDisplayName: zack-overflow
Tags: <engines>
Title: Understanding why alpha-beta cannot be naively parallelized
ThreadText: # Understanding why alpha-beta cannot be naively parallelized
  
  (Asked by: username_0 on 2022-11-15)
  
  I have seen it suggested in various places (e.g., on Stack Overflow [posts](https://stackoverflow.com/a/48976594/11800120)) 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](https://i.sstatic.net/kZoYO.png)](https://i.sstatic.net/kZoYO.png)
  
  **Tags:** engines
  
  > **Comments:**
  > **username_0**: @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?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-11-30. Score: 6 | Accepted answer
  
  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.
  
  
  ---
  
  