[Inform] Proposed parser changes

36 views
Skip to first unread message

Graham Nelson

unread,
Sep 14, 1999, 3:00:00 AM9/14/99
to

On disambiguating disambiguation
--------------------------------

Unless the designer has reconfigured it, the Inform parser
uses context and knowledge about the game world in only one
circumstance: to resolve an ambiguity in what the player has
typed. Suppose we have a set of objects which make equally
textual sense: deciding which is, or are, intended is called
"disambiguation". The rules on how to do this have evolved
over the last six years: an effort in library 6/8 and 6/9 to
simplify a byzantine mess was generally felt to have caused
more problems than it solved, producing a parser which was
over-tenacious in disambiguating (i.e., not asking the player
questions often enough) and casting the definition of "all"
too widely. It also, and justly I think, caused annoyance
that ChooseObject(o, 2) had lost much of its power.

I am currently working on library 6/10 and, at the same time,
the proofs of the Inform manual, which in section 31 contains
a description of the disambiguation rules. All in all, I'd
like to establish a revision of the rules which will keep most
people reasonably happy -- no two players ever entirely agree
about these things, but on the other hand the consensus was
that library 6/7 didn't do too badly, and I'm hoping for a
similar consensus here.

So this is a consultation exercise. If you're interested in
such things, and can spare the time, I'd be grateful if you
would download a test version of library 6/10 (don't get
excited: it's not much different from 6/9 except for this one
purpose...), from my Web page at:

http://www.gnelson.demon.co.uk/dislib.tar

This archive contains just the present posting and the only
three library files which have changed: "parserm.h",
"linklv.h" and "verblibm.h".

...And then: well, the object of the exercise is to see if
anyone can provide plausible circumstances in which the parser
makes unreasonable choices, or where "all" doesn't do what
you would want it to. If you can construct a room where bad
things happen, please email me the Inform source code for a
tiny game containing it!

A quick response would be very much appreciated. With thanks
to anybody prepared to try this,

Graham Nelson
14 September 1999


The library 6/10 rules (draft)
----------------------

(1) Call an object "good" according to a rule depending on
what kind of token is being matched:

held Good if its parent is the actor.
multiheld Good if its parent is the actor.
multiexcept Good if not also the second object,
if that's known yet.
multiinside Good if not inside the second object, if that's
known yet.
creature Good if |animate|, or if the proposed action
is |Ask|, |Answer|, |Tell| or |AskFor| and the
object is |talkable|.
other tokens All objects are good.

If only a single object is good, this is immediately chosen.

(2) If the token is "creature" and no objects are good,
fail the token altogether, as no choice can make sense.

(3) Objects which don't fit "descriptors" used by the player
are removed:
if "my", an object whose parent isn't the actor is discarded;
if "that", an object whose parent isn't the actor's location
is discarded;
if "lit", an object which hasn't |light| is discarded;
if "unlit", an object which has |light| is discarded;
if "his" or some similar possessive pronoun, an object
not owned by the person implied is discarded.
Thus "his lit torches" will invoke two of these rules at once.

(4) If there are no objects left, fail the token, as no
choice can make sense.

(5) It is now certain that the token will not fail.
The remaining objects are assigned a score as follows:

(i) 1000 times C points, where C is the return
value of ChooseObjects(object,2). (If the designer doesn't
provide this entry point then C=0. If so, then 0 <= C <= 9.)
(ii) 500 points for being "good" (see (1) above).
(iii) 100 points for not having "concealed".
(iv) P points depending on the object's position:

P = A if object belongs to the actor,
L if object belongs to the actor's visibility
ceiling,
20 if object belongs anywhere else except the
compass,
0 if object belongs to the compass.

(Recall that "visibility ceiling" usually means "location" and
that the objects belonging to the compass are exactly the compass
directions.) The values A and L depend on the token being parsed:

A = 60, L = 40 for "held" or "multiheld" tokens,
A = 40, L = 60 otherwise.

(v) 10 points for not having "scenery".
(vi) 5 points for not being the actor object.
(vii) 1 point if the object's gender, number and
animation (GNA) matches one possibility implied
by some pronoun typed by the player: for instance
"them" in English implying plural, or "le" in
French implying masculine singular.

