Today, we notice that some chess engines/IA, including the best, participate in championships between computers – the most famous being the World Computer Chess Championship and the Top Chess Engine Championship. Their level is now largely superior to the best human players. It is therefore natural to ask this question: will artificial intelligence soon put an end to human chess tournaments? This article answers this question by analyzing in depth the recent evolution of artificial intelligence in chess thanks to neural network algorithms that can still be improved.
The game of chess, dating from the 15th century with the current rules, is so complex that the game is not solved and may never be solved. A solved game is a game for which the outcome (win, loss, or draw) can be correctly predicted from any position, assuming that both players play perfectly. The complexity of solving this game can easily be seen by determining the number of unique games that can be played: 10120 (a 1 followed by 120 zeros), which is an inconceivable number, considering that the estimated number of atoms in the universe is “only” 1080…
Chess programs are one of the oldest fields of artificial intelligence (AI), having started in the early 1930s, but only recently overtaking humans in this game. Artificial intelligence in chess was brought to the forefront in 1997 when Kasparov, who was then the world chess champion and one of the best players of all time, lost to IBM’s Deep Blue AI. It was from this match that human superiority in chess began to be threatened.
Today there are many chess engines/IAs, the best of which even participate in championships between computers – the most famous being the World Computer Chess Championship and the Top Chess Engine Championship. Their level is now largely superior to that of the best human players. The four most successful AIs are Stockfish, Houdini, Komodo, and LeelaChessZero.
Chess concepts
The most successful chess engines rely on a combination of concepts and algorithms that allow them to reach a level of play far superior to human players.
One of the most important concepts for most AIs is to assign a value to each piece in the game, which the algorithms use to find the best moves. The commonly accepted values are the following: a pawn is worth 1 point, a bishop 3 points, a knight 3 points, a rook 5 points, and the queen 9 points – the king has no value since it can’t be captured. By counting the number of points that the total number of pieces on the board is worth on each side, you can tell if one player is ahead or if the game is balanced at a given moment, depending on the pieces captured. For example, capturing a bishop and a knight (6 points) is generally considered slightly better than capturing a rook (5 points).
Some concepts derived from human chess theory studies are part of chess engine algorithms. Among them are:
● Center control: the player who has best controlled the center (especially the four center squares), i.e., having the most pieces aimed at or on the center, gets a more advantageous position.
● Piece development: a player who has moved more pieces out of their initial positions than his opponent will have an advantage for the rest of the game.
● King safety: it is easier to threaten checkmate to a king not surrounded by allied pieces than to a king hidden behind a fortress of pawns.
● Material imbalances: if a player’s total remaining piece values are greater than his opponent’s, then he has an advantage.
● Pawn structure: for example, if a player has two or three pawns on a single file, then his position may be more complicated to play than his opponent in the long run.
Chess engine algorithms
The best current chess engines are composed of two parts: a search algorithm to provide a restricted selection of good moves, and an evaluation function to choose the move to play.
Two search algorithms mostly used are the Monte Carlo Tree Search (MCTS) algorithm and alpha-beta pruning.
These algorithms explore the tree of possible chessboard configurations, represented as follows (see diagram below): each node in the tree is a configuration on the chessboard at a given moment in the game, starting with the initial game configuration at the top of the tree (first node). Each child node (descendant of a parent node) is the configuration on the board after playing one move after the parent node’s configuration. All child nodes, therefore, represent the moves that were playable when the parent node was configured.
For example, you can record for each configuration the number of simulations played that went through that configuration, as well as the number of wins, and select some of the best possible moves by choosing nodes with the highest win percentages and/or nodes that have not been explored much.
This is how the LeelaChessZero engine works in part, by applying the MCTS algorithm to make a pre-selection of a few good moves among all possible ones.
After this pre-selection, chess AIs use an evaluation function to choose the move to play. This function can take for example the form of a weighting of a set of criteria determining an advantageous or bad position, such as:
c1 * material imbalance + c2 * piece development + c3 * king safety + c4 * center control + c5 * pawn structure + …
The move chosen will then be the one with the configuration that maximizes the evaluation function. It is a function of this kind that Stockfish used until 2020. However, since the advent of neural networks or Deep Learning, new engines such as LeelaChessZero, created at the beginning of 2018, have been created using a neural network. This algorithm itself creates the evaluation function from a large number of game simulations. This revolution in chess artificial intelligence caused the designers of Stockfish to modify their AI by implementing such a neural network, which increased its already high level. Another point to note that gives such a high level to chess engines is the computational depth: they can calculate a huge amount of configurations, and evaluate the configurations after the next 30 moves, for example.
To illustrate this idea, in a match between the AlphaZero engine – the predecessor of LeelaChessZero – and Stockfish in 2017, AlphaZero was looking at 80,000 configurations per second, while Stockfish was looking at 70 million configurations per second. Despite this huge computational differential, AlphaZero was the winner after several games. The key to AlphaZero’s victory was the implemented neural network that created a better evaluation function than Stockfish’s in 4 hours of simulated games, which gave AlphaZero an advantage in this competition.
Endgame tablebase
In addition to all these algorithms, AIs store endgame tablebases in their memory. An endgame is commonly referred to as one where the number of pieces remaining on the board is very small. An endgame tablebase is a database that contains endgame positions in chess and their theoretical evaluation with a perfect game (draw or win of one side, and the number of moves before winning). Thus, AIs can try to avoid or reach a given position. Such endgame databases are generated using, among other things, a form of retrograde analysis: the positions of three pieces are used to analyze the positions of four pieces, the latter participate in the generation of those of five pieces, etc.
In general, the database records every possible position with some pieces left on the board, and the best moves depending on whether it is white or black to make the next move.
For the moment, tablebases have been set up for endgames up to 7 pieces (2 kings + 5 pieces). For endgames with 6 pieces or less, all positions have been studied (nearly 4000 billion). For endgames with 7 pieces, the situations including a single king facing 6 pieces of the opposite color have been ignored (because the solution is too obvious for the side with 6 pieces), but the number of positions analyzed remains gigantic (more than 400 000 billion). Research on the creation of tables with 8 pieces is in progress.
Some engines integrate these endgame tablebases, allowing them to play perfectly without calculating when the number of pieces on the board is less than 8.
Will artificial intelligence soon put an end to human chess tournaments?
AIs in chess, despite their recent evolution thanks to neural network algorithms, are not yet ready to solve most of the positions, it is still impossible for them to predict how a game will end at a given moment, on a win or a draw, except for endgames with 7 pieces or less. The huge number of unique playable games means that chess AIs are not yet ready to solve the majority of setups, despite their near-perfect level of play.
Finally, even in the case where artificial intelligence solves a large number of chess positions, it will be impossible for human players to remember all the move sequences according to the opponent’s moves, as there are too many variants to remember. The best players in the world already prepare themselves before tournaments with chess engines to analyze some variants of the openings or first moves most played by their opponents. However, the results are not always there even when the beginning of the game has been analyzed in advance, because the players can’t remember the middle of the game, as there are so many different configurations. Also, the course of the game depends largely on the moves of the opponent, who can choose at any time to break out of an already known variation by playing unexpected moves.
In conclusion, artificial intelligence may have surpassed humans, but the appeal of chess and human tournaments is not about to disappear.
