Turochamp

Last updated

Turochamp
Developer(s) Alan Turing, David Champernowne
Genre(s) Computer chess
Mode(s) Single-player
The 1952 game between Turochamp (White) and Alick Glennie (Black). After 29 moves, White is one pawn up but about to lose its pinned Queen on the next move. Therefore, White resigns. TUROCHAMP vs Glennie, 1952.gif
The 1952 game between Turochamp (White) and Alick Glennie (Black). After 29 moves, White is one pawn up but about to lose its pinned Queen on the next move. Therefore, White resigns.

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.

Contents

Turochamp is the earliest known computer game to enter development, but was never completed by Turing and Champernowne, as its algorithm was too complex to be run by the early computers of the time such as the Automatic Computing Engine. Turing attempted to convert the program into executable code for the 1951 Ferranti Mark 1 computer in Manchester, but was unable to do so. Turing played a match against computer scientist Alick Glennie using the program in the summer of 1952, executing it manually step by step, but by his death in 1954 had still been unable to run the program on an actual computer. Champernowne did not continue the project, and the original program was not preserved.

Despite never being run on a computer, the program is a candidate for the first chess program; several other chess programs were designed or proposed around the same time, including another one which Turing unsuccessfully tried to run on the Ferranti Mark 1. The first successful program in 1951, also developed for the Mark 1, was directly inspired by Turochamp, and was capable only of solving "mate-in-two" problems. A recreation of Turochamp was constructed in 2012 for the Alan Turing Centenary Conference. This version was used in a match with chess grandmaster Garry Kasparov, who gave a keynote at the conference.

Gameplay

Turochamp simulates a game of chess against the player by accepting the player's moves as input and outputting its move in response. The program's algorithm uses a heuristic to determine the best move to make, calculating all potential moves that it can make, then all of the potential player responses that could be made in turn, as well as further "considerable" moves, such as captures of undefended pieces, recaptures, and the capture of a piece of higher value by one of lower value. The program then assigns a point value to each resulting state, then makes the move with the highest resulting points, employing a minimax algorithm to do so. [1] [2] [3] Points are determined based on several criteria, such as the mobility of each piece, the safety of each piece, the threat of checkmate, the value of the player's piece if taken, and several other factors. Different moves are given different point values; for example taking the queen is given 10 points but a pawn only one point, and placing the king in check is given a point or half of a point based on the layout of the board. [4] According to Champernowne, the algorithm is primarily designed around the decision to take a piece or not; according to Turing, the resulting gameplay produces a low level game of chess, which he considered commensurate with his self-described average skill level at the game. [1] [4]

History

Alan Turing in the 1930s Alan Turing az 1930-as evekben.jpg
Alan Turing in the 1930s

Alan Turing was an English mathematician, computer scientist, logician, cryptanalyst, philosopher and theoretical biologist. [5] Turing was highly influential in the development of theoretical computer science, providing a formalisation of the concepts of algorithm and computation with the Turing machine, which can be considered a model of a general-purpose computer. [6] [7] [8] Turing is widely considered to be the father of theoretical computer science and artificial intelligence. [9] Beginning in 1941, while working in wartime cryptanalysis at Bletchley Park, Turing began to discuss with his colleagues the possibility of a machine being able to play chess or perform other "intelligent" tasks, as well as the idea of a computer solving a problem by searching through all possible solutions using a heuristic or algorithm. [10] [11] Some of Turing's cryptanalysis work, such as on the Bombe, was done through this model of a computing machine searching through possibilities for a solution. [11] He continued to discuss the idea with his colleagues throughout the war, such as with economic statistician D. G. Champernowne in 1944, and by 1945 he was convinced that a machine capable of performing general computations would be theoretically capable of replicating anything a human brain could do, including playing chess. [10] [12]

After World War II, Turing worked at the National Physical Laboratory (NPL), where he designed the Automatic Computing Engine (ACE), among the first designs for a stored-program computer. In 1946, Turing wrote a report for the NPL entitled "Proposed Electronic Calculator" that described several projects that he planned to use the ACE for; one of these was a program to play chess. He gave a reading at the London Mathematical Society the following year in which he presented the idea that a machine programmed to play chess could learn on its own and acquire its own experience. Subsequently, in 1948, he wrote a new report for the NPL, entitled "Intelligent Machinery", which suggested a form of imitation chess. [13]

In the late summer of 1948 Turing and Champernowne, then his colleague at King's College, Cambridge, devised a system of theoretical rules to determine the next strokes of a chess game. They designed a program that would enact an algorithm that would follow these rules, though the program was too complex to able to be run on the ACE or any other computer of the time. [1] The program was named Turochamp, a combination of their surnames. [13] It is sometimes misreported as "Turbochamp". [14] According to Champernowne, his wife played a simulated game against the program, nicknamed the "paper machine", and lost. [13] [15] Turing attempted to convert the program into executable code for the 1951 Ferranti Mark 1 computer in Manchester, but was unable to do so due to the complexity of the code. [14] According to Jack Copeland, author of several books on Turing, he was not concerned that the program could not be run, as he was convinced that the speed and sophistication of computers would soon rise to make it possible. [16] That same year, he wrote a paper describing how the program's algorithm worked, though he did not name the program, which was republished in 1953 in the book Faster Than Thought. [17] In the summer of 1952, Turing played a match against computer scientist Alick Glennie using the program, executing it manually step by step. The match, which was recorded, had the Turochamp program losing to Glennie in 29 moves, with each of the program's moves taking up to 30 minutes to evaluate. Although the match demonstrated that the program could viably play against a human in a full game, it was not run on an actual computer before Turing's death in 1954. [14]

