From: Seth Cooper (scooper@cs.washington.edu)
Date: Mon Dec 06 2004 - 09:06:32 PST
The paper read is titled "PROVERB: The Probabilistic Cruciverbalist"
written by Keim et al. It presents a method for solving crossword
puzzles that combines many different AI techniques, such as search and
constraint satisfaction.
One relatively open realm of puzzle solving is that of word based
puzzles. Before this paper, there had been no broad-coverage computer
programs that solved crossword puzzles. Therefore, an important result
of this paper is the program's overall success in solving crossword
puzzles. Although it is not able to beat the world's human champions,
it far exceeds the ability of most casual human players, complete
puzzles with around 95% word accuracy. Considering that this is the
first step in the field of general crossword puzzle solving, it is an
impressive one, bringing to bear a large number of fundamental AI
concepts. Perhaps the importance of this paper lies not in the specific
application of solving crossword puzzles, but rather in the fact that an
amalgamation of techniques can be tied together to produce such an
interesting result. Another strength of the algorithm presented is that
because if its modularity; it is highly extensible. If another group of
researchers were to come up with an idea for a better way to generate
candidates from a given set of clues, it would be very easy to plug it
into PROVERB and test it out.
One weakness of the paper is the general usefulness of a program that
solves crossword puzzles. The enjoyment of a crossword puzzle for a
human lies in the solving of it. A program that solves crossword
puzzles is fundamentally different from one that, for example, plays
chess. Even though the crossword program's relative performance against
human players can be measured, it is not really competing directly
against the humans. For instance, when a human plays chess against a
computer opponent, the game the human is playing will be affected by the
skill level of the computer, and the human can enjoy the computer as an
adversary, perhaps using the computer to train and learn. There is no
adversarial component of solving a crossword puzzle; in essence, the
crossword itself is the opponent. Further, unlike other constraint
satisfaction problems, the solution is already well known, at least to
the person who wrote the puzzle. In short, this program seems like it
would be most useful for people who enjoy crossword puzzles, but are too
impatient to wait for tomorrow's paper.
One interesting use of this crossword puzzle solver would be to use it
as a judge of the difficulty of the puzzles presented to it, whether
human or computer generated. It would be interesting to see how closely
the solver's idea of a difficult puzzle corresponds to that of a
human’s. The paper mentions that the puzzle solver found the NYT
puzzles increasingly difficult as the week progressed. If that paper
were interested in making sure that its puzzles really did appear in
increasing order of difficulty, it could present all the puzzles for the
week and use it to decide in which order they should be published.
Also, it would be interesting to see if the algorithm could be modified
in some way to actually generate difficult puzzles.
This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 09:06:22 PST