Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Disambiguator tricks (Part 2)

6 views
Skip to first unread message

Jeff Hatch

unread,
Jan 28, 1998, 3:00:00 AM1/28/98
to

My original "Disambiguator tricks" post was more than a week ago. I
described how a "branch" statement could be used to create an unusually
sophisticated disambiguator with relatively little effort. If you
didn't bother reading it, or don't remember it, don't bother reading
this.


OTHER USES OF THE BRANCH STATEMENT
Besides doing a better job of disambiguating ordinary commands, I've
thought of two uses for the branch command.

1. The word "it" could refer to more than one object. An example that's
previously been mentioned in this newsgroup:

>RUB LAMP. DROP IT.
You rub the lamp. A genie appears and holds out a magic wand.
You drop the lamp.

>RUB LAMP. TAKE IT.
You rub the lamp. A genie appears and holds out a magic wand.
You take the wand.

When this example was discussed earlier, the rec.arts.int-fiction
community didn't completely agree which of those two commands should
work. Using the branch statement, they *both* could work.

2. Easy-to-implement object parts, such as a desk with a drawer. The
usual way to implement this is to write code that specifically redirects
the commands "open desk," "put pen in desk," etc. from the desk to the
drawer. Using the branch command, a programmer could simply "branch" a
redirection statement--which would automatically redirect all the
appropriate commands and none of the inappropriate ones.


TECHNICAL NOTES: BRANCH STATEMENT PERFORMANCE
An experienced programmer who examined my description of the branch
statement may wonder how it works and whether it's fast enough to be
useful.

Whenever a branch statement is reached, my program makes an exact copy
of the game's current stack, but NOT of the game's permanent "state."
When game state variables are changed, the changes are saved to an Undo
buffer. When a particular path finishes executing, the Undo buffer is
used to restore the game's state, and the previously saved copy is used
to restore the game's stack, so my system is able to begin running the
second possible path just as if the first path had never been taken.
Once the correct path is chosen, a Redo buffer eliminates the need to
re-execute the chosen path. This technique is relatively efficient,
because the stack is typically small but changes frequently, and game
state information is typically large but changes infrequently. (This
method also allows a fairly small Undo buffer to store dozens of turns'
worth of Undo data, as in TADS.)

Is it fast enough? I've only tested it in one situation--I used the
branch statement to implement indistinguishable objects. I created two
identical knives which began the game in separate rooms. (In a mature
authoring system, there's no need to disambiguate when items are in
different rooms. My parser doesn't have any concept of scope yet, so I
tried to use the branch statement to simulate this ability.) The
command "open latch with knife" branched five times, giving the
following results:

"I don't understand the word 'open' as a verb."
"I don't understand your direct object."
"I don't understand your preposition."
"I don't understand your indirect object."
"You aren't holding the knife."
"You slide the knife under the window and open the latch."

The sixth (correct) result was selected in slightly less than a second
on a 33 mHz computer, a result I deem tolerable. Using a "dictionary"
to reduce the amount of string comparisons required (as every popular
system does) will reduce this time by at least 50%. (The above example
actually took LESS time to execute than a command of four nonsense
words, which indicates that branching four times takes less than half as
much time as running four unknown words through a pre-parsing vocabulary
check without a dictionary.)

In other words: My disambiguator will be slower than Inform's, but it
will be fast enough for most people's needs. IF doesn't require much
processor power.


TECHNICAL NOTES: DEALING WITH AMBIGUITIES
Naturally, no disambiguator can figure out what truly ambiguous
sentences mean. That's why my "branch" statement has an (optional)
accompanying "ambiguity" statement, which executes only when both
branches execute successfully. The syntax is similar to "if-else"
syntax in C. For instance:

