History of chess engines

Last updated

The history of chess began nearly 1500 years ago, and over the past century and a half the game has changed drastically. No technology or strategy, however, has changed chess as much as the introduction of chess engines. Despite only coming into existence within the previous 70 years, the introduction of chess engines has molded and defined how top chess is played today.

Contents

Pre-computer era engines (until 1940s)

Depiction of 'The Turk'. Chess Automaton Willis 1821 09.png
Depiction of 'The Turk'.

The Mechanical Turk

The earliest form of a chess engine appears in the 18th century with a machine named the Mechanical Turk. Created by Hungarian inventor Wolfgang von Kempelen, the Mechanical Turk, a life sized human model, debuted in 1770 as the world's first autonomous chess robot. The Mechanical Turk could play chess and beat opponents, even going as far as solving the iconic knight's tour chess puzzle. The Mechanical Turk remained in operation from 1770 to 1854, eventually being destroyed in a fire. The hoax was uncovered years after the machine’s demise, with a human being the true source of the Mechanical Turk's intelligence the entire time. [1]

El Ajedrecista

El Ajedrecista Ajedrecista primero1.JPG
El Ajedrecista

In 1912 Leonardo Torres Quevedo built the first real instance of a chess computer, an automaton named El Ajedrecista. [2] Unlike the Mechanical Turk, El Ajedrecista was actually the first autonomous machine capable of playing chess. El Ajedrecista could play an endgame with white, in which white has a king and rook, while black only has a king. The machine was capable of checkmating the black king (played by a human) every time, and able to identify illegal moves. [3] El Ajedrecista marked the first actual chess engine, and created lots of excitement around the field in general.

The beginning of chess computing (1940s–1950s)

World War II led to astonishing technological breakthroughs, the largest of these being the invention/creation of the computer. Two men, Alan Turing and Claude Shannon pioneered these innovations, and come the end of WWII both would pick up an interest in computer chess. In 1950, Claude Shannon published a paper detailing a program that could potentially play chess against a human. [4] One year later, Alan Turing created the first computer chess playing algorithm, yet the hardware at the time lacked in power. Turing tested his algorithm by hand, and although the algorithm itself was weak, Turing and Shannon had laid the foundation of greatness.[ citation needed ]

In 1951 a close colleague of Turing, Dietrich Prinz, created and implemented a basic chess algorithm that was capable of solving mate in two. The algorithm ran on the Ferranti Mark 1, the first commercially available computer, and although lacking the power to play a full game it served as a proof of concept for chess computing. [5]

Finally, in 1957 an IBM engineer named Alex Bernstein created the world's first fully automated chess engine. The engine was built for the IBM 704 mainframe, and took around eight minutes per move. [6] Capable of playing an entire game, this engine marked the real beginning of chess computing.

The rise of chess engines (1960s–1970s)

The rapid advancement of computing in the 1960s and 1970s was key in increasing chess engine strength, both drastic software and hardware innovations lead to stronger engines.

Software advancements

The most iconic game algorithm of all, the Minimax algorithm and its alpha-beta pruning optimization, was and remains key to chess programming and optimization. This algorithm, initially proven in 1928 by John von Neumann, focuses on maximizing one players score while minimizing the other's. Major improvements to this algorithm were developed specifically for chess programming with the main goal of increasing search depth. These included move selection techniques, heuristic approaches, iterative deepening, and opening/ending databases.

During this time certain chess grandmasters devoted themselves to the improvement of chess programming, with their advanced knowledge of the game. Most notably previous World Chess Champion Mikhail Botvinnik, who wrote several papers on the subject, specifically related to move selection techniques. [7]

Hardware advancements

Previously the greatest limiter people like Turing and Dietrich had to face, hardware advanced at an astonishing rate. In 1965 Gordon Moore observed that transistor count in computers had been doubling every two years, increasing hardware speed at an exponential rate. This is commonly referred to as Moore's law, and still holds true today.

Chess specific hardware also became prominent for chess engines in this time. In 1978 a chess engine named Belle won the North American Computer Chess Championship run by the Association for Computing Machinery, the engine's special hardware allowed it to analyze around thirty million positions in three minutes. Belle also held both opening and ending database's, greatly aiding the hardware speed. Two years later Belle became to first chess engine to receive a Master rating.

Closing the gap (1960s–2000s)

Early competition

The chess engines of 1960s and 1970s failed to compete successfully with top chess players. In 1968, International Master David Levy offered $3000 to any chess engine that could best him in the next ten years. In 1977 Levy faced the chess engine Kaissa, winning the match without losing a single game. [8]