(6d) In "definite mode", such as if the player has typed
a definite article like "the", if any single object has highest
score, choose that object.

(7ip) The following rule applies only in indefinite mode
and provided the player has typed something definitely implying a
plural, such as the words "all" or "three" or "coins". Here the
parser already has a target number of objects to choose: for
instance 3 for "three", or the special value of 100, meaning
"an unlimited number", for "all" or "coins".

Go through the list of objects in "best guess" order (see below).
Mark each as "accept" unless:

(i) it has "worn" or "concealed";
(ii) or the action is Take or Remove and the object is
held by the actor;
(iii) or the token is "multiheld" or "multiexcept"
and the object isn't held by the actor;
(iv) or the target number is "unlimited" and S/20
(rounded down to the nearest integer) has fallen
below its maximum value, where S is the score of
the object.

The entry point ChooseObjects(object,accept_flag) is now called
and can overrule the "accept"/"reject" decision either way.
We keep accepting objects like this until the target is reached,
or proves impossible to reach.

(8) The objects are now grouped so that any set of
indistinguishable objects forms a single group.
"Indistinguishable" means that no further text typed by the
player could clarify which is meant. Note that there is no
reason to suppose that two indistinguishable objects have the
same score, because they might be in different places.

(9d) In definite mode, we know that there's a tie for highest
score, as otherwise a choice would have been made at step (6d).
If these highest-scoring objects belong to more than one group,
then ask the player to choose which group:

You can see a bronze coin and four gold coins here.
> get coin
Which do you mean, the bronze coin or a gold coin?
> gold

The player's response is inserted textually into the original
input and the parsing begins again from scratch with
"get gold coin" instead of "get coin".

(10) Only two possibilities remain: either (i) we are in
indefinite but singular mode, or (ii) we are in definite mode
and there is a tie for highest-scoring object and all of these
equal-highest objects belong to the same group. Either way,
choose the "best guess" object (see below). Should this parsing
attempt eventually prove successful, print up an "inference" on
screen, such as

>get key
(the copper key)

only if the number of groups found in (8) is more than 1.

(BG) It remains to define "best guess". From a set of
objects, the best guess is the highest-scoring one not yet
guessed; and if several objects have equal highest scores, it is
the earliest one to have been matched by the parser. In practice
this means the one most recently taken or dropped, because the
parser tries to match against objects by traversing the
object-tree, and the most recently moved object tends to be the
first in the list of children of its parent.

--
Graham Nelson | gra...@gnelson.demon.co.uk | Oxford, United Kingdom


lemonhead_at_anti-social_dot_com

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
this sort of thing is the main problem i have with the "best guess"
disambiguation:

>look
You can see a bronze coin and a container (in which is a gold coin).

>get coin
(the bronze coin)
Taken.

>get coin
(the bronze coin)
You already have that.

this should be dealt with before even reaching disambiguation code,
but i don't know how difficult it would be to make "take" only apply
to objects which are not already held.

come to think of it, i suspect that this bug is annoying enough (and
common enough) to have already been noted and fixed if it were
elegantly fixable.

would the interface really be hurt that much if the guessing code were
removed? i suppose the game looks less foolish for assuming a stupid
option than for asking an obvious question.

--
lemonhead at anti-social dot com
check out the i-f people photograph archive at:
http://members.xoom.com/headlemon/ifpeople.html

Kevin Forchione

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
<lemonhead at anti-social dot com> wrote in message
news:37df4516....@news.mindspring.com...

> this sort of thing is the main problem i have with the "best guess"
> disambiguation:
>
> >look
> You can see a bronze coin and a container (in which is a gold coin).
>
> >get coin
> (the bronze coin)
> Taken.
>
> >get coin
> (the bronze coin)
> You already have that.
>
> this should be dealt with before even reaching disambiguation code,
> but i don't know how difficult it would be to make "take" only apply
> to objects which are not already held.
>
> come to think of it, i suspect that this bug is annoying enough (and
> common enough) to have already been noted and fixed if it were
> elegantly fixable.
>
> would the interface really be hurt that much if the guessing code were
> removed? i suppose the game looks less foolish for assuming a stupid
> option than for asking an obvious question.

