June 23, 2012 18:15

The Turing plug-in

Alan Turing

Today exactly 100 years ago, one of the greatest minds of the 20th century was born in London (from where I happen to be writing this article): Alan Turing. He’s famous, of course, for his ‘invention’ of the modern computer and his still very relevant musings on artificial intelligence, as well as for his role in World War II as a cryptanalyst.

Alan Mathison Turing at the time of his election to a Fellowship of the Royal Society. Photograph was taken at the Elliott & Fry studio on 29 March 1951. 

Alan Turing (1912-1954) was a keen chess player and he even invented a special form of it: “round-the-house” chess, described by Douglas Hofstadter (author of the brilliant Gödel, Escher, Bach) as follows: “after you move, run around the house – if you get back before your opponent has moved, you’re entitled to another move.”

Turing was also the first to develop, on paper, a program capable of playing a game of chess. In fact, he proposed his idea for the notorious “Turing Machine” in the very same paper in which he wrote about the possibility of chess computers.

It’s worth looking up Turing’s original article titled “Digital Computers applied to chess” (1951, published in 1953) on The Turing Digital Archive and admire the typewriter script and the manual corrections in the text.  But it’s even more interesting to read what Turing wrote in the introduction:

When one is asked, “Could one make a machine to play chess?” there are several possible meanings which might be given to the words. Here are a few: –

i) Could one make a machine which would obey the rules of chess, i.e. one which would play random legal moves, or which could tell one whether a given move is a legal one?

ii) Could one make a machine which would solve chess problems, e.g. tell one whether, in a given position, white has a forced mate in three?

iii) Could one make a machine which would play a reasonably good game of chess, i.e. which, confronted with an ordinary (that is, not particularly unusual) chess position, would after two or three minutes of calculation, indicate a passably good legal move?

iv) Could one make a machine to play chess, and to improve its play, game by game, profiting from its experience?

To these we may add two further questions, unconnected with chess, which are likely to be on the tip of the reader's tongue.

v) Could one make a machine which would answer questions put to it, in such a way that it would not be possible to distinguish its answers from those of a man?

vi) Could one make a machine which would have feelings like you and I do?

Nowadays, it’s hard to believe the first three questions were ever in any kind of doubt, but the fourth one is a different matter altogether.

As anyone in possession of a chess playing program or engine surely has experienced, one of the last shortcomings of such software is the ability to teach the machine anything – from a subtle little move in an opening variation to the concept of a fortress, to a particular maneuver in an elementary rook ending.

This inability to learn anything substantial has its hilarious sides. A friend of mine, who somehow still hasn’t tired of playing his terribly strong computer program, happily loses 100 games a day if only he can beat his virtual opponent in the exact same manner twice in a row. Such a thing wouldn’t be possible against a human being, but computers still seem hardly able to learn from their own mistakes.

There’s an interesting comparison to be made with other branches of artificial intelligence, in which  sophisticated self-learning mechanisms have developed more rapidly. For instance, the well-known Tamagotchi virtual pet can, to a certain extent, adapt to previous events and anticipate accordingly. There are also several household-robots that can learn the way around a new house by trial and error.

Given the strength of most chess programs, such functions are still hardly interesting from a commercial point of view. The computer’s embarrassing losses (if a computer could feel embarrassed) that my friend so enjoys are rare indeed - in 99,99% of all games humans play against machines, the result is rather more embarrassing for our species.

Interestingly, Turing in his article didn’t ask that other ‘eternal question’ related to chess and computers: will computers  some day be able to cast the ultimate verdict on any given position, including the starting position?

In 1965, more than ten years after Turing’s death (the circumstances of which have never been fully clarified, the official cause being suicide), the mathematician Richard Bellman did ask the question in a scientific context, and proposed a method to ‘solve’ chess using so-called retrograde analysis. Nowadays, this approach is mostly applied in ‘table base’ development, which focuses on elementary endgames of a maximum of 7 pieces on the board. We still have a long way to go.

Reading Turing’s article in its original layout is a refreshing experience and a wake-up call that despite the incredible progress computer chess has made over the past 60 years, some of the most fundamental issues have still not been resolved.

Wouldn’t it be great if the next breakthrough in commercial computer chess wasn’t another strength increase of 50 rating points (as if computers needed that!) but an entirely new feature that allows users to actually ‘teach’ their program new stuff instead? Such an add-on would surely be the most exciting thing in computer chess since Kasparov-Deep Blue. And in honour of the great man, I propose to call it the Turing plug-in.

