Thursday, January 6, 2011

Forward and backward chaining

In the context of rule-based systems, programming means to create rules which are applied by the engine to a fact base. Forward and backward chaining describe the two possible ways how the engine may achieve this. I found a neat explanation here.

Forward chaining starts with the facts: If a fact which triggers a rule exists, the rule is activated and may in turn modify other facts, and so on. A possible rule could be "if the floor is dirty, clean it"; it specifies when to do it

Backward chaining starts with a goal and tries to find the necessary rules to achieve it. The engine goes back through the chain of causality to find the first step. A backward changing rule could be "to achieve a tidy floor, clean it"; it specifies how the goal can be reached, but doesn't explicitly state when to do it

Both mechanisms are of course constantly used by humans, but the reasoning seems to be very different, or otherwise most rules engines would support both.

Forward chaining can be used for implementing the rules, like triggered abilities, and possibly state based actions. Even activated abilities could be handled by modelling them as a sort of triggered ability which "triggers" on playing it.
Characteristic changing effects can be handled effectively, because a rules engine watches its facts and can determine whether it's necessary to recalculate characteristics.
This is actually the main reason I want to use a rules engine. My current approach recalculates characteristics every time they are read, which... well, I'm repeating myself. By getting rid of this need, I hope to have easier access to the core engine from other parts, like AI, GUI and network.

Backward chaining is interesting especially for the AI: Backwards chaining tries to find a way from a current state to a goal, which is exactly what's done in a game. Drools, the rules engine I'm most likely going to use, does not support backward chaining yet, but the project plans to support it in a future release. Since the AI will be modular, such a backwards chaining AI could be supported once it's possible.