> I think you misunderstand how "processing a node" works. It's a recursive algorithm. Even if you correctly identify an ALL node (which is not always easy) and say "hey process all these moves at the same time" then each move will result in a radically divergent search path that a GPU won't be able to handle.

I don't think there's as much divergence as you think there is. Someone down-thread already created a chess move-generator and evaluator: https://news.ycombinator.com/item?id=20035835

Its not the "chess" part that results in divergent thread execution, its maybe the "search part", at least with current algorithms.

Pawn, king, and knight movements won't have any thread divergence: these are pure bitboard manipulations without if-statements. Only sliding piece attacks (Bishop, queen, rook) seem complicated enough to cause divergence... but its mostly about iteration. One bitboard with 6 "bishops" (2x white bishop, 2x black bishop, 1x white queen, 1x black queen) will run diagonal sliding piece move generation 6x. But a bitboard with only 3 "bishops" will only run it 3 times. But I don't expect this kind of thread divergence to cause major issues, and most boards in a SIMD thread probably will have similar numbers of pieces.

> You're likely looking at simplified diagrams of a search tree and seeing a circle that has lines that connect it to a layer of more circles and thinking "hey just do all those circles in parallel" but the way chess engines work is 100% different from that.

Yes, that was my initial idea. But... the more I look into it, the more it seems possible. I'm just a little bit beyond that point, although its all just theory in my mind.

----------

Lets look at this implementation of alpha-beta: https://www.chessprogramming.org/Alpha-Beta#Negamax_Framewor...

Lets change it to the following:

int alphaBeta( future<int> alpha, future<int> beta, int depthleft ) {
if( depthleft == 0 ) return quiesce( alpha, beta );
for ( all moves) {
score = Spawn(-alphaBeta( -beta, -alpha, depthleft - 1 )); // <--- Issue #1
if( score >= beta ) // <---- Issue #2
return beta; // fail hard beta-cutoff
if( score > alpha ) // <---- Issue #3
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}

Issue #0: Futures/Promises -- No one has implemented futures / promises on GPGPUs yet. How can this be done efficiently on the GPU? Can the SIMD architecture be leveraged? Atomics could work, but they probably won't scale... I think something "innate" to the GPGPU architecture has to be done.

Issue #1: "Spawning" threads is pretty simple (but unconventional), even on a GPGPU. Create tasks that can be load-balanced on the SIMD GPU through the use of SIMD-Stacks and SIMD-queues to load-balance. Basically the same thing that GPGPU raytracing engines do (rays don't always "bounce", most rays miss all targets. Figuring out which rays hit a target and need to bounce... vs rays that miss and need to be terminated... is a solved problem for GPGPU programmers. Its basically task spawning). "Negation" (the -alpha, and -beta) shows that the future<int> needs to support negation, so that we don't block on that line. This line should execute in parallel.

Issue #2: score >= beta is a "hard synchronization" point, the only point where future::wait() needs to be called. However, most checks will be against a beta of -infinity (PV and ALL nodes would have a -infinity value). So this step could be skipped in a huge number of cases. In all other cases, a "blocked" thread will have to wait for its tree of future<ints> "score" value to be all finished executing.

Issue #3: This is effectively score = max(alpha, score). Across multiple iterations, this is max(alpha, score0, score1, score2, score3), etc. etc. Alpha starts as negative infinity: meaning a large number of nodes will always spawn.

The PV-nodes, CUT nodes, and ALL nodes don't need to be analyzed. You can see that this "task-based" definition spawns parallel-threads on PV-nodes and ALL nodes, while blocking on CUT nodes. This clearly becomes a (parallel SIMD) depth-first search.

---------

Of these issues, #0 (creating a future / promise) on the GPGPU is probably the hardest issue to solve. It is clear to me that this "future" needs symbolic execution (able to handle max(future, future), as well as negation -future). A difficult programming challenge, but not really insurmountable. It should be noted that if depth-first search is prioritized (if we can somehow guarantee that all "searchers" are on the left-most edge of all nodes), futures will take up a constant space roughly proportional to O(depth + size-of-parallel-cluster). (well, it seems clear to me anyway...)

The overall GPGPU task scheduling algorithm has been done in GPGPU Raytracers, even if people don't really realize it yet. http://www.cse.chalmers.se/~uffe/streamcompaction.pdf

GPGPU Raytracers have their rays either hit a target, or miss a target. If they hit a target, they spawn a new ray (!!), if they miss, then they die. Those silly GPGPU Raytracer programmers have solved a very, very difficult issue but haven't been telling everyone about it. Lol. This clearly can serve as the basis of a task-scheudling / load-balancing core on GPGPUs.

-------

EDIT: Don't get me wrong. I recognize that I'm basically proposing that a GPU recursive task scheduler / mini-SIMD operating system with futures needs to be built to accomplish the job. Yeah, that seems difficult, but it doesn't seem impossible to me.