Arne Moll's picture
Author: Arne Moll


bondegnasker's picture

Thanks for reminding us of this birthday! But I wonder:
"Turing in his article didn’t ask that other ‘eternal question’ related to chess and computers: will computers some day be able to cast the ultimate verdict on any given position, including the starting position?"
Isn't that just an enhanced version of Turing's second question? And as such, not an actual omission by the great man?

Arne Moll's picture

My interpretation is that he had in mind composed chess problems, not practical (game) positions. But I could be wrong.

Casper's picture

Do composed chess positions possess magical properties that "regular" chess positions do not have? Aside from possibly required depth of evaluation or percieved beauty? Both of which are trivial differences IMHO?

Anonymous's picture

I don't think the difference between composed and 'regular' positions is trivial given that composers can still create positions that computers cannot figure out. For most practical game positions (other than fortresses which are good for drawing only), computers have no problem finding practical solutions.

Casper's picture

But aren't composed positions just a subset of possible game positions? Which means that positions stemming from a normal game can pose exactly the same problems?

Zeblakob's picture

@Casper, no, it is not clear if a composed position can always be reached from the starting position.

Arne Moll's picture

In a composition, the composer can work out all the details before feeding it to the computer for solving (note that Turing himself gives a simple example of a Mate in 3), whereas in a practical position the outcome is completely unclear and may require a fundamentally different approach.

Casper's picture

I think that your assessment that a problem that's solvable within a few moves and a problem that requires a ridiculous depth are fundamentally different is not correct. Yes they require different technigues in modern day computer chess, because we simply cannot completely solve problems at maximum depth, i.e. starting position. However with progressing flops, computer chess definitely will be able to give more accurate verdicts than a human mind can, usually it already can. Whether or not chess can ultimately be solved completely? I'd say yes, without tree pruning, without smart searches, but that is of course a guess.

bondegnasker's picture

Turing's list is clearly organized according to a 'simplest possibility first' principle: First, can the computer differentiate between legal and illegal moves; second, can it calculate a sequence of moves with absolute accuracy (what we now call 'brute force') and so on.

My point was that solving chess falls into the brute force category: Aside from the perceived beauty of a composed study (which is something the computer won't need to pay attention to), there is no fundamental difference between a forced mate i 3 moves and a forced draw in 753 moves (assuming that the latter is an adequate description of the starting position).

Creemer's picture

I bet perceived beauty is not trivial anymore when the observer is a piece of chess software. That would be something.

Maybe that's the translation of Turing's questions to the present:
Will computers ever be able to create beautiful chess studies?

I bet they will be.

Casper's picture

Computers being able to create or perceive beauty like humans, is not trivial I admit, but in the context I feel it is. And I agree with you point, (unless it was meant ironically). Eventually I think AI will be able to perceive and create "beauty" in chess.

Alex's picture

Good article. Indeed success in computer chess is mainly due to brute force and clever heuristics and has nothing to do with machine learning, which is a pity. It might be an interesting challenge to build a computer program which starts at 1200 level but learns from the games and eventually reaches, say 2200 level.

John Doe's picture

Wouldn't that be trivial? Just use a program with good search functions and lousy evaluation functions. Subsequently recalibrate your evaluation functions using information obtained in actual played games by the engine.

Roger's picture

I thought that "self improving" opening books had been invented many years ago. Perhaps they abandoned that line of development when the Fruit/Rybka approach became popular.

The idea of self improving books was that the engine would in effect have access to its own past games, so it wouldn't fall twice for the same trick.

Roger's picture

I thought that "self improving" opening books had been invented many years ago. Perhaps they abandoned that line of development when the Fruit/Rybka approach became popular.

The idea of self improving books was that the engine would in effect have access to its own past games, so it wouldn't fall twice for the same trick.

Chess Fan's picture

As a life-long student and fan of Chess, Computer Science, and Mathematics (amongst others), I find this article fascinating.
Thank you for this article, chessvibes. Appreciate it very much and look forward to more such wonderful articles.
I first heard about the Turing Machine in college from a MIT-trained professor here, who explained how Turing demonstrated that every problem can be set up and solved by the Turing Machine concept (ballroom tissue paper and a set of colored pebbles).

brabo's picture

You can find a very recent article in Dutch language about Tablebases on my blog: http://schaken-brabo.blogspot.be/2012/06/tablebases.html

Latest articles