Final Results
Angry Words: An Automated Crossword-Puzzle Solver
Advisor: David Liben-Nowell
I. Background
Crossword puzzles are riddled with facts about the world (Giant slugger Mel; The shallowest great lake; Computer that debuted in 1946), basic "language use" knowledge (Happy as ; Word after labor or arbor), not to mention basic dictionary knowledge (synonyms), plus bad puns and vicious wordplay. Solving crosswords feels like a uniquely human endeavor—but then again, so did chess (Deep Blue) and Jeopardy! (Watson). In the most recent American Crossword Puzzle Tournament, a computer entrant named Dr. Fill, written by Dr. Matt Ginsberg, placed in the top tier of crossword solvers in the world.
Solving puzzles is hard: one needs to mix, on one hand, various knowledge sources that generate guesses about answers with, on the other, the constraints formed by the crossing words. Even the best solvers maintain competing hypotheses for a single word; they select among these hypotheses using the crossing entries (perhaps propagating information from far away in the grid).
II. The Project
For this project, you will implement an automated software system to solve crossword puzzles. A rough outline of your work on this project will be something like the following:
- Research the existing crossword-solving programs and the Jeopardy!-playing system Watson.
- Design an overall system architecture. How will you collect knowledge that may answer clues? How will you combine guesses on individual answers into a solution for the puzzle as a whole?
- Develop a platform for world- and language-knowledge facts that allows you to suck in facts about the world (from a dictionary or Wordnet or an atlas or the web or whatever) and proposes possible answers to a given clue, with some measure of confidence.
- Develop a algorithm to fill a grid. Given proposed possible answers, with confidences, how do you fill the grid?
- Develop a test plan. How will you identify "what went wrong" when you program gets stuck? How will you iteratively improve your fact platform or your algorithm?
III. References
Existing crossword-solving software:
- Matthew L. Ginsberg. Dr. Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs. Journal of Artificial Intelligence Research, 2011.
- Michael L. Littman, Greg A. Keim, Noam M. Shazeer. A probabilistic approach to solving crossword puzzles, Artificial Intelligence, 2002.
- Marco Ernandes, Giovanni Angelini, Marco Gori. WebCrow: a WEB-based system for CROssWord solving AAAI, 2005.
- David Ferrucci, Eric Brown, Jennifer Chu-Carroll, James Fan, David Gondek, Aditya A. Kalyanpur, Adam Lally, J. William Murdock, Eric Nyberg, John Prager, Nico Schlaefer, and Chris Welty. Building Watson: An Overview of the DeepQA Project. AI Magazine, 2010.
For background:
- Stuart Russell and Peter Norvig. Artificial Intelligence, A Modern Approach, 3rd edition., Prentice Hall, 2009.