Development and usage of artificial intelligence in chess

Ever since the first computers have existed, attempts have been made to make computers play chess, as the game is quite simple to learn, with easy to understand and specific, logical rules, yet hard to master, as there are billions of possibilities for how a game could play out. This paper describes how artificial intelligence technologies have been used in computerised chess and it outlines the algorithms that are used, as well as history, uses and a look into the future.

History of artificial intelligence in chess

The idea of creating an artificial intelligence capable of playing chess dates back to the 18th century, when diplomat and inventor Wolfgang van Kempelen built a chess-playing machine called The Turk. This machine went out to play against many remarkable people at the time. Unfortunately, The Turk was merely a box with a human player inside of it. Despite that, The Turk is often cited as the origin of non-human chess players.

Mechanical chess research was dormant until the 1950s, when the digital computer arrived. Since then, chess enthusiasts and computer engineers have designed chess-playing machines and computer programs with growing degrees of seriousness and performance.

Former World Chess Champion Mikhail Botvinnik was one of the few chess grandmasters to dedicate himself seriously to computer chess, writing many books on the subject. He was also an electrical engineer with a doctorate. Hardware in the 1960s was relatively primitive, and only the most efficient computers could do anything beyond a three-ply (a ply is one move taken by one player, one half of a turn) full-width scan, and Botvinnik lacked such devices. Therefore, Botvinnik had no choice but to explore software move selection strategies. Botvinnik served as a consultant for the Moscow Institute for Theoretical and Experimental Physics (ITEP) team in a 1965 electronic chess match between the United States and the Soviet Union.

One formative point of reference happened when the group from Northwestern College, which was capable of the Chess arrangement of programs, won the primary three ACM Computer Chess Championships (1970–72). The coming program, Chess 4.0, won that year's championship and its successors went on to win both the 1974 ACM Championship and that year's inaugural World Computer Chess Championship, some time recently winning the ACM Championship once more in 1975, 1976 and 1977. The type A execution turned out to be fair as fast and is described in greater detail in the next section. In reality, Chess 4.0 set the worldview that was and still is taken after basically by all present day Chess programs today. In 1978, an early interpretation of Insight Thompson's equipment chess machine Beauty, entered and won the North American Computer Chess Championship over the overwhelming Northwestern College Chess.

The AlphaZero software, which beat the leading chess engine in 2017, employs a Monte Carlo tree search variant that does not require rollout. "We could say that the victorious programs were designed with (chess) algorithms based on our own understanding – using, in this instance, the experience and advice of top grand masters... (Deep Blue) was just a dumb machine... (But with AlphaZero), that way of programming is changing dramatically", says Venki Ramakrishnan of the Royal Society. AlphaZero has revolutionized machine chess to the point that all but the last place finishers in the TCEC Season 20 Premier Division used a neural-network-based evaluation system.

Timeline

