In one of history's least noticed ironies, the commercial viability of interactive fiction (aka, text adventures such as Adventure and Zork) died at almost precisely the same time AI researchers discovered how to efficiently and effectively parse English sentences.

Here's the timeline. Infocom was founded in 1979. The Infocom parser, while lightyears ahead of the at-most-two-word verb+optional-object parsers used in previous text adventures, used the same basic technology as the most sophisticated research parsers of the time: hand crafted rules. These rules typically either constrained the possible grammatical forms (for example, the Infocom parser might have had "first, find the verb" as a rule, with the implicit assumption that there was only one verb per command) or guided the search through possible parses (e.g., "first try (verb), then try (verb direct-object), then try ...").

Rule based parsers have two major flaws. First, they are typically too rigid -- even the most anti-prescriptivist linguists find it difficult to write down rules loose enough to cover the many generally accepted ways people actually use English. To give just one example, English is mostly subject-verb-object (SVO, in the lingo) but occasionally OSV ("I hate oranges, but apples I'll eat") or even OVS ("Enigmas spoke Yoda"). Second, they deal badly with ambiguity -- the whole

(SUBJECT (ADJ time) (NOUN flies)) (VERB like) (OBJECT (ARTICLE an) (NOUN arrow))



thing. It turns out that a large percentage of suitably long English sentences have that kind of ambiguity, and it only gets worse as you add in more and looser rules to deal with the first problem.

Statistical parsers get around these issues by assigning probabilities to possible parses, learning the probabilities from a large number of parsed examples, and then searching for the highest probability parse for any given input sentence. Given enough training data, a statistical parser will learn that "time" is a much more likely subject than "time flies".

Statistical parsers started getting serious research in the late 80s, and they got good in the mid 1990s when head lexicalization was discovered. [Head lexicalization just means that every grammatical structure should have a word associated with it: not



SENTENCE_{head=flies} -> SUBJECT_{head=time} VERB-PHRASE_{head=flies}

.] These days English parsers are more than 95% accurate at parsing sentences out of the Wall Street Journal, whereas the old rule based systems weren't even good enough to measure -- they would just give up on any suitably long or complex sentence.

Infocom was shut down in 1989, but many mark the end of the commercial text adventure with Doom's 1993 release. The first good English parsers were IBM's SPATTER and SRI's Core Language Engine, both of which were first described in 1994 publications.

Now, plugging one of these modern parsers into a text adventure game might strike many as overkill, but I do remember getting frequently annoyed at the Hitchhiker's Guide to the Galaxy game before I figured out more or less which subset of English it wanted. (This is why I was only the backup member to the team from my high school that won the 1987 Bureaucracy marathon.) Besides, what's wrong with overkill?

The statistical approach has also more or less solved several minor natural language problems such as pronoun reference (which noun does "it" refer to, etc.) and word sense ("hit" as in punch, or "hit" as in top-40 radio?). People weren't even thinking about these problems before the 1990s, but they could definitely be used to improve the front end to any interactive fiction. If only there was any money in it.

One side note: in 1976, Don Woods wanted to get permission from Will Crowther to improve Will's creation, the seminal game Adventure. However, Don didn't have any contact information for Will. What did he do? He sent email to crowther @ EVERY POSSIBLE DOMAIN, something you could do back in 1976 with a reasonable chance of success. Sure enough, Will responded.