Crossword contest new challenge for computer

Source: San Francisco Chronicle
Date: February 15, 2012
Byline: James Temple

Crossword contest new challenge for computer

"Jeopardy!" was elementary for Watson, IBM's multimillion-dollar artificial intelligence supercomputer that trounced several of the quiz game's champions last year.

But can a computer beat the world's quickest minds in crosswords, a game defined as much by humor and wordplay as logic and knowledge?

We'll see next month, as an artificial intelligence program known as "Dr. Fill" takes part in the world's largest crossword contest, the American Crossword Puzzle Tournament featured in the 2006 documentary "Wordplay."

To be clear, Dr. Fill isn't competing officially. But it'll play alongside the human contestants, and the crossword — and computing — worlds are sure to keep close track of its performance.

Dr. Fill is the creation of Matt Ginsberg, an artificial intelligence scientist and cruciverbalist, the word you should fill in if you're ever starting at the clue: "a creator of crossword puzzles." The Eugene, Ore., software developer has constructed several dozen puzzles that have run in the New York Times — even though he himself is a "terrible crossword solver."

He set off on the project a little more than a year ago, in part because he felt Watson left the public with a false impression about the nature of artificial intelligence.

Lost opportunity

Ginsberg said the popular narrative became that machines are learning to outthink humans, a story line that naturally leads pessimistic imaginations to the "Terminator" movies. He thought it was a lost opportunity to make an important point about the field.

It goes like this: Computers don't think. They're not sentient, nor are they on the verge of becoming so.

But they're really, really good at processing lots of information very quickly. That plus improving artificial intelligence allows us to harness computers to solve increasingly complex problems. They're not about to rise up and take over, but they can take more mundane work off our plates and free us up for uniquely human tasks.

"They just solve problems differently and that's great, because we need help," Ginsberg said. "I hate balancing my checkbook and my computer loves it, as far as I can tell."

Still, programs that play Jeopardy! or solve crossword puzzles do represent a step forward for the field of artificial intelligence, said Peter Norvig, who teaches the subject at Stanford and works on machine learning initiatives as director of research at Google.

"We're not crossing the barrier from nonthinking to thinking machines, but it provides another example of computers dealing with uncertainty; dealing with a messy world rather than a neat world," he said.

The modern approach to artificial intelligence is mostly a matter of pattern recognition and probability. Feed the software algorithm enough documents and things like the arrangement of sentences and proximity of words begin to provide a statistical basis for evaluating the likelihood of an answer to any given query.

But solving crossword puzzles as opposed to playing a quiz game presents advantages and challenges for artificial intelligence.

The crossing words fill in letters for other clues, helping to limit the possibilities for any particular answer. At the same time, crossword creators love to use wordplay and trickery, which can throw off the otherwise orderly world of statistics.

That's one of reasons that Will Shortz, crossword editor for the New York Times and founder of the Brooklyn tournament, is skeptical about a machine's ability to beat the best human crossword players.

"Because of the complexity of the English language, the breadth of subjects covered in puzzles and the playfulness of crossword themes, I've always thought that a human brain would be better than a computer at solving crosswords," he said in a statement. "Maybe I'll be proved wrong."

Ginsberg is confident he's found some novel approaches for getting machines to deal with these challenges.

One common technique in artificial intelligence is to first answer the problem with the most constraints, which in the case of crossword puzzles would mean clues with the least number of possible answers.

Horrible strategy

But this ends up being a horrible strategy because an obvious answer might be obvious because a puzzle creator is trying to trip up the player. That would lead the computer down a series of false paths on additional clues, generating more wrong answers that happen to work with the erroneous crossing letters.

To address this, Ginsberg programmed Dr. Fill to hold off on the seemingly easy ones and explore the possibilities for the spaces around it first, until the level of certainty for that original clue reaches a higher level of probability. That, by the way, is pretty much how skilled human crossword solvers do it, too.

Dr. Fill draws its answers from a database that includes every clue that's appeared in major crosswords since 1990, including the New York Times, Washington Post, Los Angeles Times and elsewhere. In addition, it includes some search-frequency data from Google, a handful of online dictionaries and snippets from the movie site IMDb.com. Like Watson, the database also includes Wikipedia.

There are some big differences from Watson, however. A team of IBM researchers spent years and millions of dollars building the supercomputer, which can process 80 trillion operations per second. Ginsberg developed Dr. Fill himself, and the whole system, including the database, fits on a MacBook Pro.

Asked how Dr. Fill is likely to fare in the tournament, which begins March 16, Ginsberg is as prudent as any good computer scientist should be.

He said there are particular obstacles that "would totally crush it," which he's not about to advertise. But he's also run Dr. Fill through simulations of 17 previous tournaments and it came out on top several times and regularly ranked respectably. He's continued to improve Dr. Fill since those tests.

"If somebody held a gun to my head, I'd say 20th," he said.

Anybody who pulls off a John Henry-like victory over the machine gets a button that reads: "I beat Dr. Fill."

"I'm hoping not a lot of people do," Ginsberg said.