A Muse

A MUSE

Introduction

Aim

MUSE is an acronym standing for Multi-User Simulation of Environment. This document is the outline for a possible implementation of a suite of computer programs designed to create and manage a small (with respect to its tangible contents) "world", which users of the program can to some extent "enter" and "explore". This world could range in size from, say, a network of cities in which a travelling salesman could experiment on the efficiency of routes before embarking on them in practice, to the arterial system of the human body, where students of medicine could join the flow of blood and "visit" parts of the anatomy, in so doing learning more about the three-dimensional layout of human organs (and that you can't go backwards up veins!).

Historical background

MUSE is a direct descendent of a line of games programs. Ever since computers became available, programmers have, in their idle moments (such as they are), toyed with the idea of using their machine for amusement. This usually involved playing against the computer in a two-sided battle of "wits", and may algorithms have been written to do just that, especially for the game of chess. In the early 1970s, a few programs appeared which did not, in essence, play against the user on the same basis. The first, and best-known, of these is the Advent [0] program. This was virtually hard-wired to simulate (not too well) a fantasy world, where an underground complex of rooms was explored by its players. The game, however, had three major drawbacks:

It was like a game of patience, or better still, solitaire, in which once you had obtained all the points for objects, you could do so every time (once you figured out how the random-number generator worked!). Indeed, .MIC files to get all the points have been written!
It was single-user only, and hence totally deterministic. No-one around to mess you about!
It could understand only a very small section of English, due to restricting the syntax to 2 words (verb-noun).

Advent became something of a cult, itself being based upon the cult game Dungeons and Dragons [1], and soon spread around by virtue of its being written in readily-available ForTran... People naturally got around to writing their own games, the most successful of which has been Zork [2] at M.I.T.-D.M., which was initially written as a natural-language understanding project. Zork hence easily solved drawback (3) above, and also reduced the annoyance of drawback (1) because rooms could be added to it (although to have a different database would have meant a complete re-write). Adding a room meant certain modifications to the actual code of the program.

The first program in the world to attempt solving drawback (2) was Essex's MUD [3]. In effect, its attempts at the other drawbacks were less successful. It managed to introduce a primitive database language to define new worlds, but was still hard-wired as a game rather than something of more general use. It used too many methods of interacting between users to give complete safety for multi-user capability, and occasional deadlocks resulted. On drawback (3) it failed miserably, being able only to accept in effect only triples of verb, subject, object (which it applied like a function with 2 arguments). It used a simple pattern-matcher to read these in, in order that commands could be more easily interpreted from the database. However, MUSE nevertheless resembles MUD more than any other program, although it transcends the game-only aspect. Of course, games can be played if an appropriate database is presented and its users wish to treat it as one.

The final program to which MUSE owes some debt is SPACE. This relation, however, is technical and concerned with the way inter-player communication is achieved. SPACE is not a program in the same field as the others - indeed it has no natural language interface - however I mention it for two reasons: firstly, it eradicated all the deadlock situations common in MUD; and secondly, I wrote it!

MUSE is the first program of its type to have uses outside being a mere game, toy, or other source of entertainment. That is not to say that, given an adequate world to create, it would not amuse or enthral; it is just not expressly for that purpose. Some would argue that any machine which does something a human user had expected to be below its abilities has some entertainment value, and if novel and varied enough will retain that user's interest. I couldn't care less, since I'm not a psychologist...

Limitations

"MUSE is limited only by the imagination of the database designed" (Richard Bartle, making a sweeping generalisation). Well, OK if you're very lucky, but there are a few things you may want to do which MUSE finds totally beyond itself, or would be very difficult to express. Its major limitation is that it hasn't been written yet! Apart from limitations imposed by the computer upon which it would be implemented, MUSE has the following ways of dealing with the drawbacks cited earlier:

the whole point of MUSE is to be able to work on various environments, so it scores well here. However, within a given environment there is no facility to create internally new objects except randomly, which may be sufficient (a traffic ham can occur anywhere) or insufficient (you can't be cut internally but not externally).
Solved totally. All activity is user-instigated, so nothing can happen unless the users interact with the database. User-user interaction handling is above the level of adequacy.
A larger section of English is "understood", allowing more complex sentences. Ambiguities in the language may be hard to understand, and MUSE has no way of knowing whether it has made a "sensible" interpretation or not. For example, is "the man with a bow and an arrow" referring to one object (a man possessing both a bow and an arrow) or two (a man with a bow, and an arrow)? Unless MUSE could find the former, it would choose the latter. MUSE is also hard-wired for a subset of English grammar, so could not easily input a sentence from a language grammatically disjoint, such as ~~American~~ Japanese. It also accepts words from a teletype only (unless someone has invented a speech recogniser which works, recently!).

Natural language interface

Context problem

Unfortunately, many words in English have different meanings depending on whereabouts in the sentence they occur. Most simple natural-language interfaces conveniently ignore this (such as in MUD), and only allow words to have one context; other programs are hard-wired for special cases (eg. in Advent, N has the meanings of North and No). Even Zork has problems in this area, and most situations are worded so as not to prompt a response involving a tricky word. Unavoidable ones are hard-wired. However, MUSE reads its vocabulary from a database, and hence has no idea about when to assume one context for a word and when to assume another. It can take either the MUD way out, or attempt to parse trying the various meanings of words with dual sense. Note that if a word has different meanings in the same context, it can be handled much more easily by simply making alternative entries in the lexicon for that part of speech.

MUSE, however, handles the problem by making a pre-parse scan of the input line, deciding in what context a word is more likely to be by the context of adjacent words. This, I estimate, would eliminate at least 95% of all errors due to puns. A 100% success rate could only be achieved by trying to parse a sentence taking each word in all its possible meanings in sequence until all combinations are tried. This is inadequate, however, since it involves too many parses, the simple case of, say, three words having different meanings (eg. nouns usable as adjectives, like "glass") would involve 8 parses! Another disadvantage is that the more obscure meaning may be encountered first, which would totally disrupt the environment if executed (eg. "make a Swiss roll").

MUSE's pre-parse scan uses the following algorithm: "Given that I am of the type suggested by the previous word, can I get to the end of the phrase by assuming the next word is of a type which normally follows a word of the type I think I am?" What happens is that an assumption about the type of the first word is made. If this word, when looked up in the lexicon, cannot be of this type then it passes back false and another assumption is made. If it can be of that type, it tries to finish the sentence by assuming the second word is of a particular type that can follow it. Eventually, the end of the sentence will (hopefully) be reached, and assuming the last word can be of the type suggested to it by the previous one, it will return true, and this will recurse out. This inductive form of context analysis has three main advantages:

It is fast, since although it backtracks is is only doing a depth-first search, and has an explosion rate of only 2 or 3 a node (branching rate) yet with excellent branch-lopping abilities (ie. it can eliminate large sub-trees).
It will reach the most generally used possibility if the order in which it tests is sequences properly.
It can ignore, or make guesses as to the type of, a word which it does not know.

Since this is not a very explicit description, there now follows an example pre-parse function called assume, on a small section of English. The parts of speech possible are as follows:

connector: eg. and, then, but
action: eg. go, sleep, devour
qualifier: eg. with, using, on
object: eg. hand, cattle, towel
descriptor: eg. red, smelling, oval

Words like "a" and "the" can be ignored as noise words. The function works on a vector of words in order of appearance, and is called by assume(ACTION, 1).

let assume(type, nextword) = valof $( unless typecheck(type, nextword) resultis false nextword + _ 1 switchon type into $( case OBJECT: resultis assume(QUALIFIER, nextword) \/ assume(CONNECTOR, nextword) \/ eol(nextword) case CONNECTOR: if assume(ACTION, nextword) resultis true case ACTION: if (type ne CONNECTOR /\ eol(nextword)) \/ assume(OBJECT, nextword) \/ assume(QUALIFIER, nextword) \/ assume(CONNECTOR, nextword) resultis true case QUALIFIER: case DESCRIPTOR: resultis assume(DESCRIPTOR, nextword) \/ (type ne CONNECTOR /\ type ne ACTION /\ assume(OBJECT, nextword) ) $) $)

The result of this bare-bones algorithm is merely an acceptor, since it only returns true or false, but instead of resultis true a function drop(type, word) could be used, returning true as a value. typecheck is a function returning true if the nextwordth word read in is of type type or is unknown. eol(nextword) is a function returning true if nextword is the last word in the input line.

Examples of use:

"block a big red pick-up" ACTION?--/--OBJECT? no QUALIFIER? no CONNECTOR? no DESCRIPTOR?--DESCRIPTOR?--DESCRIPTOR? no OBJECT?--eol? yes A simple example, with no backtracking: ACT-DES-DES-OBJ.

"get the gold watch" ACTION?--/----OBJECT?------QUALIFIER? no CONNECTOR? no QUALIFIER? no CONNECTOR? no DESCRIPTOR?--DESCRIPTOR? no OBJECT--eol? yes A little harder, some backtracking: ACT-DES-OBJ.

"kick the awful woman in the mink then in the shins" ACT?--/----OBJ? no QUAL? no CONN? no DESC?--DESC? no OBJ?---QUAL?--/----DESC?--DESC? no OBJ? no OBJ?---QUAL? no CONN?--ACT? no OBJ? no QUAL?--/----DESC? no OBJ?--eol? yes This sentence is obviously ambiguous. It seems that the intention is to kick the unfortunate woman, then kick her again specifically in the shins. There is a complication, however, if the word "in" can be used as an action, as might be the case if someone said "in" by itself, meaning "go in". If this happened, "in" would be recorded as an action and "the shins" as its parameter. Come the execution, some interesting results could occur! The answer is to have a default verb called when none other is present or there is none earlier in the line. Thus, "in" by itself would be an adverb, augmented to some other meaning if the default word was "go".

Unknown words: MUSE handles them as follows, guessing at their meanings. Say the word "?" is unknown in these examples:

"? the door" ACTION?--/----OBJECT?--eol? yes Guesses at an action.

"open the ?" ACTION?--/----OBJECT?--eol? yes Guesses at an object.

"open the door ? the keys" ACTION?--/----OBJECT?--QUALIFIER?--/----DESCRIPTOR? no &nb OBJECT?--eol? yes Guesses at a qualifier (eg. "with") but could have meant a connector (eg. "then").

"? ? ?" ACTION?--OBJECT?-----QUALIFIER?---DESCRIPTOR? no OBJECT? no CONNECTOR?---ACTION? no OBJECT? no QUALIFIER? no CONNECTOR? no DESCRIPTOR? no eol? no QUALIFIER?--DESCRIPTOR?--DESCRIPTOR? no OBJECT? no OBJECT?------QUALIFIER? no CONNECTOR? no eol? yes Guesses at ACT-QUAL-OBJ, eg. "fight using sword", but it is unlikely to be able to execute the instruction! There is a lot of backtracking, but it's better than 5 possible parses!

Obviously, if the program doesn't understand a word it can ask for a synonym, and restrict that synonym to the class it has found until it knows better, but this results only in a quaint feature of being able to give things nicknames in practice, since most errors will be misspellings... Whatever happens, the program should not admit that a word is unknown to it; I find nothing more infuriating than being told "I don't know the meaning of the word :s", where :s is the offender. What if it were "know"? Then, the program would say it doesn't know the meaning of a word it has just used! This annoying feature harks back to the days of Advent.

The program can also be made capable of trying "intelligent" guesses: if it finds a word it doesn't have an entry for, and that word ends in "s", it should be able to strip off the "s" and see if it can find a word with the remaining letters. Other guesses, such as "-ing" words, can also be built in.

In practice, the above small grammar is inadequate (although it still beats MUD and Advent!), and several more parts of speech are incorporated, including two types of adverb (or METHODs). These relate to whereabouts in a sentence they can appear: "quickly go west" means an adverb can be followed by a verb; "go west quickly" means adverb can follow adverb can follow verb, in which case "go west quickly go" is a valid interpretation, whereas it is nonsense. It is tempting to leave the problem unresolved, since if it's nonsense perhaps no-one will say it... Unfortunately, the nonsense might be picked out if one of the words is unknown, and then the parser won't be able to handle it.

An observation to make is that the grammar specified by the assume function should be as close to English as possible. If not a large enough subset is allowed, the users will find it too constricted or too fussy. However, they need not know what format the commands may take, assuming it to be standard English - in MUD you know that unless you put verb-noun or verb-noun-qualifier-noun it'll be ejected! If too much leeway is given, as in the "go west" example, mistakes can occur for the reasons given. In practice, the best alternative between restrictiveness and openness (if a correct blend is unattainable) is the generous input format, since English grammar is in a sense a subset, and thus if people put in an English imperative sentence it should be able to accept it (thus not annoying the user); the more restrictive possibility might be nearer to proper English, but could well have idiosyncrasies which drive you up the wall!

User interaction

After the context scan, the grammatical anomalies adjusted, the parser can be called into play. Since it knows that the sentence with which it will be provided will be in an acceptable form, it needs no syntactic error-checking (although this would not necessarily have meant inefficiency). The basic aim of the parser is to break the sentence down into phrases, which it can then attempt to understand. Stacking of previous sets of objects, actions etc. is of course required for pronoun substitution, and for connections between phrases such as "swallow the chalk and then the cheese" (not the same as "swallow the chalk and the cheese").

Phrases attempted are to be sorted into one or more of the following slots for their constituent parts: action, subject, active object, passive object. It takes into account qualifiers to determine whether an object is active ("him him with the spanner") or passive ("hit him in the stomach"), or whether it is in fact the subject ("hit him"). The object and subject lots are lists of all the possible objects which fill the category, since these are looked up in the parser, their meaning depending on the existence or not of other objects to fit previous interpretations. These descriptions are provided by the user, and are lifted directly from the lexicon.

Adverbs in a sentence are treated as augmentations to the verb. Thus, for example, "get up" can be interpreted as "arise", "go quickly" as "run". Paraphrasing in this manner can also impress the user (!), eg. getting the reply "you cannot run in that direction" for the above! The ability to paraphrase is, however, not an essential part of the program, unlike Schanks's various programs to paraphrase violent encounters between children...

The parser will also bind together nouns and qualifying nouns such as "the horse with the tail", provided it can discover somewhere an example of a horse with a tail, and return merely the horse as the item since the tail information is only relevant to pinning down horses with tails rather than those unfortunate creatures bereft of the adornment. This, however, can get complicated, for example take the sentence (phrase) "the farmer with the daughter with the kittens with the tails and the wife with the ginger hair". The program will look for a man, see if he has a daughter, see if she has kittens, see if the kittens have tails, see if the kittens have wives (fail), see if the daughter has a wife (fail), see if the farmer has a wife, see if she has ginger hair (fail) and finally see if the farmer has ginger hair. Assuming their exists such a family, it would return only the farmer as the result. If he had no wife, it would look for anyone's wife, see if she has ginger hair, then return both. If there is not such family, and no wives have ginger hair, the parser will return an empty list in case the verb doesn't need a subject or whatever noun group the words were supposed to fill.

This can result in some ambiguities, such as "the cat and the dog with fur" might be trying to exclude bald dogs, or bald cats and dogs (this problem also arises with the ginger hair trailer in the previous example). Another example, such as "hit the man in the box", is more, er, "striking": if the parser can find a man in a box, it will return him as the subject; if not, but it can find a man and a box, it will return "man" as the subject, "box" as the (passive) object. The philosophy of this is that the more specific case is the more unlikely, so that if it fails then the other meaning can be chosen. However, if the specific meaning makes sense (the man could be wearing a cricketer's box - ouch!) then it is so unlikely that the user would put in something making sense (ie. having something which satisfies the description) that he must mean it. This may seem ad hoc, but any more thoughtful algorithm would still likely pick the same solution eventually, since it's true!

Hence, the parser binds as early as possible, which also has the effect of cutting down objects in number and thus making thins easier when it comes to "understanding". Of course, it has to backtrack to some extent if it finds an empty list for a noun group, but few people are going to be as verbose as I in the fabricated examples above (I hope!). Maybe if it were given to people learning English..?

Command interpretation

The third stage in the natural language interface i, to some degree, what gives MUSE its power. In the first two stages, MUSE is in effect dedicated to the syntax of English. This is for two main reasons:

the method of writing down syntax which could then be translated into some methodic (?) data structure capable of being run is too much to try at such an early stage!
I can only speak English...

The philosophy of introducing a new section into the database defining the grammar of English every time someone wanted to define a new environment is also somewhat unjustifiably needless. If any non-Enlish-speaking country actually wants to use the system (!) then a hard-wired version for their own language would have to be written.

However, given a syntactic definition of English, users of the program have the option to define the words they need and the (operational) semantics of the subset. If only a general system is needed without the full power of the MUSE parser, words like "the", "a" and "an" can be ignored as noise words (as in the examples earlier). More complex lexicons can be constructed involving greater meaning, as the need arises - it is simpler to update a database with small bits added than to put it all in at once!

The way the execution part of the interface works is to look up the verb in the lexicon and pull out a template for a sentence involving it. Associated with each verb will be a string of such templates, and each will be tried until one fits. If none fit, a set of default templates are taken, whereby the database admits it is confused and could you rephrase please thanks.

But a "fit", it is meant that all those fields present in the template are present in the phrase to be "executed". It does not matter if there are more fields present in the phrase than in the template - for example kill person as a template provided with kill person sword as verb, subject and (active) object, would count as a match, it being irrelevant as far as the semantics are concerned what you use to kill people. It doesn't even check if you're carrying a sword!

The basic layout of a template can be thought of as follows:
action subject pre object pre object <instr>.
Action is the verb, and subject the subject(s) of the sentence. Pre is a prefix saying whether the following object is to be passive or active (missing it out defaults to active, and a second time in the same template to passive). One or both objects can be missed out, and if they are then the subject can be, too. If action is missed out then the default is the last verb. Note that in the lexicon a words can have more than one meaning associated with it for one part of speech, with little or no trouble. For example, north is an adverb, but there could easily be an entry as a verb, depending on the interpretation required of the single command "north". This can cause difficulties, for example the case of the awful woman in the mink earlier, where in as a verb would disturb the meaning.

The <instr> part of the template is the most interesting, for it is here that the crux of the interface lies ("instr" is short for "instructions", if you hadn't guessed...). MUSE is said to "understand" something if, when supplied with an imperative command or question, it obeys the command in such a way as the user would consider it possible within the environment (assuming the database writer has done his stuff!). This "obeying" is made by application of a sequence of functions to the database (among other things), and which are made available to the database author(ess). The syntax of the <instr> is as follows:
<instr> ::= FN [org]* <instr> <instr> | <number> | FAIL

The function FN is an internal ability of MUSE to do something, usually change the property of an object. FNs have a set number of arguments depending on what they do, but the arguments are usually the object(s) or subject(s) of the sentence. If the FN evaluates to true. the left <instr> is taken; if false, the right. Some FNs, eg. "change prompt", only ever return true (or false), and hence the other <instr> may be omitted. There is no "dangling else" problem, since MUSE knows how many branches a FN is supposed to have.

The <number> represents the leaf of an <instr> tree, and refers to a message to be printed out. If more than one message is to be printed, a function like print could be used, taking as its argument a number of a message. Once a leaf is reached, execution of this verb is halted, and the next phrase is looked at (or asked for!).

Finally, the FAIL is also a leaf to the tree, but whereas the <number> stops execution, the fail aborts and tries the next template. This could be important, for example with puns. It does not help the "is IN a verb?" problem much apart from checking parameters and discerning IN has one when it shouldn't, so apologising; by the time the template is checked, the decision as to IN's type has already been taken. Note that when the abortion (escaper) takes place, other functions may already have been executed.

So,me words have the same meaning as other words, or partially the same meaning. "Drop teacup" is identical to "drop <anything>" except that a check has to be made to see if the cup breaks. Another example is some object which could roll away when dropped. The "drop" function will most likely be very complex, checking all sorts of things, such as whether the "room" is halfway up a cliff, whether people can hear it, etc.. To avoid repeating large chunks of the template, <instr>s can be labelled, and the label can be placed instead of any other <instr>. Note that there is no forward reference possible here, since the database is one-pass, and no words in English have a meaning which is recursive (except the word "recursive"...). Although MUD's database was one-pass, it did not allow labelling of templates since they were not nested functionally anyway. This annoyed those of us who had to program in it!

Certain of the functions will be concerned with sending packets of information to other players. There is also a section concerned with receiving packets of information, which the program checks every half-second or so. If messages have been sent, they are dealt with in order of reception.

Since packet-sending needs three arguments (destination, information, packet type), and since they never return false (although the non-existence of their destination could be construed as such), to recap, a packet template looks as follows:
<send> ::= SEND DEST TYPE INFO >instr< fn. arguments

The receive checking function would take messages from the user's queue, then switch on the type into a vector of templates, using the type as a sort of deterministic guard. The format of the guarded command is similar to that of a function template, although working by type field. When a leaf is reached, the message block is "freed" for use again. Sometimes the INFO field is unnecessary, and can be left as null.

A crude example of this in action is the following simple implementation of a fight verb. A template for fight could be made as follows (<instr>s in brackets to ease reading): fight player (ifhere subject (send subject IWFU (0) (1))) and the message-receiving definitions would be: IWFU (ifhere sender (print 2 L: (random 1 (send sender IHU (3)) (send sender IMU (4)))) (send sender INHA (0))) INHA (5) IHU (dec lives (print 8 (L)) (send sender YHKM (6))) IMU (print 9 (L)) YHKM (9) The appropriate messages are as follows (:s being the sender or destination, as appropriate): 0 1 "" 2 ":S isn't here." 3 ":S has started to fight you." 4 "You missed :s." 5 ":S has escaped." 6 ":S has killed you." 7 "You have killed :s." 8 ":S hit you." 9 ":S missed you."

What happens is this: say Polly wants to fight Bert. FIGHT BERT is parsed, and the template is found. If Bert is not in the room, Polly can't fight him so she gets message 1 typed out, "Bert isn't here.". If no message is typed, Bert gets an IWFU packet sent to him. Polly goes about her business, but in reality the fact that she were fighting would be "recorded" so she couldn't leave the room. By the time Bert gets the packet, he might have left, so if Polly isn't there he sends back a packet telling Polly to print message 5, ie. he's escaped. If he hasn't, the fight is on, so he gets a random number between 0 and 1: if 0 he hits, 1 he misses, and the relevant information is printed. Polly gets his packet, decrements her "lives" count, and if she had any to decrement repeats Bert's actions. If she hadn't, she is deaded, and tells Bert he won. The battle will continue until one of them has no lives left and gets hit.

Obviously the example is over-simplified. What if Brian comes in and starts fighting Bert? What happens when you die? What if Bert leaves the simulation before checking his message queue? What if you fight yourself? However, it does give a flavour of the way the meanings of commands are used in practice in the MUSE system, if defined within the database properly.

`Objects in the database`

General structure of the database The database is that file (or program, if you will) supplied to MUSE such that it defines the environment for MUSE to interpret as a "world" for users to enter. The database comes in three sections: incidents, vocabulary, and messages. The incidents section is especially for packet reception from other processes running the same environment, plus other things to do in special circumstances like when the simulation starts, when it ends, or when an <instr> timing function runs out. It can also have what to do when no action templates fit. The messages section is a list of standard messages to be printed out. The program does not attempt to construct sentences in English by decoding the semantics of the functions used to reach that leaf of the tree into something a human can understand; although this would be worthy in some cases, it is not necessarily so that the database writer wishes all the insides of the workings of the database to be known - there may be something secret happening which the user shouldn't know about! Messages also give a more environment-dependent detail. Perhaps a paraphrasing mode would be useful, say replacing message 6 in the previous section's messages by, for example, "BERT (has given you a) FIGHT (and your) LIVES (has been decremented) (until) (you have none left)", where the brackets separate out each paraphrasing section. This still uses stock phrases, however, which are probably necessarily held in the text of the MUSE run-time system itself. The database will normally be small enough to be loaded into MUSE by a database-loader sister program (how many muses were there? 9?). As has been explained, this can be done in a single pass, since what forward references there are can be dealt with quite simply. Furthermore, all objects are static in size and number (although this disallowed the possibility of objects containing themselves - possible in Dr Who's TARDIS!). The vocabulary section of the database consists of words followed by definitions, grouped by parts of speech for convenience of not having to use the same prefix every time, eg. action or object or whatever. In here, actions will be assigned their templates, adverbs will be told which verbs they augment and to what, and objects will be given descriptions. Certain verbs will be very often used, such as "get" or "look", and it is hoped that a library of such words could be included in any MUSE package if one was ever written. Basic objects The "atom" of the environment to be created is the object. Everything is an object - rooms, users, and, well, objects! Objects can contain each other, transmute, disappear, be carried, interconnect, combine, and a host of other things which I'm not going to ramble on about merely to demonstrate I thought of them. Each object comes in several instances, or "properties", and when the property of an object is incremented it in effect becomes another object. This idea dates back to Advent, although there the property change did not change any other features about an object, except its description. Of course, certain things about an object will not change with property, such as contents, position and existence. In these cases, the object descriptors can point to the same records (they would also point to the same record of properties so only one could be active at once!). An example of this is, say, a door. It is sensible to have only two properties, open and closed. The description messages for each object instance would be relevant to whatever state it was in. Closing the door might INCrement its property, opening might DECrement. It would have a maximum property of 1, so an INC on 1 would fail; it would have a minimum of 0, so a DEC would fail. Since the object is a link, its position record would be for two rooms as it can be seen in both, but this record will be shared by both instances of the door. The door idea is only for a simple object, but most will be even less complex than that! Decorative objects need have nothing but position and description! Classes In addition to being individual objects, each object is a member of many different sets, or classes. It is by these classes that objects are referenced in the action templates, to save having to reference individual objects by name every time (impossible in the case of names for people). Some classes themselves will be subclasses of another class. Hence, if an object such as a chair is of class "furniture", and furniture is of class "everything", then a chair will be of class "everything", as is to be expected. Objects will change class in their various instances, for example a filthy disc won't be of class "treasure", but might be if you wash it and it becomes a coin. A box may be of class "wood", but may also have class "toy" if it turns out to be a jack-in-the-box (and the message "Out leaps a puppet on a spring, giving you quite a stir." is printed). In the parser, classes are treated like the nouns they are, but when mentioned a list of their object is taken and added to the object or subject list. Objects are never mentioned by name by the user, but their print-name could be the same as a primitive class of which it is the only member, say. Fortunately, treating things as classes gets over nouns with the same meaning, if a check is made when actions are applied. For example, a "fence" can be a wooden barrier or a receiver of stolen goods. Saying "erect fence" ... hmm ... "build fence" would pull out the class of objects which were fences in the barrier sense, and those in the illegal sense. The verb "build" would have a template checking its subject was of class "wooden", and if not would fail so we'd get on to the rest of the list, where the correct fence would be discovered. If there were only the criminal type of fence, it would abort and the next template tried. Rooms as objects All items in MUSE are objects; rooms are items, therefore rooms are objects. Sounds simple, eh? This is distinct from Advent, MUD and Zork (whose database was better organised) in that rooms were disjoint from objects in those games. No-one could pick up or move a room, so it seemed sensible. A travel table was built, listing each room individually, the rooms to which it linked, the directions in which the links held, and the conditions upon travel in that direction (eg. can't do it if an interposing door is of property 1). The only way to have, say, "drop ball" have the ball roll away until it could go no further was either to transfer the ball to a given place (Advent) pr have to hardwire the drop function to follow all the gravitationally-biased connections (ie. down) until it hit a door which was shut, or there were no down pointers. The former case has a disadvantage in that you might have gone somewhere before dropping the ball and by transference it might have had to go uphill. The disadvantage of the second is that if you stop at a blockage, how is the program to know it is a door? It might be something a ball can get past but a human can't, like a monster. It could be the reverse case - a human can cross a stream but a ball can't. There is also the possibility that two rooms are down from each other, but since this is a physical impossibility it's the database designer's own fault if it goes into an infinite loop... Zork introduced the concept of containers - objects which can have other objects inside them - although this was not exploited to its full potential. In MUSE, rooms are merely the outermost containers, although in a sense there is a single, overall container for the whole world. Properties of containers: their weights are the sum of their own weights plus those of their contents (MUSE's get verb template would check this, as would the give verb); containers can contain other containers, but never themselves (in a normal world); users entering a container using the move verb should have look called so they can get a description. Note that this is a function of the verb, unlike in MUD, Zork and Adventure where it is a function of the room. In describing the container, its internal description should be printed, along with the external descriptions of other objects also within it. A brief verb could trigger short descriptions rather than long ones. If a user is "inside" an object, they cannot pick it up, drop it, or move it (unless it is special, like a vehicle). If outside, they can. However, this will merely change the object's position so that leaving it puts you elsewhere; it will not alter any links to other objects, for example those which may be interpreted as directions by move. These links are also unaffected by other actions, such as shout or drop. A large section of the database will usually be devoted to covering special cases of the move verb, equivalent to a travel-table, for example IFIN KITCHEN D M, where D labels the die verb (you walked into an oven), and M is the movement (you went elsewhere). This can get quite complicated, especially if there are many objects which can block passage and have to be tested. Searching down links for gravitational bias is easy enough (provided some berk hasn't got his connections wrong), especially if there is a function, say findlast, to do it. Additional complexity is in evidence if, say, an object is dropped from a height, since presumably it will make a noise originating in the room in which it lands, and spreading depending on its weight, structure, material, and how far it got dropped. This form of transport is also instantaneous, whereas in reality it takes a few seconds to plummet over a cliff. Also the object might make a noise in each room it enters, eg. it's a transistor radio. A timer It is apparent that certain verbs can be quite complex, since their "meaning" depends on whereabouts in the environment they are used, and the state of that environment. Many special cases have to be handled separately, but the essential part will be the same. MUD handled this by in effect predeclaring words like talk, get, move, drop, look and fight so that the database was uncluttered (apart from that, there was no way by which the writers of the database could declare them!). I am of the opinion that certain macros like this should be available within the MUSE system, inbuilt, provided that the primitive functions to build them are also available so as not to lose generality. This library idea was mentioned earlier. In MUD, what database functions it had could be used in conjunction with these special functions such as shout. The comparison can be made between, say, printing out a number the hard way in machine code, or having a monitor call to do it. It's just a combination of primitive instructions, but it's common enough to be used in one fell swoop. People as objects Apart from objects simulating people, it is desirable that users be able to be moved around and have functions applicable to them as well as merely acting in a ghost-like observing capacity only, and that more than one person can be in the simulation at any one time. The ability to hold and manipulate objects is central to the MUSE concept, and treating people is objects is a natural extension to the "everything is an object" rule. There will be slots in an object record which may be defined by the database author(ess). These could range from things like "height" or "age" to "frustration" (in a maze!) or "aliveness" (in a gladiatorial arena). Most objects might have a "value" or "score". People can act as containers for certain classes of objects (water, potatoes, beer) but they cannot hold other classes (raccoons, anchors, lecture notes). They can communicate with each other, and do nasty things to one another. It is arguable as to whether all persons should be of the same overall class or not upon entry to the simulation, and if not, how to decide? Who should be a Confederate, who a Union general? Who a red corpuscle, who a white? Who a god, who a walnut? even such innocent cases such as the person's sex may be difficult to determine without asking. Thus, a prologue of questions should be asked, creating a file for the object which that person is to assume when in the environment, and based on the persona descriptor in the database. When MUSE starts up it can then find out all about the person (like whereabouts they start!). The questionnaire program can be divorced from MUSE, like the database loader. MUD asked for name and sex, and made the rest up, dumping a <name>.mud file for later re-entry into the environment. Problems arise for objects simulating persons (OSPs). When a user encounters one, it should act as best it can like a "real" person, and not be immediately obvious as to whether or not it is a user or just a clockwork dummy. It should at least put up a good show! Typically, the players will ask questions, and attempt to determine from the reply the nature of the being. The OSP should be able to move, like a person (or at least "appear" in a room in which it hasn't always been, as if it had just entered). Better still, it could initiate conversation - very unmachinelike! On the face of it, making the OSP react properly to the user's question (put in quotes so MUSE doesn't take it as a command to itself) involves an entire re-parse so as to elicit an adequate response. However, to avoid this and the difficulty of having to write down all the <instr>s, a simple keyword trigger is used instead, eg. ifsaid hello 28 29, where 28 might be "Hello.", 29 "Go away, I'm busy.". Obviously, after a few minutes' conversation an OSP will run out of things to say (as in Eliza) [5], and early keyword-recognising program). This is not to say that the wily user cannot pretend to be an OSP, but that it is dependent upon what the simulation is to be used for (training spies?). An anecdote along this theme comes from MUD, where two new players were wandering around, met, and started talking. Apparently, one had been chased by a wizard, told to stop running around, and was killed. The other suggested that the wizard was a dungeon-generated character... In fact, MUD has no characters of this nature, nor is it likely to! Other features of objects in the database are also possible, of course; all the slots will be the same for each property incarnation of an object, ie. more structure sharing, but, in cases where this is not wanted, action templates would check. For example, a slot for "luminous" would be ignored if the object was a lamp in property "off" (or, with my luck, "out of batteries"). This is similar for extra slots for people (depending on whether they are alive, awake or dreaming...). Implementation details Language It is no use glibly hypothesising on a program if it turns out impossible to demonstrate, due to asking too much of it. The first Algol report, for Algol 58, put forward some grand ideas which were discreetly removed from Algol 60 since they could not be properly implemented on a stack-based machine. So it is with MUSE: what does it have to be capable of doing, and is this possible? Of the programs mentioned earlier, Eliza was written in LISP, Advent in ForTran, Zork in Planner/LISP/Macro (I think!), MUD in BCPL/Macro and SPACE in Macro. The multi-user aspect of MUSE makes some Macro essential for systems of locks when communicating between processes. The interpretive aspects would certainly point to the database loader being written in a systems programming language (Bliss, BCPL, C). The parser and assume parts of MUSE mean recursion is required, and the large variety of data structures would favour a language in which the programmer can create his or her own. Another vital aspect is efficiency - especially for space, since it is desirable for all the vocabulary and most of the messages to be held in core. MUD ran out of space after about 100 rooms, and had to dump onto disc and cut down on actual code segments. Speed of execution means a compiled rather than interpretive language is best, unless the interpreter is very good. I have decided that probably the best language in which to write MUSE would be BCPL, with Macro drop-down for the fiddly bits. However, Ada could be better since it has the ability to send packets between processes already, although its code is not as fast as BCPL's. I haven't enough information to choose Ada, however, at this stage. BCPL was chosen over the old AI favourite, LISP, for the following reasons: It runs 50 to 100 times faster, and has no garbage collect. Its lack of typing makes structure-sharing and convoluted data types available. It is very efficient space-wise. The database can be dumped in binary and loaded directly into the high segment. It is imperative rather than applicative, and hence, whilst not as "pretty", is easier to program! The other languages considered which stood any real chance of being used were Macro (too tedious), Pascal (too small, too constricting, too slow), Algol68 (too complicated!) and Simula67 (like Pascal only with extra bits that aren't used). Languages with which I am not familiar but which could be better include Bliss, C and Prolog. Inter-process communication Since MUD can do it, then MUSE surely can! IPC is best achieved by using a writeable, shareable segment of code (the high segment in the DEC-10). In most systems there is an inter-process communication facility, including that of the DEC-10 (upon which MUSE is intended to run), but they are slower since they have to go through the monitor, and there is a delay so that "letters could cross" (although for those interested, this would only happen between arrival in the software interrupt block and the turning off of interrupts). Also, there is the slight possibility that malevolent users could write their own programs to send spurious packets of nonsense to MUSE users (MUSErs?). With the shareable segment idea, this is impossible (if you really want to know, GETSEGging in a shareable high segment sets the meddle bit so the SETUWP fails...). The next question is whether to treat the users synchronously or asynchronously. In SPACE, the critical section of code was treated like a hot potato, in that you got rid of it as soon as you could and gave it to someone else! In MUD, access is asynchronous, and if a job is aborted (usually by resource control...) the game is not held up. People have to "tidy up" as they leave normally, so packets sent will always arrive since the message queue is dealt with finally after the user is "removed" from the simulation. This gets rid of a full-scale garbage collect due to packets being left in unusable letter-boxes, especially if people check queues for previous owners of their game-slot (well, simulation slot in MUSE) when they enter it. MUSE will use a combination of ideas for communication from MUD and SPACE. It will use MUD's ideas for parallelism, but SPACE's of having one high-segment lock (thus avoiding MUD's occasional deadlock). To run synchronously means a total determinacy is possible, but the idea of everyone having to wait while each other's messages were printed is enough to sway me (a considerable way!) in the other direction! IPCF packages mean asynchronousness is a certainty, incidentally, unless turned off (in which case they are never received!). Debugging Debug mode? All programs have bugs in, even those written by me! To pretend that MUSE wouldn't is ridiculous. However, MUSE should do its best to enable its database to be debugged properly, ie. to make the environment it represents be that intended. MUSE can be likened to an interpreter running the program of its database. Most interpreters allow run-time debugging systems to work directly on the parse tree. MUSE's representation of the environment is a threaded, intertwining, directed graph, and unfortunately the techniques used in debugging tools tend to be what MUSE is supposed to do anyway (!), ie. descending levels within the program and one-stepping execution. A debugger must be written in such a way as to have virtually no effect efficiency-wise (it's no use debugging a program if the program can only be half the size of the debugger...). Zork has GDT - Game Debugging Tool - which can be used swiftly to move to part of a world and pick things up etc.. Since MUSE is dedicated to use on the DEC-10 timesharing system, perhaps a DDT rewrite could be used here, too? MUD got over the problem by having a "Wizard Mode", whereby players are suddenly attributed amazing god-like powers, and normal mortals are incredibly disadvantaged. Wizards are able to fly off anywhere, meaning that to test new sections of the database you don't have to go there on foot (in MUD, players always start at the same place). Unfortunately, in the case of MUD, wizard mode was more fun than normal play, and the password to it became a cherished thing! (At the moment it is "SEER", by the way). Debugging multi-process interaction can be hell, however! Due to the very non-deterministic aspect for which the game of MUD was written proved standard techniques to be inadequate. Even now there is the occasional look of dread on players' faces as all of a sudden they find nothing on their screens as another undiscovered deadlock rears its ugly head... If the user wishes to debug his or her database, then provided they have sufficient confidence in MUSE's packet sending, they will have to take it as read that the system will not deadlock! There are two options for debugging, neither of which is much use for various reasons. The first is to make MUSE have some DDT-like option, and the second is to make the writer of the database put in their own options. Regrettably, I think the second option is the lesser of the two evils, because it will at least allow some proper control on the database author's part. Of course, it is still available under the other system, but encouraging its use will make the database writer forced to use a more structured way of describing the environment, although it could well go over the top and introduce another version of wizard mode. I am wide open for any sweet-talking trickster with any new ideas to suggest them to me! The database loader This is a separate program which reads the database into memory, using the same relocatable addresses as would MUSE, and dumps it out in binary for MUSE to digest raw. It is in effect a compiler, or at least a translator to a machine-like language which can then be interpreted (like Pascal's PCODE or BCPL's OCODE). Thus it has all the usual problems for compilers, such as how many passes, what data structure for symbols, level of optimisation etc.. Fortunately, the overriding influence in the design of a compiler is the language which it is supposed to compile. The database language of MUSE is simple, non-recursive, and needs little if any optimisation. This makes things nice and easy on the loader, and all can be done in a single pass, as has been mentioned earlier. The only errors likely to be made are syntactic, and thus a comprehensive error message can be given. Semantic errors appear at run-time, and thus don't affect the loader unless there is a DEBUG function in the template part of a verb, which could look at a global variable to see whether debugging was "on" or "off" (if off, the code needn't be loaded). Since the loader doesn't know the meaning of the links in objects, it is completely unable to check things like " if I go west from here I have to go east to come back". This does let through "down from here leads to itself" problems, usually made by bored typists making errors. MUD's database loader worked on MUD Definition Language (MUDDLE), but had the most appalling error detection considering as how MUDDLE was so one-dimensional and simple. It aborted on the first error, rather than trying to find as many as possible in the program to save the writer debugging time! The messages themselves are horribly unhelpful, often ambiguous, and usually print out no name of even the word at which the error occurred. In the odd attempts it made to do this, it invariably came up with a load of garbage instead of proper characters. It is hoped that MUSE would be much more professional in its approach (it couldn't be worse!), rather than saying things like MUD's "Cannot read room name" or "Unknown function S$^BA2T"... Conclusion Uses To what uses could a system like MUSE be put? Given that once written it could be improved upon (like making it go on other machines), it is probably best to ask what it can do, which is simply simulate environments (or complicatedly simulate environments!). Trivial uses are in fields such as games, or semi-frivolous educational teaching ("You are a rabbit. Try to get out of your warren without getting mangled in the farmer's combine harvester"."). More positive uses would be in learning routes (taxi-drivers?), planning the layout of buildings (architects?) or proper teaching. More negative uses are available to the military... Depending upon the definition of an environment, many novel uses can be found. Treating it like a tree, a chemistry student could be asked at each quot;room" what to do (although it wouldn't be described as a room): if they make a correct choice, then a description of how the experiment progresses (to the next room) would be given; a wrong decision and they could go to the "blown to kingdom come" room, with a message saying what their mistake was. This is just a minor use to demonstrate flexibility - the above program could be written in BASIC (ouch, did I say "program"?). However, the first project to which MUSE would be applied would be a simple map, probably of the Computing Centre. After that, a full-scale environment such as a game would be tried (that way there would be no shortage of people to debug it!). Industrial uses? Well they could have it if they had a computer upon which it would run. The military would have to buy it (but wouldn't be interested anyway because it wouldn't be in Ada). Complexity and problems MUSE is an amalgam of various fields of computer science, and artificial intelligence in particular. It involves natural language "understanding", real-time operating system interfacing, and database handling. Indeed, it "discovers" so many fields of computing by its problematic approach (eg. guarded commands come naturally) that it may even have some new ones in there somewhere! However, the size of the problem is formidable, and knowing where to stop in the numerous sections has been difficult (I think the natural language interface is too powerful). Programming up an environment in this may be difficult if the database language is not clear, concise or simple. An obscure or baroque language would make environments suffer likewise. Since most environments have the concept of a room, has MUSE done wrong in treating them as objects? Another system of the same genre as MUSE is the PIGG project, also at Essex University, and in about the same stage of development as MUSE. This system uses a much more fluid arrangement as far as descriptions go than MUSE, in that the program actually attempts to work them out from other objects/rooms. Thus, upon entry to a room, the program would scan around and describe its contents, entrances and exits, and any rooms which are transparent and can be seen through into rooms adjacent to them. Difficulties arise when at, say, the top of a hill, and everything for miles can be seen: you do not wish to be told there is a living room and a study and a bedroom in front of a garden, you wish to be told there is a house! When to use what classes as description is a horrible problem! Whilst PIGG is of more descriptive power than MUSE, the two are essentially for different uses; MUSE is for a pre-defined environment, and hence its descriptions are more detailed. PIGG is to some extent able to create its own environments, within parameters set by its database (which consists of Macro code the program needs to read into itself!). MUSE is for those who want a static but detailed world, PIGG for the dynamic but expressionless world. PIGG is for the active, MUSE the passive! MUSE's obsession with "understanding" is PIGG's with "describing". The programs do overlap, but not conflictingly. This design choice is deliberate, since understanding by obeying and understanding by telling are disjoint in their approach (well, result) to the problem. Specificness in databases has the disadvantage in that users can say more complex things, so you need a better parser! You can't win! (Hmm, I don't think that last paragraph made sense...). MUSE has a problem as to whether or not its multi-user aspect is in fact needed! The code needed to handle this takes up space which the database could use for expansion. What's the point of multi-userness (?) if the number of mainframe computers capable of running timesharing decreases as micro- and mini-computers come into use? Since MUSE will most likely be dedicated to the DEC-10, this last question can be brushed under the carpet... Nevertheless, I am of the opinion that multi-user is better than single-user since in real environments you rarely have just one person! This is a bit sweeping, obviously, but if MUSE can help people to co-operate then at least it will have achieved something. Also, learning by discovery and by being shown is made simple, in fact MUSE tends to steer its database writers to try this due to its entire section for packet reception... It is also possible that certain problems can be made such that they can only be solved if people co-operate. The classic example is the see-saw problem: ___ | | [] ______|___|______ [] ^ This consists of a door leading to a plank with a pile of treasure at each end. The plank is pivoted, and if it doesn't balance then there is a long drop for whatever is on it. The idea is that the treasure is worth having, so when two people come in through the door they both have to walk along the plank and come back, otherwise a nasty fall down a bottomless pit results. Most people would figure it out and co-operate, however there is a twist in the tail: what if there were only one treasure trough? Another dubious position taken by MUSE is that of not allowing objects to be in different states simultaneously. If a room is entered from one direction, its description should be given from that direction's perspective, ie. using left and right. the natural way to o this is to have different properties existing simultaneously dependent upon which way you go in. MUSE will tend to give some extra information, such as "there is a door in the north wall", which you know because you just used it! This makes the database writer virtually forced to use compass points for directions, so it is very difficult to get someone lost! However, despite their being ways round this, the additional tedium to a database writer of having to describe a room 3 or 4 times virtually identically overwhelms this minor advantage! The PIGG style system scores well here, though, since it does the descriptions itself from its internal representation. Originality and achievements MUSE is new in that never before has such a large-scale or serious attempt to simulate environments been fully visualised. In the now legendary SHRDLU system, the environment of the blocks world was created, but the program needed an entire rewrite to change the environment even slightly (like add a couple more blocks). Such was true of Zork and Advent, and sort of for PIGG, although MUD tried for database independence but only ever had one database written for it. MUSE, however, is the first system able to take in a description of a world, and allow entry to that world in such a way as to be astonishingly comprehensive. It sets new standards in compact knowledge representation, and the switch from procedural to declarative data, from single- to multi-user, from gaming to generality, and from natural-language bias to descriptive bias must make MUSE a very powerful package. (Some would disagree, however: Trubshaw, the author of MUD is already writing a SUD - Single User Dungeon - as he is somewhat disillusioned by the whole multi-user aspect). Unlike other systems, a small world needs only a small database. SHRDLU's blocks had a pathetically low number of objects; MUSE places less emphasis on understanding input since it's not much use understanding all given to you if you can't do it (like being paralysed from the throat down). In essence, MUSE doesn't care how it is told to do something: if it can figure out the essentials of what is said, it'll do it. Ignoring or guessing at the meaning of spurious, obsolete, unknown or mis-spelled words is OK, since if it does find a matching template for part of the sentence, the chances are that the lost information will only be qualifying the verb or an object and that the correct match was chosen anyway. Thus, the parser is insensitive to slight perturbations in phrasing, rather than the extreme pedantic attitude taken by MUD and ADVENT. Were it written, MUSE would achieve a deeper insight into the whole idea of people interacting with machines, and would allow people to "go" to places in theory rather than physically. Of course, there are variations such as drawing rooms or giving photographic displays, but this is a bit like looking before leaping... What can be said, however, is that MUSE would break new ground in education, design, and to some measure communication. Frankly, I wouldn't care if it had absolutely no uses, the idea of designing a world of my own and being able to enter it intrigues me deeply! However, MUSE has not yet been written. As I said at the beginning, this document is an outline for how it would be. It describes the main points, but glosses over the nitty-gritty of the thing (I have, for example, deliberately refrained from describing what object records look like). What I hope to have shown is the three phases of the parser, to show how communication is described, and how the loader and introduction programs assist the main interpreter. If MUSE gets no further from the drawing board, at least it will have achieved the admirable feature of making me think! Still, we shall have to see, won't we..? Richard Bartle January 29^th, 1981. Appendix A References [0] Advent or Adventure, Don Woods and Willie Crowther, ~1972. Written in ForTran and available on virtually every DEC-10 computer in existence. [1] Dungeons and Dragons, Gary Gygax and Dave Arneson, ~1970. A fantasy rôle-playing game, something of a cult and the first of its kind ever. [2] Zork, Timothy A. Anderson, ~1977. M.I.T.-D.M. in the States. [3] SPACE, Richard Bartle, January 1980. Essex University. [4] MUD (Multi-User Dungeon), Roy Trubshaw. October 1979 (MACRO), March 1980 (BCPL). Essex University. [5] Eliza, Joseph Weisembaum, January 1965. another classic program on most large mainframes which have a LISP system. [6] PIGG, Stephen Murrell, July 1980. Essex University. [7] SHRDLU, Terry Winograd, 1971. M.I.T.