Dr.Fill

Last updated
Dr.Fill
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.

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, [2] 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.

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, [3] the San Francisco Chronicle [4] and Gizmodo. [5] A description of Dr.Fill appeared on the front page of the March 17, 2012 New York Times. [6]

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. [7] [8] 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. [9]

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, [10] 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.

Related Research Articles

<i>Sokoban</i> 1981 video game

Sokoban is a puzzle video game in which the player pushes boxes around in a warehouse, trying to get them to storage locations. The game was designed in 1981 by Hiroyuki Imabayashi, and first published in December 1982.

<span class="mw-page-title-main">Crossword</span> Grid-based word puzzle

A crossword is a word game consisting of a grid of black and white squares, into which solvers enter words or phrases ("entries") crossing each other horizontally ("across") and vertically ("down") according to a set of clues. Each white square is typically filled with one letter, while the black squares are used to separate entries. The first white square in each entry is typically numbered to correspond to its clue.

<span class="mw-page-title-main">Peter Norvig</span> American computer scientist (born 1956)

Peter Norvig is an American computer scientist and Distinguished Education Fellow at the Stanford Institute for Human-Centered AI. He previously served as a director of research and search quality at Google. Norvig is the co-author with Stuart J. Russell of the most popular textbook in the field of AI: Artificial Intelligence: A Modern Approach used in more than 1,500 universities in 135 countries.

<i>Artificial Intelligence: A Modern Approach</i> Book by Stuart J. Russell and Peter Norvig

Artificial Intelligence: A Modern Approach (AIMA) is a university textbook on artificial intelligence, written by Stuart J. Russell and Peter Norvig. It was first published in 1995 and the fourth edition of the book was released on 28 April 2020. It has been called "the most popular artificial intelligence textbook in the world", and is considered the standard text in the field of artificial intelligence. As of 2023, it is used in over 1500 universities worldwide, and it has over 59,000 citations on Google Scholar. The book is intended for an undergraduate audience but can also be used for graduate-level studies with the suggestion of adding some of the primary sources listed in the extensive bibliography.

<span class="mw-page-title-main">Stuart J. Russell</span> British computer scientist and author (born 1962)

Stuart Jonathan Russell is a British computer scientist known for his contributions to artificial intelligence (AI). He is a professor of computer science at the University of California, Berkeley and was from 2008 to 2011 an adjunct professor of neurological surgery at the University of California, San Francisco. He holds the Smith-Zadeh Chair in Engineering at University of California, Berkeley. He founded and leads the Center for Human-Compatible Artificial Intelligence (CHAI) at UC Berkeley. Russell is the co-author with Peter Norvig of the authoritative textbook of the field of AI: Artificial Intelligence: A Modern Approach used in more than 1,500 universities in 135 countries.

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore an assignment of values to the variables that satisfies all constraints—that is, a point in the feasible region.

<i>The Cross-Wits</i> American television game show

The Cross-Wits is an American syndicated game show which premiered on December 15, 1975, and lasted for five seasons until its cancellation on September 12, 1980. The show was hosted by Jack Clark, with Jerri Fiala as hostess. Announcing duties were handled by John Harlan, Jay Stewart, and Jerry Bishop. The show was produced by Ralph Edwards Productions and distributed by Metromedia Producers Corporation.

<span class="mw-page-title-main">American Crossword Puzzle Tournament</span>

The American Crossword Puzzle Tournament is a crossword-solving tournament held annually in February, March, or April. Due to the COVID-19 pandemic, the 2020 tournament was canceled. In April 2021, the 43rd tournament was held virtually. Founded in 1978 by Will Shortz, who still directs the tournament, it is the oldest and largest crossword tournament held in the United States; the 2019 event set an attendance record with 741 competitors, including over 200 rookies.

Computer bridge is the playing of the game contract bridge using computer software. After years of limited progress, since around the end of the 20th century the field of computer bridge has made major advances. In 1996 the American Contract Bridge League (ACBL) established an official World Computer-Bridge Championship, to be held annually along with a major bridge event. The first championship took place in 1997 at the North American Bridge Championships in Albuquerque. Since 1999 the event has been conducted as a joint activity of the American Contract Bridge League and the World Bridge Federation. Alvin Levy, ACBL Board member, initiated this championship and has coordinated the event annually since its inception. The event history, articles and publications, analysis, and playing records can be found at the official website.

The New York Times crossword puzzle is a daily American-style crossword puzzle published in The New York Times, online on the newspaper's website, syndicated to more than 300 other newspapers and journals, and on mobile apps.

