Someone posted a pointer to a 2005 interview of Ken Thompson by John Mashey in which they discuss Thompson’s work on computer chess. It’s unusual, as far as Thompson interviews go, because it doesn’t mention Unix except to note that one of Thompson’s first chess programs appeared in the some early versions of Unix. The interview concerns itself entirely with computer chess.
One of the things that comes through clearly is that a lot of Thompson’s success came about from his playing around with computers just for the fun of it. Most of us know that Unix came about largely because of that dynamic and his successes with computer chess are the same. It’s clear from the interview that he really enjoyed the computer chess tournaments and that he was doing it not for fame or to win prizes but for fun.
Most people think of computer chess as a premier application of artificial intelligence but, in fact, there’s virtually no AI involved. It’s all brute force. The algorithms are mostly concerned with generating possible moves at each board position, pruning infeasible solutions, and picking (one of) the best of those that remain. Thompson says that the winning computer was usually fastest because it could look at more possibilities in the given time.
An interesting thing I learned from the interview was how computer chess programs handle endgames. It was widely held that a program would never be able to handle endgames. One chess expert even poked fun at Thompson for thinking otherwise. Of course, Thompson took that as a challenge and showed that it could be done. The method is entirely different from that used in the beginning and middle games. It’s worth reading the interview just to see how Thompson solved the problem.
If you have any interest in computer chess or in seeing another example of Thompson’s genius you should take a look at this interview.