if (word [index] == "knife") branch return 1;
ambiguity EndMessage ("I couldn't tell which knife you were referring
to.");
return 0;

Unfortunately, this is a very primitive technique. My "branch" command
has no memory, so the "ambiguity" statement won't know which other
possibilities may have been intended. So far, the only error message
I've implemented for ambiguities is an unhelpful: "Your sentence seemed
ambiguous." I plan to implement this:

>GET IN BOX
Do you want to: (1) enter the large cardboard box or (2) take the "In"
box?
>2
You take the "In" box off of the desk.

I plan to allow certain statements to not be undone when a branch
terminates. Whenever a "branch" path ends successfully, the command
will be added to an array of possible meanings. The path will then be
undone, but that command will stay in the array. If an ambiguity
finally results, the error message can look at this array to determine
which meanings could have been intended. I haven't begun implementing
this technique yet--until I discovered this problem, I didn't even plan
to implement arrays in my first release!


MY AUTHORING SYSTEM
I planned to release a primitive demo in early 1998, but I probably
won't. In January 1998 I decided to implement a few nonessential but
convenient features before working on my library. (For instance, my
integrated game editor can now save and load files in a more traditional
text source format.) Also, I found a memory leak in my program, which
I've traced to Microsoft Visual C++ 1.52's library. (Memory leaks are
among the most difficult errors for programmers to debug.) So I'm three
or four weeks behind schedule in creating a demo version.

But tomorrow I'm going back to school--and for me, an entire semester of
programming while in school is equal to just a few weeks of programming
while on vacation. (Perhaps less, this semester. I need to prepare for
my Senior Piano Recital next fall, and even my formerly easy math major
may begin consuming my time, since one of my profs wants me to do some
original mathematical research.) So I probably won't have a basic
library and demo version ready until June.

And I have nothing up my sleeve now that I've described the branch
statement in elaborate detail. So if you're interested in my system,
you'll have to wait five more months, and then you won't see anything
interesting that I haven't already described in this newsgroup. D'oh!
Sorry about that. :-(

I still expect to release a quality product by the end of 1998.


-Rúmil

Joe Mason

unread,
Jan 30, 1998, 3:00:00 AM1/30/98
to

In article <34D023...@hatch.net>, Jeff Hatch <je...@hatch.net> wrote:
>possibilities may have been intended. So far, the only error message
>I've implemented for ambiguities is an unhelpful: "Your sentence seemed
>ambiguous." I plan to implement this:
>
>>GET IN BOX
>Do you want to: (1) enter the large cardboard box or (2) take the "In"
>box?
>>2
>You take the "In" box off of the desk.

I'm not clear on how exactly you'll be handling ambiguities: it would be nice
to have this default behavious built into the library, rather than hard-coded.
This seems like the type of thing I'd want to play around with and change.

Perhaps you could create a data structure and allow the "ambiguous" section
of the branch statement to examine it at will? That would allow the
programmer to deal with ambiguities however they like.

>And I have nothing up my sleeve now that I've described the branch
>statement in elaborate detail. So if you're interested in my system,
>you'll have to wait five more months, and then you won't see anything
>interesting that I haven't already described in this newsgroup. D'oh!
>Sorry about that. :-(

I'll admit, I was skeptical that your system really offered anything that the
others different, until I heard about the branch statement. This definitely
sounds like something I'd like to see in more detail. Good luck!

Joe

Jeff Hatch

unread,
Jan 30, 1998, 3:00:00 AM1/30/98
to

Joe Mason wrote:
>
> In article <34D023...@hatch.net>, Jeff Hatch <je...@hatch.net> wrote:
> >possibilities may have been intended. So far, the only error message
> >I've implemented for ambiguities is an unhelpful: "Your sentence seemed
> >ambiguous." I plan to implement this:
> >
> >>GET IN BOX
> >Do you want to: (1) enter the large cardboard box or (2) take the "In"
> >box?
> >>2
> >You take the "In" box off of the desk.
>
> I'm not clear on how exactly you'll be handling ambiguities: it would be nice
> to have this default behavious built into the library, rather than hard-coded.
> This seems like the type of thing I'd want to play around with and change.
>
> Perhaps you could create a data structure and allow the "ambiguous" section
> of the branch statement to examine it at will? That would allow the
> programmer to deal with ambiguities however they like.

Yes, that's what I'm planning. Even the way that the data structure is
set up will be part of the library.


> I'll admit, I was skeptical that your system really offered anything that the

> others [didn't], until I heard about the branch statement. This definitely


> sounds like something I'd like to see in more detail. Good luck!

Thanks! I enjoy some of my editor's superficial conveniences, but the
branch statement has always been my favorite feature. Actually,
completing the branch statement was what first inspired me to post in
rec.arts.int-fiction--I'd planned to spend three weeks implementing it
from scratch, but completed it in just one, and at that rate I knew my
system was nearly complete. (Ironically, the branch statement is
indirectly what's slowed me down; I spent most of December and January
fixing an inefficient object memory addressing scheme, because I was
afraid that the branch statement would combine with that problem and
slow parsing unacceptably.)


-Rúmil

0 new messages