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.