Deep Blue, on display at IBM. Deep Blue.jpg
Deep Blue, on display at IBM.

In 1980 Edward Fredkin, computer science professor at Carnegie Mellon University, offered prizes for chess engines to break barriers in the chess world. These included $10,000 for the first engine to reach Grandmaster level, and $100,000 for the first engine to beat a chess world champion. [9] Suddenly competition in chess computing had become very real, and top minds were at play.

Deep Blue

Deep Blue began under the name ChipTest. ChipTest was developed and built by Feng-hsiung Hsu, Thomas Anantharaman and Murray Campbell at Carnegie Mellon. They entered the engine into the 1986 North American Computer Chess Championship and fell short, but came back the next year with an improved version and won the competition in a 4–0 sweep. [10]

The team developed a new machine starting in 1988, named Deep Thought. Deep Thought had significant advantages over its previous version, and would stand apart from its competition. It became the first engine to beat a grandmaster when it played Bent Larsen in a regular tournament game the same year it came out. [10] The following year Deep Thought won the World Computer Chess Championship with an unbeaten 5-0 score. Chess engines had not yet surpassed humans, and Deep Thought fell to world champion Garry Kasparov in two matches the same year. For the following years Deep Thought remained the chess engine champion, eventually becoming Deep Thought 2 and winning the North American Computer Chess Championship for the fifth time. [10] IBM sponsored the team starting in 1994, and the time of Deep Thought was ending.

Finally in 1995, a new chess engine prototype was released from the team at IBM, Deep Blue. The engine was completed in 1996, and in the same year faced chess champion Garry Kasparov for the first time. Kasparov won the six-game match by the score 4–2., [10] but this was still the first time a chess engine won a game against the current chess champion in a regular match. Deep Blue was upgraded and worked on by both engineers and top chess grandmasters, and a year later the team at IBM had another chance. In a match that would become iconic, Deep Blue became the first chess engine to beat the current chess champion in a full chess match. [10] Despite controversial claims on Kasparov's behalf that IBM had cheated, the result marked a momentous achievement in chess computing.

The era of super-human engines (2000s–current)

Kasparov's defeat marked the end of a time when the best humans could beat the engines. Money continued to flow into chess computing and the industry flourished, not without controversy however. In 2011, the four time reigning champion engine Rybka, was disqualified from the World Computer Chess Championship for code plagiarism. [11] New competitions sprang up, with the Top Chess Engine Championship being founded in 2010 with a stronger emphasis on automated play, longer games, and allowing stronger hardware.

Up until the late 2010s the world of chess computing was advancing slowly, but the progress remained consistent and the engines stronger than ever. That was until 2017 when a team of programmers at Google company DeepMind released a brand new engine, AlphaZero.

Neural network revolution

At the end of 2017 engineers at DeepMind released an engine that shocked the chess computing world. AlphaZero was fundamentally based on a different approach to chess computing, something that had never really been seen before. While previous engines had relied on searching through trees and evaluating positions, AlphaZero relied on a deep neural network for its analysis. [12] This essentially meant AlphaZero could learn chess by itself.

The initial tests with AlphaZero were staggering; in a 100 game match against the current strongest engine Stockfish, AlphaZero won 28 games and tied the remaining 72. [12] In many ways AlphaZero served not only as a breakthrough for chess computing, but for the AI world in general.

Since 2017, the presence of neural networks in the worlds top chess engines has only grown. All top engines nowadays, Leela Chess Zero, Stockfish, and Komodo have all included neural networks in their engines. Yet the deep reinforcement learning used for AlphaZero remains uncommon in top engines.

See also

Related Research Articles

<span class="mw-page-title-main">Deep Blue (chess computer)</span> Chess-playing computer made by IBM

Deep Blue was a chess-playing expert system run on a unique purpose-built IBM supercomputer. It was the first computer to win a game, and the first to win a match, against a reigning world champion under regular time controls. Development began in 1985 at Carnegie Mellon University under the name ChipTest. It then moved to IBM, where it was first renamed Deep Thought, then again in 1989 to Deep Blue. It first played world champion Garry Kasparov in a six-game match in 1996, where it lost four games to two. It was upgraded in 1997 and in a six-game re-match, it defeated Kasparov by winning two games and drawing three. Deep Blue's victory is considered a milestone in the history of artificial intelligence and has been the subject of several books and films.

