Game Parser Architecture
AlexisLi?'s Ideas
Three IOEventFilter subclasses are written. One only understands lists of IDs, and does the actual work. This is scheduled last. The filter before this translates SimpleMUE style commands into ID lists. And before this comes the full whammy 'I feel like plonking my derriere on that there tree stump' translator (good luck, Stillflame!). The third filter (the 'natural parsers') might be best implemented as many, ie one to cope with pronouns, one to sort out properties and nouns, one to isolate the verb, one to translate slang and so on.
— AlexisLi? - 18 Dec 2001
Ged's Ideas
Here's what I'd been planning to do, none of which is far off what you're suggesting:
The character maintains a finite state machine (recognizer) which is compiled from a list of Verbs which the character is capable of executing. These Verbs each have one or more accepting states which are something like:
<throw> <directobject> <throw> <directobject> <preposition>? <indirectobject> <throw> <preposition>
When a user types a command, it's passed to a LinkParser, which turns the contained sentence into linkages.
"throw the red ball at the duck behind the wall"
++++Time 0.03 seconds (236.84 total)
Found 5 linkages (5 with no P.P. violations)
Linkage 2, cost vector = (UNUSED=0 DIS=1 AND=0 LEN=17)
+----------MVp---------+
+--------Os-------+ |
| +-----Ds----+ +---Jp---+ +-----Js----+
+---Wi---+ | +---A--+ | +-D*u-+---Mp--+ +--Ds-+
| | | | | | | | | | |
LEFT-WALL throw.v the red.a ball.n at the duck.n behind.p the wall.n
Constituent tree:
(S (VP throw
(NP the red ball)
(PP at
(NP (NP the duck)
(PP behind
(NP the wall))))))
We will need some way to vet the linkages, too, as there's usually a bunch of them, but I'm not precisely sure how to do so yet. Probably ones which have the most linear or simplest constituent trees first or something...
Simplified versions (strip D*s, M[^v]s, As, etc.) of each candidate linkage are then run through the recognizer. If there's more than one accepting state, the user is queried to eliminate ambiguities and the event is discarded. If there are no accepting states, a generic "What do you mean?" error is generated.
If there's only one accepting state, the parts of the matching linkage are translated in the context of the character's current state (PerceptionObject, current ActivityProperty, wielded/worn items, inventory, etc.) into a linked object list. If any of these link-translations fail, or if there are ambiguities, an appropriate error message is generated, and the event is either discarded, or perhaps, if we really want to be fancy, kept in order to provide context to possible future commands.
Failed link: "Hmmm... your character can't see a red duck." Ambiguity: "which red duck behind the wall do you mean?"
If the ambiguity is kept, the user could then just type: "the big one.", or something, but that would require some system that recognizes simple noun phrases and applies them to previous command contexts. Link parser doesn't like bare noun phrases:
No complete linkages found. ++++Time 0.00 seconds (236.84 total) Found 1 linkage (1 with no P.P. violations) at null count 4 Unique linkage. cost vector = (UNUSED=5 DIS=0 AND=0 LEN=0) [the] [big] [one] Constituent tree: (S the big one)
Once the link-to-object translation happens, the assemblage is passed to the matching Verb, the code creates the necessary events, they're propagated, etc.
— GedTheGreysHain - 18 Dec 2001
Key Points
AlexisLi? wants a multistage parser. This means we can have something quickly, and add complexity ad infinitum.
Whatever is taken up will have to support abbrev's, ideally soundex, pronouns and ambiguity resolution. The balance between cleverness and asking for extra input will have to be carefully decided on. Too clever makes for unpredictable results, while asking for input all the time makes it awkward and discounts the ambitious aims.
Conclusions
Well, I don't think I quite understand what Ged's on about yet, so I'll do this bit later. Apologies for formatting of above, just finished at work, head in a tiz.
— AlexisLi? - 18 Dec 2001
What a Verb Knows
In Ged's scheme, a verb needs to know how it is used in a sentence. I think this can be accomplished by one of the following - either we can have a list of every acceptable sentence structure which the verb responds to, or we can have an arity with implicit grammar-type-checking of some sort off of which to match the sentence structure.
Sentence List
They verb "throw" may contain the following structures (only in link grammar): "verb-object", "verb-identifier-object", "verb-object-prepositionalphrase", "verb-object-ppphrase-adverb", &c. The sentence in question is then parsed, and for whatever structure is matched, a mapping of the words in the sentence to arguments to the verb's action method is made, and the verb's action is called. Fx, the ball at the duck sentence would have "ball" mapped to object, "the red" mapped to its identifier, "at the duck" mapped to a prepositional phrase modifying "throw", and "behind the wall" mapped to a prepositional phrase modifying "duck". The red ball object would then be found (in your hand), and the duck object would then be found (sitting over there laughing at you) and those two objects would then be passed to the verb's action.
Arity/Grammar-Checking
The verb "throw" may have an arity of (2..4) and the following signature: (throwwhat="object", throwwhere="verb-modifying prepositional-phrase", adverb="verb-modifying adverb") - with things like "object" replace by a link-grammar structure to which it would correspond. The sentence is then parsed, found within the environment, and the compenents are matched up and sent into the verb's action method.
— Stillflame - 24 Jun 2002
The "sentence list" part of your ideas are almost exactly what I meant by the "accepting states" part of my idea. I haven't figured out exactly how to represent the sentence constructs in the Verbs themselves, but I was thinking we could probably even auto-generated some of the possible sentence variants when someone creates a new verb just by parsing the Link Grammar source file/s. The mapping you suggest is called "object translation" in mine, but is also nearly the same.
Your arity idea is pretty nifty, too. Is there more of a distinction between the two than just how the valid sentence "patterns" are represented, though?
— GedTheGreysHain - 24 Jun 2002
So, here may be a better described path of execution. The sentence gets to the parser. Firstly, it looks for matches between all nouns and objects in the world/character's usable inventory. This is obviously not going to work for things like "throw a punch", or "throw the fight", where the noun is not an object in the world (maybe? maybe these things will be objects, which would simplify the parsing alot, but would not be without its own difficulties). Next, adverbs and adverb phrases would be turned into appropriate attribute objects to apply to the verb's action. These objects then have to be associated with the parts of the sentence they belong to. The next phase illustrates the difference between the two proposed choices.
The difference
Now a call to the verb's action method must be assembled. The difference between the two options, then, is whether to look at the sentence's linkage-trees themselves, or just to look at the objects' labels, assuming that both the lables and the verb's action method are sophisticated enough. The reason i think this is possible, is that we'll likely be able to succinctly decide on those parts of the sentence that are useful for most verbs - e.g. object, adverb, adverb phrases - and then just put them into their place in the method call. This would involve a redifinition of arity, to be able to return numbers, ranges or arrays, and/or adding another, maybe called #typedArity, which would return an array of the types it takes, and in what order (possibly being a two dimensional array, or something like that, to encompass more diverse signatures easily). Then, it would take objects it has, fill all required slots, and possibly fill in the optional ones.
This would, at some point, involve translating various linkage structures into the aforementioned sentence parts. We'll obviously have to have extracted out things like nouns in order to create the many objects that the sentence represents, so it may not be that much more of a step to add in the extraction of its part of sentence.
— Stillflame - 24 Jun 2002
