mot524

I told you that intra-thread communication will ruin chess engine efficiency, and in your reply, all you do is talk more about stuff that requires intra-thread communication (tasks, futures, promises, etc.). You might think that all I'm here to do is insult you, but from my point of view it seems like all you're here to do is ignore me, even though I'm the one with domain-specific knowledge. It's not a "discussion" if you're not going to consider anything I have to say.

I already told you that intra-thread synchronization is to be avoided but you're still talking about it (promises, futures, tasks, etc.) so I don't know what to say. Nothing you're saying is going to work like you think it is, but it seems like you're going to have to figure that out for yourself.

Clearly you want to talk more than you want to program. Maybe reimplementing Stockfish on a GPU is too daunting of a task. Why don't you get something simple like TSCP running on a GPU and see how far you get with that? TSCP is only about 2k lines of code and probably half of those lines are comments. With the state of GPU cores and compilers these days maybe you can get the C code running on a GPU core directly without much modification. TSCP also uses less than 64k of RAM so it should fit nicely in an Nvidia SM.

Okay, as long as we're not arguing, I will tell you that any sort of fine-grained intra-thread communication is to be avoided like the plague in computer chess. Engines are able to search millions of positions per second... most multithreading frameworks (e.g., the ones that give you your "futures" and "promises") rely on locks that can halt threads for milliseconds at a time. It's absolutely disastrous for efficiency.

I believe Stockfish uses the idea of "Lazy SMP" for parallel search which literally means no intra-thread communication other than locks on hash table entries to avoid data corruption of the hash table. Anything more sophisticated has proven to be a loss. So any sort of discussion of tasks, futures, promises, or even Young Brothers Wait is going to be fairly pointless. Also, anything that relies on offloading data to the GPU for processing for more than a few milliseconds is going to be a net loss for obvious reasons. Meaning that even if you could evaluate a million positions in parallel, and you already (somehow) knew which positions you needed to evaluate, doing the evaluation on the GPU is probably still going to be a loss due to the time it takes to copy the positions to/from the GPU.

Really, if you were tasked to come up with an algorithm that was poorly suited for GPGPU computation, it might be computer chess.

That being said, it doesn't really matter. How much were you hoping to speed up Stockfish? AlphaZero still crushes Stockfish at 10:1 time odds. Even if you were able to make Stockfish 10x faster it wouldn't change the dynamic of CNN chess engines being superior to conventional engines.

I've already spent a bunch of time explaining to you why this won't work. But hey, apparently you're the expert. If you want to reimplement Stockfish on a GPU such than it's faster than a CPU then nobody's stopping you. The source code is only ~10k lines and very well-written, clear, well-documented, and easy to understand. Go for it. You'll be famous as the first person to effectively implement alpha-beta on a GPU and as the author of the strongest conventional chess engine in history. So go for it.

Like I've been saying, you don't know what you want to q-search next until you've finished the last q-search. So you can't make a q-search queue because you couldn't add anything to the queue until the previous addition was evaluated. I feel like I've said this a few times but for some reason you're not getting it, not really sure what the hangup is?

Alpha-beta in general is so sequential that basically all the algorithms to parallelize it focus on making each thread as independent and sequential as possible. For example, the PV-split algorithm (which generalizes into Young Brothers Wait) splits the tree as low as possible (eventually to the root node) so that all threads can act as independently as possible. There is no local parallelism to be exploited because every branch is radically different from the last branch, and dependent on the result of the last branch. Local parallelism is necessary for a GPU to be effective and conventional game tree search algorithms have none.

I know exactly how much divergence there is because I'm the author of a chess engine and I've spent weeks/months looking at traces of my engine's tree searches.

I think what you're not getting is what a chess engine search tree looks like. You're thinking it has nice layers of nodes, but really, most of the time, the engine is in the quiescence search, searching sequences of captures. The branching factor is extremely low and each branch terminates at an unpredictable depth. Instead of nice layers of nodes, imagine a lightning bolt that's constantly changing. You can't predict what you're going to have to do next.

GPUs would excel if you have to do the same thing to different boards all at the same time. But that's never what happens. Imagine you're in the q-search and you're at a node with two captures. Might as well search both at the same time? Okay, a GPU can make two moves at the same time and evaluate the resulting positions simultaneously no problem. Maybe one evaluation causes the branch to terminate and then that thread needs to undo the move, whereas the other branch needs to keep going and generate and search subsequent moves. This sort of divergence is the norm, not the exception, and it's impossible to handle in any sort of efficient way with a GPU.

It's great that people have made GPU software to visit all possible positions to depth N, and it's great that somebody is making a MCTS engine run on a GPU. Both are tricky to do, and significant accomplishments if they work correctly. But in terms of making an effective engine these are just the absolute first initial baby steps and they don't signify anything about the viability of the rest of the project.

I think you misunderstand how "processing a node" works. It's a recursive algorithm. Even if you correctly identify an ALL node (which is not always easy) and say "hey process all these moves at the same time" then each move will result in a radically divergent search path that a GPU won't be able to handle.

Basically nothing in a parallel chess engine happens in lockstep. All the threads are always doing completely different things. One thread may be evaluating a position. One thread may be making a move. One thread may be taking back a move. One thread may be generating all pseudolegal moves. One thread may be generating captures. No thread is ever doing the same thing as another thread so there's no parallelism of the sort that can be exploited by a GPU.

You're likely looking at simplified diagrams of a search tree and seeing a circle that has lines that connect it to a layer of more circles and thinking "hey just do all those circles in parallel" but the way chess engines work is 100% different from that.

You're not the first person to have the idea to do alpha-beta search with a GPU. There have been many efforts, and several for chess specifically. They've all been kind of awkward and horrible and it's debatable whether or not you can even really call them alpha-beta. There are hundreds of people who make chess engines and it's not like they're all incompetent and never thought of using the GPU.

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...

I believe LC0 was being run on dual RTX 2080 Tis and Stockfish was being run on "43 cores" which I take to mean a workstation with dual Intel 22-core processors. So you're talking about two $1200 graphics cards vs. two $3000+ CPUs. So you could make an argument that LC0 was running on inferior hardware, at least dollar-wise.

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.

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.

I believe AlphaZero's CNN uses 40 residual layers and LC0 uses 20 layers. So in theory, AlphaZero could have twice as much chess knowledge. So that's a reason to believe that AlphaZero might be stronger than LC0. But there's no real way to know at this point.

Training AlphaZero for more than 4 hours on DeepMind's system didn't improve its strength. Makes you wonder if that's as close to ideal chess as we're ever going to get...

Except that LC0 wins decisively against all other engines too. You just hear about the wins vs. Stockfish because Stockfish is the best conventional engine so that's more newsworthy.