Abstract

In this seminar I present some of the threads of research from my PhD, in which I constructed a system called enigma which writes cryptic crossword clues automatically.

Cryptic crossword clues are highly unusual texts: they have two independent layers of meaning, each of which has a completely separate syntax and semantics. The starting goal for enigma is a representation of the puzzle that will be hidden in the clue. This puzzle can be rendered in very many different ways according to the conventions of cryptic crossword writing, but only a handful of these renderings will also appear to be pieces of English prose, a fundamental requirement for any clue.

Following the approach taken by human compilers described in the expert literature on cryptic crossword compilation, and my own introspection, enigma explores the search space bottom up using natural language semantic and selectional constraints as a pruning heuristic.

The implementation takes the form of a chunk-based generator in which the grammar rules are encoded as syntactic constraints on the attachments which are allowed to form between chunks. Each attachment is also underwritten by semantic selectional constraints based on data sources mined from corpora and related online resources using statistical techniques.

Enigma was evaluated with a Turing-style test in which subjects were presented with computer-generated clues and clues from national newspapers which had the same answer and had to decide which was which. On average subjects identified the human-authored clues 75% of the time.