History of chess engines

Add links
From Wikipedia, the free encyclopedia

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.

Pre-computer era engines (until 1940s)[edit]

Depiction of 'The Turk'.

The Mechanical Turk[edit]

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[edit]

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)[edit]

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)[edit]

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[edit]

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[edit]

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)[edit]

Early competition[edit]

The chess engines of 1960s and 1970s failed to compete 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.

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[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 came back the next year with an improved version and win 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)[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 brand new engine, AlphaZero.

Neural network revolution[edit]

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.

Also see[edit]

References[edit]

  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. ^ a b c d e "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. ^ a b Silver, David; Schrittwieser, Julian; Hassabis, Demis. "AlphaZero: Shedding new light on chess, shogi, and Go". Deepmind. Retrieved 8 April 2022.
Retrieved from "https://en.wikipedia.org/w/index.php?title=History_of_chess_engines&oldid=1221686145"