Legacy

Garry Kasparov speaking at the Alan Turing Centenary Conference in Manchester on 25 June 2012. Garry Kasparov IMG 0130.JPG
Garry Kasparov speaking at the Alan Turing Centenary Conference in Manchester on 25 June 2012.

Turochamp is a candidate for the first chess program, though the original program was never run on a computer. Several other chess programs were designed and attempted around the same time, such as in Claude Shannon's 1950 article Programming a Computer for Playing Chess, Konrad Zuse's chess routines developed from 1941 to 1945 for his proposed programming language Plankalkül, and Donald Michie and Shaun Wylie's chess program Machiavelli, which Turing unsuccessfully tried to run on the Ferranti Mark I at the same time as Turochamp. [13] [18] [19] [20] In November 1951 Dietrich Prinz, who worked at Ferranti and was inspired by Turing's work on Turochamp, developed the first runnable computer-based chess program for the Ferranti Mark I, which could solve "mate-in-two" problems. [1]

The original code and algorithm written by Turing and Champernowne has not been preserved. In 1980, Champernowne described the way Turochamp worked, but he was not able to recall all of the details of the game's rules. [1] [16] A version of Turochamp was developed in 2012 from descriptions of the game's algorithm as a symbolic recreation. [21] After the initial recreation was unable to recreate Turing's simulated match against Glennie, several computer chess experts and contemporaries of Turing were consulted in interpreting Turing and Champernowne's descriptions of the program, including Ken Thompson, creator of the 1983 Belle chess machine and the Unix operating system. They were unable to find the explanation for the deviation until they consulted with Donald Michie, who suggested that Turing had not been concerned with meticulously working out exactly which move Turochamp would recommend. With this in mind they were able to prove that from the very first move of the game Turing had incorrectly deviated from moves that appeared suboptimal without working out their point value. [lower-alpha 1] The resulting recreation was presented at the Alan Turing Centenary Conference on 22–25 June 2012, in a match with chess grandmaster and former world champion Garry Kasparov. [22] Kasparov won the match in 16 moves, and complimented the program for its place in history and the "exceptional achievement" of developing a working computer chess program without being able to ever run it on a computer. [23]

See also

Notes

  1. ↑ Specifically, Turing had opened by moving his pawn 2 spaces to E4 as he likely felt it was the obviously superior move to moving it one space to E3, when actually the algorithm gives it a lower point value as it leaves the king theoretically open to attack from E3, even though at that point in the game no opposing piece could possibly reach that location. [22]

Related Research Articles

<span class="mw-page-title-main">Alan Turing</span> English computer scientist (1912–1954)

Alan Mathison Turing was an English mathematician, computer scientist, logician, cryptanalyst, philosopher and theoretical biologist. Turing was highly influential in the development of theoretical computer science, providing a formalisation of the concepts of algorithm and computation with the Turing machine, which can be considered a model of a general-purpose computer. He is widely considered to be the father of theoretical computer science and artificial intelligence.

<span class="mw-page-title-main">Chess</span> Strategy board game

Chess is a board game for two players, called White and Black, each controlling an army of chess pieces, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to distinguish it from related games such as xiangqi and shogi. The recorded history of chess goes back at least to the emergence of a similar game, chaturanga, in seventh century India. The rules of chess as they are known today emerged in Europe at the end of the 15th century, with standardization and universal acceptance by the end of the 19th century. Today, chess is one of the world's most popular games played by millions of people worldwide.

<span class="mw-page-title-main">Garry Kasparov</span> Russian chess grandmaster, political activist and writer

Garry Kimovich Kasparov is a Russian chess grandmaster, former World Chess Champion (1985–2000), political activist and writer. His peak FIDE chess rating of 2851, achieved in 1999, was the highest recorded until being surpassed by Magnus Carlsen in 2013. From 1984 until his retirement from regular competitive chess in 2005, Kasparov was ranked world no. 1 for a record 255 months overall. Kasparov also holds records for the most consecutive professional tournament victories (15) and Chess Oscars (11).

<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, GNU Chess, Fruit, and other free open source applications are available for various platforms.

<span class="mw-page-title-main">Vladimir Kramnik</span> Russian chess grandmaster (born 1975)

Vladimir Borisovich Kramnik is a Russian chess grandmaster. He was the Classical World Chess Champion from 2000 to 2006, and the undisputed World Chess Champion from 2006 to 2007. He has won three team gold medals and three individual medals at Chess Olympiads.

