From GPWiki

Hello, I'm Dan and I'm going to talk to you about Rule-based AI systems. Before I start, I feel it necessary to make the reader aware that I have never implemented a game using a rule based AI system. But sometimes when staring at the blue sky, sunlight reflecting off my handsome chiseled features, well sometimes ... I do contemplate such a thing. You may think that it's rather forward of me to attempt to give a tutorial on something I've never actually done - well fear not. I have taken various AI courses and some of them did cover Rule Based AI Systems, also I have a very big book somewhere that I'll be refering to.

Theory

Rule-based systems are sometimes refered to as expert systems. This is the case when they cover a limited domain - for instance a computer that can diagnose disease. The most interesting general case rule based system is probably [Cyc]. They are no longer in-vogue with current AI researchers, searching for human like intelligence (for good reason too).

• Warning Personal Opinion incoming* Rule based systems generally deal with one objective world and this is why they make bad humans. We humans (woah this is going a bit offtopic) generally have multiple contradictory views of the world, for instance quantum physics, astrophysics and our intuitive knowledge of throwing things - each is a different view of the world. We can mix and match all these world views without getting into a never-ending loop and falling into a coma - yay us! The same can not be said for expert machines. Also expert systems have problems with time.

Now you've read my ill-placed rant, let's cover exactly what a rule-based system actually is.

Well it's made up of three things: a knowledge base, a rule set and an inference engine. The inference engine is the code that uses the knowledge base and rule set to "think". Ok example time, let's look at a mouse-expert-machine.

Knowledge base

CHEESE is GOODTHING

When our mouse is born this is all it knows.

Rule set

if X? is GOODTHING and X? is VISIBLE then moveTowards X?

Where moveTowards would be a function in our programming language of choice.

So the main loop in our mouse-bot would be as follows:

mouse.Process()
{
    knowledgebase.ClearVisibleIObjects();
    objects[] objs =  GetVisibleObjects();
    knowledgebase.AddObjectsAsVisible(objs);
 
    // Decide what to do next
    RunInferenceEngine();
    DecideWhaToDoNext();
}

After one loop the knowledge base might look as follows:

Knowledge base

CHEESE is GOODTHING

Newly Added Rules
MOUSETRAP is VISIBLE
CHEESE is VISIBLE
CHAIR is VISIBLE

So the cheese becomes visible. Yay, the mouse using its rule base deduces that cheese is good and it moves towards the cheese. And that's pretty much all there is to a basic knowledge base. The great benefit is pulling the AI logic out of the program - where's it usually heavily intertwined.

Implementation

Simplest is best! Let's create a nice simple rule base with plenty of expensive string comparisions.

Words of warning I quite like C# (I'm sure I'd also like Ruby, Python and others but argh emacs, vim I can never get it all setup up for my compile / debug cycle), so I will code in C#. Worse than that, I'll use bits of C# that are quite new and I don't know their equivalents in many other low-level languages. So before reading this: please know generics (cool things to avoid boxing, vaguely related to C++ templates), delegates (function pointers), events (restricted function pointers). Sorry! If you're particularly bright, which I'm sure you are - it's possible you can figure out the above as we go along.

Let's work on the knowledge base first. we need something that we can add pieces of knowledge to.

I'm feeling we need two classes and one struct. First lets code the knowledge chunks, which I'll call relationships.

Relationships

Relationships include such things as "is a", "wants a", "has a" etc. Extremely easy for us to make, if we're lazy. Let's be lazy and use a string for each part of the relationship:

[a] [relation] [b]

[DOG] [is] [ANIMAL]

From this it's easy to whip up a relationship class.

class Relationship
{
    string relation;
    string a;
    string b;
 
    private string Relation
    {
        get { return relation; }
    }
 
    private string A
    {
        get { return a; }
    }
 
    private string B
    {
        get { return b; }
    }
 
    public Relationship(string a, string relation, string b)
    {
        this.a = a;
        this.relation = relation;
        this.b = b;
    }
 
    public override string ToString()
    {
        return a + " " + relation + " " + b;
    }
}

It doesn't really get more basic than that. . . which is why we haven't quite finised. I want to store the knowledge chunks in a big knowledge table and for the index, to this table, - I want to use both A and A's relationship ... I'm greedy like that. If I only used A as the key to the table I'd often get a lot of redundant information. Using A and the A-relationship, the information is muc more relevant. So let's make a structure called RelationKey as follows:

struct RelationKey
{
    string a;
    string relationship;
 
