Can you guess when the first chess program was written – relative to the invention of computers? Ten years later? Wrong. Five? Wrong. The great mathematician Alan Turing did it sooner than that. During the celebrations of his 100th anniversary, in Manchester, June 2012, Garry Kasparov and I delivered a lecture on the reconstruction of the engine Turing programmed. The process has been described in a scientific paper by Frederic Friedel and Garry Kasparov, published here.
It is an amazing fact that the very first chess program in history was written a few years before computers had been invented! It was designed by a visionary man who knew that programmable computers were coming and that, once they were built, they would be able to execute a program to play chess.
The man, of course, was Alan Turing (sculpture in Bletchley Park), one of the greatest mathematicians who ever lived. He was very interested in chess, but in spite of having a brilliant intellect and putting a lot of effort into improving his game, he remained a fairly weak player. While working at Bletchley Park on breaking the German Enigma code, which decisively influenced the outcome of the World War II, he took chess lessons from GM-strength colleagues in the decryption team. Turing also invented Round-the-house chess: after each move you had to run around the house, and could play two moves in a row if you overtook your opponent. Turing was an Olympic-class runner, and this was his way of balancing out his lack of chess talent.
In 1948 Turing, assisted by his friend David Champernowne, wrote the instructions that would enable a future machine to play chess. They called the program Turochamp, but it popularly became known as “Turing's paper machine.” The goal was to make a machine which would play a reasonably good game of chess, i.e. which, confronted with an ordinary chess position, would after two or three minutes of calculation, indicate a passably good legal move.
At the time there was no machine, of course, that could execute this set of instructions, and so Turing acted as a human CPU, using paper and pencil, requiring more than half an hour to calculate each move. He played a game against Champernowne's wife, who was a rank beginner at chess, and won. Then he played one against a colleague, Alick Glennie, and lost. This second game was recorded. There is a scan of Turing's “Faster-Than-Thought” paper on Google Docs. In the original submission, typed by the author on yellow paper, with ink corrections, Turing quotes the game against Glennie:
Interestingly, nobody seems to have written an actual computer program using Turing’s algorithm, for more than fifty years after he devised it. In 2004, the programming team at ChessBase decided to reconstruct Turing’s paper machine. The basis was his description and the one sample game against Glennie, and the programmer who undertook the task was Mathias Feist. He built the engine with a standard interface for the ChessBase Fritz program, so that the Turing engine could be tested.
In the process, however, the ChessBase team encountered a problem: the engine refused to duplicate all of Turing’s moves as recorded in the Glennie game. It deviated in ten places – significantly already on the first move: the Fritz Turing engine wanted to play 1.e3, whereas Turing had executed 1.e4 in his 1952 game.
The ChessBase team spent some weeks carefully re-examining the Turing papers and discussing the implementation in the Turing engine. Since we could not locate the error, we consulted Ken Thompson, one of the pioneers of computer chess. Ken spent some time wrestling with the problem, and in fact wrote his own code on the basis of his reading of the Turing instructions. His program duplicated the ChessBase deviations from the Glennie game. It was quite baffling.
So I contacted Donald Michie, who had worked with Turing at Bletchley. “It is possible that we have got something wrong,” I said. Michie’s reaction was: “You are looking for a bug in the program, Frederic? No, no, you should look for it in Turing! Alan did not care about details; he was interested in the general principle.” He also pointed us to a quote by Champernowne, who had assisted Turing during the 1952 game: “In the actual experiment I suspect we were a bit slapdash about all this and must have made a number of slips, since the arithmetic was extremely tedious with pencil and paper.”
On the trip to the Alan Turing Centenary Conference I stopped over at Bletchley Park. That was on June 23rd, 2012, Turing’s 100th birthday! It was a visit I will never forget. In Manchester I assisted Garry Kasparov in a commemorative lecture on Turing’s chess involvement. We spoke about the reconstruction of the paper machine, and Kasparov actually played a game against it. You can watch the entire one-hour lecture here.
In the lecture, I discussed the deviations we were confronted with and how they probably came about. An important point is that Turing, working with paper and pencil, clearly used his intuition to come up with the moves. And without knowing it he used Alpha-Beta pruning, a technique that was invented by Allen Newell and Herbert A. Simon half a decade later, when machines could actually execute code. Essentially, Turing did not bother to calculate every single move in a position. Some he thought were clearly inferior, and it seemed pointless to spend a lot of time calculating exactly how bad they were (which is the point of Alpha-Beta).
In the lecture we discussed the problem of the very first move: Turing played 1.e4, the ChessBase engine (and Thomson’s reconstruction) come up with 1.e3. In the initial position material is equal, no pieces are taken, nothing has happened yet. There are twenty legal moves for White – each of the eight pawns can move up one or two squares, and the two knights have two moves each. One wonders if Turing made 20 calculations, each taking a number of minutes, before he executed the first move, 1.e2-e4. It is one of the two most common moves that start a chess game (the other is 1.d2-d4).
Turing and Champernowne used the following piece values: pawn=1, knight=3, bishop=3½, rook=5, queen=10, and in addition had the seven positional evaluation functions. If we apply Turing’s rules to the initial position, the e-pawn gets 0.4 points for moving two squares forward, but just 0.2 points for moving one step. So 1.e4 is better. But then we apply Turing’s king safety rule – defined as the number of squares from which the king could be attacked by a rook or a bishop. 1.e2-e3 gets a malus of 1, whereas 1.e2-e4 reduces the positional advantage by 1.4 points.
In his game score Turing gives 4.2 points for the move he played, 1.e2-e4, and adds an asterisk to the value, which indicates that “every other move has a lower position-play value.” But the ChessBase engine, and that of Ken Thompson, give the pawn move to e3 a positional value of 4.4. “Turing‘s calculation for e2-e4 is correct,” Mathias Feist said. “This means he did not really calculate e2-e3. As a chess player, he knew that this move is not logical, because in the initial position king safety doesn’t play a role. He probably looked at it and thought: everything is the same for both moves, except e2-e3 is 0.2 points worse because the pawn moves just one square. So he discarded it without further calculation.”
Let us take a look at move four: Turing played 4.Ng1–f3 and gave a value of 2.0. The ChessBase Turing engine plays 4.d4xe5 and give it a value of 1.1. Why?
After 4.Ng1-f3 the mobility of the queen on d1 sinks from six to three squares, and consequently the positional value from 2.4 to 1.7 (minus 0.7). The mobility of the knight g1 increases from three to five squares, and so the score increases from 1.7 to 2.2 (= +0.5). The mobility of the rook on h1 increases from 0 to 1 square, improving the score from 0.0 to 1.0 (= +1.0). So 4.Ng1-f3 improves the evaluation of the position by 0.8 points.
After 4.d4xe5 the d4 pawn has advanced by one square (+0.2) but is no longer defended (-0.3). The mobility of the queen increases from 6 to 9 squares (+0.6). The black pawn on e5 has disappeared, and with it the bonus for the two rows it had advanced (+0.4 for White). The black king safety increases from 4 to 5 (+0.2 for White). So in total 4.d4xe5 increases the score by 1.1 points.
There are a number of other deviations, more towards the end, when Turing was apparently tiring. The game clearly demonstrates how tedious and error-prone human calculation in such a situation can be. On a modern computer the ChessBase Turing engine needs less than five milliseconds to calculate the values for all legal moves in a given position, and to choose the best one to play. Turing took fifteen to twenty minutes.
For those of you who want to experiment with the ChessBase Turing engine – or simply play a game against this historical chess program – there is a download that will run as a UCI engine on any Fritz-compatible chess software. It also contains the full Manchester lecture by Friedel and Kasparov.