4 ms·
LC0 and AlphaZero work on the following principles: * GPU-based compute -- Deep Learning scales very well on GPUs, which are known to have superior parallelism
by dragontamer 7y ago
LC0 and AlphaZero work on the following principles:
* GPU-based compute -- Deep Learning scales very well on GPUs, which are known to have superior parallelism over CPUs.
* MCTS -- "Monte Carlo Tree Search", which is a different tree-search compared to Minimax. MCTS seems closer to "human-like play", with regards to search order.
IMO, it is inelegant to use CNNs / neural nets as the evaluation layer. However, its difficult to imagine an evaluation function that would scale to GPUs. 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.
GPUs have significantly higher compute power than CPUs. Chess positions can largely be represented by just a few 64-bit integers (!!). (An 8x8 bitboard is 64-bits, one bitboard per piece). So the compute-density of chess-evaluation is very very high, there just aren't any algorithms that are well suited to the GPU-architecture aside from deep learning right now.
-------
I really think MCTS is the superior search tree algorithm. The only issue is the evaluation function. Its certainly cool that Deep Learning / CNNs are being used as a "universal" GPU-function (self-learn / self-train so that a large CNN can "deeply" use a ton of GPU resources to make up its own evaluation function). But as far as I'm concerned, its a crutch.
----------
EDIT: If I had oceans of free time... I'd love to see what "translating" Stockfish's algorithms (ex: backwards pawn check. Bishop moves check. Paired Bishop advantage check. Etc. etc.) to a GPU would be like.
A GPU probably could evaluate a million boards for "backwards pawns". Then evaluate the million boards for "paired bishops". Then evaluate the million boards for "knight outpost". Etc. etc. In effect: calculate the millions of positions in parallel, by lining them up and batching them together.
Stockfish's parallelism is CPU-based, with lots of if-statements. Batching these checks into individual units would remove the if-statements and potentially make it amendable to SIMD-compute.
The tree-evaluation would try to evaluate ~1-million boards at a time, to keep the GPU busy. Maybe ~1-million boards per CPU-thread (somehow self-tuning the evaluation process for an optimal mix of CPU + GPU time used).
Again: if I had mountains of free time, lol.
- nwallin 7y ago> 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).
- currymj 7y agoCNN for Go at least seems justifiable. The use of a convolution captures the fact that a configuration of stones is mostly the same configuration of stones whether or not you shift it around the board a little bit. This is much less true for chess, although it might still be true enough.
- dragontamer 7y agoThere are a lot of configurations of pawns or knights that are highly desirable. A "knight outpost" (a knight guarded by a a pawn) is a "local" board position that is well considered to be strong. Same with a bishop outpost. "Paired knights" (knights which can protect each other) can only rarely be taken by a rook or queen. Pawn-chains are good, while "backwards pawns" and "doubled pawns" are bad. "Rook behind pawn" is good, "Rook in front of pawn" is bad. King Opposition is good (https://en.wikipedia.org/wiki/Opposition_(chess) https://en.wikipedia.org/wiki/Opposition_(chess)) Go is more uniform for sure. But there are plenty of opportunities for CNNs to work out in chess.
- bonzini 7y ago> "Paired knights" (knights which can protect each other) can only rarely be taken by a rook or queen. Not entirely true for rooks, since taking 2 knights for a rook is advantageous. Paired knights are usually considered weak.
- stuartriffle 7y agoI’m working on a brute force MCTS engine right now. It scales across SIMD (to 8x) and GPU (only CUDA so far). https://github.com/StuartRiffle/Jaglavak https://github.com/StuartRiffle/Jaglavak My GTX 780 can play about 1M games to completion per sec. Still under construction, but any advice is appreciated!
- ganeshkrishnan 7y agoWould you be able to update the readme to add build instructions, how to run it etc?
- HeWhoLurksLate 7y agoMan, if I had enough money, I would totally ship you a fancier card (and new build, if necessary). That's really cool!
- symplee 7y agoHave you graphed elo to number of roll-outs? Where do the diminishing returns kick in? How many elo points do you guess you'd gain if you improved to 10M games per sec? 10B?
- dragontamer 7y agoI 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.
- dagw 7y agoI'd love to see what "translating" Stockfish's algorithms (ex: backwards pawn check. Bishop moves check. Paired Bishop advantage check. Etc. etc.) Do you know if all these checks are documented somewhere (other than the source code)?
- dragontamer 7y agohttps://www.chessprogramming.org/Programming https://www.chessprogramming.org/Programming The "beginner chess engine" for the wiki is here: https://www.chessprogramming.org/CPW-Engine https://www.chessprogramming.org/CPW-Engine (focusing on readability instead of optimizations) For the heuristics of stockfish themselves, see https://hxim.github.io/Stockfish-Evaluation-Guide/ https://hxim.github.io/Stockfish-Evaluation-Guide/
- barrkel 7y agoIMO it makes most sense to use NN for the evaluation layer. Human heuristics are unlikely to be as well tuned as a NN, and may encode unknown biases. A NN can cover the search space more dispassionately and discover relationships that don't occur to humans, and with a delicate relative balance of tradeoffs. The evaluation of a position is to guess if it is more likely to lead to a final game outcome. The other way to determine this is to look further ahead, deeper into the search tree. The latter has significantly more information content than a heuristic. IMO it would almost certainly be a poor tradeoff of compute; the heuristic needs to be run over each possible move at each level of the search tree, so halving the cost of your heuristic is like doubling the amount of compute you use for tree evaluation. And you're talking about running heuristics over millions of boards. That's a lot of compute to leave on the table. And I think NN are very good for boiling down large computations into a few serial matrix operations, efficiently packing in dependencies and associations. I don't think a rule-based heuristic could compete, algorithmically. Don't forget that one of the great mysteries of human intelligence is that it works as well as it does while using neurons that operate incredibly slowly by comparison to digital computation. The can do it because NN bake in cached knowledge that permits good decisions to be made on very little data. Exactly what you want for evaluation.
- mot524 7y agoThe 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 agoYoung 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 agoYes, 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...