The preposterously fast ChessBase search booster

Question: First of all, Jeroen, tell us a little about yourself. Since when have you been part of the ChessBase team, and what is your role in the development of the software?

Jeroen van den Belt: I've been with ChessBase since 2000. My role? I focus mainly on multimedia, FritzTrainer, 3D, Raytracing and general user interface. I also sometimes travel to events and matches to report on them. I am Dutch and have done it quit often for Wijk aan Zee.

Q: You also developed an unusual Fritz version to play against Garry Kasparov?

JvdB: You mean 2003 in New York? The program he played against was called X3D Fritz, and it was one of my early attempts at programming a 3D chess board...

Q: ...like the spectacular ray-traced boards you have implemented in the current version of ChessBase?

JvdB: Well, yes, but for New York I programmed a true 3D board, which appeared to float in front of the screen. Of course, you had to wear special 3D viewing glasses for it.

Q: Okay, now on to the recently launched ChessBase 16. I am particularly interested in the new search booster function you have implemented, which is quite remarkable. Can you tell us how it works?

JvdB: Well, I was assisted in that by my colleague Mathias Feist. The super-fast search booster is the key to many of the new functions in ChessBase 16. Let me give you a summary of how I programmed it and how it works. I'll do it in a little article.

It is all about the data structure!

In 2007 the multinational technology company Nvidia, which designs graphics processing units for the gaming and professional markets, released CUDA. That stands for Compute Unified Device Architecture) and is an interface to program graphics cards. I always had an interest in programming hardware, so I decided to take a look at it. As with every new software technology development I ask myself, can I apply this to chess? By the way, this is why we have:

• The first very fast online database based on LDAP (2000)

• A world map on our chess server so you can see where your playing opponents live (this was in 2001, way before Google Maps);

• Fritztrainers, which originally used subtitles track to store and synchronize moves with the video;

• Hardware accelerated 3d board ( DirectX9, 10, 11 and RTX); Raytraced 3d boards.

All of this developed out of my interest for emerging technologies.

A graphics card is very good at processing pixels. This means you have a small program fragment which you execute as many times as there are pixels to process. To give you an idea: if you have a full HD screen (1920x1080 pixels), you execute a fragment program two million times. Modern graphics card are able to do this – execute fragment programs – on any chunks of data. It doesn’t need to be pixels.

Two main areas in our chess software functionality are engines and searching in databases. Engines heavily rely on recursion, which was not natively possible on graphics cards – except in the latest generation of AI engines. Searching is better suited. So I started to copy our database in to the graphics memory and ported to program to CUDA. Mind you, there were quite some limitations, including register uses, stack size, etc.

I managed to get a search function working but it wasn’t as fast I was hoping for. Why? Our database format is highly compressed and the code to decompress the data has a lot of “if” statements which makes it slow to execute on a graphics card. Because with every if instruction the graphics card serializes the two possible outcomes. A few years later I ported the CUDA code to DirectX 10, which has the advantage that is also supports AMD hardware (ATI at that time). The problem however, the code took 20 minutes to compile.

With every little experiment I did with the graphics card I noticed that "if” statements slow everything down. I had to think of an easier data structure. I converted the game database to a GPU friendly structure, and stored every move of every game. Every move contained information on which piece moved, where it came from, where it moved to, and if any promotion occurred. You need roughly four bytes for each move. By using this simple structure, the logic only needed to compare the position searched for with every position encountered.

I was surprised by the speed of it. On my powerful graphics card it took less than a second to search through eight million games. I changed to bit boards and it was even faster.

That year I discussed my experiments with my colleague Lutz Nebe. He said there is no way I can make a faster search algorithm on a normal notebook computer than the one we already had. I felt challenged, and the next day I tried the data structure and algorithm on the CPU. I was shocked. It turned out to be almost as fast as on the graphics card. A new search booster was created.

I had mixed feelings about this. I was alway nagging my colleagues about the powerful graphics card horsepower, and how we needed to incorporate this into our software. But at the same time I had proved that the CPU is all we need.

It is all about the data structure!

A year ago I decided to give it another go. A friend of mine told me about a theoretical video encoder which has a compression ratio of nearly 99.999%. How could that be possible? If you have unlimited memory, you could give every possible picture (sequence of pixels) a number. If the encoder and decoder have the same unlimited picture database, the encoder could store the movie by just using a series of numbers.

I was fascinated by it this and thought: how can I apply this theoretical idea to chess? What if I give every possible move a sequence number. You take an empty board and put a piece on it, and go through all the moves it can make. You do this for every piece and both colors. It turns out there about 50,000 different moves and you need only two bytes per move to store this information. This is a reduction of 50%.

It is all about the data structure!

This means ChessBase 16 will run faster on older computers which have limited memory (4 GB) than previous versions. And it means ChessBase 16 will be able to handle larger databases more comprehensively when searching for positions.

The previous search booster limited it search to move 40 (so it wouldn’t take too long). Now with every search all the moves in all the games (that’s roughly eight million times 60 moves = 240 million positions) are compared. And it only takes seconds.

For the more ambitious let me tell you that there is a new generation of graphics cards which have 80 GB of memory! With the new search booster eight million games require 1.25 GB of memory, so you could easily store 500 million games in the memory of these graphics cards. You wouldn’t have time to make a coffee before a search over 40 billion positions has been completed...

Q: Thank you, Jeroen, for these insights. We need to ask you about the possible applications for these outrageously fast searches. But we will leave that for the second part of our discussion.

New: ChessBase 16

This program is the key to fresh ideas, precise analyses and targeted training! With the new repertoire recommendations, main variations, secondary variations, attacking, gambits, and brand new, "fashion", you can focus on openings better than ever. Furthermore, recognition to detect weak points against your opponents can be added to your opening preparation. With the Novelty-Mining feature, you can dig deep for opening treasures. And there are many more novelties.

About the Author

Editor-in-Chief emeritus of the ChessBase News page. Studied Philosophy and Linguistics at the University of Hamburg and Oxford, graduating with a thesis on speech act theory and moral language. He started a university career but switched to science journalism, producing documentaries for German TV. In 1986 he co-founded ChessBase.

Related news:

	How to get the most from ChessBase 16 @ 08/10/2021 by ChessBase (en)
	ChessBase 16 - The search booster in action @ 12/01/2021 by Arne Kaehler (en)
	Mega cool: The games update of Mega Database 2021 @ 03/12/2020 by Martin Fischer (en)
	ChessBase 16 - The new features Part 5 @ 17/11/2020 by Arne Kaehler (en)
	ChessBase 16 - The new features Part 4 @ 16/11/2020 by Arne Kaehler (en)
	ChessBase 16 - The new features Part 3 @ 15/11/2020 by Arne Kaehler (en)
	ChessBase 16 - The new features Part 2 @ 13/11/2020 by Arne Kaehler (en)
	ChessBase 16 - The new features Part 1 @ 12/11/2020 by Arne Kaehler (en)