In 1957 the first chess program, the Bernstein Chess Program, was created by A. Bernstein. It could easily be beaten by a beginner. In 1997, 40 years later, the engine Deep Blue beats the world champion Garry Kasparov. How was this made possible ?
Since then, Chess Engines have become even better, so much that humans have no hope of victory against the bests ones. To understand how big the gap between human and engine has become, look at the graph below. It represents the Elo rating which is a measure of the strength of a player.
As we can see, there is nearly as much difference between a strong amateur and the Word Champion as between the World Champion and the strongest engine.
What is amazing about chess engine is the simplicity of the concept behind them. The principle behind the algorithms used today were discovered in the 50’s. And while there have been some changes and improvements over time, the basic principles still remain the same.
A chess engine is composed of two parts : an evaluation function and a search function. The role of the evaluation function is to determine if a position is winning or not and the role of the search function is to navigate through the huge number of possible moves to select the best one. They have complementary role and one couldn’t hope to make an engine work with only one of them. A search function alone would look at all the possibilities but be unable to tell which one is the best. An evaluation function alone would be like playing without thinking ahead about moves.
In this post, I will explain how theses functions work.
I) The Evaluation Function
The role of the evaluation function is to look at the board and answer the question : Who is winning ?
The first criteria and the most used, both by engines and humans is the number of pieces. As you can see on the board below, it often offers an accurate response.
But this isn’t always the case. Who is winning in this one ?
Here Black has more piece but White can easily win this game (By checkmating Black with his rook). While the number of pieces is a criterion there are dozens of other parameters that good chess players take into account. Here is a non-exhaustive list of criteria used by Stockfish to compute the evaluation function :
- Total values of the pieces on the board
- Pawn structure (Doubled pawn, passed pawn, etc)
- Mobility of the pieces (Number of squares available)
- Number of threats
- Number of central squares covered
- Player turns
- etc…
So, to evaluate accurately a position, an engine assigns points to each side for all the criteria above and the side with the most points is the winning side. This approach allows to know both who is winning and by how much. The greater the margin is, the better the position is. But it induces arbitrary choice in the manner which points are awarded. This can create bias which causes the engine to not play the best moves. So we need a way to choose the number of points for each criterion.
2) Choosing the criteria points
One rule chess beginners learn is that a pawn is worth 1 point, bishops and knights are worth 3 points, rook is worth 5 points and a queen is worth a grand 9 points. This simple rule allows for quick calculations over the board.
Modern Engine uses a much more precise system. Every criterion is associated with a value in centipawn (1 hundredth of a pawn). To determine the value in centipawn associated with each criterion, Stockfish uses a program called Fishtest. It allows volunteers to let different versions of Stockfish, each with a different number of points for criteria run on their computers. From the result of all the games played, we can infer the best points distribution. At the time of writing, Stockfish has played 1,731,450,347 games against itself, for a grand total of 2592.59 years of CPU time. No wonder it can beat humans, it has a little bit more experience !
3) Tapered Evaluation
Another subtlety about the evaluation function is that the criteria evolve during the game. It is usually advised to hide the king during the opening but use it as an offensive piece later on. To account for this kind of inconsistency, Stockfish uses two evaluation functions, one with rules for the opening and middle game and one for the endgame. To determine when each phase starts, Stockfish uses the number of pieces left on the board. But this would lead to a discontinuity in the evaluation function when we start the endgame. To ensure a smoothed evaluation, Stockfish computes a weighted average of the middle game and endgame evaluation functions and change the weight during the game. Consequently, the middle game evaluation counts more during middle game and the same for the endgame.
But the evaluation function isn’t enough for an engine to play chess. It needs a search function to answer a much more important question : Which move should I do next ?
II) The Search Function
To represent futures moves, engines use decisions tree. At the top (the root) is the current position and each possible position is then represented by a node. Engines then use the evaluation function on each of theses possibles moves and choose the best move with the Minimax algorithm.
1) The Minimax algorithm
The idea of the Minimax algorithm is that, in a zero sum game (game where there is no possible cooperation such as chess) one should always assume his opponent will play his best move and play accordingly. We search not the serie of moves that will give us the biggest advantage but the one that will give the biggest advantages while leaving no counter play to the opponent.
For example, look at this diagram (Below each diagram is the evaluation of the board) :
If an engine plays as White, the moves that leads to the highest score (on the right) shouldn’t be chosen because it will loose the game if his opponent plays well. On the other hand, the left part of the tree leads to a decisive advantage, whatever Black plays.
The Minimax algorithm is enough to ensure that, out of all the moves searched, the best is selected. But, because chess is a game with a astoundingly high number of possibles moves, it is impossible to search the whole tree until we reach a mate position. So engines can only search a few moves ahead. To be able to search as far as possible, engines “prune” the tree of positions using a method called alpha beta pruning.
2) Alpha Beta Pruning
The intuitive idea behind alpha beta pruning is the following : Suppose you are searching the best move to play. You have found a good move but you continue to search to make sure it’s the best. You test a second possibility but find that, if your opponent plays it well, he will mate you in 2 moves. So you can stop looking at that variation because it’s sure your opponent will play it if given the occasion.
To get a better feeling of how pruning works, look at the diagram below :
Each node represents a position with its evaluation. The engine starts by going to a fixed depth (4 here) and evaluates the positions. It then selects the position with the highest score for White and the lowest for Black (For example, on the bottom left, Black has the choice between ⑦ and ⑨ so he chooses ⑦. But 1 rank up, it’s White turn and he chooses ⑦ over ②. Here, pruned part of the tree are in grey. On the bottom left, White knows that Black will go for the position with 2 points if given the choice. As on the other hand there is a ⑦ and a ⑨ and ⑦ > ②, there is no need to evaluate the other possibilities of the branch with the ②. They are therefore pruned. The same reasoning can be applied for the right part of the tree.
3) Pruning Efficiency
Pruning can be very efficient but it depends on the order in which you evaluate the moves. For example, look at the trees below :
It is the same tree but with a different branch order. On the right is the same tree as above, but on the left is the worst case scenario for pruning. As we can see, we didn’t prune a single node in the worst case scenario. Pruning only occurs when we are sure that a branch is better. So chess engines use techniques called moves ordering to order the tree so that it is pruned as much as possible. But there is no way of knowing which series of move is going to be the best or we wouldn’t be searching. So engines have to rely on heuristics (methods that usually works but without guarantee) to try to order the tree and get the best pruning.
4) Move ordering
One method to order moves is called iterative deepening. It is represented below and the number on the node here indicates the order of evaluation.
The idea is to evaluate at low depth then reorder the tree with the information gained from the evaluations to search the most promising branch first and make a more efficient pruning of the tree. The process is then repeated until the allocated time is exhausted.
5) Time Management
Time management is critical for engines because a fast engine can make a deeper search. So there are numerous strategies to save as much time as possible.
For example, engines uses parallel computing to evaluate several positions at the same time. Stockfish has been built to run with up to 512 parallel threads.
Engines also uses tables, either for opening or for endings. Instead of searching the best move themselves, they can just look it up in the tables which is faster. One of the most advanced ending table, the Syzygy database solved every possible ending with up to 7 pieces. The total numbers of positions is 423,836,835,667,331 which is stored on 18.4 TB.
Last but no least Engines uses transposition tables which means that they store evaluated positions during the game. That way, if a similar position arises but after a different move order, engines don’t have to recompute this part of the tree. It is also useful to avoid re-evaluating moves later in the game if they were already explored.
6) Conclusion
That’s it ! There are a lot more to say about the subject and chess engines don’t all uses the same techniques but you now know what are the basic principles behind them.
If you want to learn more about chess engines or how to make one yourself, a good place to start is the wiki at chessprogramming.org
Lime Tea 