(http://www.nytimes.com/) ____________________________________ March 16, 2012 The Computer’s Next Conquest: Crossword Puzzles By _STEVE LOHR_ (http://topics.nytimes.com/top/reference/timestopics/people/l/steve_lohr/index.html?inline=nyt-per) 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_ (http://nyti.ms/yK5ETr) and _vanquish the champions of “Jeopardy!”_ (http://nyti.ms/zmENjD) But 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? 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. It can 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 humans — 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. This helps. 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 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, and one on Sunday — progressively more difficult. Rankings are determined by accuracy and speed. The top three finishers enter a playoff with an eighth puzzle on Sunday afternoon, competing for the $5,000 prize. Game challenges 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 I.B.M 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. Dr. Ginsberg’s real job is chief executive of On Time Systems, in Eugene, Ore., whose software, used by the United States Air Force, helps in tasks like calculating the most efficient flight paths for aircraft. Some of the statistical techniques in this work are also handy, it turns out, for solving crossword puzzles. A typical puzzle might have 75 words, and up to 10,000 words in the dictionary with the same number of letters as each word in the space, down or across, for the answer. To narrow its choices, Dr. Fill taps a database of millions of answers and clues. If it spots a match, that is a sure thing. If not, Dr. Fill calculates the 100 most probable answers, based on a number of factors, including how prevalent one of its millions of crossword-related words is in Google’s directory of the Web. Dr. Fill can fill a puzzle in as little as five seconds, but then the program does fit and finish work. For example, its initial best guess for a five-letter word across might be BEZEL, Dr. Ginsberg explained. The Z, though, might conflict with a higher-probability answer in a crossing word, going down, which would put W in that space. So Dr. Fill would change BEZEL to JEWEL. 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 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, Mr. Shortz said. 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 Dr. Fill, a bundle of computer code on a notebook computer. “It was totally adrift,” Dr. Ginsberg lamented. 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 -- Centroids: The Center of the Radical Centrist Community <[email protected]> Google Group: http://groups.google.com/group/RadicalCentrism Radical Centrism website and blog: http://RadicalCentrism.org