• 1769 – The Turk was designed by Wolfgang von Kempelen. It is disguised as a chess-playing automaton, but it is actually controlled by a human player hidden inside.
• 1868 – Charles Hooper introduces the Ajeeb automaton, which also contains a human chess player.
• 1912 – El Ajedrecista is a computer designed by Leonardo Torres y Quevedo that can play King and Rook versus King endgames.
• 1941 – Konrad Zuse designs machine chess algorithms in his Plankalkül programming formalism, which is at least a decade ahead of comparable work.
• 1948 – In his book Cybernetics, Norbert Wiener explores how to build a chess program using a depth-limited minimax search with an evaluation tool.
• 1950 – One of the first articles on the algorithmic methods of computer chess is published by Claude Shannon, titled "Programming a Computer for Playing Chess."
• 1951 – Alan Turing is the first person to publish a computer program that can play a full game of chess on paper (dubbed Turochamp)
• 1956 – Los Alamos Chess, created by Paul Stein and Mark Wells for the MANIAC I machine, was the first software to play a chess-like game.
• 1957 – Alex Bernstein and Russian programmers use a BESM to create the first programs capable of playing a full game of chess.
• 1958 – The alpha–beta search algorithm is used for the first time in a chess program by NSS.
• 1962 – Kotok-McCarthy, the first software to play credibly, is released at MIT.
• 1963 – Grandmaster David Bronstein beats an early chess program-running M-20.
• 1966–67 – The first computer-to-computer chess match is played. Over the course of nine months, the Moscow Institute for Theoretical and Experimental Physics (ITEP) defeated Kotok-McCarthy at Stanford University by telegraph.
• 1968 – David Levy, the Scottish chess champion, wagers 500 pounds with AI pioneers John McCarthy and Donald Michie that no computer program will be able to beat him in a chess match in the next ten years.
• 1970 – The first North American Computer Chess Championships was held in New York, organized by Monty Newborn and the Association for Computing Machinery.
• 1971 – Ken Thompson, an American computer scientist at Bell Labs and the developer of the Unix operating system, creates "chess," the first chess-playing application for Unix.
• 1974 – The first World Computer Chess Championship is organized by David Levy, Ben Mittman, and Monty Newborn, and is won by the Russian software Kaissa.
• 1975 – Northwestern University releases Chess 4.5 after nearly a decade of only modest growth, with full-width scan, bitboards and iterative learning and also reintroducing the transposition table (see the next section).
• 1976 – Microchess, the first game for microcomputers, was released in December by Canadian programmer Peter R. Jennings.
• 1977 – Chess Challenger, the first dedicated chess machine, was published in March by Fidelity Electronics. The International Computer Chess Association was established by chess programmers to organize computer chess tournaments and publish a journal on computer chess research and advancements. Boris, a dedicated chess machine in a wooden box with plastic chess pieces and a folding board, was also published that year by Applied Concepts.
• 1978 –David Levy wins the bet he made ten years ago, beating Chess 4.7 by a score of 4½–1½ in a six-game series. In game four, the machine defeated a human master for the first time in a tournament.
• 1979 – A match between IM David Levy and Chess 4.8 is organized by Frederic Friedel and broadcast on German television. Levy and Chess 4.8, which was operating on a CDC Cyber 176, the world's strongest machine, battled to an 89-move draw.
• 1980 – The Mephisto line of dedicated chess computers from the German company Hegener & Glaser starts a long run of victories in the World Microcomputer Championship (1984–1990) using dedicated computers running the programs ChessGenius and Rebel.
• 1981 – With a perfect 5–0 record and a results rating of 2258, Cray Blitz wins the Mississippi State Championship. In the fourth round, it defeated Joe Sentef (2262) to become the first machine to defeat a master and win a master ranking in tournament play.
• 1984 – The German Company Hegener & Glaser's Mephisto line of dedicated chess computers began a long streak of victories (1984–1990) in the World Microcomputer Championship using dedicated computers running programs ChessGenius and Rebel.
• 1986 – Chessmaster 2000, the first version of what would become the world's best-selling chess program line, was published by Software Country (see Software Toolworks). It was based on an engine by David Kittinger.
• 1987 – Chessbase was created by Frederic Friedel and physicist Matthias Wüllenweber, who released the first chess database software. Stuart Cracraft launches GNU Chess, one of the first 'chess engines' to provide chesstool, a separate graphical user interface (GUI).
• 1988 – HiTech, created by Hans Berliner and Carl Ebeling, defeats grandmaster Arnold Denker 3½–½. in a match, as well as several other grandmasters.
• 1991 –The World Microcomputer Chess Championship is won by a ChessMachine based on Ed Schröder's Rebel.
• 1992 – ChessMachine defeats mainframes for the first time in the 7th World Computer Chess Championship. Secrets of Rook Endings, the first book based on Ken Thompson's endgame tablebases, is published by GM John Nunn.
• 1993 – Bent Larsen defeats Deep Thought-2 in a four-game series. Chess programs running on personal computers beat Mephisto's dedicated chess computers to win the Microcomputer Championship, signaling a move away from dedicated chess hardware and toward applications running on multipurpose computers.
• 1995 – Fritz 3, a 90Mhz Pentium PC, won the 8th World Computer Chess Championships in Hong Kong, defeating Deep Thought-2, a dedicated chess machine, and programs running on multiple supercomputers. This is the first time a chess program running on commodity hardware has defeated specialist chess machines and large supercomputers.
• 1996 – Garry Kasparov defeats IBM's Deep Blue in a six-game series, 2–4.
• 1997 – Deep(er) Blue, a heavily updated version of the original, defeats Garry Kasparov in a six-game match, 3.5-2.5.
• 2000 – The Universal Chess Interface, drafted by Stefan Meyer-Kahlen and Rudolf Huber, is a protocol for GUIs to communicate with engines that would eventually become the standard method for new engines.
• 2002 – Vladimir Kramnik and Deep Fritz draw an eight-game series.
• 2003 – Kasparov drew six games in a row against Deep Junior and four games in a row against X3D Fritz.
• 2004 – A machine team (Hydra, Deep Junior, and Fritz) defeats a relatively strong human team (Veselin Topalov, Ruslan Ponomariov, and Sergey Karjakin, with an average Elo rating of 2681) 8½–3½. Fruit 2.1, a competitive closed source engine at the time, is released as source code by Fabien Letouzey. As a result, many writers revise their code to include the latest concepts.
• 2005 – Rybka takes first place in the IPCCC tournament and rockets to the top of the rankings.
• 2006 – Deep Fritz defeats Vladimir Kramnik, the world champion, 4–2.
• 2010 – Topalov trains for the 2010 World Chess Championship by sparring with the supercomputer Blue Gene, which has 8,192 processors and can perform 500 trillion (5 x 1014) floating-point operations per second. Vasik Rajlich, a Rybka creator, claims that Ippolit is a clone of Rybka.
• 2011 – Rybka's WCCC titles were taken away by the ICGA.
• 2017 – In a 100-game match, AlphaZero, a neural net-based digital automaton, defeats Stockfish 28–0 with 72 draws.

