From: Indriyati Atmosukarto (indria@cs.washington.edu)
Date: Sun Dec 05 2004 - 21:08:12 PST
PROVERB: The Probabilistic Cruciverbalist
Author: Greg A. Keim, Noam M. Shazeer, Michael L. Littman, Sushant Argawal, Catherine M. Cheves, Joseph Fitzgerald, Jason Grosland, Fan Jiang, Shannon Pollard, Karl Weinmeister
Proverb (Probabilistic Cruciverbalist) is a computerized crossword puzzle solver which attempts to maximize the number of targets in common with the puzzle's solution by combining different AI techniques such as probabilistic reasoning, information retrieval, data mining and constraint satisfaction..
It was interesting to see the 'modular' architecture of the system. Given a clue, each of the 30 expert modules would generate a weighted set of candidates and a numerical level of confidence that the correct target is in the set of candidates. The collection of the 30 candidate list would then be reweighted by the Merger module and combined into a single list. The Solver would then take the weighted list and search for the best solution that satisfies the grid constraints. The paper also highlighted the important contribution of having a Crossword Database (CWDB). Crosswords clues and target tend to recur over a certain period of time so having the database greatly improved the system's performance.
The system seems to rely too much on the CWDB which leads to the impression that the system is merely a 'database lookup' program. This shows that the system is not generalized in the sense that it would not perform well given other types of crossword puzzles, for example those with more cryptic clues. In addition, the paper should have provided more details on the performance analysis for each of the expert modules.
One interesting observation is that the program is not really mimicking the way humans solve crossword puzzles as humans would tend to go back and forth between looking at the clues and writing a potential answer and checking other adjacent grids to see what other words would fit. It would be interesting to see how different would the system's performance be if it incorporates such a behavior. Furthermore, it would be interesting to see its performance on different types of crosswords such as the cryptic crosswords.
This archive was generated by hypermail 2.1.6 : Sun Dec 05 2004 - 21:08:12 PST