From: adrienne wang (axwang@cs.washington.edu)
Date: Mon Dec 06 2004 - 04:19:48 PST
PROVERB: The Probabilistic Cruciverbalist
By G. Keim, C. Cheves, M. Littman , et. al.
In this paper, the authors present an AI system which given a set of
clues and a crossword grid, chooses the "best" solution through expert
modules.
This system incorporates many AI techniques to solve this challenging
problem. Based on the clues and the grid constraints, a list of
candidate words can be chosen. The system uses a decentralized
architecture. Expert modules generate candidates with probability-weight
and the collection of candidate lists is merged by the Merger module
which learns from the training data to weight each expert module. Then
the Solver maximizes the expected overlap with the solution through a
grid filling algorithm.
This system seems to rely too much on the creator’s distribution, which
makes it perform well in normal situations, but poorly when the game
demonstrates creativity. This somehow restricts the generalization of
the system. In addition, the Merger module uses a learning algorithm to
weight the expert modules. It is quite possible that overfitting would
occur as in all learning algorithms.
The system can improve its performance through adding new expert
modules, learning over past tournament puzzles, and improving the
implicit distribution modules. Also, this decentralized probabilistic
architecture may also be applied to other AI problems.
This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 04:19:48 PST