An In-Depth Look Into How Engines Find the Best Move

For example, if the evaluation is +0.79, this means that White has a clear advantage. However, if it is -3.65, this means that Black has a decisive advantage equal to 3.65 extra pawns.

Part 2: Weight Of Factors

The engine looks at the position that arises from a move that is played. It can then assign the aforementioned evaluation number to that given position.

Material

Material is the most important and highly weighted factor in a position. However, engines do not use the material weight system we see in most chess games. The table below has the common method of material:

Engines use centipawns, or .01 of a pawn to make the weight of a piece even more accurate.  Grandmaster Larry Kaufman who worked on Deep Blue proposed a more advanced piece value system after using an engine to conduct tests with hundreds of thousands of games. His method is the following:

This is not only what chess computers use for their piece weights. They can use relative value, which is the value of a piece based on its unique activity or potential to become active. For instance, in a closed position, a knight will be worth more than a bishop. Along with this, a rook pawn can only capture one square versus the usual two, therefore it is worth slightly less than the other pawns. In the example below, Rashid Nezhmetdinov sacrifices his queen against Oleg Chernikov for only two minor pieces. He does this because when his knight lands on d5 and his bishop on d4, he can take advantage of the weak dark squares around the king. Those two minor pieces were more valuable than his queen because they were the only things holding his opponent's position together. This sacrifice led him to win the game. Check out the full game here: chessgames.com 

This is the second most important factor that must be considered when an engine is doing its calculations. As a human, it is quite easy to tell whether a king is safe or exposed. But an engine must look for finite factors and weigh each to get an overall safety evaluation. Most engines do this differently, as there are many creative ways to test for king safety.

Before an engine castles, it must take into consideration the safety of that spot. It is important to have a shield of pawns in front of the king, and these should be immobile or moved up one square to ensure maximum protection. It must also consider the possibility of a pawn storm that creates holes in the king's shield. Semi-open files in front of the pawn shield are unfavorable as well as it can lead to high amounts of pressure against the monarch.

There are more unconventional methods of evaluating the safety of the king that not all engines use. One of these is Virtual Mobility, where the program can replace the king with a queen to see the opponent's ability to move in a horizontal, vertical, or diagonal line to the king. It is also used to determine how open the king is.

Another technique we see is scaling. Scaling is putting more weight on a certain aspect of king safety depending on factors such as material. For instance, if the pawn shield around the engine's king is damaged, it may try to exchange pieces to alleviate the danger.

Engines may struggle with common tactical patterns which can limit their tactical ability and how they are able to recognize their opponent's threats. The chess programming wiki gives an example where a minor piece sacrifices itself on g5 or g4 while it is being attacked and defended by the h-pawns at the same time. Hard-coding these fixes the gaps in the computer's tactical vision.

The most complicated evaluation method is square control around the enemy king. Control of a square is if one side has more pieces "looking at" at square than the opponent's. However, if a pawn controls a square, it is typically out of the question for the opponent's minor or major pieces. In the position below, we see the square control over e5. We rule it with four of our pieces including two pawns (note that the bishop protects that square through the pawn), while Black controls it with two pieces and no pawns. We can safely say that e5 is in our possession.

Pawn Structures

The pawn structure of a position is the placement of all pawns, disregarding every other piece. Pawn structures are especially important in the endgame when the game becomes all about the small pieces. Having a better pawn structure is a positional advantage, not a material one.

Certain pawns are very bad and can become targets of attack for your opponent. A backward pawn has both pawns beside it placed in front of it, and cannot safely move forward. Because they are so immobile and hard to defend, they are easily attacked and often overwhelmed. Doubled pawns are two pawns of one color on the same file. An isolated pawn has no other pawns of the same color on either file beside it. Both these and doubled pawns share that they are not defendable by the pawns beside them, making them weak.

Other pawns are particularly good, such as a passer, which has no other pawns in front of it on its own or adjoining files. The opponent may be forced to sacrifice a piece for it to prevent it from becoming a queen. This loops back to material gain, which is the most important factor to the engine. The position below shows a passed pawn that cannot be stopped from promoting.

Central Control

Control of the center is a very important part of chess, and is one of the main goals in the opening. It gains space and gives the pieces good squares to be developed to. Having a strong center can help with both defense and attack, because your pieces will have greater mobility. If you go on the chess.com analysis, it will recommend e4 or d4 as the best first move because this controls central squares and immediately puts a piece into the center of the board. In the diagram below, the red squares represent the direct center and the blue squares being the extended center. 

Part 3: Game Trees

A game tree is very much like how it sounds, it is a tree of all possible combinations of moves. In the context of chess, it is every legal move from each legal move before, going on for whatever the depth of the engine is. Depth is how many moves ahead the engine will make the tree out of. For example, if the depth says 24, the computer is calculating 12 moves for each side. An example game tree is shown below:

As you can see, the depth here would only be 4. When thinking of a typical chess position, there are not only five or two moves you can make, instead close to 20 or 30. This makes each step on the tree grow exponentially. For instance, in the starting position of any game of chess, you have 20 legal moves, and from there your opponent has 20 legal moves. That means that only two moves into the game, there are already 400 positions for the computer to evaluate.

Thinking practically, it would be inefficient for an engine to spend valuable time evaluating 15 moves after a queen blunder that leads to nowhere. Instead, the computer can use pruning. Pruning is where complete branches are cut off the game tree that seemingly are just bad moves. If we prune our tree above, it might look something like this. Now that is a lot less positions.

There are two types of pruning.

Alpha-Beta

Alpha represents the lowest evaluation score needed to exceed the previous one. Alpha is returned from the evaluation search if it "fails high". This means that the engine found a continuation that is better than the previous one, and the opponent has a move to prevent this winning position. We must assume that they will play this. Here is a quote by Bruce Moreland about failing high, "A fail-high indicated that the search found something that was 'too good'. What this means is that the opponent has some way, already found by the search, of avoiding this position, so you have to assume that they'll do this. If they can avoid this position, there is no longer any need to search successors, since this position won't happen."

Beta is returned if it "fails low". Failing low means that if we were playing White, the position found does not have as high a score as a previous guaranteed score. Therefore, we will not make that move because it is worse than another. Here is a quote by Bruce Moreland about failing low, "A fail-low indicated that this position was not good enough for us. We will not reach this position, because we have some other means of reaching a position that is better. We will not make the move that allowed the opponent to put us in this position."

Backward Pruning

This is the safest form of pruning as you only do it when a position has been decided. For example, if the engine has found a forced checkmate, Mate Distance Pruning will cut branches of the tree where there is no shorter mate. This is simply to find the fastest checkmate possible. It will not add any playing strength to the engine, but can be useful in solving mate in ___ puzzles. 

Part 4: Fortresses

While engines are typically correct about the "best" move, there are some positions that humans understand better than them. An example of this is a fortress, where one side seemingly "should" be winning, but there is no way to break through. An example of a fortress is shown below, where though Black has an overwhelming material advantage, they are stuck behind their own pawns and has no way of moving them out of the way. As long as White only moves their king back and forth, the game will be drawn by the 50-move rule.

Conclusion

In conclusion, engines use evaluation to assess each position, or leaf, of the game tree it creates. Evaluation is built off of many factors such as king safety and material that are each weighted differently in terms of importance to the engine. To reduce the amount of calculation, the computer can use pruning to cut off bad lines from the game tree. Even with all of these resources, the engine still has trouble understanding positions like fortresses.

It is important to note that I am not a chess engine programming specialist. While I covered many topics in this article, it is only the tip of the iceberg. However, if you want to learn more, visit the chess computer wiki at: chessprogramming.org. They even have resources on how to code your own engine if you are interested in that as well!

Back to Top