Chapter 1: Tournaments
Ken Thompson: There was a hostility about computers and chess and humans and chess and, you know, in the same tournament and whether they cheated or not, it was all a big philosophical question. Some people were just adamant. And mostly they were just apprehensive and afraid. And so I made very, very slow inroads into the chess club and built on relationships and things like that. Sponsored, you know, tournaments and always refused prizes, always moved the prizes down, if I ever won prizes. And then played friendly games and played simultaneous exhibitions with the computer. And then pass out, you know, analysis that the computer would print during its game with the people.
If you have a chess machine like this or a program and you're trying to find out how well you're doing, the best way to do that is to take it and play it and get it rated and the rating is a nice number, it says how well you're doing. I had this local chess club, Westfield Chess Club, that I cultivated as a resource to play and I went nearly every week for ten years.
These tournaments, in those days especially, you'd sit across the table from somebody who, you know, who knows chess just like you do and the computers would sit there and play and you're bored, you know, you watch the game but, you know, it doesn't take all that much time. And you talk about algorithms and you'd talk about ideas on what you're going to do about chess and then that would actually fuel you, you know, you'd play six or eight of these people over the course of four or five days.
Then you go back home, kind of absorb everything you learned, and try it, you know, the next year for the next tournament and then come back and it all happens again. That has actually changed. It's much more cutthroat now and they hide their algorithms and the programmers don't talk, they typically have heavy commercial concerns and you saw that changing in the '80s and now it's really changed. I miss the way it used to be. It was almost like a fraternity or something. It was, you know, people who knew. I don't know how to describe it.
Chapter 2: Endgames
Ken Thompson: The second tournament I was in was in San Diego in about '75, '74. And in that tournament David Levy, who is a famous chess personality, was the tournament director. And after the games we were in the bar talking and he was saying that "computers can't play endgames, even simple endgames and they never will." And he said "I am an expert in the rook and pawn against rook endgame and a computer will never play a rook and pawn against rook endgame."
And so, I went to my room that evening and was calculating the numbers and came to the conclusion that this was doable, that you could solve that game, absolutely solve it by a different mechanism, you know, not by normal computer chess but by a different mechanism. You could just have the answer and look it up and make a table of everything you are supposed to do.
And I came back the next day and told him about it and he say's "nah, it takes too many plys, you know", and I said "no, it is ply independent, this is a different method", so he say's "ah no" so he just "poo poo'd me" and I got sort of, angry is not the right word but I got, you know, you know, so I went home and I worked probably for about ten years on endgames. Almost every program now that competes has those endgames just buried in their tables, so that if they run into them they get the answer. They are actually rarely useful, you never run into the endgames in a real game.
Interviewer: Now, how is that? Usually you have an endgame sooner or later, right?
Ken Thompson: No, computer chess games are won in the middle game.
Chapter 3: Algorithms
Ken Thompson: The algorithm is where you start off with the current board position, you trial the moves and then you turn the board around and let the opponent play for each of those moves, he plays all of his moves and then, for each of those, you play yours. And so this is-- this grows exponentially and you plot how many ply you can look ahead...
Interviewer: A ply is?
Ken Thompson: Half a move. So there are 20 or so moves on a board, so two ply will be 400 and three ply will be, you know, bigger and bigger and bigger. That you profile what you're doing and you find all your time is in the mechanics of chess. It's not in the algorithms or the thinking or the evaluation. It's all mechanics, you know, finding the legal moves. And so the very first thing you think of is, you know, an accelerator to make those legal moves a lot faster and you say, aha, one more ply, you know?
And so I made a little tiny chess move accelerator that essentially did what software does, it finds a piece and then walks-- looks for blank squares, you know, wherever the piece would move, radiating out from that piece and lays down those moves. And then what happens is it presents these moves to the software and the software has to pull it out of the hardware. And then, it's kind of hard to go into bu,t you have to sort those moves before you actually play them. You can't play them in the order-- in some random order that they come out of the hardware, you must sort them. So the hardware generates these moves fairly fast and then you pull them out meticulously and laboriously into software and then you sort them and, by the time you do that, the hardware is swamped by the sort and the-- so it did speed things up but not by what you'd normally think of as a hardware solution. It sped it up by, you know, two or three, something like that, instead of 100, which you'd expect out of hardware.
Chapter 4: Hardware
Ken Thompson: Joe Condon and I teamed up and we built a small chess machine that has a LSI-11 in it and three cards, which is about a square foot each. One card was a move generator, it would generate the moves and sort them. And play them. It would actually-- it had a micro machine that would actually play them. It had another card that would evaluate the board. And then it had a third one which was made out of memory chips, 64K bit memory chips that was the transposition table to-- like a big cache so that, when you found a position you've seen before, you can just cough-up the answer instead of reevaluating it. Cut off the search.
That machine made its debut in the US Championships in Washington, DC in '78 and it won them, essentially, for the first time, cutting off Chess X.Y's dynasty. Joe and I then went off and designed another machine after that. It was built on the exact same principles but it was much more parallel. It had three sections. One section was four boards, which was move generation. One section was evaluation, which was four more boards. There was one more board that was micro-code, ran the whole thing. It was conducted by a PDP-11 an LSI-11 and it had commercial memory at this point, one megabyte big, a monster of transposition memory that was run by the microcontroller. It was probably 100 times faster than the other one. It ran about 160,000 positions per second.