Dr. Fill, Crossword Solving Software to Compete with Human Solvers

Dr. Fill, Crossword Solving Software to Compete with Human Solvers

Dr. Fill, a new software than can solve American-style crosswords, is poised to make a keenly-watched debut in the upcoming American Crossword Puzzle Tournament. Dr. Fill has been built by Matt Ginsberg, a former artificial intelligence researcher and now a regular crossword constructor for the New York Times. Matt Ginsberg is also the creator of GIB, the first bridge software to beat several top-ranked human bridge players in 1998.

The crossword solving program has been put through simulations of several past tournament crosswords and has shown consistently high scores. Based on the performance tests conducted so far, Dr. Fill's might place 20th in this year's tournament, The Economist reports.

Dr. Fill will be a "non-ranked participant" in the American Crossword Puzzle Tournament — that is, it won't be competing officially but will solve the puzzles alongside human participants and will submit the solutions to the judges for scoring. According to the banner on the tournament's official site, an "I Beat Dr. Fill" button will be awarded to any contestant who scores higher than Dr. Fill.

What is the secret of Dr. Fill's solving ability?

The abstract for Ginsberg's research paper on JAIR provides this daunting explanation:

Dr.Fill works by converting crosswords to weighted CSPs, and then using a variety of novel techniques to find a solution. These techniques include generally applicable heuristics for variable and value selection, a variant of limited discrepancy search, and postprocessing and partitioning ideas. Branch and bound is not used, as it was incompatible with postprocessing.

Gizmodo makes Dr.Fill's approach sound far more accessible. It is the same one Indians know as ratta.

What makes Dr. Fill so smart, so worthy of competition with those speedy word nerds? Memory. He's basically memorized the entire cannon of crossword puzzles to plug-and-play as needed. Unlike Watson, Dr. Fill wasn't programmed to understand the language of the clues, but rather to play the game.

Dr. Fill's database contains clues and answers for all major American crosswords created since 1900, plus references to online sources like Wikipedia and the movie site IMDb. The program does not try to make sense of the words and clues, instead it sifts through a long list of potential answers for a slot in the grid and fills in the most likely one, then works through the crossing clues.

Will Shortz, crossword editor of the New York Times, sounds skeptical about Dr. Fills ability to beat human crossword solvers but doesn't rule out the possibility [San Francisco Chronicle]:

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. Maybe I'll be proved wrong.

We’ll know soon. The American Crossword Puzzle Tournament begins on 16th March 2012.

Update: Check out this video report about Dr.Fill with shots of the software in action (there's a 30 second ad before the 2:22 min video):