<span class="mw-page-title-main">Michael L. Littman</span> American computer scientist

Michael Lederman Littman is a computer scientist, researcher, educator, and author. His research interests focus on reinforcement learning. He is currently a University Professor of Computer Science at Brown University, where he has taught since 2012.

<span class="mw-page-title-main">Computational creativity</span> Multidisciplinary endeavour

Computational creativity is a multidisciplinary endeavour that is located at the intersection of the fields of artificial intelligence, cognitive psychology, philosophy, and the arts.

<span class="mw-page-title-main">Progress in artificial intelligence</span> How AI-related technologies evolve

Progress in artificial intelligence (AI) refers to the advances, milestones, and breakthroughs that have been achieved in the field of artificial intelligence over time. AI is a multidisciplinary branch of computer science that aims to create machines and systems capable of performing tasks that typically require human intelligence. Artificial intelligence applications have been used in a wide range of fields including medical diagnosis, economic-financial applications, robot control, law, scientific discovery, video games, and toys. However, many AI applications are not perceived as AI: "A lot of cutting edge AI has filtered into general applications, often without being called AI because once something becomes useful enough and common enough it's not labeled AI anymore." "Many thousands of AI applications are deeply embedded in the infrastructure of every industry." In the late 1990s and early 21st century, AI technology became widely used as elements of larger systems, but the field was rarely credited for these successes at the time.

<span class="mw-page-title-main">Bruce Wilcox</span> Artificial Intelligence researcher (born 1951)

Bruce Wilcox is an artificial intelligence programmer.

The WebCrow is a research project carried out at the Information Engineering Department of the University of Siena with the purpose of automatically solving crosswords.

<span class="mw-page-title-main">Competitive programming</span> Mind sport

Competitive programming is a mind sport involving participants trying to program according to provided specifications. The contests are usually held over the Internet or a local network. Contestants are referred to as sport programmers. Competitive programming is recognized and supported by several multinational software and Internet companies, such as Google and Facebook.

<span class="mw-page-title-main">Lichess</span> Internet chess platform

Lichess is a free and open-source Internet chess server run by a non-profit organization of the same name. Users of the site can play online chess anonymously and optionally register an account to play rated games. Lichess is ad-free and all the features are available for free, as the site is funded by donations from patrons. Features include chess puzzles, computer analysis, tournaments and chess variants.

This glossary of artificial intelligence is a list of definitions of terms and concepts relevant to the study of artificial intelligence, its sub-disciplines, and related fields. Related glossaries include Glossary of computer science, Glossary of robotics, and Glossary of machine vision.

<span class="mw-page-title-main">Marie desJardins</span> American computer scientist

Marie desJardins is an American computer scientist, known for her research on artificial intelligence and computer science education. She is also active in broadening participation in computing.

Dan Feyer is a crossword solver and editor and the eight-time winner of the American Crossword Puzzle Tournament (ACPT). He holds the tournament record for the most championships ever, with nine total championships, and the most consecutive championships, with six. He was described by The New York Times as "the wizard who is fastest of all," solving The New York Times' Saturday crossword in an average of 4:03 minutes each week and the Sunday crossword in an average 5:38 minutes. He is listed in the Guinness World Records for both "Most wins of the American Crossword Puzzle Tournament" and "most consecutive ACPT wins."

References

  1. ↑ "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)()
  2. ↑ W. D. Harvey; M. L. Ginsberg (1995). "Limited Discrepancy Search". pp. 607–613. CiteSeerX   10.1.1.34.2426 .
  3. ↑ Glenn Fleishman (2012-03-02). "Artificial intelligence: A match for angry words". The Economist. Retrieved 2012-03-12.
  4. ↑ James Temple (2012-02-15). "Crossword contest new challenge for computer". Sfgate.com. Retrieved 2012-03-12.
  5. ↑ Michael Reed (2012-03-02). "Are Computers Human Enough for Crossword Puzzles?". Gizmodo.com. Retrieved 2012-03-12.
  6. ↑ Steve Lohr (2012-03-16). "The Computer's Next Conquest: Crosswords". The New York Times. Retrieved 2012-03-18.
  7. ↑ "Dr.Fill and the 2013 ACPT (Saturday)". YouTube .
  8. ↑ "Dr.Fill and the 2013 ACPT (Sunday)". YouTube .
  9. ↑ "Dr.Fill and the 2014 ACPT". YouTube .
  10. ↑ "The Berkeley Crossword Solver"; "Automated Crossword Solving", Wallace et al 2022
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.