10 ms·

The problem is that tree searching is largely serial, in the sense of, you don't know the next position you want to search until you finish searching the previo

by mot524 7y ago

The problem is that tree searching is largely serial, in the sense of, you don't know the next position you want to search until you finish searching the previous position. So you can't just send a million positions to a GPU to evaluate in parallel because you have no idea which positions you'll want to evaluate. So GPUs are pretty worthless for computer chess unless your algorithm evaluates positions with a deep CNN (which do run well on GPUs). It's not a question of how much time people have spent to investigate running chess algorithms on GPUs, it's a question of what kind of algorithms are better suited to CPUs vs. GPUs.

dragontamer 7y ago
Young Brothers Wait Concept: https://www.chessprogramming.org/Young_Brothers_Wait_Concept https://www.chessprogramming.org/Young_Brothers_Wait_Concept Parallel searching is possible, but it just hasn't really been done on GPU hardware. Stockfish itself parallelizes to multiple cores (although its only really designed for less than 20 from my understanding). ------- > The problem is that tree searching is largely serial, in the sense of, you don't know the next position you want to search until you finish searching the previous position. That's not the issue. Searching the game tree in parallel is stupid easy. But this creates a lot of waste. The chess minimax algorithm with alpha-beta pruning requires you to serially process nodes to know which nodes to "skip". There in lies the issue: of the three types of nodes (PV, CUT, and ALL nodes), CUT nodes have a best-case of two evaluations per CUT-node. While PV and ALL nodes have to have all of their children evaluated. Roughly 1/2 of all nodes are "cut" nodes however, which means in the best case, you can double the search depth with the alpha-beta pruning algorithm. As far as I can tell, the Young Brothers Wait Concept extends the minimax alpha-beta pruning algorithm to multiple cores, but it isn't as efficient as a fully serial processor. Still, that's probably where I'd start if I were to seriously try to put this on a GPU. ------- No matter how you look at it: a game tree grows exponentially. It only makes sense that exponentially growing trees would allow exponentially more work to be processed in parallel.
- 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.

by mot524 7y ago

dragontamer 7y ago

Young Brothers Wait Concept: https://www.chessprogramming.org/Young_Brothers_Wait_Concept https://www.chessprogramming.org/Young_Brothers_Wait_Concept Parallel searching is possible, but it just hasn't really been done on GPU hardware. Stockfish itself parallelizes to multiple cores (although its only really designed for less than 20 from my understanding). ------- > The problem is that tree searching is largely serial, in the sense of, you don't know the next position you want to search until you finish searching the previous position. That's not the issue. Searching the game tree in parallel is stupid easy. But this creates a lot of waste. The chess minimax algorithm with alpha-beta pruning requires you to serially process nodes to know which nodes to "skip". There in lies the issue: of the three types of nodes (PV, CUT, and ALL nodes), CUT nodes have a best-case of two evaluations per CUT-node. While PV and ALL nodes have to have all of their children evaluated. Roughly 1/2 of all nodes are "cut" nodes however, which means in the best case, you can double the search depth with the alpha-beta pruning algorithm. As far as I can tell, the Young Brothers Wait Concept extends the minimax alpha-beta pruning algorithm to multiple cores, but it isn't as efficient as a fully serial processor. Still, that's probably where I'd start if I were to seriously try to put this on a GPU. ------- No matter how you look at it: a game tree grows exponentially. It only makes sense that exponentially growing trees would allow exponentially more work to be processed in parallel.

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.