From: X. Miao (xm_at_u.washington.edu)
Date: Mon Dec 08 2003 - 11:03:05 PST
Title: PROVERB: The Probabilistic Cruciverbalist
Author: Greg A. Keim, Noam M. Shazeer, Michael L. Littman
Summary:
This paper discribes a sophisticate AI system could solve the crossword
puzzles better than average cruciverbalist.
Important ideas:
1. This system implements all kinds of AI techniques in tackling the
problem and combines all of them together to be a big system.
2. I think an important idea is the probabilistic model and
the decentralized the modular design. This allows many expert modules
to contribute their knowledge. A merger module will merge all the
candidate lists generated by individual expert modules together to be one
list. Then a grid filling algorithm will be run on this list to maximize
the expected overlap.
Flaws
1. To me, it seems the probability of the candidate words is updated
during the grid filling process also. But this system isolated these two
parts so that it is possible that the system ignores some useful
information. (The Implicit Distribution Modules did some contribution to
this problem but not all)
2. The three-parameter probabilistic model of the merger seems
subjective and maybe too simplied.
Further work
1. Improve the implicit distribution modules.
2. Improve the probablistic model of the merger.
This archive was generated by hypermail 2.1.6 : Mon Dec 08 2003 - 11:03:06 PST