
How Do Chess Engines Work?
Chess engines have existed since the 1950s, but at the time a strong human could easily beat one. Yet after Garry Kasparov lost to Deep Blue in 1996, this time period ended and a new reign began, one of the computers.
But how does an engine think, calculate, or find the best move? Is it similar or different to how you or I see the board? I would be lying if I said it were simple, but it is much more logical than you may think.
How Does An Engine "See" the Board?
Chess engines use "bitboards" as a way of representing where each piece is on the board.
For example, say white pawns are stored as a value of 1 and black pawns have a value of 2. The computer will see...
Computers can use this form of visualization to, for instance, recognize certain pawn structures and common themes on how they should play based on these. An example of this arises in the position below after 1.e4 c5 2.Nf3 e6 3.d4 cxd4 4.Nxd4 a6 5.c5, which features a Maroczy Bind structure.
The computer also stores other variables1 such as whose move it is, if en passant is possible, if castling is possible, etc.
All of these factors contribute to how the engine views the chess board, but bitboards are the main features.
Game Trees In Engines
A game tree is the beating heart of a chess engine. It is every state in a game, and each state from that state, etc. If that's sounding confusing, here's an example.
In a given chess position there are 5 legal moves. From each of those moves there are 2 legal moves, and from each move there, there are either 1 or 2 legal moves. The game tree would look like:
This is an extremely simplified version of a game tree. In the example, we would only see a depth2 of 1.5, and very few moves. In an actual position, there would most likely be around 30 or more legal moves to start, then 30 moves from each branch. That is already 930 legal moves the computer analyzes from only a depth of 1. In our browser-based computer, the depth is around 20x higher.
This may seem like a lot, but for a serious engine, it is impractical to calculate so many variations when most will lead nowhere. So, the computer can use a function called pruning to cut down on how many variations they calculate, making finding the best move take less time. Pruning is where they cut off certain variations on the game tree that seemingly lead nowhere. This can lead to missing a tactic every once in a while, but it is worth it to limit how much time the computer spends calculating.
An example of pruning being the cause of a missed tactic is in this study where it takes the engine some time to find the mate in 5 for white. At first, the position is evaluated as around equal, but after some time the computer sees the killer blow. Can you spot what the computer has trouble with?
How Does An Engine Analyze?
The most important part of any engine is finding the best move in any given position. They do this by weighing certain factors such as king safety, piece activity, material, and others. Each factor has a weight that contributes to the overall "score" of the position. For example, king safety and material will have a greater weight than how good the pawn structure is.
The score of a position is in relation with the weight of each piece, such as how a pawn is 1 point and a rook is worth 5. If the score of a position is +3.5, the position is so good for white it is as if he is up a knight and half of a pawn. Conversely, if the score is -0.72, it is as if black has an advantage of 0.72 of a pawn. If there is a plus sign in from of a score, it means white is winning, and vise versa for a minus sign.
This table shows what each scoring means in terms of winning or equality.
Glossary
1. A variable is a storage location represented by a word or symbolic letters that stores a value. For example, if the computer stores x = 3, then the following equation would be: 2 + x = 5.
2. Depth is a number that represents how many "half moves" or moves by a single side they consider. For instance, if the Stockfish you are using has a depth of 20, it will calculate 10 levels of the game tree for each side.