A "smart" parser is a treat to work with. It's been a while since I've used
Inform, but you don't really want to remove the intelligence from the
parser. TADS handles this kind of thing by silently calling a method
connected to the object (verDoTake()) to determine if the action makes sense
for the object. Much of the difficulty in the Inform parser is due to its
"scoring" approach, which means that objects must be carefully weighted
based on several factors. Getting the formula right can be a real headache.

For instance, in the case of "take coin" you don't want to rule out objects
in your inventory altogether; othewise you will get a "I don't see any coin
here" message, instead of the "you already have the coin". But you *do* want
to score an inventory item much lower than an object not in inventory ...
depending upon the verb. This makes it difficult, because "drop the coin"
has the opposite priority.

The trade-off is an approach similar to that used by TADS, where every
object has verification methods. This idea won't work for Inform, but in
principle every verb will need to have an equivalent "verification" function
to make it intelligent. Most verbs will be able to share functions, but new
grammar would need to be scrutinised to determine if the parser will
disambiguate objects intelligently for it.

--Kevin

BrenBarn

unread,
Sep 16, 1999, 3:00:00 AM9/16/99
to
>this should be dealt with before even reaching disambiguation code,
>but i don't know how difficult it would be to make "take" only apply
>to objects which are not already held.
I think this is the kind of thing we need to really look at --
verb-specific disambiguation.

>come to think of it, i suspect that this bug is annoying enough (and
>common enough) to have already been noted and fixed if it were
>elegantly fixable.

It annoyed me enough that I fixed, but my solution wasn't elegant at all.
I basically stuffed extra code into the regular disambiguation routines so that
certain verbs required that their objects have or not have certain attributes.


From,
Brendan B. B. (Bren...@aol.com)
(Name in header has spam-blocker, use the address above instead.)

"Do not follow where the path may lead;
go, instead, where there is no path, and leave a trail."
--Author Unknown

Graham Nelson

unread,
Sep 16, 1999, 3:00:00 AM9/16/99
to
In article <19990915230131...@ng-cs1.aol.com>, BrenBarn

<URL:mailto:bren...@aol.comRemove> wrote:
> >this should be dealt with before even reaching disambiguation code,
> >but i don't know how difficult it would be to make "take" only apply
> >to objects which are not already held.
> I think this is the kind of thing we need to really look at --
> verb-specific disambiguation.

This is already part of the rules; the Take and Remove actions are
treated slightly differently from all others.

I'm not too keen on going much further down this road, though, as
the result might well be a parser terribly well tuned to the
library's own actions, but completely inept with new actions
invented by the game designer.

Kevin Forchione

unread,
Sep 16, 1999, 3:00:00 AM9/16/99
to

Graham Nelson <gra...@gnelson.demon.co.uk> wrote in message
news:ant161036345M+4%@gnelson.demon.co.uk...

> In article <19990915230131...@ng-cs1.aol.com>, BrenBarn
> I'm not too keen on going much further down this road, though, as
> the result might well be a parser terribly well tuned to the
> library's own actions, but completely inept with new actions
> invented by the game designer.

That's exactly the risk. Better to have a library which handles most
conditions equally well. If you begin to tighten up the "intelligence" of
the parser then it is quite likely that an author will have to hack it for
any new actions that don't fit into what is bound to be a more narrow field.
Perhaps ... instead of tweaking the rules of the parser overly much it might
be benificial to provide an object based mechanism that assists in such
discriminations. I'm not suggesting developing "verification" methods, but
some mechanism that would assist the parser in its scoring process and that
would indicate that "this object is preferred".

--Kevin

Graham Nelson

unread,
Sep 16, 1999, 3:00:00 AM9/16/99
to
In article <OJu29tEA$GA.355@cpmsnbbsa05>, Kevin Forchione

<URL:mailto:Lys...@email.msn.com> wrote:
> Perhaps ... instead of tweaking the rules of the parser overly much it might
> be benificial to provide an object based mechanism that assists in such
> discriminations. I'm not suggesting developing "verification" methods, but
> some mechanism that would assist the parser in its scoring process and that
> would indicate that "this object is preferred".

Yes, this is exactly the mechanism which Inform does use, by means
of the ChooseObject entry point.

