Checkmate for Traditional Chess?

The chess hype that the Netflix series ‘The Queen’s Gambit’ has sparked is unprecedented. eBay revealed there was a 273% surge in searches for ‘chess sets’ on the auction site in the weeks following the show’s release [1]. The series follows this clearly brilliant girl emerging in the US chess world. It is, however, notable that even she cannot perform at the top simply on her own merits. Studying others’ theories, having a geek-team, and the occasional pills give her an edge. All these factors support a common goal: to help her study as many paths and combinations as possible. When stating it like this, it sounds very well optimizable, so let’s see how far we have gotten over the years. Written by: Tamara Dert and Luuk Sommers

Our modern version of European chess can be traced back to the fifteenth century. Throughout the years, the rules of the game varied a bit to make the game run faster. Pawns got the ability to move two squares in their first move and Queens could go ‘mad’ as the Italians liked to call the abilities of the modern queen. These kinds of changes made the game more accessible, but the base remained the same. For quite some time chess had clearly defined rules, having complete information for all possible states while each state can be evaluated. Therefore, it is a beautiful problem to target with math. So, why has chess not been ‘solved’ yet? 

Combinatorial Complexity

The answer is simple, although the field of chess is only eight by eight, it is too complex. If you try making a decision tree you will soon find an exponential explosion, as visualized in Figure 1. At the start of a game, each player has sixteen pieces with a total of twenty possible moves (two for each of the eight pawns, plus two for each knight). This means that after just two moves, a game can be in 400 different positions [2]. On average a player has about 40 legal move options, so you can imagine that the number of scenarios will get enormous as the game continues. The current best estimation of the number of possible chess games is 10^120 and belongs to Claude E. Shannon. This might seem like a graspable number, but please think again, the total estimated amount of atoms in the universe is only 10^75.

Figure 1: A visualization of the exponential growth of combinations for just the first two moves.

Although in 1996, it was estimated that only 10^47 of these are actually reachable chess positions, the problem of chess is still unsolvable within a reasonable time, even with supercomputers [3]. In 2017, top supercomputers could do about 10^16 floating point operations per second (FLOPS) which is the unit for computing power. If we then assume that Moore’s law about the speed of innovation works in the future and that it takes 100 operations to evaluate a position, which yields 10^14 positions per second, then it would take about 128 years to ‘solve’ chess. Let alone if you try this with your own computer that can on average perform about 10^13 flops. So computers have not cracked chess yet and probably will not do so anytime soon. However, you do not have to worry about your perspective in the computer science sector. Computers have been better than men for ages now. Even world chess champions have been getting defeated by chess engines since 1997.

The working of a chess engine

So what kind of algorithm is behind a chess engine? Most chess engines work according to the same idea [4]. A chessboard and pieces are generated, this in combination with the implementation of the basic rules gives the computer the ability to calculate all legal moves. Then comes the creative part: position evaluation. Here, the computer gives a score to the position that each possible move conjures. If you, for example, build a simple chess engine, you could achieve this by counting the relative strength of the pieces on the board which the computers play minus the ones of the opponent. In the final part, the computer must determine which is the best move. For this problem, a Minimax algorithm with alternate moves is used to explore the recursive tree of all possible move scores to a given depth. The computer maximizes its score and the algorithm assumes that the opponent always reacts rationally: minimizing the score of the computer.

The performance of a chess engine is mostly determined by two things: the number of moves it can think ahead of and the strength of its position evaluation. The first is bottlenecked by the time. This race is won by the algorithm running on the computer with the biggest computing power, but strong alpha-beta pruning also plays a key role. Alpha beta is an optimization method that allows the engine to disregard non-rational branches in the tree. It stops evaluating a part of a search if it finds a move that leads to a worse situation than previously discovered. This makes it possible for the engine to evaluate the minimax search tree deeper whilst using the same resources. The second thing, position evaluation, is not constrained. The better a computer can evaluate positions, the less important the recursion depth becomes. A lot of chess theory is therefore often incorporated in this part. This varies from the belief that control of the center squares is important to upping scores for positions that could be the start of a favorable sequence.

Figure 2: Alpha-Beta pruning on a recursive tree with depth 2 with a limited complication.
Note 1: Alpha-Beta pruning is more efficient as it visits the good paths first.
Note 2: Alpha-Beta pruning does not influence the outcome of the minimax algorithm.

Fall of the traditional chess engines

Chess computers are so widely developed that in 2010, Martin Thoresen constructed the Thoresen Chess Engines Competition (TCEC), later called the Top Chess Engines Competition. The most famous player of this tournament is Stockfish. Stockfish is an open-source chess engine that is developed by an entire community [5]. Since its first participation in the TCEC in 2013, Stockfish reached the final in every season with only one exception. Eight times it won the TCEC championship and it still is the reigning champion of the TCEC. Stockfish was worldwide considered as the strongest chess engine and seemed unbeatable.

In 2017, the chess world was shocked when Stockfish lost to a relatively new player called AlphaZero [6]. AlphaZero is an AI system created by Google researchers which developed superhuman performance in chess, shogi (Japanese chess), and Go. The main reason AlphaZero could defeat Stockfish is that this chess engine is constructed completely differently. As mentioned before, traditional chess engines, such as Stockfish, rely on position evaluation. These evaluations are mostly based on openings and strategies of human top chess players. Per second, Stockfish can calculate up to sixty million possible moves that are all valued according to previous human plays and their outcomes.

