#13 How chess engines work
#13 How chess engines work
Stockfish might incorporate a neural network in the future
Stockfish, one of the most famous and powerful chess engines, may incorporate neural networks for the first time to remain competitive against recent developments like LeelaChess Zero. I thought it would be a good idea to go through the current codebase and available documentation before the current version is relegated.
The key ideas behind Stockfish are to search across all possible positions from the current position (which is not possible even with the current form of computers) based on a depth-first search of a tree representation of the game state smartly choosing not to evaluate certain lines based on heuristics which are defined by the programmers based on thousands of past games. There is an evaluation function which is based on things like board material imbalances, assigning hardcoded bonus to certain material in certain formations and positions on the board (piece square tables). For example, doubled pawns (two pawns on the same file, after an adjacent pawn captures opposing piece has its penalty in the code.)
It is interesting to mention that Stockfish uses compute from volunteers to test its code changes (something like Folding@Home.)
Roughly speaking, a traditional chess engine does the following steps -
Initialize the internal data structure representation of the chessboard, game state, hash tables for caches, and populate the solved endgames database.
Check if the current board position is a draw, checkmate, three folds repetition or has a solved endgame. If not, evaluate.
Evaluation - Based on certain pre-defined penalties and bonuses, do a depth-first search with certain optimizations and heuristics and return a score for the position. Cache evaluated positions in case they arrive later.
Stockfish has been consistently winning the online Chess Engine competitions, except recently when it was defeated by AlphaZero and LeelaChess Zero. It is also the most popular choice across online chess websites and chess enthusiasts.
Key search ideas
Minimax and alpha-beta pruning
Some CS stuff first. Below is a minimax tree. Imagine the nodes as being derived from certain chess position states. A chess engine given a current state has a finite computation power to lookahead a certain number of steps. Given that say white has played, the next level would be black’s choices and so on. Assuming an optimal player making perfect choices to minimize our return, while we work on maximizing it. This is the simple way in which Chess engines’ search for moves works. Here is a nice allowed by license image from the wiki if that helps.
Since minimax has an exponential time complexity, anything to cut down on branch exploration would help. Stockfish uses alpha-beta pruning to reduce the number of states it has to look at. Both players will maintain two values alpha and beta representing the minimum value the player looking to maximize the value is guaranteed and the maximum value the player looking to minimize is guaranteed respectively. The idea is that given a certain value in a particular branch, there is no point to explore another sibling which has a higher value.
Quiescence search and iterative deepening
One of the disadvantages of searching up to a fixed number of future steps is that certain interesting turn of events are cut off and not pursued further since we have run out of the steps just when things start to look interesting. At the same time, a branch where nothing interesting is happening is still being explored to the fixed amount of depth. In the case of Chess, interesting events that might need further depth would be piece captures, promotions, and checks. Imagine a particular line of the tree where a pawn can be promoted for sure to a queen at depth 29 and we are hardcoded to limit the search to 30 moves. Stockfish’s search() calls the qsearch() function when the remaining depth count hits zero.
Transposition table
Computing positions that have already been computed before (though arriving from a different move order) is a waste of time. Stockfish uses a cache called a transposition table to keep track of board positions that have been evaluated in the past in the context of the current game.
Heuristics & enhancements
Further enhancements and heuristics are used to cut down on the number of states to explore. Stockfish uses futility pruning where for the parent nodes of the leaf nodes, it adds a buffer margin (or futility margin) to the current best value and if even adding that does not improve the result, there is no point exploring the leaf nodes. Stockfish also does null move pruning, where before going for a full-depth search it does a reduced depth search with the opponent to move. If even this does not improve the beta value in alpha-beta pruning, there is no point in exploring that branch to the full depth and we save on computation.
Board representation
Bitboards
Like in some other games, pieces on a chessboard are represented by a single bit. This is convenient for chess since most commodity computers are 64-bit and chess has 8x8 or 64 positions. So, for example, a single 64-bit integer can store the positions of all white pawns, another 64-bit number can store the white king position, and so on, marking them as set bits, while others vacant positions are marked as zero. The main advantage of storing the board positions as numbers is that it enables fast arithmetic when we have to find information such as attacks or count pieces, some of the operations supported natively by microprocessors. The position states of a game are also stored as a deque which also enables detection of a draw by repetition.
There were some bits of nostalgic bit magic that do not suit say the simple over clever philosophy of Python. E.g. Enumeration of subsets -
Zobrist hashing
Since the number of possible board positions is large, it is infeasible to have a tabular lookup for all positions. Instead, we use a data structure called a hash table which, given an input (can be text, image, board position), apply a certain function (aptly called the hash function) which generally gives a fixed length and smaller length output. Since the output space is some order of magnitudes smaller than the input, there is a possibility of collision. One of the key requirements with transposition tables is to have a hash function that hashes arbitrary board positions to hash values (think large numbers). Another key requirement is that calculation of hashes using the hash function should not take a lot of time (sometimes the inverse is true in hashing though, e.g. in-case of a cryptographic hash function used in security.) Zobrist hashing uses the XOR function which has a key property of being its inverse (a XOR b and then the result XORed again with b is a.) The key idea is to assign a random number to all possible position and piece combination and then XOR all of them and some extra information like castling rights, thus allowing incremental hash key updates on each move instead of recomputing using the entire board info on every step.
FEN representation
Stockfish uses the FEN (Forsyth–Edwards Notation) for accepting game state. FEN is one of the standards that uses ASCII characters to save and restore the game state. FEN stores the information of each of the eight ranks, the next turn color, number of moves, etc. For example, the FEN representation of game start is below -
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
If you would like posts like this to be delivered to your inbox every weekend, please subscribe for free.
Position evaluation
Stockfish has a hardcoded Piece-Square Table (PSQT) that provides bonus scores for pieces in different positions on the board. These scores differ based on if we are in the middlegame or endgame. For example, a Bishop might be worth more in the endgame with a lot fewer pieces than the generally cramped middlegame. Below is the table from the Stockfish codebase for Knights and Bishops. The pair scores are for the position in middlegame and endgame respectively.
As mentioned earlier, some specific conditions on the board are penalized or given a bonus based on human analysis and intuition. For example, a rook can move straightforward so it makes more sense to have it on an open file free of any obstructions like a pawn.
Given a board game evaluation, the win probability is calculated by a third-order hardcoded polynomial that has been derived from the data based on test games that are running Fishtest across hundreds of computers that choose to participate in running Stockfish tests. Note the interesting parameter called centipawn which is also being calculated here, is a made-up number that represents a material advantage to a side during the game. A pawn is assigned 100 centipawns, other pieces are generally assigned as follows - 300 centipawns for knights and bishops, 500 centipawns for rooks, and 900 centipawns for queens. A considerable number of people have researched the value to be assigned to pieces, which more or less agree on the above numbers, though some placing bishops and particularly having bishop pairs at a slightly more advantage than say a pair of knights.
Some general heuristics for evaluation of positions which work for human or computer gameplay are -
Developed minor pieces (i.e. Knights and bishops not sitting idle on their original squares) are good.
Controlling the four center squares is good.
Having a pair of bishops vs a bishop and a knight is good in open games.
Castling is good. Losing the right to castle is bad since it would take additional moves to move the king to safety from the center of the board.
Connected Rooks (protecting each other) are good.
Doubled pawns are bad. Isolated single pawns are bad too.
Passed pawns are good. Adjacent passed pawns are even better.
Endgames
A game is called solved when you can definitely output the result given a current state and even when both players play optimally. While Chess as a game remains unsolved, some endgame states involving few pieces (6-7 in total counting both sides) have been solved and a database has been created for such game states. Stockfish uses one such database by the name of Syzygy. This pre-computed result allows Stockfish to predict mating positions several moves in advance near the end of the game.
For example, reproducing a portion of Stockfish code above for the Rook and pawn vs Rook endgame below shows a checkmate for white in 10 steps. Some endgames require more than 50 moves without a capture or a pawn move, which is not good since the opposition can claim a draw under the current Chess rules.
Other features
Time control
Time management is of utmost importance in chess engines. Instead of allocating a fixed time each move, Stockfish includes code to compute an optimal duration to process a game state depending on the current status. Stockfish also supports a ‘ponder’ mode where there is speculative calculation happening while the opposite player is thinking during their move.
Strength handicap
Chess governing bodies around the world use the Elo rating format for ranking players. The standard Stockfish is way above human chess playing capabilities even on a laptop. To give a comparison, the latest Stockfish is around 3800 Elo while Magnus Carlsen, arguably one of the greatest chess players in the history of the game is just below 2900 (though both may not be directly comparable due to Elo being relative and both playing different pool of players). To enable better training and gameplay, a setting has been provided to decrease the strength of Stockfish. This is done by selecting top N candidate moves and then probabilistically choosing one of them, favoring non-optimal ones in case of lower ratings. UCI (Universal Chess Interface) which is used by most modern chess engines includes a parameter to specify engine strength.
Chess960
Stockfish supports playing Chess960, a variant in which the major variation is that minor pieces do not sit on the traditional squares. Chess960 has been recently approved as a valid Chess version in addition to the traditional chess, with the first Chess960 championship held last year. Bobby Fischer, one of the game legends, presumably got bored of playing normal chess and tried to encourage Random chess, variants of which existed even before his time. A modified FEN representation is used in Stockfish to represent Chess960 games.
This was a different kind of post than what I have written in the past three months. Let me know if you would occasionally like more such posts with code and tech. Or not. See you next weekend.