From: goetz@acsu.buffalo.edu (Phil Goetz)
Newsgroups: rec.arts.int-fiction
Subject: Parser heresy (was Re: Searching for a sense of wonder)
Date: 16 Nov 92 20:47:43 GMT
Article-I.D.: acsu.BxttrL.E6x
Organization: State University of New York at Buffalo/Comp Sci

In article <1992Nov15.155951.3262@starbase.trincoll.edu> rbryan@Mail.trincoll.edu (Russell L. Bryan) writes:
>Now, I will admit, I would probably enjoy an interactive game without
>puzzles very much, but at this moment such a pastime is impossible.  The
>reason that there are puzzles in interactive fiction is because the
>parser hasn't been created yet that can accept any words and sentences
>which you give it.  Think of it this way -- if all the puzzles were
>removed from your favorite game, you could walk through the entire world
>in the matter of maybe ten minutes' typing.  Therefore, a non-puzzle game
>would have to be many, many times larger than an ordinary IF game to be
>of any lasting interest.  However, the parsing problem mentioned earlier
>will not allow for extremely large worlds because the vocabulary would
>become unmanagable, not to mention the increased number of actors with
>whom you would have to have far more detailed conversations, because you
>would not be limited by the actor waiting to hear key phrases -- those
>key phrases are stripped out with the puzzles.

Well, let me throw a bit of heresy at you which I believe:  Parsing is not
a problem for adventure programs.

I don't have much data here to support my view.  I am presenting an opinion
based on years of struggling with parsers, knowledge rep, and reasoning,
especially studying CASSIE, the "cognitive agent" of the SNePS system (basically
a dialogue program).

If you take stories, instructions,
conversations, etc., and try to get a computer program to "understand" (i.e.
answer questions about) them, you will find you get stuck on almost every
sentence because you don't know exactly what information is being conveyed,
or how to represent it.

In reference to the above post:

1. Vocabulary.  This is not a technical problem.  You could have every
word in the English language in your game's vocabulary and still have no
noticeable delay looking each word in a sentence up, provided you use
intelligent methods for searching the lexicon (the most basic of which,
binary search, requires time lg(# of words)).  Size of the lexicon becomes
unwieldy much slower than size of the world representation does.
 
2. Conversation.  This is not a parsing problem, it is a knowledge
representation and reasoning problem.  If you give me a good representation
for the concepts in a sentence, I can write a parser for it quickly.
Syntactic structure is easy.

The first problem is, we cannot represent most of
the information in sentences precisely because _we are not aware of_ much of
the information in our sentence.  Try translating a story into predicate
calculus someday, then examine the results.  You'll find some very hairy
problems that are not evident on the surface!  For instance, take the frame
problem:  How do you know which things change/{represent transitory states}
and which things are constant?

I am sick.
vs.
I am tall.

You wouldn't call me on the phone and say, "So, Phil, are you still tall?"
unless you knew I had an appointment with Procrustes.
(I have heard claims that Black English distinguishes between these two cases
this way:

I am sick
vs.
I be tall.

where "be" indicates a long-term state.  Or maybe it was the other way around.
I don't know if this is true.)  This, you say, can be resolved by commonsense.
OK, but commonsense knowledge is a knowledge representation & reasoning (KR&R)
issue, not a parsing issue.

If you say, "Two blue bugs lived in a jar", how do you represent the two bugs?
As one indiscriminate collection, or as two separate objects?  What if it is
"The average German cockroach lays 1 million eggs a year."?  You don't represent
1 million different eggs.

When you are given an ambiguous sentence, do you assume some interpretation
and keep hold of it till forced to revise it, or use a "lazy evaluation" method
that represents the knowledge in something near surface structure and doesn't
try to disambiguate it until necessary?

Just today I heard a man say, "I had two brothers.  One died when he was a baby.
The other was killed in World War II.  ...  Rob was the one who lived."  Rob did
not live; he died in WWII.  "He lived" applies to Rob only if you can construct
a context referring to childhood and embed the proposition "he lived" in it.

These aren't even good examples.

The second problem is, once you've got a logical representation of a sentence,
what do you do with it?  That is the reasoning problem.  It is probably worse.

3.  (You're going to scream at this one.)  Adventures just don't present you
with situations where you even WANT to use most grammatical constructs.
Observe a 2-year old baby.  This baby gets what it wants in the world with
2 or 3-word utterances, i.e. "Go!  Get egg!" or "Want more doggie!"  You, in
the adventure, are like that baby.  The ways you want to interact with the
world are quite restricted.  You are giving orders to a puppet.

Phil Goetz
goetz@cs.buffalo.edu