5 ms·

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 s

by 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.
- mot524 7y ago
  I know exactly how much divergence there is because I'm the author of a chess engine and I've spent weeks/months looking at traces of my engine's tree searches. I think what you're not getting is what a chess engine search tree looks like. You're thinking it has nice layers of nodes, but really, most of the time, the engine is in the quiescence search, searching sequences of captures. The branching factor is extremely low and each branch terminates at an unpredictable depth. Instead of nice layers of nodes, imagine a lightning bolt that's constantly changing. You can't predict what you're going to have to do next. GPUs would excel if you have to do the same thing to different boards all at the same time. But that's never what happens. Imagine you're in the q-search and you're at a node with two captures. Might as well search both at the same time? Okay, a GPU can make two moves at the same time and evaluate the resulting positions simultaneously no problem. Maybe one evaluation causes the branch to terminate and then that thread needs to undo the move, whereas the other branch needs to keep going and generate and search subsequent moves. This sort of divergence is the norm, not the exception, and it's impossible to handle in any sort of efficient way with a GPU. It's great that people have made GPU software to visit all possible positions to depth N, and it's great that somebody is making a MCTS engine run on a GPU. Both are tricky to do, and significant accomplishments if they work correctly. But in terms of making an effective engine these are just the absolute first initial baby steps and they don't signify anything about the viability of the rest of the project.
  - dragontamer 7y ago
    I appreciate the discussion. > most of the time, the engine is in the quiescence search That seems to be the best case for GPUs. Whenever a GPU SIMD thread finishes a quiescence search, just grab another position that is under quiescence search. Frankly, the quiescence search part seems most ideally suited to GPUs out of all, as long as it is appropriate batched. > Imagine you're in the q-search and you're at a node with two captures. Might as well search both at the same time. Put them onto the q-search queue, which will be checked as GPU threads go idle. The q-search problem is exactly identical to raytracers. GPUs don't know if a ray will bounce zero, once, or even 10 times. But that doesn't cause divergence because it's just about sticking rays onto a queue and evaluating them Rays in raytracers can even spawn multiple rays in a bounce, such as subsurface scattering. This pattern is solved!

by mot524 7y ago

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.

mot524 7y ago
I know exactly how much divergence there is because I'm the author of a chess engine and I've spent weeks/months looking at traces of my engine's tree searches. I think what you're not getting is what a chess engine search tree looks like. You're thinking it has nice layers of nodes, but really, most of the time, the engine is in the quiescence search, searching sequences of captures. The branching factor is extremely low and each branch terminates at an unpredictable depth. Instead of nice layers of nodes, imagine a lightning bolt that's constantly changing. You can't predict what you're going to have to do next. GPUs would excel if you have to do the same thing to different boards all at the same time. But that's never what happens. Imagine you're in the q-search and you're at a node with two captures. Might as well search both at the same time? Okay, a GPU can make two moves at the same time and evaluate the resulting positions simultaneously no problem. Maybe one evaluation causes the branch to terminate and then that thread needs to undo the move, whereas the other branch needs to keep going and generate and search subsequent moves. This sort of divergence is the norm, not the exception, and it's impossible to handle in any sort of efficient way with a GPU. It's great that people have made GPU software to visit all possible positions to depth N, and it's great that somebody is making a MCTS engine run on a GPU. Both are tricky to do, and significant accomplishments if they work correctly. But in terms of making an effective engine these are just the absolute first initial baby steps and they don't signify anything about the viability of the rest of the project.
- dragontamer 7y ago
  I appreciate the discussion. > most of the time, the engine is in the quiescence search That seems to be the best case for GPUs. Whenever a GPU SIMD thread finishes a quiescence search, just grab another position that is under quiescence search. Frankly, the quiescence search part seems most ideally suited to GPUs out of all, as long as it is appropriate batched. > Imagine you're in the q-search and you're at a node with two captures. Might as well search both at the same time. Put them onto the q-search queue, which will be checked as GPU threads go idle. The q-search problem is exactly identical to raytracers. GPUs don't know if a ray will bounce zero, once, or even 10 times. But that doesn't cause divergence because it's just about sticking rays onto a queue and evaluating them Rays in raytracers can even spawn multiple rays in a bounce, such as subsurface scattering. This pattern is solved!