From: Daniel Lowd (lowd_at_cs.washington.edu)
Date: Sun Dec 07 2003 - 19:57:27 PST
"PROVERB: The Probabilistic Cruciverbalist"
by Keim, Shazeer, Litttman, et al.
This paper describes an automated crossword puzzle solver, its many
components, and the insights gained into the problem domain.
Its primary contribution is to suggest that solving crossword puzzles is a
good testbed for artificial intelligence, and to demonstrate that it is
already a tractable problem. While researchers have focused on chess for
decades, crossword puzzles are interesting in that they require real-world
knowledge as well. Its second contribution is to detail their solution,
which integrated many heterogeneous systems and different fields of AI.
This project was an excellent example of how diverse strategies and
approaches can be successfully combined to achieve decent results on a
real-world problem.
The one thing I would have liked to see in this paper is some ideas about
future work. While PROVERB looks like a massive undertaking, something
very hard to duplicate, it would still be nice to know how to improve it.
What sorts of clues posed the biggest problem for PROVERB, and how might
IR techniques or search heuristics be developed in the future to better
solve these?
It remains an open question as to how much better AI techniques can do on
crossword puzzles. Would faster computers or larger databases make a big
difference, or do diminishing returns imply some asymptotic limit?
Furthermore, I wonder if some optimizations could lead to faster answers
or let PROVERB handle larger databases in the same time. For example,
when can potential answers be pruned? Could the results of some experts
be used to constrain the searches of other experts?
This archive was generated by hypermail 2.1.6 : Sun Dec 07 2003 - 19:57:29 PST