Development of AI in chess

Attempts at using computers to play chess were made as early as in the 1950s, when Claude Shannon published a paper on the subject. Shannon’s paper outlines two possible approaches as to how computers would play chess. Type A being the brute force method, looking at possible moves ahead for a certain number of moves (lookahead), and then doing the best move. Shannon saw this method as inferior, as it required a lot of computing power, and exponentially more for every move added to lookahead. Type B programs would implement quiescence search, which attempts to simulate human “intuition”, where a human player would not play a move because it would look bad. Therefore type B would only look at a few good moves for each situation, rather than all possible moves. Shannon believed that Type B would be the more prevalent type, however, as computing power increased and became cheaper, it became apparent that Type A would lead the way with its full width brute force search method. As computers became more advanced, type A was able to look at all possible moves and therefore find the best one, even if it didn’t quite match “intuition” that type B tried to emulate, and with only a slight delay in time.

To optimise the search for the best move, several optimisations are used. For example, pruning, which would remove moves that are obviously bad. Pruning had to be tuned correctly - too aggressive and a good move may be missed. Too little and the computer would waste time calculating bad moves, or even performing them if not searching deep enough. Transposition tables are used to record moves that have previously been calculated. For example, the IBM Deep Blue had 500 million entries in its transposition table.

One of the greatest problems for early chess computers was the endgame. It required a very long search depth to come out with a good endgame play. So instead, predefined endgame tablebases were used, where the endgame with for example a king and pawn is analysed completely end to end. The endgame analysis has also provided more for the chess community itself as well. For example, several endings, which were first thought to be a loss, were able to result in a draw.

Chess computers also use predefined openings that are also known to regular chess players. The openings are quite well defined, so the computer will usually follow them, where a human chess player would deviate and make their own strategy. During the early years, this posed a disadvantage to computers, but the openings in computers have become more in depth now, so if a human player deviated from them, it would likely lose, as the computers now simply know more possible moves.

Chess engines

Overview of chess engines

A chess engine is a piece of software that analyses chess and chooses the strongest possible moves. They usually have a command line interface, and are paired with a front end to provide user interactivity and graphics. This is in contrast to what were known at the time as computer chess programs, which include graphics but are worse at playing chess. To communicate with the user, standardised protocols are used for developing the front-end, which sits between the user and the chess engine. These protocols include the Universal Chess Interface (UCI) or Chess Engine Communication Platform. (Knudsen, 2010)

Currently, the Stockfish engine tops the leaderboards, which is a free and open source chess engine first released in 2008 and version 13 released in February 2021. Compared to other chess engines, Stockfish has a deeper search depth (Stockfish depth vs. others; challenge, 2013). It is the default chess engine in many freely-available chess apps on Android and iOS. The source code is written in C++, but can also be compiled to JavaScript, which allows it to run in a browser. In 2013, Fishtest was released, which is a form of distributed computing where volunteers can donate some of their CPU resources to improve the development of Stockfish.

In 1999, Garry Kasparov played a game against the world - a team of over 50 000 people from 75 countries. Both sides used chess engines for assistance. Kasparov won the game after discovering a forced checkmate in 28 moves with the Deep Junior engine. The game lasted 4 months, and is often referred to as the greatest game of chess in all time.

Chess engine Maia

The newcomer to the AI chess field is a customized version of Alpha-Zero called Maia. The difference of it compared to other chess engines in the field is that it focuses more on predicting real human moves, including all the mistakes they make while the other engines focus on winning the game. It can show the common mistakes people should practice more and which mistakes they should avoid when playing to improve their skills. According to Jon Kleinberg, a professor at Cornell University who led the development of Maia, says it is a first step toward developing AI that better understands human fallibility. He adds that the same kind of technology could be used also in the medical field.

What comes to the other chess engines in general, the Computer Chess Rating Lists website the best chess engines of the world in 2021, based on their rankings are Stockfish, Fat Fritz 2, Komodo and Houdini. Even though chess engines are great opponents and have shown new ways to improve the game in many ways, the ugly truth is that the development of chess engines has decreased the creativity of the players, now they are just focusing on learning different kinds of complex strategies straight from these machines.

Functions and algorithms used by chess engines

The evaluation function

The aim of an evaluation function is to evaluate the given board situation and decide who is more likely to win in the current situation. For example, the function could simply check who has been checkmated, count the pieces on each side in a weighted way. An algorithm using this function will understand the basics of the game such as what pieces are worth more and which less when to take a trade, and when not to. To further improve a basic evaluation function, it is required to add some positional intuition to it. Thus, scoring could be made more sophisticated and therefore accounting for more tactics available. Usually, evaluation functions and search algorithms are implemented independently of each other.

Example of a weighing system

An algorithm using this function will understand the basics of the game such as what pieces are worth more and which less when to take a trade, and when not to. To further improve a basic evaluation function, it is required to add some positional intuition to it. Thus, scoring could be made more sophisticated and therefore accounting for more tactics available. Usually, evaluation functions and search algorithms are implemented independently of each other.

The minimax search

The search algorithm’s job is to compare possible moves. Evaluation functions work together with search algorithms to make reasonable decisions. Search algorithms involve a search tree as a way to represent the board and its possible moves to be made from that position.

Illustration of a search tree branching out.

Since chess is a zero-sum game, the minimax algorithm can be used to decide on possible moves. A zero-sum game means that the loss and gain of each participant are balanced by the loss or gain of another participant. Each move in chess can be seen as a way to maximize one’s chances of winning and lowering the others. In terms of a search tree, choosing the next move is based on the choosing of children nodes and their scores based on the chances of winning.

Minimax can perfectly win the game if one would let it run indefinitely but that is very impractical because of the method being incredibly slow. This is due to the fact that each position has many possible moves and its branch has as many moves and that grows exponentially with depth.

A way to get around this was to use the Shannon type B variation of minimax. The algorithm opted to search only a few of the top moves. That resulted in much more realistic times to search for moves but left room for errors and traps. By the time when machines started being more powerful (around the 1970s), an optimization of minimax known as alpha-beta pruning was discovered that made the Type A (search all possible variations) approach viable.

Illustration of Shannon Type B

Alpha-Beta pruning

Alpha-Beta pruning is a variation of minimaxing where the nodes of a search tree, which result in worse results than the current best result, are skipped. This results in much faster times of move computing. Alpha-Beta pruning makes the brute-force search possible, however, there are limitations. In the best case, alpha-beta pruning reduces the time it takes to compute a move by a square root of the time it would take minimax to compute the move. For example, if minimax takes 100 seconds to decide the move, for the pruning method it would only take 10 seconds. However, in most cases pruning will not perform that well and might still take up some time, this is due to how the algorithm visits the nodes of a search tree. When beginning computing the algorithm picks nodes at random and it might pick a node that has a bad result but at that point, it is still the best result so it keeps computing its future moves.