BrenBarn

unread,
Sep 17, 1999, 3:00:00 AM9/17/99
to
>This is already part of the rules; the Take and Remove actions are
>treated slightly differently from all others.
>
>I'm not too keen on going much further down this road, though, as
>the result might well be a parser terribly well tuned to the
>library's own actions, but completely inept with new actions
>invented by the game designer.
It's sad but true. :-) But I wouldn't consider it out of line to create
specific verb handling for the specific verbs the library provides.
Your recent post about the parser changes indicated that Choose Objects
had a beefed-up functionality. My question is, does ChooseObjects allow me to
do this:
[ChooseObjects obj code;
switch (action_to_be) {
##Take: if (IndirectlyContains(obj,player) || obj has static or scenery) return
-100; ];
. . .and thus eliminate obj from the practical choices (by subtracting 100
from its score) if the player tries to take it and it either A) is carried; B)
has static; or C) has scenery? And can I do this with other verbs? If such a
function is provided, extending the verb-specific disambiguation wouldn't be
too painful -- you could just add a line to the switch statement.

Graham Nelson

unread,
Sep 18, 1999, 3:00:00 AM9/18/99
to
In article <19990917194540...@ng-da1.aol.com>, BrenBarn

<URL:mailto:bren...@aol.comRemove> wrote:
> Your recent post about the parser changes indicated that Choose Objects
> had a beefed-up functionality. My question is, does ChooseObjects allow me to
> do this:
> [ChooseObjects obj code;
> switch (action_to_be) {
> ##Take: if (IndirectlyContains(obj,player) || obj has static or scenery) return
> -100; ];
> . . .and thus eliminate obj from the practical choices (by subtracting 100
> from its score) if the player tries to take it and it either A) is carried; B)
> has static; or C) has scenery?

You would actually do it by returning 0 for these objects and
1 for all others, but yes, that's broadly right.

One has to be careful. We're talking about disambiguation here:
not enforcing the world model. If a player unambiguously asks
to "take sky", that's what the parser should deliver up: it's
then for the world model, and the game, to sort out how (and
indeed if) to stop him. The present disambiguation rules do
indeed rule out anything being held from being taken when it
is referred to only by implication ("take all"), but not when
it is referred to specifically, and that must be right.

graham...@hotmail.com

unread,
Sep 26, 1999, 3:00:00 AM9/26/99
to
In article <ant1419271cbM+4%@gnelson.demon.co.uk>,
Graham Nelson <gra...@gnelson.demon.co.uk> wrote:
>
> On disambiguating disambiguation
> --------------------------------

Well, I don't know how much use this is to you, but I dug up the list of
parsing features I added in my library hack. Some of these features
required major rewriting of the parser code, but other features only
required minor rewriting (such as adding more descriptors). I believe I
gave descriptors more influence in the parsing by rewriting the various
functions that weed out objects from the list of possibilities. I think
I kept more objects in the list and used more of a score-based system,
instead of a system that chops objects out altogether. Of course, there
are still circumstances that chop objects out, but not as many. If you
like, I can dig through the code to figure out just exactly what I did.
It's been a while.

The thing is available at
http://www.geocities.com/CollegePark/9315/gfinfo3d.zip

I believe it also fixes a few of the parser bugs. I can try to find out
which ones.

--- excerpt from the doc file ---

Recursive disambiguation based on object parents
------------------------------------------------
"Push the button on the control panel"
will know that you mean the button on the control panel, and not the
button on your laser rifel.

"Take the book which is currently residing on the sofa"
will know that you mean the book on the sofa, and not the book on the
floor.

"Take the book in the box on the desk"
will know that you mean the book in the box on the desk, and not the
book in the box on the trolley.


Ignorance of unmatched adjectives
---------------------------------
"Open the stupid door"
is now understood as "Open the door".

"Take the frigging annoying box and the ugly-as-sin book and open the
marmosetian window" is now understood as "Take the box and the book and
open the window".

Note that it doesn't handle adverbs yet, so "quickly take the book" will
still produce an error.


Better handling of AND and THEN
-------------------------------
"Take the box and then open it" works now.
"Take and open the box" works now.
"Pick up the box and the ball and open the box and look in it" works
now.
"Take and open the book and the box and put the book in the box" works
too.


