For many students, crossword puzzles are a way to pass time during class. For a group of students last semester, passing their class hinged on dissecting crossword puzzles.
These students, led by Assistant Professor of Computer Science Michael Littman and computer science graduate students Greg Keim and Noam Shazeer, created the first computer program able to solve American crossword puzzles.
In the 22nd Annual American Crossword Puzzle Tournament this past March, the program, called Proverb, placed 147th out of 254.
Proverb assesses the crossword's across and down clues separately and then determines the best grid layout of possible answers. It selects responses from a database that contains facts on various topics and about 400,000 previous crossword puzzle clues.
The class that created Proverb consisted of two undergraduates, three master's degree students, four doctoral students, and a visiting professor. On the first day of class, Littman handed out an essay by New York Times Crossword Puzzle Editor Will Shortz outlining his belief that it was impossible for a computer to match humans at solving crossword puzzles.
"I told them, 'This should make your blood boil,'" Littman said. "People got pretty excited about that."
The class spent the entire semester designing a program to meet the challenge. Littman said, "Usually in artificial intelligence, the technology is given and you try to determine what problem it could solve. This class started from a problem and then searched for the technology to solve it."
During class, students learned about different artificial intelligence techniques and then had small-group meetings to implement the solver. "Each person worked on a different module of the solver that does a specific type of clue," said Shannon Pollard, a computer science graduate student. "My part tried to answer clues on movies and television, for example."
The tournament provided a way for the team to assess Proverb's success even though it was not an official competitor. In the world of artificial intelligence, crossword puzzles "seem harder than the traditional game [computers usually solve] because of the natural language element," Pollard said, "I think we were all really pleased that it actually works as well as it does."
Littman's team wrote two papers on Proverb and its technical elements. The team will present the papers at the American Association of Artificial Intelligence conference this summer.
Although Littman does not foresee an opportunity to teach a similarly focused class in the near future, he said he would definitely enjoy doing so again. "It worked out very well," he said. "The students were very enthusiastic about the goal. Everyone worked very well together."
Get The Chronicle straight to your inbox
Signup for our weekly newsletter. Cancel at any time.