Dr.Fill
 | This article needs more citations. (August 2024) |
| Dr.Fill | |
|---|---|
| Developer | Matt Ginsberg |
| Type | Crossword software |
Dr.Fill is a computer program that solves American-style crossword puzzles. It was developed by Matt Ginsberg, who described it in the Journal of Artificial Intelligence Research.[1] Ginsberg claims in that article that Dr.Fill is among the top fifty crossword solvers in the world.
History
[edit]Dr.Fill participated in the 2012 American Crossword Puzzle Tournament, finishing 141st of approximately 650 entrants with a total score of just over 10,000 points.[2][3] It received coverage in the popular press, including The Economist,[4] the San Francisco Chronicle,[5] Gizmodo,[6] and the front page of the March 17, 2012 New York Times.[7]
Dr.Fill continued to place higher in subsequent tournaments,[8] scoring 10,550 in 2013 (92nd place) and 10,790 in 2014 (tied for 67th). Recordings of its solving sessions from both tournaments, including a talk by Ginsberg on its 2014 performance, are on YouTube.[9][10][11]
Its results kept improving after 2014, reaching 10,920 (55th, 2015), 11,205 (41st, 2016) and 11,795 (11th, 2017), before dropping to 10,740 (78th) in 2018 and returning to "form" with 11,795 (14th) in 2019.
The 2020 ACPT was cancelled due to COVID-19, so Dr.Fill competed as a non-competitor in the Boswords tournament instead, outscoring the humans 11,218 to 10,994 despite making one mistake to their zero.
The 2021 ACPT was held virtually, again due to COVID-19. Joined by the Berkeley NLP Group as the hybrid Berkeley Crossword Solver,[12][13] Dr.Fill won the main event with 12,825 points, ahead of the highest-scoring human, Erik Agard, on 12,810.[14][15] The championship playoff was won by Tyler Hinman (12,760 points), who solved the puzzle perfectly in three minutes to Dr.Fill's 49 seconds.
After winning the tournament, Ginsberg announced on August 8, 2021, that both he and Dr.Fill would be retiring from crosswords.[16]
Algorithm
[edit]As described by Ginsberg, Dr.Fill works by converting a crossword to a weighted constraint satisfaction problem and then attempting to maximize the probability that the fill is correct. Probabilities for individual words or phrases are computed with statistical techniques based on features such as prior appearances of the clue and the number of Google hits for the fill. In this respect Dr.Fill tackles a problem similar to the one solved by the Jeopardy!-playing program Watson. It runs on a laptop rather than a supercomputer, and Ginsberg remarks that Watson is far more effective at this part of the task. Instead of computational horsepower, Dr.Fill relies on the constraints provided by crossing words to refine its answers.
A variety of artificial intelligence techniques are applied to find the most likely fill, including a small amount of lookahead, limited discrepancy search,[17] and postprocessing. Ginsberg chose postprocessing over branch and bound because the two techniques are mutually incompatible and postprocessing proved more effective in this domain.
Following Dr.Fill's retirement, later research explored solving crossword clues directly with large language models instead of an explicit constraint-satisfaction search, reporting competitive results without a dedicated grid-search algorithm.[18]
References
[edit]- ↑ "M. L. Ginsberg (2011) Dr.Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs". Jair.org. Archived from the original on 2018-04-23. Retrieved 2012-03-12.
{{cite web}}: CS1 maint: bot: original URL status unknown (link)() - ↑ NPR Staff (2012-03-12). "Paging Dr. Fill: Computer Takes On Crossword Experts". NPR. Retrieved 2026-07-23.
- ↑ Timothy Prickett Morgan (2012-03-19). "Humans best crossword-puzzling computer". The Register. Retrieved 2026-07-23.
- ↑ Glenn Fleishman (2012-03-02). "Artificial intelligence: A match for angry words". The Economist. Retrieved 2012-03-12.
- ↑ James Temple (2012-02-15). "Crossword contest new challenge for computer". Sfgate.com. Archived from the original on February 16, 2012. Retrieved 2012-03-12.
- ↑ Michael Reed (2012-03-02). "Are Computers Human Enough for Crossword Puzzles?". Gizmodo.com. Retrieved 2012-03-12.
- ↑ Steve Lohr (2012-03-16). "The Computer's Next Conquest: Crosswords". The New York Times. Retrieved 2012-03-18.
- ↑ Adam Wernick; Annie Minoff (2014-09-24). "'Dr. Fill' vies for crossword solving supremacy, but still comes up short". The World from PRX. Retrieved 2026-07-23.
- ↑ "Dr.Fill and the 2013 ACPT (Saturday)". YouTube.
- ↑ "Dr.Fill and the 2013 ACPT (Sunday)". YouTube.
- ↑ "Dr.Fill and the 2014 ACPT". YouTube.
- ↑ Eric Wallace (2022-05-20). "The Berkeley Crossword Solver". BAIR Blog. Retrieved 2026-07-23.
- ↑ Eric Wallace (2022). Automated Crossword Solving. Association for Computational Linguistics. arXiv:2205.09665.
- ↑ Oliver Roeder (2021-04-27). "Dr. Fill, an A.I., won the American Crossword Puzzle Tournament. Here's how". Slate. Retrieved 2026-07-23.
- ↑ Magdalene L. Crowley (2021-05-26). "NLP team helps a computer win the 2021 American Crossword Puzzle Tournament". "Krzyżówki". EECS at Berkeley. Retrieved 2026-07-23.
- ↑ Reena Debray (2022-05-01). "Dr. Fill in the blanks". Berkeley Science Review. Retrieved 2026-07-23.
- ↑ W. D. Harvey; M. L. Ginsberg (1995). "Limited Discrepancy Search". pp. 607–613. CiteSeerX 10.1.1.34.2426.
- ↑ Soumadeep Saha (2024). "Language Models are Crossword Solvers". arXiv:2406.09043 [cs.CL].