<span class="mw-page-title-main">Computer chess</span> Computer hardware and software capable of playing chess

Computer chess includes both hardware and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training. Computer chess applications that play at the level of a chess grandmaster or higher are available on hardware from supercomputers to smart phones. Standalone chess-playing machines are also available. Stockfish, Leela Chess Zero, GNU Chess, Fruit, and other free open source applications are available for various platforms.

Feng-hsiung Hsu is a Taiwanese-American computer scientist and the author of the book Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. His work led to the creation of the Deep Thought chess computer, which led to the first chess playing computer to defeat grandmasters in tournament play and the first to achieve a certified grandmaster-level rating.

<span class="mw-page-title-main">Deep Blue versus Kasparov, 1996, Game 1</span> Computer vs. human chess match

Deep Blue–Kasparov, 1996, Game 1 is a famous chess game in which a computer played against a human being. It was the first game played in the 1996 Deep Blue versus Garry Kasparov match, and the first time that a chess-playing computer defeated a reigning world champion under normal chess tournament conditions.

HiTech, also referred to as Hitech, is a chess machine built at Carnegie Mellon University under the direction of World Correspondence Chess Champion Hans J. Berliner. Members of the team working on HiTech included Berliner, Murray Campbell, Carl Ebeling, Gordon Goetsch, Andy Palay, and Larry Slomer. In 1988, it became the first computer system to beat a grandmaster.

Deep Thought was a computer designed to play chess. Deep Thought was initially developed at Carnegie Mellon University and later at IBM. It was second in the line of chess computers developed by Feng-hsiung Hsu, starting with ChipTest and culminating in Deep Blue. In addition to Hsu, the Deep Thought team included Thomas Anantharaman, Mike Browne, Murray Campbell and Andreas Nowatzyk. Deep Thought became the first computer to beat a grandmaster in a regular tournament game when it beat Bent Larsen in 1988, but was easily defeated in both games of a two-game match with Garry Kasparov in 1989 as well as in a correspondence match with Michael Valvo.

<i>Game Over: Kasparov and the Machine</i> 2003 Canadian film

Game Over: Kasparov and the Machine is a 2003 documentary film by Vikram Jayanti about the match between Garry Kasparov, the highest-rated chess player in history, the World Champion for 15 years (1985–2000) and an anti-communist politician, and Deep Blue, a chess-playing computer created by IBM. It was coproduced by Alliance Atlantis and the National Film Board of Canada.

Advanced chess is a form of chess in which each human player uses a computer chess program to explore the possible results of candidate moves. Despite this computer assistance, it is the human player who controls and decides the game.

<span class="mw-page-title-main">El Ajedrecista</span> First true automaton able to play chess

El Ajedrecista is an automaton built in 1912 by Leonardo Torres Quevedo in Madrid, a pioneering autonomous machine capable of playing chess. As opposed to the human-operated The Turk and Ajeeb, El Ajedrecista had a true integrated automation built to play chess without human guidance. It played an endgame with three chess pieces, automatically moving a white king and a rook to checkmate the black king moved by a human opponent.

Murray Campbell is a Canadian computer scientist known for being part of the team that created Deep Blue; the first computer to defeat a world chess champion.

<span class="mw-page-title-main">Deep Blue versus Garry Kasparov</span> 1996 and 1997 chess matches

Deep Blue versus Garry Kasparov was a pair of six-game chess matches between then-world chess champion Garry Kasparov and an IBM supercomputer called Deep Blue. Kasparov won the first match, held in Philadelphia in 1996, by 4–2. Deep Blue won a 1997 rematch held in New York City by 3½–2½. The second match was the first defeat of a reigning world chess champion by a computer under tournament conditions, and was the subject of a documentary film, Game Over: Kasparov and the Machine.

<span class="mw-page-title-main">Anti-computer tactics</span> Human methods against game-playing computers

Anti-computer tactics are methods used by humans to try to beat computer opponents at various games, most typically board games such as chess and Arimaa. They are most associated with competitions against computer AIs that are playing to their utmost to win, rather than AIs merely programmed to be an interesting challenge that can be given intentional weaknesses and quirks by the programmer. Such tactics are most associated with the era when AIs searched a game tree with an evaluation function looking for promising moves, often with Alpha–beta pruning or other minimax algorithms used to narrow the search. Against such algorithms, a common tactic is to play conservatively aiming for a long-term advantage. The theory is that this advantage will manifest slowly enough that the computer is unable to notice in its search, and the computer won't play around the threat correctly. This may result in, for example, a subtle advantage that eventually turns into a winning chess endgame with a passed pawn.

