Some really quick notes on interactive fiction and rule based systems.
This is an interesting introduction to rule-based systems. The basic point of contention is that you can get away from object-orientation in interactive languages by simply giving the complete rule set. The critical point in his discussion, though, is the question of “which rules take priority,” to which proposed solutions often smell sufficiently like the “sufficiently smart compiler…” trope that is rolled out every so often. The other concern here is avoiding something that can’t be resolved in linear time; that is, if it’s computable but gets exponentially more difficult to figure out the execution path, it’s not going to be realistic for a real-world IF system.
Different papers on these topics use different notations, but let us restate the problem into simple terms:
I am handwaving away here prepositions (easily handled with attributes) and noun lists (while interesting to parse don’t affect the main issue).
Prolog isn’t a great notation for this – notationally it elevates the verb / action to a special significance, but in reality you should be able to reason about the verb just as easily as the nouns – but it’s well understood notation, so let’s go for it So, something as simple as handling immovable objects:
take(X) :- immovable(X) => "That object can't be taken." take(X) :- => ... handle take ...where the notation is Prologish but for convenience separates the conditional :- from the action =>.
Logic systems map onto this pretty directly; at the point a statement is provable, you can just as well assume that provability maps to some execution. So, take for example an example from this paper on defeasible logic:
$$ r_1: monotreme(X) \Rightarrow mammal(X) \\ r_2: asFur(X) \Rightarrow mammal(X) \\ r_3: laysEggs(X) \Rightarrow \neg mammal(X) \\ r_4: hasBill(X) \Rightarrow \neg mammal(X) $$
You can easily imagine this as restated as:
note(X) :- mammal(X) => "Okay, you've noted the {X} in your notebook." note(X) :- => "That is not a mammal!" mammal(X) :- monotreme(X). mammal(X) :- has_fur(X). mammal(X) :- lays_eggs(X) => fail. mammal(X) :- has_bill(X) => fail. monotreme(platypus). has_fur(platypus). has_bill(platypus). lays_eggs(duck). has_bill(duck).… with the essential problem being: do note platypus and note duck do the right things?
In the above example it seems simple to resolve via source-code order, but source-code order is liable to drive you insane on a large piece of interactive fiction. Also, source-code order hurts the notion of composability; basically, it would be really nice if I could bring in a module and have everything just work. Defeasible logic handles it in linear time by explict rule ordering (i.e., in the example above, rule 1 and 3 are prioritized above rules 2 and 4) but down that route lies insanity for anything large and complex.
There are some implicit rules that seem to make sense 95% of the time (i.e., before doing anything to an object, be sure to ask the container of the object, the more specific case takes priority over the more general case) but even those are tricky to implement. For example, deciding the “more specific” of two rules is easy if one rule is a complete subset of another – but what if rule 1 is c1, c2, c3 and rule 2 is c1, c4, c5? How do you decide which is more specific? The thing is, object orientation in IF languages isn’t really used as much for code sharing (since most items are distinct – properties are used way more than subclassing), but instead, as a method of constraining event propagation and making sure that the events get routed to some handling routine.
Understandable rules for precedence are a big thing that object-oriented systems give you. In TADS, you know that the path of execution is pretty much:
This seems pretty straightforward.
So, assume the simplest example:
File 1:
examine(X) :- foo(X) => "You can't, it's foo."File 2:
examine(X) :- bar(X) => "You can't, it's bar."Given examine item, which evaluates first? If you assume foo() and bar() are arbitrarily complex functions then it become undecideable which takes priority at compile time without an explicit prioritization from the coder. The trivial example for this is when foo and bar are mutually recursive.
Ordering by rule groups and/or predicates might not be sufficient. One can easily envision that foo and bar should be prioritized one way for animate objects and another way for inanimate objects, for example. Or, that there is a specific ordering for one particular item. Assuming a rule is comprised of conditions and actions:
$$ r(v, n_1, n_2, …) := c_1, c_2, … c_n \Rightarrow a_1, a_2, … $$
is there a method by which we can unarbitrarily decide the ordering of the conditions?
A simple rule is that the developer needs to specify every priority between cn and cm for every rule that has both appearing. Another way of saying this: if condition 1 and condition 2 are not both used to evaluate a particular command, then we don’t care about their prioritization against each other, since the question is moot. Given this, can we flag underspecification at compile time? That is, can we make it so that the IF developer does not have to explicitly declare dependencies, but instead, warn them if something is not sufficiently defined?
Let’s take an example.
You can’t see anything in dark rooms, unless you have a light source. But the Black Pit prevents even light sources from working.
Starting from a tabula rasa, assume we have:
look :- dark(player.location) => "You can't see anything!"
look :- => describe_room(player.location)
(presume that this should all work even if those lines were in two separate files – it helps get away from the implicit notion that we should be relying on source ordering)
Now, how do we specify a light source?
look :- has_light(player, X) => describe_room(player.location)Suddenly, this is underspecified – the IF system does not know how to prioritize has_light vs. dark. This can indeed be caught at compile / interpret time. It gets interesting (or gross) for more complicated situations, though; imagine that the conditions are not primitives but instead call other conditions, so either we require the developer to a) explicitly state dependencies for the top level items, or b) get into strange decideability problem. For example:
xyzzy :- foo(X) => ... xyzzy :- bar(X) => ... foo(X) :- c1, c2 => ... bar(X) :- c3, c4 => ...The ordering for xyzzy is unknown due to c1 and c3 not being prioritized. Adding new rules would potentially get bunches of warnings for underspecification – since any new combination of conditions would need to prioritized in order to specify execution order.
In our example, the ordering is underspecified and flagged, and needs to be added:
prioritize has_light(X) > dark(X)Now add the Black Pit:
dark(black_pit).
Note that this would be accepted but would (probably) not be flagged as an underspecification by the interpreter, since we have already stated that has_light > dark. But to get the behavior we want we have to specify more:
So, we were able to specify two exceptions to the general rule. In an object-oriented IF system this behavior would have needed to be specified in the base object; for example, the notion of a “light source” that obviates the behavior for a dark room would need to be declared in the implementation of look, whereas with our system we were able to incrementally add the behavior. Okay, specified or at least thought about. To some extent TADS allows quite a bit of customization in the processing of commands by the multi-tier check system and by having virtuals that can be overridden. Fundamentally, though, the notion that a dark room can be overridden by a light source has to be defined somewhere in an object-oriented system. Inform 7 also has a predeclared prioritization, mostly defined by the runtime, but there are interesting ways to customize it.
Oddly enough, I started this article sure that rule-based systems were either NP-hard or not worth the extra complexity, but now I’m not convinced of either. The fundamental question in my mind is: What would using a rule-based system feel like? Would it be asking about underspecified prioritizations every 18 seconds, or would that be an exception? Would the day-to-day coding flow naturally?
And, even if those are true: could the rules be expressed in a way that was clear and unsurprising? Inform 7 is a marvel of programming but oftentimes I find its behavior inexplicable.
If I have a conclusion, it’s the same as Zarf did in his article: need to try it on a reasonably sized adventure. Next step is to mock up something simple to get a feel for it.
Briefly tried a rule based system on Cloak of Darkness, but it’s not complex enough to be interesting. Simplest form, stripped down of verbiage, assume some base runtime:
fiddled_count = 0. room(foyer). room(bar). room(cloakroom). path(foyer, south, bar). path(foyer, west, cloakroom). dark(bar) :- contains(bar, velvet_cloak). go(north) :- location(player, foyer) => "There's no point, it's rainy out." go(north) :- location(player, bar) => move(player, north). * :- location(player, bar) => "Really? You might disturb things."; increment(fiddled_count). has(cloakroom, brass_hook). attribute(brass_hook, hanger). attribute(brass_hook, immovable). has(player, velvet_cloak). attribute(velvet_cloak, hangable). has(bar, message). attribute(message, immovable). examine(velvet_cloak) :- "The cloak seems to be light absorbent." read(message) :- fiddled_count < 3 => "You have won"; game_won. read(message) :- => "You have lost"; game_lost.Some points did come up in thinking this through, though:
go(north) handler needs to be checked before the wildcard handler.Still thinking about it.
Comments are moderated whenever I remember that I have a blog.
There are no comments on this article.