5 ms·

Yes, parallel search is possible, but inefficient. Searching with e.g. 32 cores already cuts efficiency in half, in most useful scenarios (i.e., where the best

by mot524 7y ago

Yes, parallel search is possible, but inefficient. Searching with e.g. 32 cores already cuts efficiency in half, in most useful scenarios (i.e., where the best move changes), and it gets worse from there. But regardless, it seems you have a fundamental misunderstanding of how GPUs work vs. CPUs. GPUs "cores" are designed to run the same instructions on huge amounts of data simultaneously. So they're great for e.g. Photoshop filters where you have to do the same operations to each pixel of an image, or neural networks where you have to do the same operations on each value of a matrix. 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. There's a reason why CPUs and GPUs are different products, and Intel can charge $1500 for a CPU with 16 cores whereas you can get an Nvidia graphics card with 768 cores for $150. It's because these cores don't do the same things. You're right that game trees grow exponentially and that's actually the reason why GPUs are worthless. You can get a GPU to execute every possible sequence of chess moves from a given position--people have done that, and it's phenomenally fast. But that has a branching factor of ~35, meaning that for a search of depth 8, you have to visit 35^8 positions = 2251 trillion. 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...

dragontamer 7y ago
> 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.
- mot524 7y ago
  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. Basically nothing in a parallel chess engine happens in lockstep. All the threads are always doing completely different things. One thread may be evaluating a position. One thread may be making a move. One thread may be taking back a move. One thread may be generating all pseudolegal moves. One thread may be generating captures. No thread is ever doing the same thing as another thread so there's no parallelism of the sort that can be exploited by a GPU. 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. You're not the first person to have the idea to do alpha-beta search with a GPU. There have been many efforts, and several for chess specifically. They've all been kind of awkward and horrible and it's debatable whether or not you can even really call them alpha-beta. There are hundreds of people who make chess engines and it's not like they're all incompetent and never thought of using the GPU.
  - dragontamer 7y ago
    > 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 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_Framework 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 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.

by mot524 7y ago

dragontamer 7y ago

> 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.

mot524 7y ago
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. Basically nothing in a parallel chess engine happens in lockstep. All the threads are always doing completely different things. One thread may be evaluating a position. One thread may be making a move. One thread may be taking back a move. One thread may be generating all pseudolegal moves. One thread may be generating captures. No thread is ever doing the same thing as another thread so there's no parallelism of the sort that can be exploited by a GPU. 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. You're not the first person to have the idea to do alpha-beta search with a GPU. There have been many efforts, and several for chess specifically. They've all been kind of awkward and horrible and it's debatable whether or not you can even really call them alpha-beta. There are hundreds of people who make chess engines and it's not like they're all incompetent and never thought of using the GPU.
- dragontamer 7y ago
  > 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 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_Framework 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 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.