    public RelationKey(string a, string relationship)
    {
        this.a = a;
        this.relationship = relationship;
    }
}

Doesn't need accessors because its only use is as a key. For extra slickness let's add a function to the Relationship class, that will return the above structure.

[Quick tip: This goes in the Relationship class]
 
public RelationKey GetRelationKey()
{
    return new RelationKey(a, relation);
}

Great. That's the knowledge-chunks formalized now let's work on the table. I want the table to work as follows:

Banana Knowledge

BANANA is FRUIT BANANA is YELLOW BANANA is SOFT

Let's say this is the knowledge we wish to enter into our knowledge table / knowledge base. (Somewhere in our wet humans brains we have this knowledge, encoded some how - we don't pick up a glass vase the same way we pick up a banana.)

Anyway when I call the knowledge base I want to use this syntax:

Relationships[] r = knowledge[new RelationKey("BANANA", "IS")];

Then it will return all relationships starting "banana is", and I can at last begin my banana based plans. Ok let's make my dream come true!

class KnowledgeBase
{
    private Dictionary<RelationKey, List<Relationship>> knowledge 
            = new Dictionary<RelationKey,List<Relationship>>();
 
    // Returns an array of relationships.
    public Relationship[] this[RelationKey key]
    {
        get
        {
            return knowledge[key].ToArray();
        }
    }
 
    public void Add(Relationship r)
    {
        RelationKey key = r.GetRelationKey();
 
        if (knowledge.ContainsKey(key))
        {
            // If the rules already added don't do it again.
            if (knowledge[key].Contains(r)) return;
 
            knowledge[key].Add(r);
            return;
        }
        else
        {
            List<Relationship> relationList = new List<Relationship>();
            relationList.Add(r);
            knowledge.Add(key, relationList);
        }
    }
 
    public override string ToString()
    {
        if (knowledge.Count == 0)
            return "Empty";
 
        string output = "";
 
        foreach (KeyValuePair<RelationKey, List<Relationship>> kvp in knowledge)
        {
            foreach(Relationship relationship in kvp.Value)
            {
                output += relationship.ToString() + "\r\n";
            }
        }
 
        return output;
    }   
}

Wow, that was easy and quick! So we now have a dictionary structure, this keeps a record of all of our rules. It stores them like so.

KEY VALUES

BANANA IS BANANA IS FRUIT BANANA IS YELLOW BANANA IS SOFT

BANANA HAS BANANA HAS FETCHING_TOP_HAT

Let's do a quick program to test our knowledge base is working as we'd hope.

KnowledgeBase kb = new KnowledgeBase();
kb.Add(new Relationship("CHEESE", "is", "GOODTHING"));
kb.Add(new Relationship("CHEESE", "is", "VISIBLE"));
Console.WriteLine(kb.ToString());

Output is: CHEESE is GOODTHING CHEESE is VISIBLE

It seems to me, we're on the right path. Next let's add a deduction function.

Deduction, dear Watson

So deduction what's that?

IF A is B and
   B is C then
   A is C.

Bit confusing? here's another example with more "english bits".

IF Roger is a DOG and
   DOGs are ANIMALs then
   Roger is an ANIMAL.

Ah, Holmes would be proud.

Sorry the next function is a beast. So pseudo code.

Get all the relatiohships where A->B Get all the relationships where B->C If it doesn't already exist, add the rule A->C Do this for each rule in the knowledge base.

These relationships are all going in the knowledge base class.

[Quick Tip: This goes in the KnowledgeBase class]
 
public void Deduction()
{
    List<Relationship> potentialNewKnowledge = new List<Relationship>();
    // Iterate through all the rules
    foreach (KeyValuePair<RelationKey, List<Relationship>> kvp in knowledge)
    {
        foreach (Relationship relationship in kvp.Value)
        {
            DeduceRule(relationship, potentialNewKnowledge);
        }
    }
 
    //Attempts to add new rules, won't add rules if they exist
    //already.
    foreach (Relationship r in potentialNewKnowledge)
    {
        Add(r);
    }
}

So we look through every rule and then call the deduce function on it. Just before we gallop to the deduce function let's consider deduction one last time.

CHEESE is GOODTHING CHEESE is VISIBLE

Might suggest to the uniformed, that, GOODTHING is VISIBLE.

but this is wrong wrong wrong, humans aren't robots but computers are. Consider

C is G C is V

Cats are GoodPets Cats are Vicious -> ? GoodPets are Vicious?

CHEESE is s GOODTHING, CHEESE is VISIBLE -> all GOODTHINGS are VISIBLE