On the other hand, AlphaZero [8] uses a deep neural network that does not take any prior knowledge of the game except for the basic rules. In millions of games against itself, it learns which moves are ‘good’ moves and which are ‘bad’ moves. In the beginning, it plays randomly, but over time the system learns from wins, draws, and losses by adjusting the neural network. In future games, it can make decisions based on the adjusted neural network and again improve the neural network. In this way, the neural network keeps improving when the engine is playing. 

Instead of considering millions of moves per second, AlphaZero only considers sixty thousand moves per second. However, using Monte Carlo Tree Search, it does not have to calculate each move, but certain strategies are evaluated. Let two moves have the same direct value, such as moves 2 and 3 in Figure 2. Then this implies for traditional chess systems that the moves are equally good in this level of the tree. Therefore, the system has to consider the next possible moves and dive deeper into the tree. In contrast, AlphaZero assigns values not only based on the move itself, but also how it experienced this move in previous plays. Therefore, it would have known from previous chess games that move 2 is less promising and is thus lower valued. The more games AlphaZero plays, the more accurate these values get. 

During the training process of AlphaZero, Google kept track of the current Elo rating. This rating system, invented by Arpad Elo, reflects the player’s chess performance [10]. In Figure 3, one can see that AlphaZero’s neural network made huge improvements in the first 150,000 training steps. After approximately 300,000 training steps, it succeeded Stockfish’s Elo rating and after 700,000 steps Google clarified that AlphaZero has mastered the game of chess. It took AlphaZero only an impressive 9 hours to complete those 700,000 training steps. After just four hours of training, it already outperformed Stockfish’s chess rating. A rating that Stockfish achieved after years of development.

Figure 3: Training progress of AlphaZero.
Note 1: each training step represents 4,096 board positions.
Note 2: the highest human Elo rating ever achieved is 2882.

After Alphazero’s development was completed, it challenged reigning champion Stockfish. In the 100 games that the two chess engines played, AlphaZero won 25 games as white and three as black. As all other games resulted in a draw, AlphaZero managed not to lose once against Stockfish [7]. At this moment, chess players and researchers knew that AI-based chess engines would eventually overtake human-based chess engines. Although chess engines were beating humans for years, the only part in these engines that needs human input is now on the verge of being eliminated.

New chess arrives

For many chess players, this will not only be seen as the start of the AI chess engine era, but also as a new impulse to human chess. Garry Kasparov, considered as one of the best chess players in the world, stated the following about AI chess engines: “It was a mistake to think that if we develop very powerful chess machines, the game would be dull.” ”It found that it could actually sacrifice material for aggressive action. It’s not creative, it just sees the pattern, the odds. But this actually makes chess more aggressive, more attractive” [9]. AlphaZero did not only break the Elo rating record, but it also created a whole new playstyle. A style in which material is sacrificed to keep control of crucial in-game positions. AI has proven that intuitively unusual moves can be considered as ‘good’ moves, which gives new opportunities to human chess. Where traditional chess engines learned from moves that top chess players performed, it is now up to top chess players to learn from moves that are performed by AI chess engines. 

References

[1] The Queen’s Gambit sparks enormous surge in search for chess sets | Metro News (2020). The Queen’s Gambit sparks enormous surge in search for chess sets. Metro, March 4, 2021.

[2] How Chess Algorithm Works?. Chess is a two-player strategy board… | by Fernaldi Fauzie | Analytics Vidhya | Medium (2020). How Chess Algorithm Works? Analytics Vidhya, February 28, 2021.

[3] https://www.uio.no/studier/emner/matnat/ifi/INF4130/h17/undervisningsmateriale/chess-algorithms-theory-and-practice_ver2017.pdf (2017). Chess Algorithms Theory and Practice. Universiteit van Oslo, March 1, 2021

[4] https://www.freecodecamp.org/news/simple-chess-ai-step-by-step-1d55a9266977/ (2017). A step-by-step guide to building a simple chess AI. FreeCodeCamp, March 1, 2021.

[5]  https://www.chess.com/terms/stockfish-chess-engine#what (2020). Stockfish. chess.com, March 2, 2021.

[6] https://www.chess.com/news/view/updated-alphazero-crushes-stockfish-in-new-1-000-game-match (2019). AlphaZero Crushes Stockfish In New 1,000-Game Match. chess.com, March 2, 2021.

[7] https://www.chessgames.com/perl/chess.pl?tid=91944#:~:text=On%20December%204th%2C%202017%2C%20Google,fields%20of%20computing%20and%20chess.&text=AlphaZero%20played%20Stockfish%20100%20games%2C%20winning%2028%20and%20drawing%20the%20rest (2017). AlphaZero – Stockfish (2017). chessgames.com, March 4, 2021.

[8] https://deepmind.com/blog/article/alphazero-shedding-new-light-grand-games-chess-shogi-and-go (2018). AlphaZero: Shedding new light on chess, shogi, and Go. DeepMind,  March 2, 2021.

[9] https://en.chessbase.com/post/garry-kasparov-at-peace-with-ai (2020). Garry Kasparov: At peace with AI. chessbase.com, March 2, 2021.

[10] https://www.chess.com/terms/elo-rating-chess (2020). Elo Rating System. chess.com, March 4, 2021.