Concepts familiar from grade-school algebra have broad ramifications in computer science.
Cilk was smooth right up to the endgame.
MIT's Cilkchess, a chess-playing computer program developed at the Laboratory for Computer Science (LCS), breezed through the first five rounds of the 12th Aegon Computer Chess Tournament in the Netherlands from April 16-23, defeating two international masters and playing to a draw against a grand master.
Needing only a draw in round six to finish first among the 50 computers in the tournament, Cilk made a short-sighted blunder early in the match--victimized by its limited ability to anticipate moves in a game.
"I saw it coming," said Don Dailey, a sponsored research staff member at LCS and Cilk's principal programmer. "I knew that our computer had no chance of seeing it. It was beyond our horizon." Cilk, which can evaluate 2.5 million possibilities per second for a single play, could contemplate only 10 future moves (one play by each player) at that point in the match.
Mr. Dailey said he and Cilk's opponent, Dutch International Master Johan van Mil, both recognized the error as fatal at the time. They exchanged a look, Mr. Dailey recalled, in which Mr. van Mil said, in effect, "Gotcha now."
"The computer is tactically smart but weak in position play," said Professor Charles E. Leiserson of LCS, director of the chess program. "It's sort of an idiot savant of chess."
Cilk wound up with four points, tied for 11th with 16 other participants, including eight other computer programs. Three computers finished in the top 10. The tournament had 50 international computer programs and 50 people from 10 countries in the field, including 12 grand masters.
Going into the final round, Cilk had won three matches and played to two draws. Two of the victories were over Dutch International Masters Erik Hoekesma and Gert Ligterink in the fourth and fifth rounds. In round three, Cilk played a draw against Grand Master Yasser Seirawan of the United States, the defending champion who finished second this year.
The winner of the tournament was 26-year-old Israeli Grand Master Yona Kosashvili, with a perfect six points. Mr. van Mil tied Mr. Seirawan for second place with 5.5 points. Overall, the computers defeated the humans, 151.5 to 148.5 points.
During the tournament, Cilk ran on a new 32-bit Silicon Graphics Origin 2000 with four gigabytes of memory, provided by Boston University. Mr. Dailey and LCS postdoctoral fellow Aske Plaat were in the Netherlands for the competition. Along with Professor Leiserson, they are evaluating Cilk's performance in the tournament, hoping to solve the critical problem.
The program was developed by a team that included Professor Leiserson, Mr. Dailey, Dr. Plaat and Christopher Joerg (SB '87). Cilk won the Dutch Open Computer Chess Championship last fall.
A version of this article appeared in MIT Tech Talk on April 30, 1997.