[go: up one dir, main page]
Jump to content

Turochamp

This is a good article. Click here for more information.
From Wikipedia, the free encyclopedia

Turochamp
Developer(s)Alan Turing, David Champernowne
Genre(s)Computer chess
Mode(s)Single-player
This article is part of the series on
Chess programming
Board representations
Evaluation functions
Graph and tree search algorithms
Chess computers
Chess engines
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.

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

[edit]

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

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

[edit]
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.[a] The resulting recreation was presented at the Alan Turing Centenary Conference on 22–25 June 2012, in a game with chess grandmaster and former world champion Garry Kasparov.[22] Kasparov won the game 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

[edit]

Notes

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

References

[edit]
  1. ^ a b c d e 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. ^ a b 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. ^ a b Hodges, Andrew (30 September 2013). "Alan Turing". Stanford Encyclopedia of Philosophy. Stanford University. Retrieved 22 May 2019.
  11. ^ a b 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. ^ a b c d Beavers, pp. 644–650
  14. ^ a b c 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. ^ a b 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. ^ a b 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

[edit]
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Turochamp&oldid=1223905728"