> 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.
> 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.
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).
If I understand correctly, you propose using GPUs so that traditional chess engines can search even more nodes per second.
Leela evaluates three orders of magnitude less nodes per second than Stockfish (70K vs 70M), yet it still won. You need to search smarter, not deeper, as this result shows.
> You need to search smarter, not deeper, as this result shows.
This result pits a GPU with 10,000 GOPS worth of compute and 500GBps of memory bandwidth against a CPU with only 100 GOPS of compute and 50GBps memory bandwidth.
All I'm saying is: how do we test a "fair" comparison? Well... lets (somehow) rewrite the CPU algorithm to run on the GPU. Its an unsolved problem, maybe its completely unsolvable. But its at least a research-question worth pondering.
---------
The TL;DR is: I think its possible to port Stockfish's evaluation functions over to a GPU. However, there are numerous unsolved research problems that need to be solved if this were to happen. The hash-table needs to be reworked, the search tree needs to be reworked, "Lazy SMP" won't work on a GPU, etc. etc. Most of the "tree search" methods need to be completely rewritten from scratch to be GPU-based.
But the fundamental evaluation functions of Stockfish are brutally simple and look like they could work on a GPU shader to me.
Stockfish tests improvements by also playing random games:
> Changes to game-playing code are accepted or rejected based on results of playing of tens of thousands of games on the framework against an older "reference" version of the program
Think about it, a human makes a small tweak, then they run a lot of games with it and decide if it's worth keeping or not.
That's basically a terrible implementation of a neural network's gradient descent.
Now imagine instead of a human coming up with a small tweak, you randomly search for it and take a holistic view of the board instead of micro-heuristics. Oh, you just invented AlphaZero :)
BTW, since chess is highly parallel, you can run Stockfish on a computer cluster. Using this approach you can equalize the GPU power and have a balanced computer power match (of course, it will be totally unbalanced power-consumption wise). I'm not convinced Stockfish will win with equal computing power.
> Now imagine instead of a human coming up with a small tweak, you randomly search for it and take a holistic view of the board instead of micro-heuristics. Oh, you just invented AlphaZero :)
I'm fairly certain that the human brain does not work off of FP16 floating point numbers with back-propagated errors being calculated with differential equations to set the weights of our individual neurons. :-)
Artificial neural networks are fascinating self-learning machines. But remember: they're artificial. There's nothing "human" about LeelaZero, AlphaGo, or any other CNN. Especially because AlphaGo / LeelaZero are augmented with an exceptionally powerful MCTS search functionality (no human counts the number of positions they visit and "balances" each node... nobody does that. MCTS is an extremely powerful computer algorithm for search, also an artificial construct)
> I'm not convinced Stockfish will win with equal computing power.
Ehh? The results are 10-Leela / 8-Stockfish / 82 draws. It was an exceptionally close set of 100 games.
Note that Stockfish works with a global hash-table of chess positions it shares between threads. This methodology works with a "low" number of threads (ie: 16 threads, maybe even 64 threads). But it absolutely will not work at GPU-scale (~16,386+ SIMD threads on Vega64, or similar GPUs).
It is not going to be an easy job to "port" Stockfish properly to a GPU-based system, or even to a cluster of 100x racked up computers. How do you efficiently share a global hash table across 100x clustered computers?
I mean, you simply cannot. Stockfish simply isn't designed to scale that high. Stockfish is innately a single-node design that's constrained by the RAM.
---------
The fact of the matter is: modern systems need a higher-form of scaling. I think LeelaZero / AlphaZero are "cheating", in that they've found methodologies that allow the huge amount of GPU easily be used.
I think this is a wakeup call: that algorithms need to start looking at the GPU more carefully. Heavy compute definitely needs to start thinking about how to scale to 16,000+ threads and work on GPU-like systems.
Today's Stockfish running on a low end computer would still beat Stockfish from many years ago running on a much more powerful one, because it's evaluation function is significantly better.
Chess is not strictly about computing power, and neural-network evaluation functions are vastly better.
Would you please edit the uncivil bits out of your comments here? Lines like "You keep on missing the point" and "You know very well" just add acid to the mix and are against the site guidelines.
I think you misunderstand. I absolutely understand your point. I'm explicitly rejecting your point. There's a crucial difference.
The evidence laid out in this test does not necessarily lead to the conclusion you have here. There are a number of confounding factors, that if I had more time... I'd like to investigate.
True, your point is ONE possible story for what is going on here. But alas, my instincts suggest something else is going on. I think CNNs have simply been extremely well optimized for the GPU platform, and that indeed, they are one of the few algorithms that run extremely well on a GPU.
I'm curious how a well-put together "classical" chess AI would work if it were ported to a GPU. I understand that no such chess AI has ever been written, but that doesn't change my curiosity.
-------
EDIT:
> Chess is not strictly about computing power, and neural-network evaluation functions are vastly better.
I just thought of a way that would test this assertion. Instead of porting Stockfish to a GPU, port LeelaZero to a CPU. Run the Neural Net on the same set of hardware, and see who wins.
That way, Stockfish keeps its (cannot be scaled) centralized hash table / lazy SMP algorithm, while LeelaZero runs at the same compute-power that Stockfish has.
It was 14 wins for leela and 7 wins for sf, which is pretty large for the level they are playing at. Anyway people have thought about using GPU for chess engine but it was difficult to make work. (https://chess.stackexchange.com/questions/9772/cpu-v-gpu-for...). GPU and CPU have fundamentally different architecture and comparing them using just ops per second without taking into account their capabilities is missing the point.
You know very well that LeelaZero was designed to run on a GPU, just like Stockfish was designed to run on a CPU.
You can also do the reverse, it's easy to naively make Stockfish run on a GPU, it will just be performing terribly bad since it's algos will not utilize the GPU properly.
I mean, that's what needs to be done, for the test to work.
Either Stockfish's style of algorithm needs to be ported to a GPU (and I'm arguing its possible to do so efficiently. But a number of unsolved problems do have to be solved).
Or... Leela Zero needs to be ported to a CPU.
I'm not saying a naive port: I mean a port where the programmer spends a good bit of effort optimizing the implementation. That way its fair. Those are the two hypotheticals that can happen for a "fair" test.
I'm, personally, more interested in the case of Stockfish -> somehow ported to GPU, mostly because its never been done before. I mean, I don't want to do it, but if anyone ever did it, I'd be very interested in reading how they solved all of the issues. :-)
Implementing Stockfish's evaluation function on a GPU is almost certainly possible, but stupid. Stockfish is able to evaluate several million nodes per second. By the time it identified a position to evaluate and copied it to the GPU, it could have already finished evaluating it on the CPU.
But a GPU can evaluate many positions in parallel... great... not helpful here because you don't know which positions you need to evaluate.
This is a case of apples and oranges. CPUs are good at running conventional chess engines and GPUs aren't, that's just a fact and there's no way around it. GPUs are good at running some stuff like neural networks, so, great.
If you need to run a neural network engine (LC0) then run it on a GPU, if you need to run a conventional engine, then run it on a CPU. Which is what people are doing now. Trying to change this is nonsensical, and trying to argue about which has more compute power makes as much sense as arguing about whether a car can drive on water better than a boat can drive on land.
I'm hoping you're right and can show this in a couple of years as effectively a third way to build a world class chess engine.
I don't understand how anyone can tell you "AlphaZero beat Stockfish with a method that involves evaluating fewer positions, so any new engine should also evaluate fewer positions." Chess engine research is not finished: there are a lot of things still to try.
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.