Better handling of multiple subjects (optional)
-----------------------------------------------
Most verbs now allow multiple subjects, like "Look at all". To keep
things fair, daemons are allowed to run between actions, but only if the
action took time to do.

For example, if you had a Rat daemon going and you typed "open all", you
might get something like this:

Book: Opened. <- it worked so it took time
The rats are chewing on your foot. <- this is the Rat daemon
Table: That's not something you can open. <- no time taken so no
daemon
Door: Opened. <- took time
The rats are still chewing on your foot. <- that Rat daemon again


New list method for cleaner recursion
-------------------------------------
Simply by setting the global variable Glyph_Look to 1, the library goes
from this:

You can see a fridge (in which is a bucket (in which is some ice (in
which is a bottle of champagne and a spatula) and a severed hand) and a
meatloaf) here.

to this:

You can see a fridge here. In the fridge is a bucket and a meatloaf. In
the bucket is some ice and a severed hand. In the ice is a bottle of
champagne and a spatula.

This affects looking, searching, and other stuff involving lists.

It will affect the inventory listing if and only if the ENGLISH_BIT is
set, which can be accomplished by putting the following line
Initialise[] :

inventory_style = ENGLISH_BIT;


Cleaner adjectives
------------------
Simply by setting the global variable Glyph_Adjectives to 1, the library
goes from this:

You can see a box (which is open) and a microwave (which is on) here.

to this:

You can see an open box and an active microwave here.


User-defined adjective routines
-------------------------------
If you don't like the library's default adjectives, you can make your
own, for individual objects or classes of objects, like this:

You can see an incredibly open box and a microwave which is humming and
buzzing about here.


More descriptors
----------------
You can now do this:

>look
You can see a blue book and a red book.

>open the blue book
You open the blue book.

>take the open book
Taken.

>i
You are carrying an open blue book.

This works with open, opened, closed, lit, unlit, active, inactive,
locked and unlocked. (It used to only work with lit and unlit)


Slightly Better Disambiguation
------------------------------
Some decisions about which object the player is referring to have been
put off until later in the parsing, so the parser doesn't jump to
certain confusing conclusions. This allows descriptors to have more
appreciable effects.


... more stuff irrelevant to parsing.


- GLYPH


Sent via Deja.com http://www.deja.com/
Before you buy.

Jonadab the Unsightly One

unread,
Oct 10, 1999, 3:00:00 AM10/10/99
to
"Kevin Forchione" <Lys...@email.msn.com> wrote:

> > >get coin
> > (the bronze coin)
> > You already have that.
> >

> > this should be dealt with before even reaching disambiguation code,
> > but i don't know how difficult it would be to make "take" only apply
> > to objects which are not already held.

Actually, you'd want it to apply FIRST to objects not already held.

> > come to think of it, i suspect that this bug is annoying enough (and
> > common enough) to have already been noted and fixed if it were
> > elegantly fixable.

No, it wouldn't be hard:

[ UnheldObject i;
i = noun;
while ((parent(i)~=0)&&(i~=player))
{ i = parent(i); }
if (i==player) rfalse; rtrue;
];

Extend "take" first
* noun=UnheldObject -> Take;

Only problem with this is that it does not support multiple objects;
however, that can be remedied by replacing the noun=routine token
with a scope=routine token (these are allowed to take multiple
objects by returning (IIRC) true when scope_stage==1), which could be
set up to mimick (or, indeed, copied from) the library's usual
scoping routines but with the player's inventory excluded. I could
write it, and it wouldn't be all that particularly hard.

One possible improvement to the compiler I'd be happy to see would
be this syntax:

[ IsFoo;
if (noun in fooland) rtrue;
rfalse;
];

verb "foo"
* multi=IsFoo -> Foo;

(Just like noun=routine but accepting multiple objects,
testing each with the routine and taking all that pass.)

However, this would just be a handy shortcut. The same
thing can be accomplished with a scope=routine token,
provided you're willing to duplicate the parser's scope
determination code.


"His eye twitches involuntarily." -- Calvin
"Can't we play something else?" -- Hobbes

Reply all
Reply to author
Forward
0 new messages