[MUD-Dev] [Theory?] Parsing of knowledge to allow for more interactive NPCs

[Robert Zubek]

Well, I'm not a MUD developer per se, but I'm working on natural
language conversations with game characters, so I know what you mean
about the trickiness of dealing with such commonly-used elements as
pronouns, indexicals (this, that, here) and prepositions. Alas, none
of this is anywhere near being a solved problem.

There are two aspects of your email that I'd like to comment on -
first, the general ambiguities of parsing, and second, the pronoun
reference problem.

First, parsing out the object of a command may be more tricky than
you describe. While it's simple to parse simple second-person
action-target commands ('hit the monster', 'take the apple' etc.),
more complex commands will introduce ambiguity that will somehow
have to be dealt with. Consider a command such as 'hit the man with
the broom' - does it mean 'hit with the broom' or 'the man with the
broom'? That is, how do you know how to parse out the object - does
the prepositional phrase apply to the action, or to the object?

There's no good structural way of dealing with this, so you will
either have to establish usage rules (which as an engine designer
you can always do), or the parser will have to include some kind of
a semantic module to disambiguate. For example, it may have to look
at both the agent's and the target's possessions, and parse the
sentence in a way that best accounts for the extraneous broom. This
now ties the parser into the knowledge base, and will have to be
implemented with care, because the parser's behavior may end up
communicating world knowledge that the player shouldn't have access
to (such as who owns what).

Unfortunately, there will always be cases that will require
extensive common-sense knowledge to disambiguate. For example, 'hit
the man with the funny hat' - we intuitively know that a funny hat
is an unlikely weapon, and a very likely descriptor of the intended
target, and would interpret it as instructing to hit the man
*wearing* a funny hat, if we did own a funny hat ourselves. If
objects in your world can perform only a small set of actions each,
then this ambiguity won't be a huge problem - the parser can just
look up a hat, and check whether it can be the method of a 'hit'
action. Otherwise, if your world model allows for all objects to
perform all actions with certain probabilities, you can implement a
number of fixes, from a straightforward user query (eg. "you mean I
should hit the man wearing the funny hat, right? [Y/n]"), to
something more complex, like annotating the object database with
different usage probabilities that can get used to help in parsing
(eg. "hat, is-a: garment, use-for-combat: unlikely,
use-for-spellcasting: unlikely, etc.")

The second problem you mention is pronoun disambiguation and again,
it's a hard problem that's difficult to get Completely Right,
although it can be approximated for the purposes of a MUD.

You're on the right track using attribute lists (eg. "gender: male,
number: singular") to bind pronouns, and keeping the bindings
'latched' from one sentence to the next. This makes pronoun binding
quite easy, and very similar to unification in pattern-matching
algorithms.

However, similar ambiguities surface here, especially when there is more
than one good binding for the pronoun. Consider:

    "take the apple from the box and lock it"
vs. 
    "take the apple from the box and eat it"

Again, structurally they're the same, and there's more than one good
binding for the ambiguous pronoun. What lets us understand one
command one way, and the other a different way, is the common-sense
knowledge of the world: we know that apples are not very lockable,
and boxes not very edible. This could again be implemented by
requiring the parser to examine the functions that each object can
perform, and parsing the sentence in a way that makes most
sense. Even though it won't work as an approach to general natural
language understanding, it should do quite well in a MUD. And when
the human requests something completely vague, such as "lock the box
with the key and drop it", the engine should probably just give up
and double-check with the user (eg. "Do you mean drop the box or the
key?"), because even a human would have a trouble with a command
like that.

So much for my rant on ambiguity. Oh, and the final note on
professional NLP literature - don't be discouraged, it's meant to be
overpowered. The research on NLP attempts to capture language usage
in most intricate detail, so it will inevitably lead to tools that
are extraordinarily complex. For the purposes of command-parsing in
MUDs most of this research probably won't be useful, since it deals
with phenomena that are much more complex. Instead, I too would be
curious to hear what actual MUD developers have successfully used in
their systems.


Rob


--
Robert Zubek
rob at cs.northwestern.edu
http://www.cs.northwestern.edu/~rob



_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev