Date: March 19, 2012
Byline: Alex Armstrong
Computer Competes in Crossword Tournament
Can a computer program beat the best human crossword puzzle solvers? Not yet according to the results of last weekend's American Crossword Puzzle Tournament in which the computer was foiled by the ingenuity of the human puzzle setters.
Artificial intelligence can outwit humans at chess and at knowledge quizzes, as demonstrated by IBM's Watson in the Jeopardy TV show last year, but it's not yet honed the subtle skills required to beat us at solving crossword puzzles.
ginsberg
Dr.Fill, a computer program devised by Matt Ginsberg, an artificial intelligence scientist who also constructs crossword puzzles for the New York Times, was an unofficial entrant in the 35th annual crossword challenge in which players solve seven puzzles created especially for the event.
Dr.Fill's participation in the competition was unofficial, in that only humans can win the challenge, but it was also well publicized. Matt Ginsberg presented a talk on the inner workings of his program, whose name is wordplay on crosswording and talk show host Dr. Phil McGraw. This is a topic on which has already published an academic paper in the Journal of Artificial Intelligence Research.
Prior to the event Ginsberg had expected to do well, predicting a place in the top 30 on the basis of having excelled in most simulations of the 15 past tournaments.
However, as Steve Lohr pointed out, writing in the New York Times in advance of the contest:
Humans and machines play the games very differently. Humans recognize patterns based on accumulated knowledge and experience, while computers make endless calculations to determine the most statistically probable answer.
Lohr also quoted artificial intelligence expert and Google research director, Peter Norvig as saying:
“We’re at the point where the two approaches are about equal. But people have real experience. A computer has a shadow of that experience.”
In the event it was the ability of humans to notice and adapt to changes in established patterns that gave them the advantage.
acpt
Although Dr Fill completed the seventh and final puzzle, supposedly the most difficult one, perfectly it was stumped by the second and fifth puzzles, ones that were described as "particularly innovative". One of them included words that had to be spelled backwards and the other required answers not just across and down, but diagonally as well.
Before the contest, last year's winner Dan Feyer (who went on to win again last weekend) said he expected that the contest would include "a puzzle or two that involved innovative twists or patterns to trip up Dr. Fill."
So were puzzles chosen deliberately to put the computer program at a disadvantage? Tournament organizer Will Shortz shook his head and smiled when that question was put to him.
So given these novel twists which Dr Fill could not have anticipated, the ranking of 141st out of 600. which places it in the top fourth of human contestants, isn't too shabby a score. Hopefully it won't deter Matt Ginsberg from pursuing his AI crossword-solving hobby. The hobby is one which fits well with his full time occupation. He is chief executive of On Time Systems whose software is used by the United States Air Force, for calculating the most efficient flight paths for aircraft. Both areas share some of the same statistical techniques — weighted CSPs (Constraint Satisfaction Problems).
More Information
American Crossword Puzzle Tournament
Dr.Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs