Parser IF disambiguation hassles

Monday, January 15, 2024

Comments: 24   (latest 3 days later)

Tagged: if, interactive fiction, inform, inform 6, inform 7, parser, snow

Sidewalk The blizzard has mostly passed, but the sidewalk is a mess. Get to work.

You can see some snow and a snow shovel here.

>SHOVEL SNOW WITH SHOVEL Which do you mean, the snow or the snow shovel?

>SNOW Which do you mean, the snow or the snow shovel?

>SNOW Which do you mean, the snow or the snow shovel?

Boston got a snowstorm last weekend, and this grim scenario was on my mind as I wielded my mighty blade. Not the snow per se, but the parser error. IF authors have been bedeviled by that problem since the art form began. It's still quite easy to run into. The above was generated by this very short Inform 7 program:

Shoveling it with is an action applying to two things.
Understand "shovel [something] with [something]" as shoveling it with.

The Sidewalk is a room. "The blizzard has mostly passed, but the sidewalk is a mess. Get to work."

Some snow is in the Sidewalk.
The snow shovel is in the Sidewalk.

If you're not familiar with Inform 7, you may be furrowing your brow. Don't get hung up on the natural-language format, though -- that's not today's topic. You could do exactly the same thing in Inform 6:

Verb 'shovel' * noun 'with' noun -> Shovel;

Object   Sidewalk "Sidewalk"
  with description "The blizzard has mostly passed, but the sidewalk is a mess. Get to work.",
  has  light;

Object -> snow "snow"
  with  name 'snow',
  with  article "some";

Object -> shovel "snow shovel"
  with  name 'snow' 'shovel';

