Fall 1998 Using the Web to Solve Crossword Puzzles


Regular meeting time: Wednesdays 3pm-4pm D243 (LSRC), working group meeting Wednesdays 4pm-5pm D209.

For the past two years, the American Association for Artificial Intelligence (AAAI) has sponsored a "Hall of Champions" in which the world's best programs play the world's best humans in games such as backgammon, chess, Othello, Scrabble, poker, bridge, checkers, and go. In this seminar, we will try to put together the first-ever program to compete with human beings in tournament crossword-puzzle solving. If successful, we will exhibit the program at the Hall of Champions for 1999. Unlike the other games mentioned, crossword puzzles are AI-complete---that is, solving arbitrary crosswords with human-level performance is as hard as the general human-level-intelligence problem (e.g., the Turing test). As such, our crossword solver will need a tremendous database of lexical and cultural knowledge in machine-readable form---just the sort of thing we can get from the web. We will study and perhaps extend ideas from a variety of disciplines:

We welcome individuals from all backgrounds and at all levels of training---there are lots of interesting experiments to run. We will hold weekly discussions to explore related areas of computer science and AI and to make progress reports. We will also have a number of top-notch invited speakers from inside and outside Duke. Students taking the course for credit will be required to run one seminar session and participate in the programming effort. Auditors are welcome to kibitz and participate in design and brainstorming sessions.

Interested undergrads, please send me email---we can arrange for credit via an independent study. First-year graduate students are also very welcome (in fact, a main goal of the seminar is to give first-year students exposure to AI research at Duke).

Evolving Syllabus

Other Topics


Minda Zetlin. Thinking machines. Games, pages 12--15,61, April 1998.

Will Shortz. Introduction to The New York Times Daily Crossword Puzzles, volume 47, Random House, 1997.

Will Shortz (editor). American Championship Crosswords, Fawcett Columbine, 1990.

Dechter survey

CSP Survey, Dynamic Backtracking

Ginsberg, M. L., Frank, M., Halpin, M. P., & Torrance, M. C. (1990). Search lessons learned from crossword puzzles. In Proceedings of the Eighth National Conference on Artificial Intelligence, pp. 210-215.

Landauer, T. K., Laham, D., & Foltz, P. W., (1998). Learning human-like knowledge by Singular Value Decomposition: A progress report. In M. I. Jordan, M. J. Kearns & S. A. Solla (Eds.), Advances in Neural Information Processing Systems 10, (pp. 45-51). Cambridge: MIT Press.

Chris Manning and Hinrich Schuetze (forthcoming). Foundations of Statistical Natural Language Processing, MIT Press.

Robert Schapire, Yoram Singer, Amit Singhal (to appear). Boosting and Rocchio Applied to Text Filtering. In ACM SIGIR '98.

Amit Singhal, Chris Buckley, Mandar Mitra (1996). Pivoted Document Length Normalization. In ACM SIGIR '96, (pp. 21--29).

Michelle Keim and David D. Lewis and David Madigan. Bayesian Information Retrieval: Preliminary Evaluation. In Preliminary Papers of the Sixth International Workshop on Artificial Intelligence and Statistics, pages 303-310, 1997.

Jay M. Ponte and W. Bruce Croft. A Language Modeling Approach to Information Retrieval. In Proceedings of SIGIR 98, pp. 275-281.

Djoerd Hiemstra. A Linguistically Motivated Probabilistic Model of Information Retrieval. In Christos Nicolaou and Constantine Stephanidis (eds.), Proceedings of the second European Conference on Research and Advanced Technology for Digital Libraries: ECDL'98, Springer-Verlag, pages 569-584, 1998.

Rina Dechter. Bucket Elimination: A Unifying Framework For Structure-driven Inference. To appear in the volume in "Learning and Inference in Graphical Models."

Rina Dechter and Irina Rish. Mini-buckets: a general scheme for approximating inference. Appears as an ICS Technical Report, October, 1998.

Seminar Organizers

Michael L. Littman Greg A. Keim
Last modified: Wed Aug 19 09:46:48 EDT 1998 by Michael Littman, mlittman@cs.duke.edu