Move ordering

The way to achieve the ideal case for alpha-beta search is through move ordering. The general idea is to look for the most promising moves first thus eliminating bad ones. Since it is impossible to determine which moves are the best without an in-depth search, the determination process has to be guided by heuristics. Instead of choosing a subset of moves, like in Shannon Type B, we preferentially order moves. This can be something similar to ordering captures first and considering all else after all the captures have been analyzed.

One of the most common heuristics for non-capturing moves is the “killer” heuristic. Within the search tree, there are going to be sibling nodes, which are very similar in positions because they derive from the same parent node. This means if a move that causes an alpha-beta cutoff in one node will result in a very important move for its siblings as well and this will be analyzed first.

For AI not to recalculate its moves every turn but rather keep the already calculated data, there needs to be a memory-efficient way to store this data.

Transposition tables

As previously mentioned alpha-beta pruning is greatly improved by the use of move ordering and this can be even further improved by the use of transposition tables.

Transposition tables store the information about the calculated nodes and skip the nodes it has already seen. This greatly saves time because in the case of calculating a node and the node has already been seen somewhere else, the time to find an optimal move is reduced.

Since keeping track of transposition tables requires a lot of memory, programmers have opted to check the hashes of moves rather than the whole nodes themselves. The use of hashing reduces high-information objects into lower ones and thus there could be created overlaps of information where two moves have the same hash. This can be mitigated by a larger transposition table size, usually, a size of 10 million entries is enough.

Quiescence search

Sometimes when calculating the moves the AI might see that the move results in a loss of a piece and thus dropping the further research of the node even if one of the future moves could resolve the issue and grant a winning move. This is known as the horizon effect. To minimize the horizon effect a search function known as quiescence search is used. To not lose out on possible good moves a second limited search is done on “unstable” nodes trying to stabilize them.

Monte Carlo tree search

The Monte Carlo tree search is a heuristic algorithm which can be used for finding the best possible moves in a game, such as chess. The root is the current state of the game. The leaves are possible moves by either the opponent or the player from which no complete playout is completed. The first stage is selection, when a leaf with no complete playout has been selected. Second, child nodes are generated from that leaf in the expansion stage. Third is the simulation: one complete game is played out from a random node generated in the last stage. The last stage is backpropagation, where the result of the playout, either a loss or win, is propagated back to the original node.

The schematic above describes one possible round of the Monte Carlo tree search. Each node shows the number of victories divided by the number of total playouts. For the playout in the image, white lost, so it was marked as 0/1. The total move count in all nodes was increased, but the win count was only increased for black nodes.

Chess boom of 2020

In the year 2020, most of the countries issued a lockdown for their people and many people turned to chess as a coping mechanism. The chess boom was fueled even further by the rising popularity of chess on social media platforms such as Twitch.tv and YouTube. One of the most notable examples of this was a player with the Grandmaster title (being the highest title obtainable for a chess player) named Hikaru Nakamura. (Behler, 2020). Over the year 2020, he had gotten an additional 670 thousand subscribers to his YouTube channel (according to SocialBlade) and his streams had roughly 10 000 concurrent viewers at all times.

In addition, the Netflix series Queen’s Gambit premiered in October. It reached the #1 most-watched show in many countries and has a close to 100% score on Rotten Tomatoes.

The biggest website for online chess used to play against players and AI is chess.com (as of April 15th, 2021). The website has AI of different levels of skill for anyone to try ranging from chess ranking 600 up to 2750 (which is on the level of most grandmasters).

Chess as eSports

For decades there has been discussion whether chess is a sport or not and the International Olympic Committee recognized chess as a sport in 1999 and a year later it was seen at the Sydney Olympics too. One of the reasons that supports the argument above is the fact that playing chess puts a person through great amounts of mental pressure, and this exertion also manifests itself physically. Also, chess is a game that has to be practiced daily to develop skills and maintain them because of its competitive nature and rapidly evolving strategies. Looking at the reasons, it’s pretty clear that chess is a sport and it’s using the same objects as any other sport, what comes to eSports, it can be considered a subcategory within sports. In August 2020 the chess grandmaster Hikaru Nakamura was signed with eSport gaming team Team SoloMid (TSM) which is one of the biggest eSports organizations in North America and became one of the first professional chess players that has been signed with an eSports organization, other has been WGM Qiyu Zhou with Counterlogic Gaming. At the same time the chess streaming grew enormously and made online chess even popular across the platforms with regular events like online amateur chess tournaments Pogchamps by chess.com.