But INVISIBLE CLOAKS are GOODTHINGS! and is cheese only good when it's visible? what about toasted cheese sandwiches eaten, wearing a blind fold? See, see the tower of logic fall and crumble!

Ok ready for the big fat deducer function (written in one go, tested once :D)

[Quick Tip: This goes in the KnowledgeBase class]
 
private void DeduceRule(Relationship relationship, 
    List<Relationship> potentialNewKnowledge)
{
    Relationship aIs = relationship;
 
    //Get the B's
    List<Relationship> theBs = knowledge[aIs.GetRelationKey()];
 
    foreach (Relationship secondRelation in theBs)
    {
        // A is B1, B2, B3 ...
        string b = secondRelation.B;
 
        RelationKey bRelation = new RelationKey(b, "is");
 
        if (!knowledge.ContainsKey(bRelation))
            break;
 
        List<Relationship> theCs = knowledge[bRelation];
 
        foreach (Relationship bIs in theCs)
        {
            //Create A is C, if it doesn't exist add it.
            Relationship newRelationship
                = new Relationship(aIs.A, "is", bIs.B);
 
            potentialNewKnowledge.Add(newRelationship);
        }
    }
}

Quick quick test.

KnowledgeBase kb = new KnowledgeBase();
kb.Add(new Relationship("A", "is", "B"));
kb.Add(new Relationship("B", "is", "C"));
Console.WriteLine(kb.ToString());
kb.Deduction();
Console.WriteLine(kb.ToString());
Console.ReadLine();

... and Skynet is born. Your own thinking machine. And that's just the knowledge base - consider the power when we add rules! (Currently this isn't much more than a context free grammar)

Rules

Well obviously we need a rules class. This particular rules class is going to be quite funky. We want rules to do one of two things (in the future you might want rules that do even more).

• Add knowledge to the knowledge base
• Execute C# functions

To this end we'll need a delegate (a variable that stores the C# function to be called if the rule is matched). I wrote this in the namespace scope so it is nice and accessible by whatever class is going to create the rules.

[Quick Tip: All my classes and structs so far are in the namespace "RulesMess"]
 
namespace RulesMess
{
    delegate void RuleFunction();

As you can see by looking at the delegate definition, we're only going to have the most simple of functions - no parameters, no returns. (A future expansion might be to include the knowledge, or pieces of knowledge, that led to this rule being fired.)

I'm just going to throw the rule class down now and then we can dicuss it's possible quirks.

class Rule
{
    private event RuleFunction thenRule;
    private Relationship ifTrue;
    public Relationship IfTrue
    {
        get { return IfTrue; }
    }
        
    /// <summary>
    /// On rule being correct add some knowledge
    /// </summary>
    public Rule(Relationship ifTrue, Relationship addToKnowledgeBase,
            KnowledgeBase knowledgeBase)
    {
        this.ifTrue = ifTrue;
 
        thenRule += delegate()
        {
            knowledgeBase.Add(addToKnowledgeBase);
        };
    }
 
    public Rule(Relationship ifTrue, RuleFunction functionToFire)
    {
        this.ifTrue = ifTrue;
 
        thenRule += functionToFire;
    }
 
    public void Fire()
    {
        if (thenRule != null)
        {
            thenRule();
        }
    }
 
}

As you can see a rule has two parts, a relationship and a delegate. The hidden logic is IF relationship THEN fire delegate. There are two constructors one constructs an add-knowledge-type-rule, like IF relationship THEN ADD relationship. This is done by passing in a relationship to be matched, the knowledgebase and a relationship to be added.

Example of a rule that adds knowledge

if ?x KILLS ?y and ?y is HUMAN then ?x is DANGEROUS

One thing to note in the implementation is the use of sn anonymous method. We add a method to the delegate that just says add the this knowledge to the knowledge base when fired. It's nice as we don't have to hold any superfluous variables.

The second type of rule is the type of rule that will call a C# function for us. This is very useful if we want to tie the knowledge base into our game code.

if x? is STOLEN and ?x is PROPERY then AttackPlayer();

And that's rules.

Inference Engine

Next up is the inference engine, there's a number of ways this can work and the main issues are which rules should be fired first. For our example this will be rather simple, we'll fire the very first rule that we can first and proceed from there.

Well here's the code:

class InferenceEngine
{
    public void Infer(List<Rule> rules, KnowledgeBase kb)
    {
        foreach (Rule rule in rules)
        {
            Relationship[] knowledgePieces = 
                    kb.MatchRelations(rule.IfTrue.GetRelationKey());
 
            if (CanFireRule(rule.IfTrue, knowledgePieces))
            {
                rule.Fire();
            }
        }
     }
 
