Dr.Fill
 | This article needs additional citations for verification. (August 2024) |
| Developer(s) | Matt Ginsberg |
|---|---|
| Type | Crossword software |
Dr.Fill is a computer program that solves American-style crossword puzzles. It was developed by Matt Ginsberg and described by Ginsberg in an article 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. The appearance led to a variety of descriptions of Dr.Fill in the popular press, including The Economist,[2] the San Francisco Chronicle[3] and Gizmodo.[4] A description of Dr.Fill appeared on the front page of the March 17, 2012 New York Times.[5]
Dr.Fill's score in 2013 improved to 10,550, which would have earned it 92nd place. Videos of the program solving the problems from the tournament are available on YouTube.[6][7] The score in 2014 improved further to 10,790, which would have tied for 67th place. A video of the program solving the first six puzzles from that tournament, together with a talk given by Ginsberg describing its performance, can be found on YouTube.[8]
Dr.Fill has largely continued to improve since the 2014 event. In 2015, it scored 10,920 points and finished in 55th place. In 2016, it scored 11,205 points and finished in 41st place. In 2017, it scored 11,795 and finished in 11th place. In 2018, it scored 10,740 points, dropping to 78th place. Dr.Fill returned to "form" in 2019, once again scoring 11,795 and finishing in 14th place.
The 2020 ACPT was cancelled due to COVID-19, and Dr.Fill participated as a non-competitor in the Boswords tournament instead. The program outperformed the humans, scoring 11,218 points (fast solves with a total of one mistake) while the best scoring human scored 10,994 points (slower solves but no mistakes).
The 2021 ACPT was virtual, again due to COVID-19. The Dr.Fill effort was joined by the Berkeley NLP Group, creating a hybrid system named Berkeley Crossword Solver,[9] and Dr.Fill won the main event, scoring 12,825 points with Erik Agard, the highest scoring human, scoring 12,810 points. The tournament was won by Tyler Hinman (12,760 points), who completed the championship puzzle perfectly in three minutes. Dr.Fill also completed that puzzle perfectly, but in 49 seconds.
After winning the tournament, Ginsberg announced on August 8, 2021, that both he and Dr.Fill would be retiring from crosswords.
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 in the puzzle are computed using relatively simple statistical techniques based on features such as previous appearances of the clue, number of Google hits for the fill, and so on. In doing this, Dr.Fill is attempting to solve a problem similar to that tackled by the Jeopardy!-playing program Watson; Dr.Fill runs on a laptop instead of a supercomputer and Ginsberg remarks that Watson is far more effective than Dr.Fill at solving this portion of the problem. Instead of computational horsepower, Dr.Fill relies on the constraints provided by crossing words to refine its answers.
A variety of techniques from artificial intelligence are applied to attempt to find the most likely fill. These include a small amount of lookahead, limited discrepancy search,[10] and postprocessing. Ginsberg remarks that postprocessing was chosen over branch and bound because the two techniques are mutually incompatible and postprocessing was found to be more effective in this domain.
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)() - ^ 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. 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.
- ^ "Dr.Fill and the 2013 ACPT (Saturday)". YouTube.
- ^ "Dr.Fill and the 2013 ACPT (Sunday)". YouTube.
- ^ "Dr.Fill and the 2014 ACPT". YouTube.
- ^ "The Berkeley Crossword Solver"; "Automated Crossword Solving", Wallace et al 2022
- ^ W. D. Harvey; M. L. Ginsberg (1995). "Limited Discrepancy Search". pp. 607–613. CiteSeerX 10.1.1.34.2426.