Brains in Bahrain was an eight-game chess match between World Chess Champion Vladimir Kramnik and the computer program Deep Fritz 7, held in October 2002. The match ended in a tie 4-4, with two wins for each participant and four draws.

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.

A game of chess can end in a draw by agreement. A player may offer a draw at any stage of a game; if the opponent accepts, the game is a draw. In some competitions, draws by agreement are restricted; for example draw offers may be subject to the discretion of the arbiter, or may be forbidden before move 30 or 40, or even forbidden altogether. The majority of draws in chess are by agreement.

<span class="mw-page-title-main">Ferranti Mark 1</span> First commercial computer

The Ferranti Mark 1, also known as the Manchester Electronic Computer in its sales literature, and thus sometimes called the Manchester Ferranti, was produced by British electrical engineering firm Ferranti Ltd. It was the world's first commercially available electronic general-purpose stored program digital computer.

<span class="mw-page-title-main">Kasparov versus the World</span> Game of chess

Kasparov versus the World was a game of chess played in 1999 over the Internet. It was a consultation game, in which a World Team of thousands decided each move for the black pieces by plurality vote, while Garry Kasparov conducted the white pieces by himself. More than 50,000 people from over 75 countries participated in the game.

<span class="mw-page-title-main">Deep Blue versus Kasparov, 1997, Game 6</span> Chess game between human and computer

Game 6 of the Deep Blue–Kasparov rematch, played in New York City on May 11, 1997 and starting at 3:00 p.m. EDT, was the last chess game in the 1997 rematch of Deep Blue versus Garry Kasparov.

<span class="mw-page-title-main">D. G. Champernowne</span> English economist and mathematician

David Gawen Champernowne, was an English economist and mathematician.

Alick Edwards Glennie (1925–2003) was a British computer scientist, most famous for having developed Autocode, which many people regard as the first ever computer compiler.

<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.

Dietrich Gunther Prinz was a computer science pioneer, notable for his work on early British computers at Ferranti, and in particular for developing the first limited chess program in 1951.

The history of chess began nearly 150 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.

References

  1. 1 2 3 4 5 Copeland, pp. 563-564
  2. ↑ "David Champernowne (1912-2000)". ICGA Journal . 23 (4): 262. December 2000. doi: 10.3233/ICG-2000-23419 .
  3. ↑ Cochlin, Daniel (26 June 2012). "Kasparov versus Turing". University of Manchester . Retrieved 9 April 2019.
  4. 1 2 Levy; Newborn, p. 35
  5. ↑ "Turing, Alan Mathison" . Who's Who (online Oxford University Press  ed.). Oxford: A & C Black. 2017. doi:10.1093/ww/9780199540884.013.U243891.(Subscription or UK public library membership required.)
  6. ↑ Newman, M. H. A. (1955). "Alan Mathison Turing. 1912–1954". Biographical Memoirs of Fellows of the Royal Society . 1: 253–263. doi: 10.1098/rsbm.1955.0019 . JSTOR   769256.
  7. ↑ Gray, Paul (29 March 1999). "Alan Turing – Time 100 People of the Century". Time . Retrieved 7 February 2019.
  8. ↑ Sipser, p. 37
  9. ↑ Beavers, pp. 481–485
  10. 1 2 Hodges, Andrew (30 September 2013). "Alan Turing". Stanford Encyclopedia of Philosophy . Stanford University . Retrieved 22 May 2019.
  11. 1 2 Copeland, Jack; Proudfoot, Diane (2012). "Alan Turing, Founder of the Modern Computer". The Rutherford Journal. 1 (4). ISSN   1177-1380.
  12. ↑ Hodges, p. 488
  13. 1 2 3 4 Beavers, pp. 644–650
  14. 1 2 3 Clark, Liat; Steadman, Ian (7 June 2017). "Remembering Alan Turing: from codebreaking to AI, Turing made the world what it is today". Wired . Condé Nast . Retrieved 7 February 2019.
  15. ↑ "Reconstructing Turing's "Paper Machine"". ICGA Journal . 40 (2): 1–8. June 2018.
  16. 1 2 Oppy; Trakakis, pp. 13–14
  17. ↑ Turing 1953, ch. 25: Digital Computers Applied to Games
  18. ↑ Dasgupta, p. 193
  19. ↑ Turing 2015, ch. 9
  20. ↑ Atkinson, p. 39
  21. ↑ "Player of the Century". New In Chess . Interchess. August 1999. pp. 6–7. ISSN   0168-8782.
  22. 1 2 Kasparov, Garry (June 2012). The Reconstruction of Turing's 'Paper Machine'. Alan Turing Centenary Conference. Manchester, England. Retrieved 9 April 2019– via VideoLectures.net.
  23. ↑ Parnell, Brid-Aine (26 June 2012). "Chess algorithm written by Alan Turing goes up against Kasparov". The Register . Situation Publishing. Retrieved 9 April 2019.

Sources

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.