6 ms·

> I'm curious how to use the SIMD-compute model to evaluate chess positions, but it doesn't seem like very much research exists on the subject. I disagree very

> I'm curious how to use the SIMD-compute model to evaluate chess positions, but it doesn't seem like very much research exists on the subject. I disagree very strongly with this statement. Evaluation heuristics have been studied extensively, but the overwhelming consensus is that the simpler the heuristic, the better. If you make your heuristic worse, but fast enough to give you +1 on your search depth, you will almost always be better. So our evaluation heuristics are almost trivial because thirty years of research has demonstrated that the trivial heuristics are the best ones. SIMD doesn't help us for a few reasons. First, because bitboards are extremely sparse. You'll have at most 8 pawns in your pawn bitboards, 1 king in your king bitboards, and only under exceedingly rare circumstances will you have more than 2 pieces in your other 8 bitboards. Under no circumstances will you have more than 32 1s in your twelve bitboards, a density of one 1 per 24 zeroes. Second, you have a lot of loops with depths determined at runtime. You won't know how many squares your bishop can move until you're evaluating the position. SIMD isn't very good at that. > I really think MCTS is the superior search tree algorithm. The only issue is the evaluation function. The issue is move ordering. In minimax + alpha-beta pruning + PVS + hash table move cache, you don't need a near-perfect heuristic to tell you which order to evaluate moves. If there are 20 legal moves, it's fine if the best move is the 4th-8th move you search, although alpha-beta is faster if you search the best move first, which is why PVS+hash table is such a strong improvement. MCTS requires a good heuristic. If you have 20 legal moves, MCTS will evaluate maybe 2 of them, and if they're the 4-8th best moves, your AI will always be terrible, always. PVS+hash tables can't help you, because the only thing they can tell you was what move was good in the past. There isn't a good way to sit down and get a human to write a good heuristic. NNs are really good at it though. IMHO, if you want MCTS, you either need NNs or something like it. There's no way to jury-rig classical evaluation functions into it. (by "classical evaluation functions" I mean everything from Deep Blue to Stockfish) Replacing NNs in this context will likely mean replacing NNs in every other context. This would be a good thing, a great thing even, but it would require a new paradigm in the AI/ML world, not just something unique to chess. I actually agree with you about the elegance of MCTS and bitboards, and the inelegance of NNs and minimax. (and all of minimax's accompanying optimizations) But there's not really a good way forward.

