> What they can't do is have each core running its own sequence of branchy, serial code on its own data, which is what chess engines do.

You're correct on one front, but mistake in an important case. GPUs only have 32x SIMD (on NVidia) or 64x SIMD (on AMD). Which means we only have to figure out how to scale the algorithm to ~32x SIMD to solve the thread divergence issue.

Each 32x (NVidia) or 64x (AMD) workgroup can be branching and looping on its own without any slowdowns.

I think you're underestimating the flexibility of GPGPU branching. Actually, I think everybody is. Its not an issue of solving the GPU divergence issue in general, its about solving thread-divergence at size 32 (NVidia) or size 64 (AMD).

As long as a set of 32-threads (NVidia) or 64-threads (AMD) take the same branches, then your utilization will remain high.

> If you're doing a serial search with modern optimizations, the branching factor is closer to 5, which means you have to search ~390 thousand positions for a depth 8 search. So for this relatively shallow search, a serial algorithm is almost 6 million times more efficient than a hypothetical GPU algorithm. (And that discrepancy gets worse the deeper you search.) There isn't a GPU with 6 million times more cores than a CPU...

I agree that a parallel search will always be less efficient than a serial search. There are more tricks to process in serial than in parallel.

But the "big gain" would be a work-efficient parallel algorithm for alpha-beta pruning. To some degree, it seems possible. Think of all the parallelism that can be fit in.

1. PV Nodes (Knuth Type 1) can be searched in parallel without any slowdown. Alpha-beta pruning requires all PV Nodes to be searched, so right here there's a major source of parallelism.

2. CUT Nodes (Knuth Type 2) need to be done in serial. However, there are millions of cut-nodes generated across an alpha-beta search. In theory, a GPU can batch up all of these CUT Nodes, and process them in parallel without slowdowns.

3. ALL Nodes (Knuth type 3) are also processed in parallel.

So serious question: has it been proven that a GPU cannot process Alpha-beta pruning in parallel? Or is it just that people haven't done it yet?

Not all tricks can be parallelized. But from the perspective of minimax + alpha-beta pruning, it seems possible that an algorithm (probably a very complex one) can be used to process all of the Type 1 / Type 3 nodes in parallel, while batching Type 2 nodes together and processing (different) Type 2 nodes in parallel.

Thread divergence would be O(3), since there are only three cases. All three cases have the same bulk code: they generate the potential moves of the node... the only question is if they spawn a new worker (in the case of ALL Nodes / PV nodes), or if they wait for Alpha/Beta values (in the case of CUT nodes)

Granted, I don't know how to implement a "future" in GPGPU land. But the general concept is pretty easy to see the parallelism if you imagine Alpha-Beta values as C++ futures and/or promises.

-------------------

A hypothetical GPU algorithm would be to process PV Nodes and ALL Nodes somehow in parallel. CUT Nodes can be evaluated in parallel, but must wait for the results of previous nodes to know if they are pruned or not. Still, the first result of any CUT Node must be processed, which leads to potential work that can be processed in parallel.