In both snippets, we have an object whose name has two words (SNOW, SHOVEL) and an object whose name has just one word (SNOW) and therefore the player is screwed. Any attempt to refer to SNOW is ambiguous and cannot be resolved. (The word SOME doesn't help; Inform considers articles too sloppy to rely on.)

Since time immemorial (1976, which, okay, I remember, but never mind) the recommended solution to this problem has been: "Don't do that, dumbass." Give each object enough synonyms to have a unique name. Honestly, two-word names will solve 99% of your problems. You could change "the snow" to "the snow blanket" or "the fallen snow" or even "a quantity of snow". (Infocom used "a quantity of..." quite a lot, although I think it was mostly to avoid printing "a snow" in object lists.)

You can see some fallen snow and a snow shovel here.

>SHOVEL SNOW WITH SHOVEL Which do you mean, the fallen snow or the snow shovel?

>FALLEN Heave ho, a merry old time shoveling the walk.

But this isn't an entirely satisfying solution. We're telling the author, "Look, the parser isn't smart enough to handle the game you designed. Write a different game."

Now, this is game design. Contorting your story to fit the engine is just another day ending in Y. Plus, IF authors love copious synonyms. Ever since we got past the C-64, the feeling has been, hey, throw in any word the player might possibly use. Why not? So beefing up "some snow" with a few more synonyms isn't an arduous ask.

But the ambiguities love to sneak back in. Take that classic Magnetic Scrolls command, "PLANT THE POT PLANT IN THE PLANT POT". Here we have an object whose name has two words (POT, PLANT) and another whose name also has two words (PLANT, POT). How are we to sort that out?

Okay, the answer is pretty obvious. Word order! In each case one word is an adjective and one is a noun. We know (in English anyway) that adjectives come before the noun, and they're not mandatory. So "PLANT" and "POT PLANT" should refer unambiguously to one object; "POT" and "PLANT POT" should refer to the other.

Inform 7 can do that just fine. Going back to the Sidewalk:

Understand "shovel", "snow shovel" as the snow shovel.

This specifies that SNOW by itself is not enough to match the shovel; it only counts if it's immediately followed by SHOVEL. But SNOW by itself is enough to match the snow object, so our problem is solved.

(Nitpickers: you need to add privately-named above to prevent Inform from generating a default word list. Let's ignore this.)

Great. Our problem is solved. What's this post about?

To answer this, I need to get down into some parsing guts. Specifically, the difference between matching and precedence.

When the parser receives a command, here's what it does. I'm simplifying, of course, but roughly:

  • Figure out the verb part of the command. Let's not worry about this stage. In the examples above, the verb is easy: shoveling or planting.
  • The rest of the command is the object part. (Assume one object, for simplicity.) Look through all the objects in the room ("in scope") to see which ones could match that text. Create a list of the possibilities.
    • If the list has exactly one entry, carry out the command.
    • If the list is empty, error: "You can't see any such thing."
  • Otherwise, we have several entries. Proceed to disambiguation.
    • Apply various criteria to rank the options.
    • If there's one best option, carry out the command.
    • If there's a tie, ask the player: "Which do you mean, ...?"

I'm not going to get into the disambiguation criteria. Inform has a long list. (Maybe too long!) But the author can set up rules to declare which options are better. This is the "Does the player mean" rulebook in I7, or ChooseObjects() in I6. It's not a perfect mechanism but it works well enough.

The important summary:

Matching is a yes/no decision. Does this object make the possibility list or not? If the player typed "GET KNIFE", any knives in scope are possibilities. Objects that lack the word KNIFE are completely eliminated.

Disambiguation is a ranked decision. Inform handles this by assigning a numerical score to every object on the list. (You could imagine comparing objects on the list to each other, or sorting the list. That's roughly the same idea, but the numerical score plan is easier to talk about and faster-running too. So we'll stick with that.)

Most important: in Inform, words are only considered in the matching stage. That's when we match command words against object words. In the disambiguation stage, we have a list of objects, not words! We compare the objects to each other; we've forgotten what words the player used to name them.

(Yes, I said I was simplifying. Pronouns and articles can have an effect on disambiguation. But not nouns or adjectives.) (There's a Curses-era hack for the words LIT and UNLIT but I am really not getting into that one.)

With this in mind, we can see that all our solutions so far have been about matching. The word SNOW only matches the shovel if it's directly followed by SHOVEL. If not, there's no match -- the shovel is eliminated from contention. Similarly, PLANT by itself doesn't match the plant-pot.

This works, but it's... imperfect.

Inform's default handling for object names is the bag-of-words model. You list a bunch of words for the object; the player can use any or all of them. All words count equally and order doesn't matter. Earlier I talked about nouns and adjectives, but really the parser doesn't have any such notions. It's all just words.

The bag-of-words is simplistic, but that's a good thing. It's easy for the author to understand; it's easy for the player to understand.

But now we've declared that the words SNOW and SHOVEL have to be adjacent. Order and position matter -- for this one case. And it improves this one case. But in general? Objects can have lots of adjectives, and the order isn't always fixed. What if you typed "GET THE BIG SNOW PLASTIC SHOVEL"? With the adjacency hack, that command would fail to match.

English famously doesn't treat adjectives as a bag of words; there's a conventional order. "BIG SNOW PLASTIC SHOVEL" sounds wrong. Most people would type "BIG PLASTIC SNOW SHOVEL". But it's not always that easy. What about a "SNOW POWER BLOWER MACHINE"? What word do you attach SNOW to then? "SNOW BLOWER" and "SNOW MACHINE" are both very reasonable player references, and "SNOW POWER BLOWER" should work too. Pretty soon you're knee-deep in variations.

Another benefit of the bag-of-words is that players can take shortcuts:

Toolshed You see a rusty knife, a snow shovel, and a nasty knife here.

> TAKE RUSTY With a qualm, you pick up the rusty knife.

You don't have to specify KNIFE. There's only one rusty object in the room, so the command works, no noun required. This isn't a critical feature, but it's nice.

(Another consequence is that long-cuts also work: "TAKE RUSTY RUSTY KNIFE RUSTY KNIFE" works fine in Inform. This doesn't bother players; it's just an amusing side effect.)

But notice that the shortcut fails for our snow shovel:

Toolshed You see a rusty knife, a snow shovel, and a nasty knife here.

> TAKE SNOW You can't see any such thing.

SNOW alone will never match the shovel. Even though there's no snow present to confuse with! The fallen snow is outside, on the Sidewalk, but our word-order hack is still in force. We'd like to avoid such inconsistencies.

One alternative is to only apply the word-order hack when snow is present. You can cajole Inform into doing this:

Understand "snow" as the snow shovel when the snow is not in the location.

This is pretty baroque! It requires a sort of double-negative thinking. (And it misses some edge cases; you have to get even more baroque to avoid all bugs.) We shouldn't drag game authors into this sort of contortion.

At this point in the conversation, someone usually suggests that the parser should distinguish nouns from adjectives. (In fact this post was inspired by such a conversation. See this forum thread, which started with the question, "Which do you mean, the heavy light or the light light?")

I think this is a false lead. It's not exactly wrong, but it's an "easy solution" which turns out to be grouchy and nonoptimal.

What does "support adjectives" mean, for the parser? One possible answer: An object only matches the player's command if the player has used at least one noun word. If the player has only typed adjectives, the object isn't a match.

This is not a new idea. In fact it's Exercise 75 in the old I6 manual. Really it's the same as the "SNOW requires SHOVEL" solution, except that we no longer rely on word order. The word SHOVEL just has to occur somewhere. Well, that's an improvement -- we've eliminated one unnecessary factor. But it's still a binary decision at the matching phase! We're still rejecting "TAKE SNOW" even when you're indoors and the command is unambiguous.

Here's a better plan: At the disambiguation stage, an object scores better if the player has used at least one noun word. Unfortunately, this is hard in Inform. Remember: by the disambig stage, the parser has forgotten what words were used.

Arguably my entire post boils down to "Inform's parser is missing a critical step." Yeah, sorry. It's not impossible to add this in. Again, someone did it back in the I6 days. But I7 has a different extension model, and the parser has gotten way more complicated over the years.

Even ignoring the implementation problem, the adjective/noun split still doesn't make everything magically better. Deciding what's a noun isn't always easy. Remember the "SNOW POWER BLOWER MACHINE"? You could say, well, obviously MACHINE is the noun and the earlier words are adjectives -- but that won't necessarily solve your disambig problem. If you've got a SNOW BLOWER MACHINE and a LEAF BLOWER, then BLOWER and MACHINE are both functionally nouns; it's only the SNOW and LEAF that are lightweight referents.

For that matter, COFFEE CUP and CUP OF COFFEE may well be two names for the same object. (Some games simulate drinking and an empty cup, but not all.) Is there a last word there? COFFEE may be an adjective or a noun; it depends whether you're worried about a SILVER CUP or a COFFEE MACHINE elsewhere in the game. And that's the simple case. What about a BIG GAUDY PORTRAIT OF LORD DIMWIT FLATHEAD?

I think people are imagining a scheme where if you define each individual object properly, then disambiguation will always work. And then assuming that a noun/adjective distinctive is such a scheme. I think that's two false assumptions. You're always going to have to think about what's in your game, what combinations the player will encounter. And if you're thinking about that, then dividing up nouns and adjectives is a distraction. You have to think about what words will distinguish the objects you've got.

Okay, that's a bunch of handwavy negativity. Let's talk about what I do want. (We can at least end with some positive handwaving.)

  • We should solve name collisions with at the disambiguation stage, not the matching stage. (Like I said above.)

  • Furthermore, we only need to apply a disambig tweak when there's a name collision to resolve. If the situation can be resolved by asking the player a disambig question, it should be.

  • Most objects don't run into disambig problems, so the author mostly shouldn't have to think about disambig. Use the bag-of-words model until you need to resolve a collision.

  • If an author adds one synonym, they'll want to add three. Or ten. Here's a definition from Hadean Lands, and not the longest:

Understand "twisting", "twisted", "involuted", "illegible", "stroke", "strokes", "lines", "marks", "markings", "black", "alien", "script", "graffiti", "graffito" as alien-script.
  • The point is, throwing another word into the bag should always be easy. It shouldn't lead to new problems.

  • Even in the noun/adjective way of thinking, an object can have several nouns. The a BRASS LAMP is equally a BRASS LANTERN. A RUBY is a RED GEM and probably also a RED JEWEL (unless you're doing something highly specific with jeweler's jargon). So we have to think in terms of groups of correct words, not a single correct name.

So what does that add up to? Here's how I want to think about it:

The parser already has a feature where objects can be indistinguishable. The idea is that if two things have the same synonyms, then nothing the player types can disambiguate them. So we shouldn't even try. Instead, the parser skips the disambig question and just picks one for you:

Treasury You see a gold coin, a gold coin, and a gold coin here.

> TAKE COIN Taken.

(Normally the parser would also treat them as indistinguishable for listing, and say "You see three gold coins." I've suppressed that to make the case clearer.)

This fits nicely with what we want! We'd like to say that if one thing's synonyms are a proper subset of another's, the parser would skip the disambig question and just pick the object with the smaller set.

Treasury You see a worn gold coin, a gold coin, and a coin here.

> TAKE COIN Taken.

Unfortunately (again), this is easier to say than to implement. First: the indistinguishability feature is somewhat limited in Inform 7. It's fine if you define several identical objects of the same kind:

A coin is a kind of thing.
Three coins are in the Treasury.

But the compiler isn't very smart about noticing if two separately-defined objects just happen to have the same set of synonyms:

The lighter is a thing in the Kitchen.
Understand "cigarette" as the lighter.

The cigarette is a thing in the Kitchen.
Understand "lighter" as the cigarette.

We'd need it to be at least that smart to extend this to the subset case. Then there's conditional synonyms, property-based synonyms, and all the other nice features that I7 supports.

Also, it doesn't currently think about word order. Recall the PLANT POT and the POT PLANT. That's the same synonym list, but even if the parser notices that, it will auto-select arbitrarily rather than considering what word the player used first.

(Indicating which object prefers which order is an exercise left to the implementer... Remember, in general there could be adjectives between PLANT and POT.)

Also, this feature doesn't account for the difference between printed names and synonym lists:

The thick red wax candle is a thing in the Kitchen. The printed name is "wax candle".
The thin blue wax candle is a thing in the Kitchen. The printed name is "wax candle".

> GET CANDLE Which do you mean, the wax candle or the wax candle?

The player could distinguish the objects by typing RED/BLUE/THICK/THIN. But they have no way to know that. The printed name properties don't mention those words. You might say "So don't do that, dumbass," but that's where we started, right?

(Most likely we got into this situation by adding synonyms without thinking about the printed name. Yellow card! Throwing more words into the bag is supposed to be simple and safe!)

So that's my conclusion: this whole disambiguation issue is close to something that the parser already tries to do. But (a) it doesn't do it perfectly; (b) extending the mechanism isn't trivial because parser guts; (c) the whole feature needs some rethinking.

But if we nail down the "indistinguishable" business, we have a pretty good basis for solving the "disambiguation loop" business in a logically tidy way.

Comments from Andrew Plotkin

Comments from Mastodon