I finished groking the CUDA stuff, looks good in general!
For those who want an overview: stuartriffle follows the MCTS algorithm, which has two parts. The MCTS is the general C++ code "TreeSearch" (which I haven't grok'd yet. The textbook UCT evaluation function is there, but there's some async stuff going on that I don't understand yet). For the evaluation function / heuristic, its a classic random-rollout code, which randomly plays Chess until it discovers a win, loss, or "draw" (which seems to be a "max moves == 0" case).
"Random Rollout" is the most naive implementation of MCTS, but its still an important demonstration showing that GPUs can indeed play chess within its shaders. The engine as a whole seems free of any obvious GPU-divergence issues, so I'd expect it to be reasonably efficient at random chess playing.
So chess engines CAN be ported to a GPU. From here on out, its a matter of experimenting with various methodologies to see what creates the most powerful chess player.
--------
I'm going to have to go through the MCTS part later. Its clearly some kind of parallel implementation that batches up nodes for MCTS evaluation.
The GPU probably can run some of the MCTS stuff faster than the CPU (ex: the UCT evaluation probably should be on the GPU: which could be done relatively easily by passing play-statistics to the GPU kernel. GPUs are very fast at square-roots and stuff, and you're already spinning up a GPU thread for the whole random-rollout thing, might as well evaluate the UCT value while you're still in GPU land. I think anyway)
But yeah, I haven't fully understood how you're doing the MCTS stuff yet. Its definitely interesting code though.
----------
EDIT: I'd personally want to figure out how to get the MCTS search into the GPU somehow. But doing the rollouts on the GPU is the "obvious" first step (at a minimum, you need to have a chess engine in the GPU before any further steps are possible), and its cool that you found a practical use of the random-play engine with the classic MCTS algorithm.
For those who want an overview: stuartriffle follows the MCTS algorithm, which has two parts. The MCTS is the general C++ code "TreeSearch" (which I haven't grok'd yet. The textbook UCT evaluation function is there, but there's some async stuff going on that I don't understand yet). For the evaluation function / heuristic, its a classic random-rollout code, which randomly plays Chess until it discovers a win, loss, or "draw" (which seems to be a "max moves == 0" case).
"Random Rollout" is the most naive implementation of MCTS, but its still an important demonstration showing that GPUs can indeed play chess within its shaders. The engine as a whole seems free of any obvious GPU-divergence issues, so I'd expect it to be reasonably efficient at random chess playing.
So chess engines CAN be ported to a GPU. From here on out, its a matter of experimenting with various methodologies to see what creates the most powerful chess player.
--------
I'm going to have to go through the MCTS part later. Its clearly some kind of parallel implementation that batches up nodes for MCTS evaluation.
The GPU probably can run some of the MCTS stuff faster than the CPU (ex: the UCT evaluation probably should be on the GPU: which could be done relatively easily by passing play-statistics to the GPU kernel. GPUs are very fast at square-roots and stuff, and you're already spinning up a GPU thread for the whole random-rollout thing, might as well evaluate the UCT value while you're still in GPU land. I think anyway)
But yeah, I haven't fully understood how you're doing the MCTS stuff yet. Its definitely interesting code though.
----------
EDIT: I'd personally want to figure out how to get the MCTS search into the GPU somehow. But doing the rollouts on the GPU is the "obvious" first step (at a minimum, you need to have a chess engine in the GPU before any further steps are possible), and its cool that you found a practical use of the random-play engine with the classic MCTS algorithm.