16

GPUs are better at certain types of calculations, e.g. generating bitcoins and performing climate simulations.

Would chess engines benefit if they calculated with GPUs instead of CPUs?

Maybe some knowledgeable person can highlight the differences between the two and enlighten us as to whether GPUs are (un)suitable for the type of calculations that chess engines execute.

13

EDIT:

Few other points raised in http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=32317.

  • GPU not so good for recursion
  • GPU not so good for floating
  • GPU might work better for new machine-learning approach, but not the traditional engine algorithms

Original:

@Maxwell86 has already given excellent links and resources. Pay attention to the zeta-chess engine. It's a GPU chess engine. Unfortunately, GPU has not proven its usefulness in chess programming. In fact, the zeta chess engine project went absolutely nowhere.

GPU works very well on floating calculations and algorithms that can be paralleled. This requires independence. But if we look at a typical min-max (or alpha-beta) tree (used by every chess engine )

enter image description here

The right branch depends on the left branch. In particular, if we can get a cutoff (fail-high), we wouldn't even need to search the remaining nodes. Unfortunately, this is not something that a GPU can do efficiently. It's possible to write a GPU program for alpha-beta, but the GPU threads (known as kernels) will need to be paused to wait. Unlike a CPU, a GPU kennel can't just switch to something else ( a process known as thread-switch or even process-switch).

Our existing algorithm and engine knowledge was derived for the CPU world. The entire algorithm would need to be reinvestigated for the GPU. Unfortunately, there is not much interest and research on it.

  • You don't have to offload the minimax itself. There are certain subtasks (e.g. Botvinnik's alpha path finding, board hashing, static evaluation, etc) which are very well suited for GPU. That said, I have no knowledge of any research in this area. – user58697 Jul 22 '15 at 14:56
  • True. But if the main search itself can't be offloaded, there should be no point to offload the small tasks. – HelloWorld Jul 22 '15 at 15:13
  • 3
    This is an excellent answer. Where on my screen is the +3 switch? I can't find it! – thb Jun 11 '16 at 0:24
7

I have no experience with GPU programming, but, typically, GPUs are very efficient in executing simple commands in a parallel way. Apparently, this is not the case for the search tree that is used for chess engines. Therefore, the GPU loses its computational advantage over a CPU.

Of course, this is the current state of GPU programming for chess engines, but GPU programming is relatively new, so maybe they'll find solutions for the current problems in the future.

Here are a couple of interesting links, especially the blog about implementing a chess engine for GPU is quite insightful.

  • 1
    You've missed: zeta-chess.blogspot.com – HelloWorld Jul 19 '15 at 12:10
  • Things GPUs are good at include fractional math, vector operations, and parallelization requiring minimal synchronization. Chess engines have the last one but not the first two. – intx13 Jul 19 '15 at 16:57
5

The LC0 (Leela Chess Zero) project, an open source adaption of AlphaZero for chess, shows the benefit of gpus, floating point performance and memory bandwidth used in large neural networks.

http://lczero.org/

https://en.wikipedia.org/wiki/AlphaZero

https://groups.google.com/forum/#!forum/lczero

2

I finished my current run on Zeta v099a, my experimental gpu chess engine.

https://github.com/smatovic/Zeta

The actual conclusion of the current iteration is, that an simple engine, with standard chess programming techniques, can be ported to OpenCL to run on a gpu, but it would take more effort to make the engine competitive in terms of computed nodes per second (speed), heuristics (expert knowledge), and scaling (parallel search algorithm).

Computer Chess, as an computer science topic, evolved over decades, starting in the 40s and 50s, and reached one peak 1997 with the match Deep Blue vs. Kapsarow. Nowadays chess engines are tuned by playing thousands and thousands of games, so to get an chess playing engine running on the gpu and to get an competitive chess playing engine running on the gpu are two different tasks.

0

I've some experience with CUDA and chess programming (not engine programming). This question also came to my mind many times. Here is my opinion, I never studied this.

Well, first, it is virtually certain that with current design of chess engines it's impossible. Otherwise someone would simply do it.

Whether you could use it in completely new design, that's a bigger question. There's no problem with integer operations, but clearly there is huge thing that you must run primitive code with no serious branching on many of entities.

In my opinion all the tree calculations should run on CPU.

But I can imagine (I don't say it's possible) some partial evaluation function(s) that just make as much evaluations on positions as possible, to give CPU more time, to help him build the tree in a better way, lets say one such function could calculate how serious calculation should be made on each position.

You can calculate number of squares attacked, pieces attacked, firepower around kings and in some subregions on board, pawn structure related things, you could probably make GPU optimised code for these. You can probably get a lot of useful informations for free (no CPU time, no CPU waiting), but you would have to be real genius to use full horsepower of modern GPUs for such small things.

It is probably not very interesting thing to do to create completely new design of engines to get let's say 30% extra speed. And to get let's say 20x speedup on state of the art GPUs, you would have to make evaluation functions really alien.

And last thing on this what I see to be a problem. You can run one code on CPU with not many thinking, but in CPU+GPU scenario you would have to deal with really different ratios of CPU and GPU. speeds and core counts. You would need different code for 16 cores cluster with weak GPU than on slow CPU with super fast GPU to use full capabilities of hardware. Benchmarking CPU vs. GPU and then running more code on the faster machine would be desirable. But still, I think you will get nowhere close to feeding 3000 cores beast just with evaluation function(s).

Edit: Just to make things clear, CPU would regularly send GPU arrays of positions to make partial evaluations. Maybe that wasn't clear from what I wrote.

Many problems to make this work.

0

I see only benefits in using a GPU based chess engine and don't see any serious problems doing that. Maybe you have that issues try using a standard chess program, don't know much about the others. I just start up to write a chess programm from the first line on, as a second CUDA based program after I make some first programming tests on CUDA without specific sence. Soon I can make some first performance tests and test games against other engines. Maybe during next week. I just start creating it but I'm already close finish it and most functions already finished.

  • Google has proven GPU ideal for machine learning but GPU is not good for traditional chess programming. – HelloWorld May 5 '18 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.