intfiction.org

The Interactive Fiction Community Forum
It is currently Mon Aug 20, 2018 1:46 am

All times are UTC - 6 hours [ DST ]




Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: making a dynamic parser
PostPosted: Thu May 24, 2018 5:16 pm 
Offline

Joined: Tue Mar 09, 2010 2:34 pm
Posts: 5320
Location: Burlington, VT
Continuing a discussion from here.

Inform 7 allows a game to understand things by properties--you can say that a block can have a color (red, green, or blue), say "Understand the color property as describing a block" and then the game will understand "RED BLOCK" as a red block if and only if the color of the block is red--so when the color changes the way it can be understood changes.

But what about dynamically generated descriptions that go beyond colors? My "game" Garbage Collection generates a series of random descriptions of garbage:

Quote:
You pick up some garbage from the dump: A gray secretion wets a fragment of rope and drips from a chunk of rock.

Examine another piece of garbage? (y/n) y

A rope fragment.

Examine another piece of garbage? (y/n) y

A cracked panel of metal is set in a piece of rock.

Examine another piece of garbage? (y/n) y

Out of a dirt surface wells a purple film.

Examine another piece of garbage? (y/n) y

A smooth shard of metal is set in a sharp panel of wood.


Not every word generated here is a property of the piece of garbage in a straightforward way (source code is here) and in any case it might be nice to just have the parser automatically understand the string generated for the piece of garbage as referring to it. So if these five pieces of garbage were generated, it would understand the difference between "x purple film" and "x cracked metal" and "x smooth metal" etc.

This might, for instance, help us simulate a gigantic heap of garbage with only a few objects--have a few objects representing pieces of object defined in the code, and assign them new descriptions as new pieces of garbage are drawn from the pile while old ones are returned to it.

The virtual machines that Inform compiles to don't do this easily (as far as I know)--they rely on dictionary words that are generated at compile time, which are assigned to objects... well, somehow (won't pretend I understand the parser)... there's a sort of pre-parser or something that resolves a command into dictionary words and non-dictionary text, and as the parser processes dictionary words it looks around to see what objects the words might match.

How might we make a system that's more friendly to dynamic parsing in this way? Well, it seems to me that one way might be to flip the order. Instead of having the parser understand words and find objects to match them, have the underlying machine assign words to objects. Then a pre-parser could figure out what objects are available for reference at any given time, and what words refer to them, and the parser could check if the words in the command match the words that refer to the available objects.

That would make it easier to the sort of generation I described--just change the list of words associated with an object. It could even happen with words that themselves were generated, so you could generate random names like "huwikaz" and "zucimut" and assign them to objects.

I mentioned some of these ideas here, but the context was "How can I actually do this?" rather than "How can I describe a system I'd like someone else to write?" ;)


Top
 Profile Send private message  
Reply with quote  
PostPosted: Thu May 24, 2018 11:16 pm 
Offline
User avatar

Joined: Wed Oct 14, 2009 4:02 am
Posts: 2507
The VM's dictionary is really just a way of giving each input word a canonical integer. For the Z-Machine it's part of the VM's design, which means it has more limitations, namely that it needs to be sorted. Possibly in Glulx it would be possible to have a dynamically growing dictionary so that you could add randomly generated or user entered words at run time. Or another possibility would be to make it hash the words it can't find in the dictionary between the tokenising and parsing stage. The same hashed value could be added to the object tree.

It's definitely possible in theory to do a lot more. It just depends on what exactly needs to be supported, and then how that should be programmed most simply and/or efficiently.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Thu May 24, 2018 11:53 pm 
Offline

Joined: Mon Mar 19, 2018 12:30 am
Posts: 15
Also, the dictionary is just an optimization to do string comparisons (in Glulx using a binary search of fixed-length values) against a list of pre-sorted words. The parser could use string arrays directly, comparing words the user typed against property values of in-scope objects, character-by-character.