     private bool CanFireRule(Relationship ifTrue, Relationship[] knowledgePieces)
     {
         foreach (Relationship r in knowledgePieces)
         {
             if (r.B == ifTrue.B)
                 return true;
         }
 
         return false;
     }
}

It's pretty simple. One visible function called Infer, this matches the "if A is" part of the rule to the current knowledge. We look through all the "A is" knowledge in the knowledge base and if there's one with the same "B" as "if A is B". Then we fire the rule.

A is C A is D A is K A is B <- MATCH! We can fire the rule!

You may notice I've added a function to the knowledge base here. It's called MatchRelations. This just allows us to access the relationships in the knowledge base. It's quite simple:

[Quick tip: This goes in the knowledge base class]
 
public Relationship[] MatchRelations(RelationKey key)
{
    return knowledge[key].ToArray();
}

Now let's write a test for a rule that adds knowledge.

KnowledgeBase kb = new KnowledgeBase();
kb.Add(new Relationship("mouse", "is", "dead"));
 
List<Rule> rb = new List<Rule>();
rb.Add(new Rule(
       new Relationship("mouse", "is", "dead"), 
       new Relationship("mood", "is", "upset"),
       kb));
 
InferenceEngine ie = new InferenceEngine();
 
ie.Infer(rb, kb);
 
Console.WriteLine(kb.ToString());
Console.ReadLine();

And a test for the other type of rule.

KnowledgeBase kb = new KnowledgeBase();
kb.Add(new Relationship("mouse", "is", "dead"));
 
List<Rule> rb = new List<Rule>();
rb.Add(new Rule(
       new Relationship("mouse", "is", "dead"),
       new RuleFunction(OnMouseDead)));
 
InferenceEngine ie = new InferenceEngine();
 
ie.Infer(rb, kb);
 
Console.WriteLine(kb.ToString());
Console.ReadLine();

You'll also need this handy function in the same scope.

public void OnMouseDead()
{
    Console.WriteLine("Oh no, the mouse it died!");
}

Wonderbar! We now have a reasoning machine.

Download the Source Code

I was contacted with some problems getting the code running, so here, in all it's glory, is the full source code.

Extension

There are many places you could take this rather basic code. The order here is roughly easy to hard.

• Allow rules to REMOVE knowledge from the knowledge base
• Negation such as if cheese is NOT visible then Cry()
• Introduce the AND keyword so if mouse is dead then OnMouseDead() AND mood is unhappy
• Variables in rules if x is a mouse then x is mortal
• Add a natural language parser so you can write the rules and knowledge in plain english.
• Consider efficency in even the vaguest sense
• Rules that add new rules to the rule base
• Pass knowledge into the C# functions for instance if x is dead then CommentOnDeath(x)
• Have active knowledge by using functions to check the state of the world. For instance if isMouseDead() then mouse is dead
• Actually tie the rule base to some type of game or simulation
• Meta rules that determine which order the rules should be fired
• Research GOAL searching, rather than our current knowledge generation approach
• Introduction fuzziness we're 50% sure a mouse is an animal. You may have to research fuzzy reasoning.

Implementing this in a game

If I was writing a game I think I'd have at least two types of knowledge, short term that dies after a game loop and long term that's always there. I'd also probably have an active-world knowledge base to draw short-term knowledge off from.

Active World Knowledge:

.
.
.
Steve drops AXE.
axe is GETTABLE.
orc is angry.
orc attacks Steve.
.
.
.

If I was going all out maybe a third "general knowledge base and rule base".

axe is WEAPON
weapon is SELLABLE

And a general knowledge rule base

if x attack I then I attack x
if x attack y and y is FRIEND then I attack x
if x is GETTABLE and x is GOLD then MoveAndGet(x)

Final Words

As I mentioned at the start I'm Dan and I'm more normally found posting about my RPG building woes on http://einfall.blogspot.com. I think rule based systems could be extremely powerful in a simulation or RPG setting (I haven't played Oblivion but to me that's what Radiant AI soundslike). Consider such relationships as:

• desire / want - I desire goal
• have / has
• can
• like
• hate
• feel

At some point I'm thinking of adding this style of AI to my RPG but it's while off yet. In the back of my mind, I'm hoping that Prolog will be ported to .Net, by then, and is as easy to embed as Lua.

Have fun!