dragontamer 7y ago
> SIMD doesn't help us for a few reasons. First, because bitboards are extremely sparse. You'll have at most 8 pawns in your pawn bitboards, 1 king in your king bitboards, and only under exceedingly rare circumstances will you have more than 2 pieces in your other 8 bitboards. Under no circumstances will you have more than 32 1s in your twelve bitboards, a density of one 1 per 24 zeroes. You're thinking too traditionalist :-) You're 100% correct in that the above is a "traditional" application of SIMD. However, I'm talking about a "non-traditional" SIMD approach. (or perhaps... "more traditional", closer to the original 1980s style SIMD that GPU programmers use in their pixel shaders) NVidia calls it SIMT, but the concept existed since the dawn of the SIMD methodology. I don't want to repeat what others have done. Give the first 2 pages of this paper a lookthrough for this "nontraditional" SIMD approach: http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1997/CS/CS0891.pdf http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1... My short summary is... the AMD Vega64 is effectively a 16384-wide SIMD unit. (or perhaps... 64 parallel CU clusters of 256-wide SIMD units). What you're suggesting (which won't work) is to use the 16384 SIMD units to evaluate one bitboard. Of course this won't work, even though its the "traditional" approach to SIMD. Even breaking things down "per CU" so that each compute-unit's 256x shaders is "too much parallelism" to work one bitboard. Instead, I suggest using the 16384 SIMD Units of Vega64 to evaluate 16384 different bitboards (!!). I'm very confident that Vega64's SIMD units are advanced enough to handle this kind of task... although the algorithmic details haven't really been figured out by anyone yet (well... that I'm aware of anyway). --------- Every SIMD Shader of Vega64 has 256 (!!) 32-bit registers which can be used once per clock. My estimate is that it takes 25-registers (12x 64-bit boards for the white+black occupancy, + 1x32 register for misc purposes like enpassant, castling, etc. etc.). That leaves 231 registers left over for other calculations. (Occupancy 1). With luck, maybe Occupancy 4 or higher could be reached (limit of only 64x registers used), which would make RAM access more efficient. The question I have is: how do you coordinate these 16,386 simultaneous threads of execution? How does this turn into an efficient tree search? > Evaluation heuristics have been studied extensively, but the overwhelming consensus is that the simpler the heuristic, the better. If you make your heuristic worse, but fast enough to give you +1 on your search depth, you will almost always be better. So our evaluation heuristics are almost trivial because thirty years of research has demonstrated that the trivial heuristics are the best ones. Exactly! Which is why I'm confident that these simple heuristics can be evaluated on each SIMD-shader of a modern GPU. 256x 32-bit registers leaves a LOT of room for these SIMD "shaders" to work with! There's a lot of unknowns that I'd have to work with if I were to code something up in OpenCL (or more likely, ROCm). But a lot of the fundamental research and heuristics have already been done. Just no one has even tried writing them for a GPU yet. The biggest issue is how to represent a search tree in a way that would be efficiently represented in a GPU. Neither MCTS nor Minimax have really been written in a GPU, although the concept of "iterative deepening", and other such simple searches HAVE been executed on a GPU-per shader basis. I haven't really thought how the full details would work. But Vega64 has 4096 shaders operating at 1.5 GHz. If each shader spent 1000-clock cycles per bit-board evaluation, we're looking at 6.1 Billion nodes per second on a single GPU. > hash table move cache That wouldn't scale unfortunately: there's no way for 16386 different SIMD threads to access one shared cache. Maybe a shared cache would be split up to the 64-individual compute-units of the Vega64, perhaps in the small 64kB "shared memory region" (which can be accessed within 32-clock ticks worst-case of Vega64... 1-clock tick in ideal situations). "Shared memory" can be shared with up to 1024 SIMD Threads. A 64kB hash table is extremely small however, giving you the idea of how little memory is available per SIMD-thread. The idea of a "globally shared hash table" will have to be sacrificed in porting the code to a GPU effectively. Or... at best... it would have to be shared on a per-1024 thread workgroup basis. There's no way 16386 threads banging on RAM (even a 512GBps RAM like HBM2) would scale. Heck, 1024-threads banging the 10,000GBps (aggregate) 64kB shared-memory region is probably still not going to scale very well... but that 64kB region is the only thing that is anywhere fast enough to do something like the traditional hash table move cache. This 64kB "shared memory" is the GPU's greatest weapon to scale for parallelism, but there's so many chess algorithms that want to use it. The Rook-move "Sliding Piece Attacks" table with "Magic Bitboards" takes up 64kB already. (16kB for Bishop moves). So figuring out which things will fit inside of that memory region is going to be a big problem for whoever writes the first GPU-based chess AI. -------- > MCTS requires a good heuristic. EDIT: Not really! The original MCTS go AIs searched randomly. "Random rollouts" was their heuristic. "Random Rollouts" is how MCTS got its start. It was surprising how good MCTS performed with random results (and eventually, modern MCTS algorithms have CNN-based heuristics... but the original MCTS bots prove that "bad heuristics" is still good enough for MCTS).

dragontamer 7y ago

