Jonathan Amsterdam is a graduate student at MIT's artificial intelligence laboratory. He has articles published in several magazines, and may be reached at 617-253-7881.
While browsing around my local computer system not long ago, I had the misfortune to stumble upon the source code for the original Crowther-Woods Adventure program. It's a gut-wrenching display of non-modularity run rampant. Except for the text of the messages and the network of room interconnections, the entire game, from the properties of rooms and objects to the movements of the bear, troll, pirate and dwarves, was coded right into the program.
I'm sure I wasn't the first to be goaded by this horror into designing a special-purpose language for writing adventure games. But mine differs from others I have seen in its attempt to combine the best of three different programming styles into a single, unified, Adventure Authoring Language, AAL. In this article, I describe AAL (pronounced simply "AI"), emphasizing the roles of the programming styles that comprise it and their implementation challenges.
The programming styles used in AAL all arose from artificial intelligence (AI) research of the 1960s and 70s. Today, each style is typified by a single programming language. The core of AAL involves deductive retrieval from a database of facts and rules, as popularized by the logic programming language PROLOG. AAL borrows the idea of inheritance from object-oriented languages such as Smalltalk for describing the objects of adventure games. And the list manipulation abilities, syntactic freedom, and general-purpose power of LISP make it the ideal language for implementing AAL.
First, I'll supply an overview of AAL, to give you an idea of how these aspects of the language are realized. Then I'll discuss the programming styles in slightly more detail. Finally, I'll consider some key points of implementation. Because of space limitations, I won't be able to describe all of AAL or its implementation.
Overview of AAL
AAL is designed for writing text adventure games in which players move from location to location and manipulate objects by typing brief commands. AAL maintains the state of a running game in a list of facts called the database. Portions of AAL programs can query the database to find out about the current state and can add (assert) and delete (retract) facts to change the state. Facts are represented by lists of symbols; the fact (in keys house) could mean that the keys are in the house.
Patterns are used to query the database. A pattern is like a fact but may contain variables, which in AAL begin with an asterisk. A pattern matches a fact if all the constants are identical; the result of a match is to bind the variables in the pattern to the corresponding constants in the fact. So, for example, the pattern (in x room) matches (in bear room) with *x bound to bear but does not match (in bear house) because room and house are not equal.
AAL programs cause actions to happen in the adventure game by examining and modifying the database using rules. The rule:
((at lamp *x) (on lamp) -> (lit *x))
says that if the lamp is at a location *x, and the lamp is on, then *x is lit. Rules consist of zero or more antecedents (patterns to the left of the ->) and one or more actions or consequent. If all the antecedents match the database, then the actions are taken. Variables appearing in the actions have the same values that they were bound to when the antecedents were matched.
Rules can be combined into rule lists, which act like nested if...then...elses. The rule list:
(((carrying player rod) -> "The bird is frightened")
((not (carrying player cage)) -> "You can't carry it")
(-> (take player bird)))
specifies what happens when the player tries to take the bird in the original Adventure. If the player is carrying the rod, the message "The bird is frightened" is printed and nothing else happens. If the player is not carrying the cage, the message "You can't carry it" is printed. If neither of these conditions hold, then the player takes the bird. (A rule with no antecedents is like an else: it always fires. It is also OK to omit the -> entirely in this Case. In general, a rule list can have any number of rules. Their left-hand sides are examined starting from the top, and the first rule to match is activated.
There are several different kinds of actions; you have already seen three. If a string occurs as an action, it is printed. If the first symbol in an action is the name of a built-in AAL procedure, such as take, then that procedure is executed (in the case of take, the procedure alters the database by asserting the statement [carrying player bird] and removing the statement that says in which location the bird is). If an action begins with the word lisp, it is given to the LISP interpreter for evaluation; this is an easy action to implement because AAL is written in and runs on top of LISP. If the action can't be classified as one of the above, it is assumed to be a statement to be asserted, as in the case of (lit *x) AAL programs consist of descriptions of the locations, objects, and commands in the adventure game. Listing One, page 58, shows a short AAL program for a simple adventure with only two locations.
The loc form is used to describe locations. The first symbol after the word loc is the AAL identifier for the location-very entity in an AAL program must have a unique identifier. The next item in the list is a string giving the long description of the location; the identifier, slightly modified, serves as the short description (the firstroom is modified to "The First Room").
The remaining elements of the loc form are keyword lists-that is, lists beginning with special AAL keywords. A list beginning with the symbol con ta ins specifies the items that the room contains at the start of the game. The exits list specifies the actions to take when the player attempts to leave the location. Each element of the exits list is itself a list, whose first element is the direction the player wants to go (for the first room, west and south are the only choices) and whose remaining elements provide the actions to take.
If an action is a symbol, it is assumed to be the identifier of another location and the player is transferred there without incident. If an action is a string, the string is displayed. So, if the player is in the first room and tries to go west, the list (w the-second- room I is examined and results in the player's being moved directly to the second room. If the player goes south from the first room, a message is printed and the player is left where he was. As the north exit from the second room demonstrates, rule lists can be used to implement more complex actions.
The third form in Listing One describes the blow command, which the player can enter to blow an object (such as the whistle--see later). The list (blow *obj) indicates the syntax of the command: the verb is followed by a single thing, the object of the blowing, which is bound to the global variable *obj. The requires list specifies what conditions must hold for the command to be carried out; this one says that the player must be carrying the object. If not, a message is printed that varies depending on what the object is. This is accomplished using the syntax of Common LISP's FORMAT function, a flexible output system similar to but more powerful than C's printf function. Because AAL is implemented in and runs on top of LISP, it is very easy to adopt FORMAT directly into the language. The last line of the blow command description specifies the default action to take; in this case, it is to print a message.
The next form describes the throw command. The synonyms hurl and chuck can be used by the player, but internally only throw is used. Throw's syntax is a little more complicated than blow's: you say throw <some object> at <something>, The variable *instr is set to the object thrown and the variable *obj to the thing at which it is thrown. To throw something, the player must be carrying that thing, and the target must be here (at the player's location).
The fifth form in Listing One is an obj form describing an object-the game's monster. Each item in an obj form is either a feature or a keyword list. In this example the monster has one feature, fixed, indicating that it is fixed in place and so can't be taken by the player. Each object in an AAL program may have several features, which describe various aspects of the object. For instance, a bottle might have the container feature, which allows the player to put things inside it; or a door, grate, or chain might have the lockable feature, which says that it can be locked and opened with a suitable instrument.
Features also act as predicates; giving the monster the fixed feature will result in the fact (feed monster) being asserted at the beginning of the game. In the monster description, there is also one keyword list that describes what to do when the monster is the object of a throw command: the monster destroys what is thrown, and a message is displayed.
The next form defines a feature, treasure, which describes how to figure the score of an object (using the method of the original Adventure). Because many objects can share the same feature, features provide for great economy of coding. Here you see also that features can take arguments, allowing them to be adapted to different situations.
The next form describes the whistle, indicating that when it is blown, it emits a screech and kills the monster if it's present.
As you can see from the definitions of the throw and blow commands, the monster, and the whistle, the actions to take on a command are distributed throughout the program. Here's what happens when a command is entered: first, it's parsed according to the template supplied by the verb, and up to three variables are assigned: *command to the command verb, *obj to the object, and *instr to the instrument. The last two are assigned as specified in the syntax template of the command.
Processing the command then begins, in two stages. First, the requirements are checked. The requirements specified with the command itself are checked first, then those on the object, and finally those on the instrument. In my example only the commands themselves have requirements, but it is common for special objects or instruments to place their own constraints on commands.
If all the requirements are satisfied, the command is executed. First, the object is checked to see if it has any actions; if so, they are carried out and processing stops. If the object has none, the instrument is tried, and if it has none, the actions on the command are done. In this way, objects implement their own actions for the most part, and actions specified with commands are the defaults.
This overview of AAL has hit the major features of the language, but unfortunately I have had to omit some features and many details. You will meet a few other aspects of AAL in the rest of the article.
AAL's Programming Styles
Having seen what AAL looks like, let's examine its roots. As I said, AAL combines aspects of three programming styles: logic programming, object-oriented programming, and LISP. Let's start with logic programming.
Logic Programming
In the late 1960s, it was noticed that mechanical theorem provers could be harnessed to answer questions about a database of information. Further refinements led to several powerful AI programming languages, including PLANNER, Conniver, and AMORD. PROLOG is a cleaned-up (but watered-down) successor of these languages. The basic idea behind deductive retrieval is simple: a query--typically a pattern containing variables--is compared against a database of facts, and those facts that match the query are returned.
You can add rules to the picture to make things more interesting (and complicated). There are two kinds of rules: backward rules, which are activated by queries, and forward rules, which are activated when new facts are added to the database. AAL has both these kinds of rules, though the earlier description didn't mention them.
Backward rules have a single consequent and one or more antecedents and are written in AAL with the consequent on the left, like so:
((in2 *x *y) <- (in *x *z( (in *z *y))
This rule says that something *x is in2 something else *y if *x is in some third thing *z and *z is in *y. Backward rules are the rules of PROLOG; you could write the preceding rule in standard PROLOG syntax as:
in2(X, Y) :- in(X, Z(, in(Z, Y).
Backward rules are stored in the database along with facts. When a query comes along that matches the consequent of a backward rule, processing continues with the rule's antecedents treated as subqueries. So, if your database consists of the facts:
(in water bottle) (in bottle house) (in food bag) (in bag house)
and the preceding rule, then the query (in2 water house) would match the consequent of the rule, binding x to water and *y to house; then the query (in water *z( is processed and matched against (in water bottle) with z bound to bottle; and finally, the second antecedent of the rule, which is (in bottle house) given the current variable bindings, is processed and matched against the identical fact in the database.
Note that the last two facts in the database provide a second answer to the query; if desired, this answer can be found via backtracking. Note also that with rules present, you have to extend the simple pattern-matching algorithm to deal with the case of matching two unbound variables against each other. In this case you simply bind the variables to each other; when either one becomes bound, the other is automatically bound to the same value. This generalized matching process is called unification.
So far, everything I have said is exactly as in PROLOG. Forward rules, however, do not exist in PROLOG (though they did in PLANNER and related languages). In AAL, a forward rule looks like this:
(when-asserted (in *x y) -> (contains *y *x))
This rule says that if something *x is in something else *y, then *y contains *x. More precisely, whenever a fact of the form (in *x *y) is added to the database, this rule is activated and the actions on its right-hand side are taken. In this case, the only action is to assert another fact into the database. Backtracking never occurs with forward rules. Forward rules are similar to the production rules of languages such as OPS5.
Note that the rules in Listing One are strictly speaking neither forward nor backward because they are activated by commands, not queries or assertions. But because they behave more like forward rules, they have a similar syntax.
Object-Oriented Programming
Object-oriented programming, typified by languages such as Smalltalk and C + +, consists of two major ideas: a program consists of a network of objects that communicate by message passing, and these objects obtain many of their attributes by inheritance.
The second of these ideas is an outgrowth of AI research into frame representation languages, 5,6 and it is the one AAL employs. Objects can have more than one feature, and features may themselves have features, allowing an interconnecting web of inheritance. As in standard object-oriented programming languages, inheritance facilitates the abstraction of common behaviors and properties.
LISP
LISP's enormous power derives from several sources. One source is LISP's ability to model a wide variety of abstractions using higher-order procedures, a feature best exemplified in the Scheme dialect but also available to a large extent in Common LISP. I use this ability to implement streams, a data type crucial to AAL's implementation.
Other sources of power are LISP's great syntactic flexibility and list-processing power. Using these, it is possible to implement languages on top of LISP very easily, without the need for bulky and complex lexical analyzers and parsers. Instead, you let LISP's macros and READ function take care of that tedium and work at the much more convenient level of lists. And because LISP's interpreter is always present, even when AAL programs are running, you can easily allow AAL programs to escape into LISP, thereby in effect making AAL a superset of LISP.
Implementing AAL
There are numerous interesting aspects of AAL's implementation, but here I only have space to discuss a few of them. The most difficult and interesting part is the deductive retriever, or deducer as it's called in AAL, so I'll consider that first,
Listing Two, page 58, shows the entire code for the deducer. The interface to the rest of AAL consists of the four functions assert, retract, deduce, and deduce-pattern. Assert is responsible for adding a fact or rule to the database. It only adds something if it is not already present. If it does add a fact, assert checks the left-hand sides of the forward rules to see if any apply and executes the actions of all those that do apply.
Retract removes a fact or rule from the database if it is there. AAL also allows rules to trigger when facts are retracted, and retract handles this.
Deduce and deduce-pattern are far more complicated, so I'll look at them in great detail. Deduce takes two arguments a list of patterns that make up the query and a list of variable bindings. Deduce augments the list of bindings it is given initially with bindings for variables in the pattern list and returns a stream of augmented variable bindings. II will explain streams later; for now you can think of them as lists.) From these augmented bindings, the caller of deduce can obtain values for the variables in the query. The pattern list is taken as a conjunction, so if called with the list ((in *x *y( (in *y *z)), deduce will return a stream of all bindings for x *y and z that satisfy both patterns.
Deduce begins by checking to see if the list of patterns is empty; if so, the query is trivially true and deduce returns a single-element stream consisting of the current bindings. Again, you can think of stream operations such as stream-cons as their list equivalents, and you can treat *empty-stream* as nil.
If the list of patterns is not empty, deduce first obtains a stream of bindings satisfying the first pattern, using the deduce-pattern function. Then it calls itself recursively on the remaining patterns for each binding in that stream, appending all the resulting binding streams into one large stream (that is the function of stream-mapcan).
Deduce-pattern simply calls deduce-pat with the pattern, bindings, and a list of facts and rules from the database that might possibly unify with the pattern. In its simplest form, find-possible-unifiers could just return the entire database all the time; I will make use of a slightly more sophisticated indexing scheme that can cut down significantly on the number of facts and rules returned.
Deduce-pat takes a pattern, a list of bindings, and a list of possible unifiers and returns a stream of augmented binding lists. It first checks to see if there are any more possibilities. If not, it returns the empty stream, indicating failure. Otherwise, it takes the first possibility and tries to unify it with the pattern, renaming its variables first if necessary.
If the unification fails, deduce-pat calls itself recursively on the remaining possibilities. If the unification succeeds, deduce-pat calls deduce on the antecedents of the rule (which will be null if the rule is actually a fact and the bindings produced by the unification. It appends the resulting stream to the stream obtained from calling itself recursively on the remaining possibilities and returns the result. This call to stream-append, like the earlier call to stream-mapcan, is necessary to ensure that every possible binding of the query variables is found,
Several internal functions of the deducer deserve mention. The unify function takes two patterns and a set of bindings and tries to unify the patterns. It returns the bindings augmented with new ones if it can unify and the symbol fail if it can't. It proceeds by recursively cdring down the patterns, trying to match each element. Variables are handled by unify-var: unbound variables are bound and the match succeeds; bound variables are treated like their values, by calling unify-const. Unify-const just compares the two elements for equality, returning the existing bindings if they are equal and fail if not. This unifier does not handle patterns containing nested structures as does PROLOG's, but it could easily be modified to do so.
Variable bindings are implemented as LISP association lists (alists). The add-binding function just conses a new pair onto the binding list, and the var-value function uses LISP's built-in assoc function repeatedly to find the value at the end of the chain of bound variables.
The functions add-to-database, remove-from-database, and find-possible-unifiers implement the database indexing scheme. This scheme is quite simple: facts are stored by their first element, on the element's property list. For instance, all the facts beginning with in are stored together. Backward rules (the only kind of rule stored in the database) are stored by the first element of their consequent, unless that element is a variable, in which case the rule is stored under the symbol. The possible unifiers for a pattern whose first symbol is a constant include those on the property list of the constant and the rules stored under , If the first element of a pattern is a variable, you are forced to search the whole database.
This indexing scheme has the advantage of generality. Further improvements could be obtained, still preserving generality, by indexing off more than the first element; see note 8, Chapter 14, for one such technique. Because many relations, such as in, will be ubiquitous in adventure games. they can be treated specially to improve efficiency even more. For instance, if the program maintains, with each object, a list of things that that object contains, then finding the values for *x in the pattern (in *x object) is just a matter of fetching that list. Many such optimizations are possible, but keep in mind that they are efficiency hacks, to be hidden in the database indexing mechanism and not made a feature of the language. The view of the adventure world as a single database of facts is a great strength of AAL.
Streams
If streams are just lists, then deduce will find every possible binding of the variables and return a list of all of them. This could be a big waste of time if you want only the first binding. And if (as is possible) there are an infinite number of answers, then deduce will never return. It would be nice if deduce worked more like PROLOG, returning the first answer as soon as it is found but remembering where it was so that subsequent answers could be requested. In fact, this is just how deduce works because streams are not lists but special data structures with a rather interesting property.
Streams behave much like lists-they have a car, which is a value, and a cdr, which is another stream (possibly the empty stream). They are constructed using an operation such as cons. The crucial difference is that a stream s elements are not all evaluated; only the first is. The evaluation of the remaining elements is delayed until they are actually requested.
Compare the two expressions:
(cons 1 (cons 2 nil))
and:
(stream-cons 1 (stream-cons 2 *empty-stream*))
In the first of these, the inner call to cons is evaluated, then the outer one, resulting in the list (1 2). But in the second expression, the inner call to stream-cons is not evaluated immediately. Its evaluation is delayed, and the resulting object looks something like:
(1 [delayed computation of (stream-cons 2 *emptystream*)])
(This notation is merely for explanation; you'll see the actual implementation in a moment.( When stream-car is called on this object, I is returned immediately. But calling stream-cdr forces the evaluation of the delayed computation. This results in a new stream, which you can write as:
(2 [delayed computation of *empty-stream*])
Another call to stream-car will produce 2, as it should, and calling stream-cdr again will result in the empty stream. So, using stream-car and stream-cdr on a stream is just like using car and cdr on a list, except for when the work is done.
The implementation of streams is remarkably simple. provided you have a lexically scoped LISP such as Scheme or Common LISP (see Listing Three, page 62).
You can implement them in terms of two primitives--delay and force. Delay takes a LISP expression and turns it into a delayed computation; force takes a delayed computation and evaluates it.
To delay a computation. all you have to do is enclose it in a function of no arguments, so an expression such as (+ 2 3) becomes #`(lambda () (+ 2 3)) (in Scheme, the # and `characters aren't necessary). You can write delay as a simple macro:
(defmacro delay (thing)
`#`(lambda () ,thing))
To force a delayed computation, you need only funcall it, so you can write force like so:
(defun force (thing)
(funcall thing))
You can implement a stream as a LISP dotted pair (cons cell) whose car contains the car of the stream and whose cdr contains the delayed computation. Constructing a stream from a value v and a computation c can be done by writing (cons v (delay c)), which is just what stream-cons does:
(defmacro stream-cons (thing comp)
`(cons ,thing (delay ,comp)))
Note that stream-cons must be a macro so that the second argument is not evaluated.
The other stream functions are simple. Stream-car is identical to car, whereas stream-cdr has to force the cdr of the stream object. You can represent the empty stream with nil, making the stream-empty? predicate equivalent to null. With these functions in place, you can write more complex ones such as stream-mapcan and stream-append just as you'd write their equivalent list-manipulating versions. The remaining trick is to delay the second argument of stream-append so that only the first argument is evaluated.
What is the effect of using streams in deduce? Instead of computing all the answers before returning any, deduce will take the first answer it finds and return a stream whose car is that answer and whose cdr represents the rest of deduce's work. if only the first answer is desired, the rest of the stream can be thrown away and no more work will be done. If another answer is wanted, calling stream-car on the stream will generate it. In this way, only as many answers as required are actually computed.
Streams have many useful applications besides this one. For an excellent description of streams and their uses, including a PROLOG-like interpreter similar to the one I've presented here, see note 7.
Applications of the Deducer
Let's consider three uses of the deducer in the implementation of AAL: rules, the every action, and requirements checking.
Much of the work in a typical AAL program is done by rules. A typical rule might say:
((at lamp *x) (on lamp) -> (lit *x))
To evaluate the rule, you first see if the antecedents (the patterns to the left of the -> symbol) can be satisfied, and if so you execute the actions on the right of the -> with the bindings for the variables on the left. Only the first set of bindings that matches the antecedents is used, so you really do not need the full power of streams here. The implementation is simple:
(let ((bindings-stream (deduce (rule-antecedents rule) bindings)))
(if (stream-empty? bindings-stream)
:did-not-fire
(do-rule-actions (rule-consequent rule)
(stream-car bindings-stream))))
Here, bindings are whatever bindings are in force at the time. If the rule occurs at top level, these will be the bindings of the AAL global variables. But rules may also occur as actions in other rules, so the bindings may contain variables accumulated from those rules.
As another application of the deducer, consider a kind of AAL action I haven't yet mentioned-the every action. It allows an action to be taken for every possible binding of a variable. For instance, to "take inventory"that is, display the items that the player is carrying-you could write:
(every *x (carrying player *x) -> (lisp (print *x)))
Implementing the every action is trickier than it might seem. The basic idea is to obtain the stream of bindings from using deduce on the antecedents, then execute the consequent for each binding. The problem with this approach is that a binding may be repeated if the deducer can derive it via different routes. The solution is to turn the stream of bindings into a list, then remove the duplicates. The implementation is shown in Listing Four, page 62.
As my final and most complex example, consider how the requirements for an action are checked. The compiler parses each requires specification into a list of requirement structures, each of which has three fields: a pattern to be checked against the database; a string to output if the pattern fails; and a Boolean variable called succeeded?, whose use I'll describe later. These structures (along with everything else mentioned when an AAL entity is defined) are stored on the property list of the entity's identifier.
Requirement checking is done by the satisfies-requirements function, which is called with the command, object, and instrument of the user's command and calls check-requirements for each of the three. Check-requirements gets the list of requirements for the command from the given entity, sets their succeeded? fields to nil, then calls check-reqs with the requirements list and the list of bindings of AAL's global variables. If check-reqs returns t, so does check-requirements; otherwise, check-requirements displays the string returned by check-reqs and returns nil.
Check-reqs' job is to return t if all the requirements can be satisfied or the string that should be printed if they can't all be satisfied. If AAL didn't allow different strings to be associated with each pattern, then you could represent the requirements as a list of patterns and implement check-reqs very easily using deduce:
(defun check-reqs (reqs bindings)
(if (stream-empty? (deduce reqs bindings))
"The requirements could not be satisfied"
t))
But the presence of strings for each pattern doesn't permit this approach because, when deduce returns an empty stream, you don't know which pattern was responsible for the failure. You need to use deduce-pattern on each pattern individually. One plausible first attempt might look like Example 1, below. Unfortunately, this isn't correct. Because of backtracking, it is a little tricky to pin down just which requirement is to blame when failure occurs.
Consider the requirements of lighting a lamp, which stipulate that the lamp contain batteries that aren't dead:
(requires ((in *x lamp) "Nothing is in the lamp")
((battery *x) "There are no batteries in the lamp")
((not (dead *x() "The batteries are dead"))
You would like a message to print out only when the corresponding pattern is the one responsible for failure. But the guilty pattern is not always the last pattern that fails.
Consider a situation in which there are two things in the lamp, only one of which is a battery, and the battery is dead. Say.that when deduce-pattern is called with the first pattern (in *x lamp), it returns a stream whose first element is a binding list with *x bound to the battery. Then the second pattern (battery *x) succeeds, but the third one fails because the battery is dead. A message should not be printed out yet because there might be other, nondead batteries in the lamp. So you eventually backtrack to the first pattern and get the second binding for x, which is the other object in the lamp. Now the second pattern fails right away because the second object is not a battery. Clearly, you would like to say that the reason why the lamp could not be lit was that the batteries in it were dead; the fault is with the third pattern, not the second. But the version of check-reqs in Example 1 will return "There are no batteries in the lamp."
Example 1
(defun check-reqs (reqs bindings)
(if (null reqs) ;; all requirements passed--success
T
;; else, check the first
(let* ((req (car reqs))
(binding-stream (deduce-pattern (requirement-pattern req
bindings))
(result))
;; if it failed, return its failure string
(cond
((empty-stream? binding stream)
(requirement-failure-string req))
;; else, try all the bindings on the other reqs until success.
;; dostream just iterate over the elements of the stream.
(t
(dostream (binds binding-stream)
(setq result (check-reqs (cdr reqs) binds))
(if (eq result t)
;; the remaining requirements passed --success
(return-from check-reqs t)))
;; No other bindings worked; return the last failure string result)))))
Example 1: An incorrect attempt to use deduce-pattern on each pattern individually
The key to the right solution is to notice that once a pattern has succeeded once, it cannot be the cause for ultimate failure, even if it later fails. Only a pattern that never succeeds can be guilty. The correct version of check-reqs uses the succeeded? field of the requirement structure to record this fact; it is given in Listing Five , page 63.
Review
You've seen how AAL combines three programming styles into a powerful language. At AAL's heart is the deductive-retrieval or logic-programming style of PROLOG; AAL represents the state of an adventure game as a database of facts, and AAL programs work by examining and manipulating this database. The pattern-matching, rule-following, and backtracking abilities of the deducer make it easy to write powerful rules and conditions simply.
AAL uses the idea of inheritance from object-oriented languages to ease the definition of game objects, locations, and commands. Each of these entities can possess one or many features, which not only act as abbreviations for properties but also serve as predicates in the database. Features can take arguments and may themselves have features, allowing complex networks to be constructed. Using features to group commands, locations, and objects can also result in considerable economy in rule writing because a whole group of entities (for example, commands that move the player) can be described with a single pattern.
Finally, AAL would have been an order of magnitude more difficult to implement were it not written in and on top of LISP. LISP's reader and macro facility trivialized the parser and compiler for AAL. LISP's property lists, built-in symbol table, and support for association lists simplified many aspects of the implementation. Its ability to construct and call functions on the fly made possible the implementation of the vital stream data type. And by allowing AAL programs to escape to the underlying LISP system, I obtained hundreds of useful functions for free.
What Next?
Here I have offered only a sketch of AAL, which is itself only a small part of what could be done in this direction. Many of the fine points of AAL and its implementation can be gleaned from reading the source code. But the deducer stands on its own as a useful program, or it can serve as the beginning of a PROLOG implementation. I have taken care to have all the essential code for the deducer published with this article, so you can begin without delay.
I realize that Common LISP is, despite its name, not terribly common compared to languages such as C and Pascal. But other LISPs, such as XLISP and Scheme, are available and will do just as well. And it is certainly possible to translate AAL into a language such as C, though I would guess the code size would more than double. The major difficulty concerns streams, which cannot be implemented in their full generality in a language that does not allow run-time creation of functions. Ersatz streams designed expressly for their role in the deducer can be implemented, however, by allocating a structure (or record) and storing the relevant local variables in it directly.
I have hardly mentioned the natural-language aspects of AAL because they are secondary to the concerns of the article and are not well developed in any case. Much could be done with existing natural-language technology to improve the parser and the treatment of command execution, I would guess that the conceptual-dependency representation of Roger Schank and his students might prove useful in this domain (see, for example, note 9).
Let me close with a specific, rather ambitious suggestion for improving the natural-language part of AAL. One weakness of the language is that it forces commands to be specified fully: you must say "throw axe at dwarf" instead of just "throw axe, as the original Adventure would let you do, or "blow whistle" instead of just "blow" when the whistle is the only blowable thing you're carrying. Adventure's resolution of the ambiguity was extremely ad hoc.
One reasonable solution when something is omitted from a command would be to look around for a thing that satisfied the requirements of the command and, if there was only one such thing, to use it. That would take care of blowing the whistle, but not killing the dwarf, and not a case in which the player said "drink" and was carrying a bottle of water, but the cap was on the bottle and the bottle was in a locked chest.
A more general mechanism would determine the player's desired action (drink the water in the bottle), construct a plan to achieve it (open the bottle, open the chest-do I have the key?), and execute the plan. It would be a very ambitious programmer indeed who tried to implement this idea; a good solution would probably be worth a Ph.D. thesis. In fact, see Allen's for a start.
Notes
- 1. Bertram Raphael, "SIR: A Computer Program for Semantic Information Retrieval," Semantic Information Processing, ed. Marvin Minsky (Cambridge, Mass.: MIT Press, 1968): 33-145.
- 2. Carl Hewitt, "PLANNER: A Language for Manipulating Models and Proving Theorems in a Robot," Proceedings of the First International Joint Conference on ArtIficial intelligence (IJCAI) (1969): 295-301.
- 3. Gerald Sussman and Drew McDermott, "Why Conniving Is Better Than Planning," MIT AI Lab Memo, no. 255A (1972).
- 4. Johan de Kleer; Jon Doyle; Guy Steele. Jr.; and Gerald Sussman, "AMORD: Explicit Control of Reasoning," 345-356.
- 5. Marvin Minsky, "A Framework for Representing Knowledge," Readings in Knowledge Representation, eds. Ronald Brachman and Hector Levesque (Los Altos, Calif.: Kaufmann, 1985): 245-262.
- 6. R. Roberts and Ira Goldstein, "The FRL Primer," MIT AI Lab Memo, no. 408 (19771.
- 7. Harold Abelson and Gerald Sussman, Structure and Interpretation of Computer Programs (Cambridge, Mass MIT Press, 1985).
- 8. Eugene Charniak, Christopher Riesbeck, and Drew McDermott, Artifical Intelligence Programming (Hillsdale, NJ.: Lawrence Erlbaum, 1980).
- 9. Roger Schank and Christopher Riesbeck, Inside Computer Understanding (Hillsdale, NJ.: Lawrence Erlbaum, 1981).
- 10. James Allen, "Recognizing Intentions from Natural Language Utterances," Computational Models of Discourse, eds. Michael Brady and Robert Berwick (Cambridge, Mass.: MIT Press, 1983): 107-166.
[LISTING One. A simple adventure game written in AAL]<a name="00a3_0011">
(loc the-first-room
"You are in a small, gloomy room lit by an unseen source above you.
The walls and floor are smooth, hard and dark, like obsidian. Exits
lead west and south."
(contains whistle)
(exits
(w the-second-room)
(s "You have wandered around and wound up back where you started")))
(loc the-second-room
"You are in a vast chamber of ice and rock. Fiery torches in the walls
provide an eerie light. There is a passageway south and another exit to
the north."
(contains monster)
(exits
(s "The passageway is blocked by rubble.")
(n (((alive monster) -> "The monster won't let you pass.")
the-first-room))))
(command blow
(blow *obj)
(requires ((carrying player *obj) "You don't have ~a" *obj))
"You can't blow that!")
(command (throw hurl chuck)
(throw *instr at *obj)
(requires (carrying player *instr)
(here *obj))
"Nothing happens."))
(obj monster fixed
(action throw *obj
("The monster destroys the ~a" *instr)
(destroy *instr)))
(obj whistle
(action blow *obj
"The whistle emits a piercing screech."
((here monster) ->
"The monster's eyes bug out--wider--wider--and then,~
finally, close forever."
(dead monster))))
<a name="00a3_0012"><a name="00a3_0012">
----------------------------------------------------------------
<a name="00a3_0013">[LISTING Two. [omitted--approx. 2 pages]]<a name="00a3_0013">
<a name="00a3_0014"><a name="00a3_0014">
----------------------------------------------------------------
<a name="00a3_0015">
[LISTING Three. Code for streams]<a name="00a3_0015">
(defvar *empty-stream* nil)
(defmacro delay (thing)
`#'(lambda () ,thing))
(defun force (thing)
(funcall thing))
(defmacro stream-cons (thing stream)
`(cons ,thing (delay ,stream)))
(defun stream-empty? (stream)
(eq stream *empty-stream*))
(defun stream-car (stream)
(car stream))
(defun stream-cdr (stream)
(force (cdr stream)))
(defmacro dostream ((var stream) &body body)
(let ((tempvar (gensym)))
`(do* ((,tempvar ,stream (stream-cdr ,tempvar))
(,var (stream-car ,tempvar) (stream-car ,tempvar)))
((stream-empty? ,tempvar) *empty-stream*)
,@body)))
(defmacro stream-append (stream1 stream2)
`(stream-append-func ,stream1 (delay ,stream2)))
(defun stream-append-func (stream delayed-stream)
(if (stream-empty? stream)
(force delayed-stream)
(stream-cons (stream-car stream)
(stream-append-func (stream-cdr stream) delayed-stream))))
(defun stream-mapcar (function stream)
(if (stream-empty? stream)
*empty-stream*
(stream-cons (funcall function (stream-car stream))
(stream-mapcar function (stream-cdr stream)))))
(defun stream-mapcan (function stream)
(if (stream-empty? stream)
*empty-stream*
(stream-append (funcall function (stream-car stream))
(stream-mapcan function (stream-cdr stream)))))
(defun stream->list (stream)
(if (stream-empty? stream)
nil
(cons (stream-car stream)
(stream->list (stream-cdr stream)))))
(defun list->stream (list)
(if (null list)
*empty-stream*
(stream-cons (car list)
(list->stream (cdr list)))))
<a name="00a3_0016"><a name="00a3_0016">
----------------------------------------------------------------
<a name="00a3_0017">[LISTING Four. Code for the every action]<a name="00a3_0017">
(defun do-every-action (rule bindings)
;; Get a list of bindings for the single quantified variable, using the
;; antecedents; then execute the consequents for each binding.
(let* ((quant-vars (rule-quant-vars rule)))
(if (not (= (length quant-vars) 1))
(error "Only one quantified variable allowed in rule ~a" rule)
(let* ((bindings-stream (deduce (rule-antecedents rule) bindings))
(bindings-list (stream->list bindings-stream))
(filtered-list (mapcar #'(lambda (b) (extract-bindings b
quant-vars))
bindings-list))
(undup-list (delete-duplicate-bindings filtered-list))
(new-bindings-list (mapcar #'(lambda (b) (append b bindings))
undup-list)))
(dolist (new-bindings new-bindings-list)
(do-rule-actions (rule-consequents rule) new-bindings))))))
<a name="00a3_0018"><a name="00a3_0018">
----------------------------------------------------------------
<a name="00a3_0019">[LISTING Five. The check-reqs function]<a name="00a3_0019">
(defun check-reqs (reqs bindings)
(if (null reqs)
t
(let* ((req (car reqs))
(binding-stream (deduce-pattern (requirement-pattern req)
bindings))
(fstring nil))
(cond
((stream-empty? binding-stream)
(return-from check-reqs (if (requirement-succeeded? req)
nil
(requirement-failure-string req))))
(t
(setf (requirement-succeeded? req) t)
(dostream (binds binding-stream)
(let ((result (check-reqs (cdr reqs) binds)))
(if (eq result t)
(return-from check-reqs t)
(if result
(setq fstring result)))))
fstring)))))
Example 1
[PT1][AL1][LM5](defun check-reqs (reqs bindings)
(if (null reqs) ;; all requirements passed--success
T
;; else, check the first
(let* ((req (car reqs))
(binding-stream (deduce-pattern (requirement-pattern req)
bindings))
(result))
;; if it failed, return its failure string
(cond
((empty-stream? binding-stream)
(requirement-failure-string req))
;; else, try all the bindings on the other reqs until success.
;; dostream just iterates over the elements of the stream.
(t
(dostream (binds binding-stream)
(setq result (check-reqs (cdr reqs) binds))
(if (eq result t)
;; the remaining requirements passed--success
(return-from check-reqs t)))
;; No other bindings worked; return the last failure string
result)))))