Turochamp

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 two-move heuristic to determine the best move to make: it calculates all of the potential moves that it can make, then all of the potential player responses that could be made in turn, assigns a point value to each resulting state, then makes the move with the highest average resulting points.[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]

Alan Turing at age 16

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

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][17][18][19] 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.[20] 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.[21] 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.[22]

• List of chess software
• List of things named after Alan Turing

• Hodges, Andrew (2014). Alan Turing: The Enigma. Princeton University Press. ISBN 978-1-4008-6512-3.
• Beavers, Anthony (2013). Cooper, S. Barry; van Leeuwen, Jan (eds.). Alan Turing: His Work and Impact. Elsevier. ISBN 978-0-12-386980-7.
• Oppy, Graham; Trakakis, Nick (2011). The Antipodean Philosopher. Lexington Books. ISBN 978-0-7391-6655-0.
• Atkinson, George W. (1998). Chess and Machine Intuition. Intellect Books. ISBN 978-1-871516-44-9.
• Copeland, B. Jack (2004). The Essential Turing. Oxford University Press. ISBN 978-0-19-825079-1.
• Levy, David; Newborn, Monty (2009). How Computers Play Chess. Ishi Press. ISBN 978-4-87187-801-2.
• Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-95097-2.
• Dasgupta, Subrata (2014). It Began with Babbage: The Genesis of Computer Science. Oxford University Press. ISBN 978-0-19-930941-2.
• Turing, Dermot (2015). Prof: Alan Turing Decoded. The History Press. ISBN 978-0-7509-6524-8.

• Video of chess match between Garry Kasparov and the Turochamp recreation
• Alan Turing vs Alick Glennie (1952) "Turing Test" at Chessgames.com
• Turochamp (Computer) vs Garry Kasparov (2012) at Chessgames.com
• PyTuroChamp on GitHub — Open Source Python implementation of Turochamp
• Turochamp in a web browser, based on this Nim version: nimTUROCHAMP on GitHub