Many are familiar with the 1997 defeat of Garry Kasparov, the world’s reigning chess champion, by IBM’s “Deep Blue” computer [1997 NY Times article]. This feat was hailed as a major milestone in the development of artificially intelligent computer systems.
But even this feat was overshadowed by the 2011 defeat of the two most successful contestants on the American quiz show Jeopardy!, by a new IBM-developed computer system named “Watson” [2011 NY Times article]. As we explained in a previous blog article, the Watson achievement was significantly more impressive than the Deep Blue because it involved “natural language understanding,” namely the intelligent “understanding,” in some sense, of ordinary English text [Math Drudge blog #1]. Indeed, Watson more than Deep Blue well deserves the assessment of legendary Jeopardy! champ Ken Jennings, who wrote, on his computer tablet conceding victory to Watson, “I for one welcome our new computer overlords” [Math Drudge blog #2].
Now computer scientist Matthew Ginsberg has his eye on a similarly challenging problem: Defeat the world’s best human crossword puzzle solvers. Ginsberg, who has received a Ph.D. from Oxford and has written a book on artificial intelligence, is presently the Chief Executive Officer of On Time Systems in Eugene, OR. He has already tested his computer program, known as “Dr. Fill,” in a series of crossword puzzle tournaments, finishing on top in three of 15 contests.
Typical full-size newspaper crossword puzzles have roughly 140 words, and, as in Jeopardy!, the clues are often notoriously subtle. As an example, in a 2010 New York Times crossword puzzle with the theme “rabbits,” the correct answer to clue “Famous bank robbers” was “BUNNYANDCLYDE.” As another example, the correct answer for the clue “Apollo 11 and 12 (180 degrees)” was “SNOISSIWNOOW” (i.e., “MOON MISSIONS” written upside down and backwards).
Obviously such machinations require some degree of imagination and creativity. Or, at the least, the computer program’s analysis on other, more straightforward, clues must be so strong that it can still complete the puzzle in spite of its failing to “understand” some of the most subtle clues.
Will Shortz, tournament director and crossword puzzle editor for the New York Times, who has seen a demonstration of “Dr. Fill” in action, believes that the computer program may crush human opponents on easier puzzles. But on more difficult puzzles, particularly those with many subtle clues, it will be a closer match.
David Ferrucci, leader of IBM’s Watson project, agrees that “Games are a great motivator for artificial intelligence — they push things forward.” But he emphasizes that “what really matters is where it is taking us.” He is now involved with an effort to commercialize Watson’s technology in the health care field. Perhaps similar applications will be found for Dr. Fill.
For additional details, see a 2012 NY Times article, from which some of the above is excerpted.