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.