A chess engine is just computer program written by humans and this is how they do it.
10 years ago I wrote an article on how chess engines work. It was written as a warm up for Magnus Carlsen's second World Championship match against Viswanathan Anand and was featured in two big Norwegian news outlets (VG and Tek.no).
The article was written for the general public and tried to attract some attention, so sorry in advance for some of the clickbait language 😆
Parts of the information is slightly outdated, but the main takeaways are still very much relevant today. The one big thing that has happened since then is that AI has also entered the scene. I address this after the original article.
So here it is, pretty much as it was written in 2014, except for some minor editing and translation from the Norwegian language.
2014 | The world's best chess player is not Magnus Carlsen
How is it possible to claim something so outrageous now that our dear World Chess Champion is playing against the grandmaster Vishy Anand, the tiger from Madras, in one of the greatest chess matches of all time?
Well, quite simply by expanding the concept of chess player to also include computers. If you do that, there are actually quite a few chess programs today that are well ahead of the best human players in the world. One of the leading ones is called Stockfish and was originally written by the Norwegian Tord Romstad. Stockfish is open source and a good chess player. Very good. In fact, so good that statistically speaking, the program would win 96 out of 100 games against Magnus Carlsen if only considering the rating (playing strength). That's no small feat when we're talking about the man from Lommedalen who many consider to be the greatest chess player of all time, and who as a young boy had to live with being called the Mozart of Chess.
What does it take for a small chess engine running on a cheap laptop to beat the best players the world has to offer? That's what this article will try to shed some light on.
As you probably already understand, a chess engine doesn't run on diesel, and it's strength can't be measured in horsepower. The term is used to describe a computer program designed solely to make chess moves. Chess engines have existed for almost as long as computers.
Already back in the 1950s, programs were created that could play full games of chess, and it didn't take long before they evolved to beating humans. However, it would take considerably longer before they could compete with the top players of the world.
The epic match between Garry Kasparov and Deep Blue in 1997 forever changed history
Technology is ever making progress, breaking boundaries and driving the world forward. As MegaHertz turned into GigaHertz there was finally a breakthrough in 1988. IBM's chess engine Deep Thought defeated a grandmaster for the first time in an elite tournament, and the victim was none other than Bent Larsen, the Danish chess genius. Not only that, it also tied for first place ahead of, among others, former World Chess Champion Mikhail Tal, a gifted Soviet-Latvian player who has left his mark on the history books of chess.
Inspired by this feat, IBM continued developing this monster for almost ten years, renamed it to Deep Blue and sent shockwaves through the world in 1997 when the reigning World Chess Champion Garry Kasparov was defeated in a spectacular match. The reigning chess king of that time was completely speechless, aside from the usual excuses, but the loss remains to this day a milestone in the history of chess engines. In the years that followed, the hardware improved, the developers became smarter, and people finally stopped laughing at those who programmed their binary friends to play chess.
It's time to jack up the car, open the hood, and dissect the engine. How do these programs work? To find the answer we need to roll up our sleeves and delve a little deeper.
A few bytes of the Stockfish source code
Chess is what's called a finite game. That means there is an upper limit to the number of possible moves one can make, or in other words, the number of paths one can take to reach the goal. The problem is that this limit is a number so high that no one has yet been able to do anything other than estimate.
The universe contains around 1080 atoms, but chess has about 10123 different variations 🤯
Wikipedia will tell us that the estimated number of different possible positions is 1047 and the number of possible moves is a whopping 10123. We're talking BIG FIGURES here. Comparing them to the number of atoms in the known universe (around 1080) it's easy to understand that solving chess mathematically presents a bit of a challenge. Fortunately, there are many clever tricks and smart algorithms that a programmer can use to tame these Divine Numbers.
Even with a toolbox full of magic, it's hard to ignore the fact that building a good chess engine is a complex affair. Full understanding of how everything fits together requires a lot of reading, determination, and above all, time. Nevertheless, it's not too difficult to grasp the basic principles behind it all. A chess engine must be able to solve many small and large tasks, but broadly speaking, there are three that stand out.
Generating legal moves
Searching through moves
Evaluating different positions
We humans don't think much about these tasks when we play. They blend together and often happen automatically due to the knowledge we picked up as children when our parents brought out the board for the first time. A computer on the other hand must have clear defined boundaries between the different steps in the process so that the code implementation is fast, tidy, and efficient. Throughout history several methods and strategies have been used, but we will focus on the best and most commonly used ones.
Being able to generate valid moves is the cornerstone of the program and often where one starts. A valid move is simply a move that does not violate the rules, like a rooks cannot move diagonally and pawns cannot move backward. Easy for us humans to understand, but a computer must be fed this with a spoon. This task is also one of the most "costly" in terms of processing power, so it is important to be both smart and meticulous to get the code as efficient and optimized as possible.
The first thing a chess engine needs is a way to represent the game's rules, the board's states, and the pieces' positions. This is done using something called a bitboard. In a row of 64 binary bits (64-bit unsigned integer), each bit represents an individual square on the board. If that's confusing just imagine these bits being organized as an 8x8 matrix and you literarily have a chessboard!
Pieces represented by a bitboard
With this approach, the position of the black queen can be represented by setting the value to 1 on the bit that corresponds to the square she occupies. This method is very efficient and is also used to store various other things, such as the game's rules, all occupied squares, all white pieces' positions, squares a piece can move to, and so on.
The move generator uses the bitboards along with some clever techniques to suggest valid moves. Binary numbers have the advantage that bitwise operations (AND, OR, NOT, and more) can easily be performed on them. These operations are part of the processor's instruction set and can therefore mostly be carried out within one clock cycle.
Three examples of bitwise operations on an 8-bit binary number
Today's 64-bit processors are the gift from technology that truly makes this method shine. It’s almost as if the researchers had the 64 squares of the chessboard in mind when they developed them. Of course they didn't, but this little coincidence makes these bitwise operations extremely efficient. In practice a processor only takes 3-4 cycles to determine if the black queen has put the white king in check and thats lightning fast when we talk about clock frequencies in the GigaHertz range.
Ok, so now that the chess engine can make legal moves, it's actually possible to play a full game of chess! With a little bit of luck it might even manage to beat a 3-year-old.
No one makes headlines by creating a program that is a world champion in losing. If it is to have any chance of reaching the goal with the flag raised, a bit of intelligence is needed. This is where the last two main points come in. To play good chess, a search tree and an evaluation function are needed.
Mikhail Botvinnik (1911-1995), former World Chess Champion
Three-time World Chess Champion Mikhail Botvinnik was convinced that the only way a computer could become good at playing chess was to think like a grandmaster. He believed it was wisest to select a few good moves and only calculate further on them. This is understandable considering the hardware available at the time, but it turned out to be the wrong approach in hindsight. This line of thinking has a clear disadvantage, namely that sometimes you will miss move sequences that might lead to defeat 20 moves later.
Therefore, all modern chess engines use a brute force strategy, which involves examining absolutely all legal moves. It costs a bit of CPU cycles, but can be justified with the incredible speeds we have on processors today. Various search trees based on the min-max algorithm are used to handle the search. The algorithm recursively finds all possible moves in a position until a defined depth is reached. At the bottom of the depth, an evaluation function is used to analyze the position and give points based on how good it thinks it is. These points are then sent back up the tree according to rules determined by the algorithm.
Example of how the min-max algorithm works (Norwegian language)
You'll find lots of videos out there explaining this in greater detail.
Lets use an example, where for simplicity's sake we cheat a bit and reduce the number of possible moves to two. To find the best move in an initial position (above image) one then does the following:
White tries two moves, pawn to h3 and bishop to e4
Black responds with two moves for each of them
White responds with two moves for each of them again and the bottom is now reached
The evaluation function calculates the score for each of the eight final positions
The scores are now sent up the tree again using the min-max algorithm. White always assumes that black will make the best move and vice versa. In our example, low numbers are good for black (min) and high numbers are good for white (max).
White compares the 4 "move pairs" scores and sends the highest number one step up
Black does the same but sends the lowest number one step up
White again chooses the highest number and finds that the pawn to h3 is the best move
Of course in real-world games the computer will search much deeper over many more possibilities. For every single move, the number of variations grows exponentially, leading to an immense amount of calculations. To tackle the problem more advanced solutions like negamax, alpha-beta pruning and transposition table are used. These algorithms have different ways to prune the tree or said in another way, find shortcuts down to the bottom.
Stockfish calculates variations at a rate about 1 million moves per second on an Intel Core i7 with 8 GB RAM
The evaluation function that assesses a position at the end of the search tree is the final important task to build a complete chess engine. It separates the men from the boys in a world where digital chess players fight fiercely to be the best.
All methods and algorithms mentioned so far can be described as cold calculation while evaluating a position requires a bit deeper knowledge of chess. There are also plenty of mundane calculations and known techniques, but those who often win have that little extra. Therefore, programmers often have a Grandmaster or two on their team to come up with the smartest solutions.
The relative weights/points of the chess pieces
Not everyone is as privileged, but fortunately one can still get far with the familiar and accessible. To evaluate a chess position, it is most natural to start with the value of the pieces. The difference between the total value of each player's pieces provides a good indication of who's got the better position. It is also worth mentioning that pieces can have different values at different stages of the game or where they are on the board. Other methods used to assign points in a position can include:
The weights/points of each square on the board
How the pieces are placed in relation to the center of the board
Number of pawns and their formation
How safely the king is positioned
How much space on the board the pieces control
Control over strategic squares
Development of the pieces
And so, the chess engine has actually solved all three most important tasks and is ready to challenge any chess player. There is always room for improvement, but small tweaks can go a long way.
Ok, to avoid the risk of being ambushed by enthusiastic Carlsen supporters at the next chess tournament, it may be wise to end with a slightly different tone than the one set from the beginning.
Street art by LAA STAA
Computers are here to stay and plays good, godly, uncompromising chess. They never get tired and rarely miss anything as long as the search tree goes deep enough. Humans, on the other hand, have a better understanding of certain types of positions on the board and can still see deeper than the machines in some rare cases. With the right strategy and good endurance, it is still possible to defeat Stockfish and his friends, but probably only for the very top elite players.
If we once again expand the definition of a chess player to include "a computer with a human by it's side", then Magnus Carlsen is definitely number one.
It is fitting to end with a quote from the programmer Rune Zakariassen. In an inspiring lecture he gave together with Grandmaster Rune Djurhuus, he said the following with a glimmer of hope in his voice:
I will never beat Magnus Carlsen in chess, but theoretically, I should be able to create a chess engine that is just as good.
That is probably the closest us mortals can get to defeating a World Chess Champion in chess.
Good luck in the World Chess Championship, Magnus!
A lot has happened in the 10 years since this the above article was written, main thing of course being that AI has taken over the world. How has this affected the chess world? Quite a bit actually.
Not only has the engines become much stronger, but more importantantly the way they play the game has sparked many new ideas among top players. Magnus Carlsen himself has said he is very much inspired by how the new AI engines play the game.
In 2017, Google's DeepMind research group published a paper on their AlphaZero system, which was able to achieve superhuman performance in the games of chess, shogi, and Go by learning the games from scratch through self-play.
All hail the King and Queen of the chess world!
The impressive results of AlphaZero against the top chess engine Stockfish sparked a lot of interest in the chess community. However, the source code was closed and proprietary (boo 👎) which led to the development of an open source project called Leela Chess Zero (yey 👍). Leela quickly started winning and together with Stockfish would come to dominate the computer chess scene for years to follow.
Results of TCEC season 14-25 (2018-2023)
Before 2020 Stockfish was solely using the classical brute force technique described in the first (old) part of this article, but doing it extremely well. Being smart people, the developers realized the need for modernization and starting with Stockfish 12 (2020), a neural network board evaluation function was incorporated. Later in version 16 (2024) the classical board evaluation functions were completely removed, leaving just the neural network.
So yea, AI has had a huge impact on chess engines!
Deep neural networks is the main ingredient here and is pretty much what has revolutionized AI these past years. The topic of neural networks goes quite deep (pun intended) and is a bit beyond this article (and beyond me for that matter), so why not ask a neural network for an explaination?
Deep neural networks are a type of artificial intelligence that are inspired by the way the human brain works. Just like your brain has billions of tiny cells called neurons that work together to help you think and learn, deep neural networks have layers of interconnected nodes, also called neurons, that work together to solve complex problems.
The "deep" in deep neural networks refers to the fact that these networks have multiple hidden layers between the input (what you start with) and the output (the answer you get). Each layer takes the information from the previous layer, processes it, and passes it on to the next layer. This allows the network to learn increasingly complex features and patterns in the data.
The real magic of deep neural networks is their ability to learn and improve on their own, without being explicitly programmed. As the network is exposed to more and more data, it can adjust the connections between its neurons to become better and better at the task it's trying to learn.
So there you have it. I hope you understand what's being said here. It would have taken me hours to try to explain this in such a simple way and I probably would have failed.
How well we understand what's really going on here is still up for debate though. We've learned how to set up a simple simulation of our brain and the benefits are great, but lets face it, we don't even understand how our own brain is working!
What we do know is how to optimize these layers of nodes for playing chess so that our brain simulator can play games against itself infinitely and learn while doing so. And there lies the real trick. These networks don't only train on existing data (all human games ever played), but creates it's own data to train on as it progresses.
The way the engines get better these days is mainly by training and most of the development goes into improving the algorithms and parameters in the training process. Anyone can contribute to Leela Chess Zero or Stockfish by sharing training data, thereby helping out moving the world forward.
How do we as humans improve our chess game? We play games against each other, do lots of puzzles, read books or watch some videos. Then after years and years of doing this we slowly start to remember patterns and recognizing tactics, thus getting better.
Now imagine you lived to be a billion years old and did this every single moment of your life. That's basically what these new chess engines do.