> SIMD doesn't help us for a few reasons. First, because bitboards are extremely sparse. You'll have at most 8 pawns in your pawn bitboards, 1 king in your king bitboards, and only under exceedingly rare circumstances will you have more than 2 pieces in your other 8 bitboards. Under no circumstances will you have more than 32 1s in your twelve bitboards, a density of one 1 per 24 zeroes. You're thinking too traditionalist :-) You're 100% correct in that the above is a "traditional" application of SIMD. However, I'm talking about a "non-traditional" SIMD approach. (or perhaps... "more traditional", closer to the original 1980s style SIMD that GPU programmers use in their pixel shaders) NVidia calls it SIMT, but the concept existed since the dawn of the SIMD methodology. I don't want to repeat what others have done. Give the first 2 pages of this paper a lookthrough for this "nontraditional" SIMD approach: http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1997/CS/CS0891.pdf http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1... My short summary is... the AMD Vega64 is effectively a 16384-wide SIMD unit. (or perhaps... 64 parallel CU clusters of 256-wide SIMD units). What you're suggesting (which won't work) is to use the 16384 SIMD units to evaluate one bitboard. Of course this won't work, even though its the "traditional" approach to SIMD. Even breaking things down "per CU" so that each compute-unit's 256x shaders is "too much parallelism" to work one bitboard. Instead, I suggest using the 16384 SIMD Units of Vega64 to evaluate 16384 different bitboards (!!). I'm very confident that Vega64's SIMD units are advanced enough to handle this kind of task... although the algorithmic details haven't really been figured out by anyone yet (well... that I'm aware of anyway). --------- Every SIMD Shader of Vega64 has 256 (!!) 32-bit registers which can be used once per clock. My estimate is that it takes 25-registers (12x 64-bit boards for the white+black occupancy, + 1x32 register for misc purposes like enpassant, castling, etc. etc.). That leaves 231 registers left over for other calculations. (Occupancy 1). With luck, maybe Occupancy 4 or higher could be reached (limit of only 64x registers used), which would make RAM access more efficient. The question I have is: how do you coordinate these 16,386 simultaneous threads of execution? How does this turn into an efficient tree search? > Evaluation heuristics have been studied extensively, but the overwhelming consensus is that the simpler the heuristic, the better. If you make your heuristic worse, but fast enough to give you +1 on your search depth, you will almost always be better. So our evaluation heuristics are almost trivial because thirty years of research has demonstrated that the trivial heuristics are the best ones. Exactly! Which is why I'm confident that these simple heuristics can be evaluated on each SIMD-shader of a modern GPU. 256x 32-bit registers leaves a LOT of room for these SIMD "shaders" to work with! There's a lot of unknowns that I'd have to work with if I were to code something up in OpenCL (or more likely, ROCm). But a lot of the fundamental research and heuristics have already been done. Just no one has even tried writing them for a GPU yet. The biggest issue is how to represent a search tree in a way that would be efficiently represented in a GPU. Neither MCTS nor Minimax have really been written in a GPU, although the concept of "iterative deepening", and other such simple searches HAVE been executed on a GPU-per shader basis. I haven't really thought how the full details would work. But Vega64 has 4096 shaders operating at 1.5 GHz. If each shader spent 1000-clock cycles per bit-board evaluation, we're looking at 6.1 Billion nodes per second on a single GPU. > hash table move cache That wouldn't scale unfortunately: there's no way for 16386 different SIMD threads to access one shared cache. Maybe a shared cache would be split up to the 64-individual compute-units of the Vega64, perhaps in the small 64kB "shared memory region" (which can be accessed within 32-clock ticks worst-case of Vega64... 1-clock tick in ideal situations). "Shared memory" can be shared with up to 1024 SIMD Threads. A 64kB hash table is extremely small however, giving you the idea of how little memory is available per SIMD-thread. The idea of a "globally shared hash table" will have to be sacrificed in porting the code to a GPU effectively. Or... at best... it would have to be shared on a per-1024 thread workgroup basis. There's no way 16386 threads banging on RAM (even a 512GBps RAM like HBM2) would scale. Heck, 1024-threads banging the 10,000GBps (aggregate) 64kB shared-memory region is probably still not going to scale very well... but that 64kB region is the only thing that is anywhere fast enough to do something like the traditional hash table move cache. This 64kB "shared memory" is the GPU's greatest weapon to scale for parallelism, but there's so many chess algorithms that want to use it. The Rook-move "Sliding Piece Attacks" table with "Magic Bitboards" takes up 64kB already. (16kB for Bishop moves). So figuring out which things will fit inside of that memory region is going to be a big problem for whoever writes the first GPU-based chess AI. -------- > MCTS requires a good heuristic. EDIT: Not really! The original MCTS go AIs searched randomly. "Random rollouts" was their heuristic. "Random Rollouts" is how MCTS got its start. It was surprising how good MCTS performed with random results (and eventually, modern MCTS algorithms have CNN-based heuristics... but the original MCTS bots prove that "bad heuristics" is still good enough for MCTS).