The Z-Machine has a built-in @tokenise opcode, but if you look at the parser Tokenise__ function for Glulx (I'm only familiar with the I6 version) you'll see how it does the word-splitting and dictionary lookup much as in any other language.

The pname.h extension shows how one could override the default parser behavior (looking at the standard name property) to provide alternate object resolution.

> "How can I describe a system I'd like someone else to write?"

Heh heh, now that's the hard part!

~Jesse


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri May 25, 2018 7:44 am 
Offline

Joined: Wed Aug 26, 2015 11:18 am
Posts: 102
Location: The Netherlands
Regardless of any specific authoring system, here are my thoughts on dynamic parsing.

I see two things in dynamic parsing:
    1. creating dynamic object descriptions, like in matt w’s opening post;
    2. mapping user input text to objects and actions dynamically.

There are several definitions of parser or interpreter. When I started building mine, I used the following definitions:

    Parser: translates a string of characters entered by the user to objects and actions that exist in the game. E.g. the char string “ancient sword” is translated or mapped to object 4567.
    Interpreter: interprets the parser’s output: the interpreter knows how to perform the actions on the objects by changing states, printing text, etc.

I’m not saying these definitions are correct, but this is where I’m coming from.

Normal (static) parsing:
Each object has one or more textual descriptions. The parser maps the user input by only looking at these textual descriptions, or at least a part of it.

Code:
Examples:
“sword” maps to “ancient sword” and to “elvish sword”
“ancient” maps to “ancient sword” and to “ancient map”
“ancient map” maps to “ancient map”’ but not to “ancient sword”

With static parsing, you can run into ambiguities when objects have identical words in their static descriptions and the user input doesn’t make it clear (like with the 2nd example above).

Dynamic parsing:
I think dynamic parsing can help in resolving ambiguities (mapping user text to the right object/action) without having to ask the user what he means.

Some thoughts on how to do this:

    look at attributes/properties, like the red block example in the opening post. If the block can change color, the color cannot be in the static description. We should learn the parser to take properties into account when it cannot uniquely map the user input to 1 object. There’s some things to think about, like should it only try to map adjectives to properties or also nouns/prepositions etc. Should it only consider properties when static parsing doesn’t yield a unique match? Etc

    look at the action involved. For example, if “take box” maps to more than 1 box, try to limit the search space to only boxes that are not already held by the player. Similar situations are for drop, open, lock etc. I actually implemented this in my parser and it works pretty well.

    look at relations between objects. Let’s take the “contains” relation: an object can contain or be contained in another object. The containment can be “in”’, “on”, ‘under”, etc etc.
    Now, if the user would enter “examine the box on the table” it would be nice if the parser could deduce something like: there are red box and blue box objects, there is a table object, the red box has a contained relation with the table described as “on”, so the user wants to examine the red box.

But… looking at relations introduces new possible ambiguities. Consider the following

Code:
You see an old man, a young man and a grey stone here. The old man picks up the grey stone.

> hit man with stone

Depending on the parser’s mapping, the interpreter can have several outcomes:

Code:
> hit man with stone

You make a fist and hit the old man right on his nose! The young man runs off.

Or

Code:
> hit man with stone

Which man do you mean? The old man or the young man?

> young

> you take the grey stone from the old man and hit the young man with it.


Both responses are valid. There is IMO no way the parser can predict what the user means here, so it needs a priority order in how to try to map things.

Something like:
    First try static mapping
    Then consider the action involved
    Then take into account the properties/attributes
    Then try the relations
    If that still doesn’t give a unique mapping, ask the user.

Just my thoughts, hope this contributes.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri May 25, 2018 9:39 am 
Offline
User avatar

Joined: Sat Jun 25, 2016 12:13 pm
Posts: 240
What you're referring to here is non context free parsing as opposed to context free parsing whereby the meaning is independent of the situation. I was assuming that by "dynamic" parsing, we mean the ability to change the grammar rules at runtime, or at at least perform some kind of dictionary reassignment.

Dynamically creating objects is, i think, yet another problem. Referring to "matt w"'s "garbage" problem, this reminds me of what i call the "sandy beach" problem;

You're on a beautiful sandy beach stretching far both to the east and west. On the beach, the sand is almost pure white and behind, a few palm trees wave softly in the breeze.

Code:
> put sand in bucket with spade


You can already see the problem; next thing, the whole game is filled with "some sand here" after i take the bucket and empty it in every game location and into every container!

Just make the sand a scenery item! Good idea, but what if the story requires me to dig at a specific beach location to find some mystery buried item. No doubt i can manipulate the sand then?

So this problem, ie how to deal with the fact that you can keep getting "some sand" or "some gravel" or "some water" etc. is similar to Matt's garbage problem, except here, the object is the same and does not require a property change (which is a separate problem).

Oh, then there's this; "Which sand, the sand or the sand?"

Because they are all the same.

Now some systems support this by allowing objects to be in multiple places at once. This can work providing you are not able to change the property of the item. For example, if the sand can be either wet or dry, then having the same "sand" in multiple locations fails to distinguish the dryness.

Another idea is to have a predefined "pool" of sand objects (eg 3 instances) and find a convenient excuse to prevent the player from taking more than the pool. This can work but leads to the "which sand?" problem.

The most common solution is to create a plot device to prevent the player from removing any sand from the beach. Let the player get the sand and drop the sand, but only when at the beach locations which are all (conveniently) adjacent. If you get some sand in the bucket and try to get more, it can say, "but you've already got some sand", or something like that. Whenever you drop some sand, there's a hook that resets the beach sand state.

So this is similar to Matt's garbage problem because it asks for the dynamic proliferation of objects; a bit like generating a new object from the "garbage" heap. It is different because the garbage problem generates random unique objects; from which you can still fill up the game with junk should you be so inclined. Additionally, the generator would have to be careful not to repeat itself otherwise you might get the "which old rag, the old rag or the old rag?" problem.

So moving away from the "sandy beach" problem, there's the problem of whether systems can support the dynamic creation of objects - even if there's only one such object. Naturally, if there's a fixed amount of such objects (eg 1), perhaps there could be some mechanism to have a pre-allocated "blank" object, which at runtime could be assigned a description and properties, including parser "noun" and "adjective".

First consequence; saved games!

Dynamically created or modified objects would have to go into the saved game. This would include any new words added to the dictionary etc. If objects were truly dynamic, ie not re-assigned "blank" ones, the save game (and object tables) would increase in size and may eventually (or even soon) exceed limits. So there'd have to be non-story related checks for this.

Earlier on, i talked about changing the grammar rules at runtime. Why would you want to do this? Actually you don't within any given game, but is common to require new grammatical forms for different styles of game. Pirate slang anyone?

Two pirates aboard ship:
Mate: "There be ships on the horizon, captn'!"
Captain: "arrrrre!"

Changing grammar rules isn't the re-assignment of adjectives or being context sensitive, these are all part of a given grammar set. New grammars are often required for new games and not within a game. consider;

Code:
"put sand in bucket with spade"
"get sand with bucket"
"get sand with bucket and spade"
"fill bucket with sand using spade"
"use spade to get sand"
"use spade to put sand in bucket"
"use spade to fill bucket with sand"
"dig sand with spade and put it in the bucket"
"dig up sand with bucket and spade"
"shovel sand into bucket with spade"


There are many more and these are mostly all slightly different grammatical constructions.

Changing adjectives is a dictionary update problem constrained by making sure you do not accidentally create identical (ie indistinguishable) objects.

Being context sensitive is part of clause resolution with regard to the world state. This is mostly performed eagerly within the parser, but can lead to problems;

Code:
> put some sand in the bucket"
OK
> put some sand in the bucket"
into what?


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri May 25, 2018 10:47 am 
Offline
User avatar

Joined: Mon Aug 28, 2017 12:07 pm
Posts: 31
jkj yuio wrote:
New grammars are often required for new games and not within a game.


I can think of an example where a modifiable parser in-game would be desirable:

You are tasked with building a translator to talk to Yoda and have to assemble electronic components that are essentially parts of speech. Later, you have to reassemble the pieces in a different order to talk to a different alien. You want the game to allow the player to assemble the pieces in any order and produce bad output if they fail in the task.

https://www.theatlantic.com/entertainment/archive/2015/12/hmmmmm/420798/

I'm totally loving all the examples people are giving. Keep them coming.

_________________
"She is not refined. She is not unrefined. She keeps a parrot."


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri May 25, 2018 12:19 pm 
Offline

Joined: Sat Jan 23, 2010 4:56 pm
Posts: 5714
Quote:
The virtual machines that Inform compiles to don't do this easily (as far as I know)--they rely on dictionary words that are generated at compile time, which are assigned to objects... well, somehow


This is not a serious difficulty for the kind of dynamic parsing you're talking about. It's true that dictionary words have to be known at compile time, but if you're setting up a space of objects, you're defining lists of dictionary words.

Words are normally assigned to objects at compile time, but these mappings can be made or changed at runtime. Admittedly this is easier in I6 than in I7, which has a slightly overbearing approach to object naming.

Prepositional phrases are the interesting next step, but a tricky one, for the reasons people have already outlined. I think a reasonable parser would have to accumulate a list of parsings ("hit (man with stone)", "hit (man) with (stone)") and then apply weightings according to a bunch of heuristics -- including recent history and game salience. (Is this a game about hitting people, do people commonly carry stones, etc.)

This is unfortunately where Z-code and Glulx add a lot of friction. (As opposed to the dict word handling, which is straightforward.) You want to represent these possible parsings with bags of complex data structures. This is trivial in Perl or Python -- and I assume it's trivial in TADS3 also -- but the Inform VMs weren't built for that sort of work and it's clunky.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri May 25, 2018 2:22 pm 
Offline

Joined: Tue Mar 09, 2010 2:34 pm
Posts: 5320
Location: Burlington, VT
zarf wrote:
Quote:
The virtual machines that Inform compiles to don't do this easily (as far as I know)--they rely on dictionary words that are generated at compile time, which are assigned to objects... well, somehow


This is not a serious difficulty for the kind of dynamic parsing you're talking about. It's true that dictionary words have to be known at compile time, but if you're setting up a space of objects, you're defining lists of dictionary words.


Well, besides the huwikaz/zucimut issue where the words are themselves generated (that's from something where I wrote a simplistic name generator that randomly alternates consonants and verbs), this would in theory require figuring out every word I wrote in quoted text strings that could possibly apply to an object and seeding the dictionary with it, wouldn't it? Including if I have a verb "stain" I'd have to add "stain" and "stained" to the dictionary?

I guess this wouldn't necessarily be a VM issue, because you could have something that compiled to the VM that generated these things as dict words... but it seems like it'd be clunky to do with existing tools.

The main reason I'd be interested in the dict words is that I'm told that doing string comparisons on the player's command is computationally expensive. If I try to whip up an example sometime I probably just won't worry about computational expense.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri May 25, 2018 2:52 pm 
Offline
User avatar

Joined: Sat Jun 25, 2016 12:13 pm
Posts: 240
What kind of contextual clause resolution does I6/7 have out of the box. For example, if i say;

Code:
> put key in bag on table


Does it correctly resolve,

1 put (key in bag) on table
2 put key in (bag on table)

Where in (1) the key is in the bag and (2) where the bag is on the table. The hit man with stone is similar to this.

More complex resolutions, might need story hooks,

Code:
> ask the butler about the man


Assuming the butler is male and only one other "man" were, so far, encountered by the player, this could resolve to a specific "man", otherwise it would need qualification, eg "old man" etc.

Ask abouts are tricky because the object asked about does not have to be local, consequently it's difficult to prompt resolution without accidental spoilers;

"which man the delivery man or the old man?" (bad idea!)

Suppose, as yet, you'd seen no "old man". Additionally, suppose you _had_ seen the old man but some time ago and the "delivery man" was just mentioned by the game;

eg.

Code:
> ask butler about cheese
The butler says, it's very cheesy.

At that moment, a van pulls up outside, stops and out steps a delivery man who proceeds to drop off a parcel near the door. He then gets back in the van and immediately drives off.

> ask butler about the man
"which man?"


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri May 25, 2018 3:25 pm 
Offline

Joined: Tue Mar 09, 2010 2:34 pm
Posts: 5320
Location: Burlington, VT
jkj yuio wrote:
Ask abouts are tricky because the object asked about does not have to be local, consequently it's difficult to prompt resolution without accidental spoilers;

"which man the delivery man or the old man?" (bad idea!)

Suppose, as yet, you'd seen no "old man".


This particular one is easy in Inform 7. The Epistemology extension is something that marks a thing as known when it's seen. You can make your conversation action apply only to known things, and then only unknown things will show up in the disambiguation:

Code:
Include Epistemology by Eric Eve.

Quizzing it about is an action applying to one thing and one visible thing. Understand "ask [someone] about [any known thing]" as quizzing it about.

Report quizzing: say "[The noun] does not know about [the second noun]."

Lab is a room. Gold Room is south of Lab. Silver room is south of Gold Room. Bronze room is south of Silver room.

A gold coin is in Gold Room. A silver coin is in Silver room. A bronze coin is in bronze room.

Marvin is a person in Lab.


Quote:
Lab
You can see Marvin here.

>ask marvin about coin
There is no reply.

>s

Gold Room
You can see a gold coin here.

>n

Lab
You can see Marvin here.

>ask marvin about coin
Marvin does not know about the gold coin.

>s

Gold Room
You can see a gold coin here.

>s

Silver room
You can see a silver coin here.

>n

Gold Room
You can see a gold coin here.

>n

Lab
You can see Marvin here.

>ask marvin about coin
Which do you mean, the gold coin or the silver coin?

>silver
Marvin does not know about the silver coin.

>s

Gold Room
You can see a gold coin here.

>s

Silver room
You can see a silver coin here.

>s

Bronze room
You can see a bronze coin here.

>n

Silver room
You can see a silver coin here.

>n

Gold Room
You can see a gold coin here.

>n

Lab
You can see Marvin here.

>ask marvin about coin
Which do you mean, the gold coin, the silver coin or the bronze coin?


Top
 Profile Send private message  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next

All times are UTC - 6 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group