This article documents the progress of significant human–computer chess matches.

<i>Kasparovs Gambit</i> 1993 video game

Kasparov's Gambit, or simply Gambit, is a chess playing computer program created by Heuristic Software and published by Electronic Arts in 1993 based on Socrates II, the only winner of the North American Computer Chess Championship running on a common microcomputer. It was designed for MS-DOS while Garry Kasparov reigned as world champion, whose involvement and support was its key allure. A Macintosh version was planned to be released in 1995.

AlphaGo is a computer program that plays the board game Go. It was developed by the London-based DeepMind Technologies, an acquired subsidiary of Google. Subsequent versions of AlphaGo became increasingly powerful, including a version that competed under the name Master. After retiring from competitive play, AlphaGo Master was succeeded by an even more powerful version known as AlphaGo Zero, which was completely self-taught without learning from human games. AlphaGo Zero was then generalized into a program known as AlphaZero, which played additional games, including chess and shogi. AlphaZero has in turn been succeeded by a program known as MuZero which learns without being taught the rules.

AlphaGo versus Lee Sedol, also known as the DeepMind Challenge Match, was a five-game Go match between top Go player Lee Sedol and AlphaGo, a computer Go program developed by DeepMind, played in Seoul, South Korea between 9 and 15 March 2016. AlphaGo won all but the fourth game; all games were won by resignation. The match has been compared with the historic chess match between Deep Blue and Garry Kasparov in 1997.

<span class="mw-page-title-main">AlphaZero</span> Game-playing artificial intelligence

AlphaZero is a computer program developed by artificial intelligence research company DeepMind to master the games of chess, shogi and go. This algorithm uses an approach similar to AlphaGo Zero.

<span class="mw-page-title-main">Leela Chess Zero</span> Deep neural network-based chess engine

Leela Chess Zero is a free, open-source, and deep neural network–based chess engine and volunteer computing project. Development has been spearheaded by programmer Gary Linscott, who is also a developer for the Stockfish chess engine. Leela Chess Zero was adapted from the Leela Zero Go engine, which in turn was based on Google's AlphaGo Zero project. One of the purposes of Leela Chess Zero was to verify the methods in the AlphaZero paper as applied to the game of chess.

<i>Turochamp</i> 1948 chess program

Turochamp is a chess program developed by Alan Turing and David Champernowne in 1948. It was created as part of research by the pair into computer science and machine learning. Turochamp is capable of playing an entire chess game against a human player at a low level of play by calculating all potential moves and all potential player moves in response, as well as some further moves it deems considerable. It then assigns point values to each game state, and selects the move resulting in the highest point value.

References

  1. ↑ See Schaffer, Simon (1999), "Enlightened Automata", in Clark et al. (Eds), The Sciences in Enlightened Europe, Chicago and London, The University of Chicago Press, pp. 126–165.
  2. ↑ Montfort, Nick (2003). Twisty Little Passages: An Approach to Interactive Fiction. MIT Press. p. 76. ISBN   0-262-63318-3.
  3. ↑ Atkinson, George W. (1998). Chess and machine intuition. Intellect Books, pp. 21-22. ISBN   1-871516-44-7
  4. ↑ Heath, David (1997). The Historical Development of Computer Chess and its Impact on Artificial Intelligence. University of Luton.
  5. ↑ Bowdon (1953). Faster Than Thought.
  6. ↑ "Chessville – Early Computer Chess Programs – by Bill Wall – Bill Wall's Wonderful World of Chess". Archive.is. Archived from the original on 21 July 2012. Retrieved 1 December 2014.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  7. ↑ "Publications in Computer Games". Archived from the original on 2004-09-19.
  8. ↑ Douglas, J R (December 1978). "Chess 4.7 versus David Levy". BYTE. p. 84. Retrieved 17 October 2013.
  9. ↑ JOANN LOVIGLIO (July 1997). "Deep Blue Team Awarded $100,000 Fredkin Prize". NYT. p. 1.
  10. 1 2 3 4 5 "History of deep blue". IBM . Retrieved 27 February 2016.
  11. ↑ ICGA Investigation Documents Archived 2016-03-03 at the Wayback Machine . None. Retrieved on April 8th, 2022.
  12. 1 2 Silver, David; Schrittwieser, Julian; Hassabis, Demis. "AlphaZero: Shedding new light on chess, shogi, and Go". Deepmind. Retrieved 8 April 2022.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.