Computing Community Consortium Blog

The goal of the Computing Community Consortium (CCC) is to catalyze the computing research community to debate longer range, more audacious research challenges; to build consensus around research visions; to evolve the most promising visions toward clearly defined initiatives; and to work with the funding organizations to move challenges and visions toward funding initiatives. The purpose of this blog is to provide a more immediate, online mechanism for dissemination of visioning concepts and community discussion/debate about them.


“The Computer’s Next Conquest: Crossword Puzzles”

March 17th, 2012 / in Research News / by Erwin Gianchandani

From yesterday’s New York Times:

Matthew Ginsberg is the man behind a computer program called Dr. Fill  that will be on show at the American Crossword Puzzle Tournament. A recent New York Times crossword puzzle is shown in the foreground [image courtesy The New York Times].What’s a 10-letter word for smarty pants?

 

This weekend the world may find out when computer technology again tries to best human brains, this time at the American Crossword Puzzle Tournament in Brooklyn.

 

Computers can make mincemeat of chess masters and vanquish the champions of “Jeopardy!” The question is: Can the trophy go to a crossword-solving program, Dr. Fill — a wordplay on filling in a crossword (get it?) and the screen name of the talk show host Dr. Phil McGraw — when it tests its algorithms against the wits of 600 of the nation’s top crossword solvers? [More after the jump.]

 

DOCTOR FILL was created by Matthew Ginsberg, 56, who holds a Ph.D. from Oxford, taught at Stanford and wrote a book on artificial intelligence. As a hobby, he also constructs crossword puzzles, including more than two dozen published in The New York Times.

 

The program has already excelled in most simulations of 15 past tournaments, finishing on top three times. Dr. Fill is a speed demon. It can successfully complete easier puzzles in a minute; even lightning-fast human solvers take about three minutes. Hard puzzles may take three minutes, about half as long as human whizzes.

 

Whatever Dr. Fill’s final ranking at the Brooklyn matchup, which ends on Sunday, the program is an impressive achievement, experts say, and a sign of the times. In cerebral games, like chess, bridge, “Jeopardy!” and crossword puzzles, computers can now perform comparably to the top tier of human players — sometimes a bit better, but also sometimes a bit worse.

 

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.

 

“We’re at the point where the two approaches are about equal,” said Peter Norvig, a leading artificial intelligence expert, who is a research director at Google. “But people have real experience. A computer has a shadow of that experience.”

 

Also, people tend to have a sense of humor, and this turns out to be helpful.

 

Puzzle constructors sometimes put in answers not found in the dictionary. For example, in a puzzle with the theme of rabbits, the answer to famous bank robbers might be BUNNY AND CLYDE, Dr. Ginsberg said, which requires a little imagination.

 

Or take this clue from a 2010 puzzle in The Times: Apollo 11 and 12 (180 degrees). The answer is the letters “SNOISSIWNOOW, seemingly gibberish. A clever human could eventually figure out that those letters when flipped 180 degrees, spell MOON MISSIONS.

 

This sort of thing requires imagination and creativity. Humans get the joke, while a literal-minded computer does not. “Occasionally, Dr. Fill just doesn’t get it,” Dr. Ginsberg said. “That’s my nightmare.”

 

At the tournament, players will get six puzzles to solve on Saturday, one at a time, and one on Sunday — progressively more difficult. Rankings are determined by accuracy and speed; contestants raise their hands when done, and roving referees mark the time.

 

The top three finishers enter a playoff round with an eighth puzzle on Sunday afternoon, competing for the $5,000 prize. All the contestants can try to solve the puzzle for fun. Game challenges, though, are not just fun and games, but serious science that has opened the door to practical applications.

 

“Games are a great motivator for artificial intelligence — they push things forward,” said David Ferrucci, the IBM researcher who led the development of Watson, the “Jeopardy!” computer champion. “But what really matters is where it is taking us.”

 

Watson, for example, is being adapted for business uses, first in health care to assist doctors in making diagnoses…

 

How smart is Dr. Fill really?

 

“On the easier puzzles, I think Dr. Fill will kill the field,” said Will Shortz, the tournament director and the crossword puzzle editor for The Times, who has seen a demonstration of Dr. Ginsberg’s program.

 

The real hurdle for Dr. Fill, and perhaps its comeuppance, will come from the harder puzzles, especially those with the tricky themes or wordplay.

 

Dr. Fill was flummoxed by a puzzle from a previous tournament that had the theme of spoonerisms — the switching of first letters in two words. So a clue might be heavy mist, and a logical answer would be LIGHT RAIN. But spoonerized, it becomes RIGHT LAIN.

 

An expert human solver, Mr. Shortz said, would “slap your head and say, ‘Oh, now I get it.’” Not so for Dr. Fill, a bundle of computer code on a notebook computer. “It was totally adrift,” lamented Dr. Ginsberg, whose hobby is constructing crossword puzzles, including more than two dozen published in The New York Times.

 

Dan Feyer, an ace solver who has won the last two tournaments, is betting that Mr. Shortz, who commissions and edits the puzzles, will include one with a quirky twist to try to stump the computer.

 

Mr. Shortz isn’t saying. But he is handing out buttons to anyone who trounces the computer: “I Beat Dr. Fill.” And he is making sure that even if Dr. Fill wins, he will not taste all the fruits of victory. The machine is not eligible for the $5,000 prize.

 

“The tournament is for humans,” Mr. Shortz said.

Check out the full article here.

(Contributed by Erwin Gianchandani, CCC Director)

“The Computer’s Next Conquest: Crossword Puzzles”
  • sabervan

    Awesome, No more words to explain 🙂 🙂 😀 just…cool blog