Friday, June 22, 2012

Alan Turing

Image and video hosting by TinyPic

Alan Turing (June 23, 1912 – June 7, 1954) was a British mathematician and logician who is considered the father of computer science and artificial intelligence (AI). Among his accomplishments were: an independent proof that Hilbert's Entscheidungsproblem was, in general, unsolvable; the invention of the idea of Turing machines; the formulation of the halting problem; played an integral part in breaking the German ciphers in WWII; presented the first design for a stored-program computer; discovered LU decomposition (used to solve matrix equations); invented the idea of the Turing test to determine if a computer could successfully imitate a human; and contributed work in the field of mathematical biology.

More germane to this particular blog, Turing and his colleague, D. G. Champernowne, wrote the first chess engine in 1948, known as Turochamp. Turochamp, though its code was never completely encoded into a computer, played at least one game of chess, with Turing computing the playing algorithm with pencil and paper. It took over an half hour to compute each move.

Here is the PGN of Turochamp's match against Turing's colleague Alick Glennie (courtesy of CPW)

[Event "Paper machine - Human"]
[Site "Manchester, UK"]
[Date "1952"]
[Round "?"]
[White "Turochamp"]
[Black "Alick Glennie"]
[Result "0-1"]
1.e4 e5 2.Nc3 Nf6 3.d4 Bb4 4.Nf3 d6 5.Bd2 Nc6 6.d5 Nd4 7.h4 Bg4 8.a4 Nxf3+ 
9.gxf3 Bh5 10.Bb5+ c6 11.dxc6 0-0 12.cxb7 Rb8 13.Ba6 Qa5 14.Qe2 Nd7 15.Rg1 Nc5
16.Rg5 Bg6 17.Bb5 Nxb7 18.0-0-0 Nc5 19.Bc6 Rfc8 20.Bd5 Bxc3 21.Bxc3 Qxa4 
22.Kd2 Ne6 23.Rg4 Nd424.Qd3 Nb5 25.Bb3 Qa6 26.Bc4 Bh5 27.Rg3 Qa4 28.Bxb5 Qxb5 
29.Qxd6 Rd8 0-1

In 2004, ChessBase published an engine, known as Turing, that was based on Turing's ideas (the actual code for Turochamp does not seem to exist). It was written by Mathias Feist with help from Ken Thompson, and it can be downloaded here.

Sadly, Turing took his own life two years after being convicted in the United Kingdom for gross indecency in connection with a homosexual relationship, which was illegal at that time in the UK. As punishment, Turing chose chemical castration over imprisonment. In 2009, the British Government issued a posthumous apology to Alan Turing for prosecuting him as a homosexual.