Game Theory: How Stockfish Mastered Chess
Game theory is utilized in the development of computer engines which play chess and also other turn-based games. The most popular and strongest engine to date is Stockfish so we will be considering how it uses game theory.
Chess is a deterministic game which means that one can infer what the evaluation of the position is just based on logical concepts, without having to traverse the roughly 10^120 nodes to all final game states possible (Shannon’s number) which is, of course, unfeasible. However, since chess is not fully deterministic there is an element of randomness. This means engines must take a probabilistic approach to maximizing their chances of winning. Although, theoretically, any arbitrary chess position only has one of three evaluations (0.0 (draw given perfect play from both sides), #n (forced mate in maximum of n moves by white), -#n (forced mate in maximum of n moves by black)) Stockfish uses a probabilistic approach to generate a decimal which is significantly negative if it thinks black is winning, significantly positive if it thinks white is winning and close to zero if it thinks the position is drawish. At times it can calculate a forced mate for either side in which case the evaluation will be either #n or -#n (strictly dominating and dominated strategies) and a forced draw with perfect play in which case it outputs exactly 0.0 (pareto-optimal strategy, neither side has a payoff). The unit for evaluation is centi-pawns which is intuitively unclear but generally anything more than a magnitude of 1.5 is significant (human masters will almost certainly convert this to a win) and anything more than a magnitude of 4 is completely winning or losing. The mixed Nash equilibrium maintains a similar concept – there is no pure strategy, akin to a “forced” line in chess, but there are probabilistically best approaches which are represented as a mix of decimal probabilities. However, the difference is that in the mixed Nash equilibrium we play each move with their associated probabilities while engines play whichever move has the highest probability of winning.
Stockfish uses a static evaluation function, or a function which calculates an estimate evaluation of the position using a heuristic (a manually constructed algorithm designed to fit any arbitrary chess position) which has been hand-crafted by computer scientists and chess grandmasters for over a decade. Since the evaluation function is very powerful we can assume it will do a good job most of the time to evaluate a position. However, this is not enough for a game as complex as chess – it is a Dynamic Game as opposed to a simultaneous-move game and involves niche game tree paths which can never be fully encapsulated in the problem space of an evaluation heuristic. There is a high probability that the function will evaluate a position as winning and miss a line or path of moves by the opponent which causes us to actually lose. It can also evaluate a position as losing and miss a line which is actually winning. The static evaluation function capitalizes on the deterministic nature of the game, however we need to do more to deal with the element of randomness. Hence, it is necessary for the engine to be able to calculate into the future.
Stockfish uses a calculation method known as minimax. In the minimax algorithm, Stockfish considers a set of potential strategies (current moves which can be played) and the best strategies that can be utilized by the opponent as a response to each strategy. This leads to a game tree in which each “layer” alternates between white and black’s moves and the tree grows exponentially in size. This is an extensive-form game representation since the board position is constantly changing as moves are played. Once calculation comes to a halt, the tree propagates the evaluations of the leaf nodes up the tree such that each node contains the best evaluation that a player can achieve given perfect play from both sides. For example, if we are in a “white” layer such that it is white’s turn to move, the node’s value should end up being that of the leaf node with the highest payoff for white given perfect play from both sides to full depth. Since the minimax tree grows exponentially, it is incredibly important to be able to prune the search tree effectively.
One pruning method used by Stockfish is alpha-beta pruning. The engine first lays out it’s potential strategies from the current node in the game tree in order of their promise. The moves with higher promise, or a higher static evaluation payoff, are considered first (known as “late move reduction”). Say the current best evaluation white can go for is A (alpha) and the best evaluation black can go for is B (beta). The only reason white would want to calculate the next sibling node is if white has the potential to get a higher evaluation or payoff for the sibling node (P(sibling) > A). However, if black already has the option to change the path of the game state earlier/higher in the tree such that black receives a better evaluation or payoff than the current node (B < A) then it is in black’s favor to go down that path instead. Hence, assuming best play from our opponent, it is useless to traverse the sibling node and we prune the search. We are ignoring “This pruning only pays off if the order that moves are considered in is truly increasing in quality/strength because that maximizes the chances of pruning as a depth-first search occurs on the game tree.
Stockfish utilizes a combination of minimax with alpha-beta pruning and a powerful static evaluation function to maximize the probability of playing a winning move. The developers of Stockfish designed the static evaluation function to consider the most aggressive and tactical options first (captures, checks, and deeper tactical ideas) in order to lead to “sharper” and more forcing lines so that the probability of a missed sideline is minimized. It also uses other strategies such as null-move searching, where it simply replaces the opponent’s moves with “null” moves and makes a succession of moves for one player to gain some insight into tactical and sharp ideas. The engine then utilizes minimax calculation to consider the opponent’s threats to minimize the chance of error.
– Mohammad Hamzah
https://en.wikipedia.org/wiki/Late_move_reductions
https://www.chessprogramming.org/Null_Move_Pruning
https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-4-alpha-beta-pruning/
https://arxiv.org/pdf/2109.11602.pdf#:~:text=Stockfish%20uses%20the%20alpha%2Dbeta,player%20will%20redirect%20the%20game.