History of chess engines
The history of chess began nearly 1500 years ago. The introduction of chess engines around 1960 and permanent improvement over time has made chess engines become an integral part of chess analysis and influenced what and how chess is played today by humans. It also lead to the problem of cheating.
Pre-computer era engines (until 1940s)
[edit]
The Mechanical Turk
[edit]The earliest form of a – supposedly – 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 so-called world's first autonomous chess robot. The Mechanical Turk seemingly could play chess and beat opponents, even going as far as solving the iconic knight's tour chess puzzle. It 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
[edit]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.
The beginning of chess computing (1940s–1950s)
[edit]After World War II the invention of the computer spurred the development of chess engines. Two pioneers of the computer, Alan Turing and Claude Shannon 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 a foundation.[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]
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] The computer was capable of playing an entire game.
The rise of chess engines (1960s–1970s)
[edit]Drastic software and hardware improvements in the 1960s and 1970s lead to stronger engines.
Software advancements
[edit]The Minimax algorithm and its alpha-beta pruning optimization, remains key to chess programming and optimization. The algorithm, initially proven in 1928 by John von Neumann, focuses on maximizing one players score while minimizing the other's. Improvements and extensions to this algorithm were developed for chess programming with the goal of increasing the search depth, and so the playing strength. These included move selection techniques, heuristic approaches, iterative deepening, and opening/endgame tablebases.
During this time certain chess grandmasters devoted themselves to the improvement of chess programming. Most notably previous World Chess Champion Mikhail Botvinnik, who wrote several papers on the subject, specifically related to move selection techniques.[7]
Hardware advancements
[edit]Hardware, previously the greatest limiter people like Turing and Dietrich had to face, 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.
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 databases, aiding the hardware speed. Two years later Belle became the first chess engine to receive a Master rating.
Closing the gap (1960s–2000s)
[edit]Early competition
[edit]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]

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]
Deep Blue
[edit]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 won the competition in a 4–0 sweep in the next year.[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 started sponsoring the team in 1994.
In 1995, a new chess engine prototype named Deep Blue was released from the team at IBM. 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 the first time a chess engine won a game against the current world chess champion in a regular match. Deep Blue was upgraded and worked on by both engineers and top chess grandmasters, and a year later, Kasparov and Deep Blue played another match. This time Deep Blue would beat Kasparov and become the first chess engine to beat the current world chess champion in a match.[10] Despite controversial claims on Kasparov's behalf that IBM had cheated, the result was considered a momentous achievement in chess computing by many.
Engines constantly beating humans (2000s–current)
[edit]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 new type of engine, AlphaZero.
Rise of neural networks
[edit]At the end of 2017 engineers at DeepMind released an engine named AlphaZero, using a neural network for its analysis, a new approach that had not been used before. While previous engines had relied on searching through trees and evaluating positions using handcrafted algorithms, AlphaZero relied on a neural network for its analysis, learning chess on its own by playing games against itself.[12] In a 100 game match against the current strongest engine Stockfish, AlphaZero won 28 games and tied the remaining 72.[12] By many, AlphaZero was considered a breakthrough for chess computing and for Artificial Intelligence in general.
Since 2017, the presence of neural networks in the worlds top chess engines has grown. All top engines nowadays, Leela Chess Zero, Stockfish, and Komodo include neural networks in their evaluation function. Yet the deep reinforcement learning used for AlphaZero remains uncommon in top engines.
See also
[edit]References
[edit]- ^ 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.
- ^ Montfort, Nick (2003). Twisty Little Passages: An Approach to Interactive Fiction. MIT Press. p. 76. ISBN 0-262-63318-3.
- ^ Atkinson, George W. (1998). Chess and machine intuition. Intellect Books, pp. 21-22. ISBN 1-871516-44-7
- ^ Heath, David (1997). The Historical Development of Computer Chess and its Impact on Artificial Intelligence. University of Luton.
- ^ Bowdon (1953). Faster Than Thought.
- ^ "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) - ^ "Publications in Computer Games". Archived from the original on 2004-09-19.
- ^ Douglas, J R (December 1978). "Chess 4.7 versus David Levy". BYTE. p. 84. Retrieved 17 October 2013.
- ^ JOANN LOVIGLIO (July 1997). "Deep Blue Team Awarded $100,000 Fredkin Prize". NYT. p. 1.
- ^ a b c d e "History of deep blue". IBM. Retrieved 27 February 2016.
- ^ ICGA Investigation Documents Archived 2016-03-03 at the Wayback Machine. None. Retrieved on April 8th, 2022.
- ^ a b Silver, David; Schrittwieser, Julian; Hassabis, Demis. "AlphaZero: Shedding new light on chess, shogi, and Go". Deepmind. Retrieved 8 April 2022.