From: Lincoln Ritter (lritter_at_cs.washington.edu)
Date: Mon Dec 08 2003 - 08:54:28 PST
The Probablistic Cruciverbablist
Keim, Shazeer, Littman, et al.
The authors synthesize diverse AI techniques along with probablistic
methods to develope a fast solver for crossword puzzles.
The paper presents a very sophisticated system for solving crossword
puzzles. The modular design of their system allows for the addition
of new expert modules, speciallized at solving particular types of
clues. Furthermore, by separating the function of various types of
expertise, the contribution of each type of module can be adjusted.
One can imagine this might be done to give certain modules more weight
with certain "genres" of puzzles.
Moreover, the method of probablistically selecting candidates really
makes sense in terms of my intuition about how humans solve these
problems. The solver encounters a clue and based on his/her/it's
previous history with that clue or what he/she/it thinks the clue is
about, tries to "pencil in" a word that probably is right. Since this
is pretty much what humans do, as pointed out by the authors, it is
good to see someone doing some AI that actually makes sense in terms
of how people actually seem to be thinking when trying to solve a
similar problem.
Although citations were offered, some more depth of coverage of the
algorithms used would have been nice: specifically, how to combine
the probablistic candidate generation with the grid constraints.
The authors point out that after looking at the whole CWDB, it is
expected that 34% of the clue/value pairs of a random puzzle will have
been seen. Further, 50% of the clues will have been seen. Given this
information, i would be nice to know how much work each part of the
system was contributing to the final solution. if a large part of the
suzzle is solved by running through a list of clue/value pairs, then
other parts of thes system seem less impressive. Some data please.
This could easily be done by simply turning off some modules.
I guess my ideas for future work stem from the previous criticism. I
would like to see some quantitative analysis of how the system
performs with various parts of it turned off. This would allow us to
see what advantages the probablistic system offers and what advantages
the expert modules offer. As this, methods seems to work fairly well
given a pretty complex problem, it would be well worth the effort to
determine how each of these parts contribute to a final solution so
that the application of methods similar to those presented can be
intelligently applied.
This archive was generated by hypermail 2.1.6 : Mon Dec 08 2003 - 08:54:28 PST