Review of "PROVERB: The Probabilistic Cruciverbalist"

From: Seth Cooper (scooper@cs.washington.edu)
Date: Mon Dec 06 2004 - 09:06:32 PST

  • Next message: Annamalai Muthu: "Paper Review"

            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.


  • Next message: Annamalai Muthu: "Paper Review"

    This archive was generated by hypermail 2.1.6 : Mon Dec 06 2004 - 09:06:22 PST