Chess tournaments during the pandemic

Most of the major chess events that were supposed to take place in the second half of 2020 were canceled due to the pandemic restrictions. Although events like the 44th Chess Olympiad and the match for the title of World Chess Champion were canceled, a lot of major national and international chess competitions were played online for the first time in history. That has raised the concerns of cheating in this new online environment because the use of artificial intelligence would be easy.

Cheat detection in online chess tournaments

People have used artificial intelligence to better learn the game but now it is also being used to successfully detect if some contestants play better than usual, considering their previous game history.

International Chess Federation (FIDE) has mentioned in the Anti-Cheating Guidelines published in 2014, that in most cases, a handheld metal detector was sufficient enough to ensure that electronics were not carried into the playing venue, providing cheating protection for onboard games. However, for online chess tournaments, cheating protections have proven to be much harder to implement.

The European Online Chess Championship took place in May 2020 to which almost 4000 people from 55 different European federations registered. This was the record number of participants in an official international chess championship. A total of 5 out of 6 players at the top of the B group (rating of 1400-1700) of the European Online Championship were disqualified. Approximately 2% of the players were disqualified across all the categories, but mostly from the beginners or youth categories. This highlighted one of the biggest problems of online chess: cheating.

Recently many different software companies, including DeepMind, which developed MuZero, have been working to improve existing cheat detection software or develop new software that will precisely estimate if a player is cheating. For example, on Chess.com, a cheat detection system uses millions of chess games stored in its database to create a statistical model that decides if it’s likely for the player to make at a certain skill level to do moves a chess engine or greatest chess players would do. Reports of possible cheating accusations are analyzed by a team of experts. The results are published monthly in the website’s “Month in Review.”

So far most of the games played in this period have been rapid chess, and games that would last longer would be a bigger challenge for the anti-cheat teams. FIDE has approved a complex cheat detection system and an AI behavior-tracking module for its Online Arena games.

Cheat detection issues

The cheat detection that uses AI is not flawless though as it has difficulties classifying a cheater if the person has no official records of play beforehand. Cheating is more clear when there are irregularities seen in the plays and the likeliness of using a chess engine for every single tournament game is very small. These kinds of AI systems require a lot of previous data to operate and even then they may make a false claim against top players. Most probably high-level players will not risk their reputation and career for a single tournament over a single strange or highly advanced move.

Future of AI in chess

The future of chess divides a lot of people’s opinions, others say that chess should remain as a board game and not be as popular as it is at the moment. However, chess big names like a chess world Champion Magnus Carlsen and a chess Grandmaster Gregory Seper estimate that the game keeps evolving and changes the world of board games more and more towards the online tournaments and games. Gregory Seper stated in Chess.com webpage in 2017 that in 10 years or so, the opening monographs will completely switch to computer games and analysis. They will probably mention human games only to demonstrate typical mistakes to avoid. He also mentions that he believes that a major change happens in opening trends too. Magnus Carlsen stated in 2020 when he was asked about the future of chess that he thinks that it’s just not realistic to expect people to play long games online and that it is not realistic to expect people to watch it with great interest. He also added that the rapid format is excellent for online play because you keep at least some semblance of high quality chess and it also doesn’t take too long. You get to play more games in a day and that way you get more excitement possibly. Also Nick Barton, a director of business development at Chess.com stated in a interview of Dexerto in January 2021 that online chess is the future of chess itself because of its accessibility. In a matter of seconds you can play a chess game with anyone from around the world and you have a wealth of learning resources such as lessons, analysis and puzzles at your fingertips and the growth of online chess, especially among brand new players, has shifted the definition of what it means to play a game of chess.

Conclusion

The use of artificial intelligence in chess has a long and convoluted history and has evolved a lot throughout it. Increased computational power has paved the way for many breakthroughs in computerised chess, and the innovations have found uses in e-sports and tournaments. AI will likely continue to have an important presence in the world of chess.