Unique interactive natural language input

ANDI-Land aims at eliminating the type of scripted dialogue that is almost universally adopted by today's games. Such straight jacketed dialogues typically has the player choose between three canned sentences, two of which are humorous sidetracks and one which will move the dialogue forward to the next three canned sentences.

Ultimately one would wish for complete freedom in text input. But this is not currently realistic for two reasons. First, no one has yet been able to construct a grammar that covers the entire English language. With only naïve use of a grammar with partial coverage, input would often have to be discarded with something equivalent to a "parse error" message. Even more seriously, the player wouldn't get any clues for how to rephrase the sentence so that it would parse correctly. Secondly, the knowledge of the NPCs is relatively narrow. Many sentences would simply be completely outside the area of competence of the NPCs, and they would have to respond with an "I don't know". These two problems would reduce the adventure to a sort of guessing game where the player, more or less blindly, would have to guess sentences that both parse correctly and whos meaning is understood by the NPCs.

The solution to both of these problems is a unique form of interactive natural language input that guides the player towards sentences that both parse correctly and are relevant in topic. As soon as the player starts typing, the game starts producing partial parses that cover as many words as possible. The partial parses are used to generate possible continuations of the incomplete sentence. These are presented as a list of words that are syntactic possibilities at the current position in the sentence. E.g. if the player starts typing "Buy the", the game might suggest a list of nouns s.a. "bread", "torch", and so on. The process could be likened to the widespread T9 mobile phone text input, except that the system understands the grammar of entire sentences rather than just the spelling of words.

Moreover, we are now in a position to deal effectively with the second problem, the narrow expertiese of game characters. By limiting the grammar to concepts covered by the NPCs knowledge we can ensure that most, or all, of the input sentences are answered intelligently.

Even a very small grammar will still present the player with a multitude of choices in dialogue interaction. It is our hope that this will remove the forced linearity of scripted dialogues. Rather than mindlessly trying all alternatives, the player will actually need to think.

Reversible grammar

Which sentences are acceptable is decided by a context free grammar. Attached to each rule is a lambda expression that represents its meaning. Meaning fragments are combined and extracted from completed parse trees as formulas of first-order logic. These formulas are directly used for reasoning and thus represent the game's understanding of the input sentence.

A chart parser performs the actual parsing, resulting in the logical form. By using a reversible parser we can apply the same rules, starting from a logical form and resulting in the corresponding English sentence. This has the great advantage that anything the NPCs can understand, they can speak. Extending the grammar improves both parsing and generation, without additional effort.

The grammar used is an extremely simple CFG. This could be developed, perhaps into a HPSG that can be used with the LKB. If you are knowledgeable in computational linguistics and interested in a cooperation, don't hesitate to contact me.

Automated natural deduction intelligence

The "brains" of the game characters is an automated natural deductive theorem prover ANDI. Any time an NPC receives an English sentence it will parse it into a logical form and try to prove it. The proof proceeds in the context of the knowledge that character currently has about the game world.

Three types of responses are possible. The simplest input is a factual statement, such as "The torch's price is 3 gold.", in which case the corresponding proof will result in true or fail. In simple scenarios, fail represents a negative answer, but in the general case, it might represent unknown. More complex are requests for information, such as "What is the torch's price?". The corresponding logical form contains an answer variable, which will be bound to the answer value during the proof process. This value can then be used to construct an informative reply. The most complex input type is actions. Actions are added to NPCs knowledge and cause existing knowledge to change over time.

Game graphics in Lisp

The entire NPC application is implemented in Lisp using Franz Allegro CL, including the game loop and graphics engine. Why, one might justifiably ask, would anyone program game graphics in Lisp? The answer is a pragmatic one. The focus of the project is on artificial intelligence, which benefits tremendously from being implemented in Lisp. It is convenient to keep the entire project in the same development environment. Thus, the relatively simple graphics engine is written in Lisp. When the NPC AI is integrated in other games, the Lisp graphics front-end will not be needed.