Borg Knowledge Assimilator

 

Background

A little while ago a Star Wars-themed Flash game made the blog and email rounds, letting players try to stump Darth Vader. 

The premise of the game is that Darth asks you to think of something, and attempts to guess what you were thinking of by asking questions to which you answer "Yes", "No", "Maybe", "Sometimes", etc. Part of the fun of the game is hearing Darth insult you, seeing the dancing Storm Trooper at the end, and other UI fluff, but part of the fun is also watching Darth home in on your word by asking what occasionally seems like really insightful questions.

After playing the game for a short time, I realized that it was just walking a tree structure of questions and "things". I was struck by the similarity of the game to one I played back in the early 80's on my TRS-80 Color Computer (obviously, without the Flash interface). Back then, PC implementations of fake AI programs like Eliza were all the rage, and decision trees were seen as a possible way to implement limited AI. The program (unfortunately I can't remember the name) asked you Yes and No questions, and seemed to learn from the experience. We were young and easily impressed back then.

It was all just string manipulation, of course, but it was *compelling* string manipulation. Evidently it's just as compelling now. After watching people in the office play the Sith game repeatedly, I became interested in re-implementing the original in C# and XML using everyone's other favourite fact-hungry villain, the Borg. In this article, I'll show you how to write a game that mimics the core functionality of the Sith game and talk about console applications, XML serialization and the good old days...

The Algorithm

I think it's beneficial to talk through a sample run before we dive into the code. I'll use the same data as is shown in Image 1. You can distinguish user input from program output because user input is always coloured bright green.

When the application runs, it prompts the user to think of a noun. In this example, the user will be thinking of a rabbit. The application asks its only question and solicits a yes or no answer from the user. In the database provided in my source, the initial question is "Is it alive (y/n)". The answer to this question (thinking of a rabbit), is "Yes", so the user enters "y". The app traverses the tree on the "Yes" side and reads the noun on the Yes branch of the initial question (turtle). If the "Yes" node had been another Question object, the game would have just asked that question text and continued to traverse the "Yes" and "No" properties of the questions until a Noun object was found. In this example, though, it has arrived at the end of this branch of the decision tree and asks the user if "turtle" was the noun which they were thinking.

The answer will be "no", since we're thinking "rabbit". Now the app switches into knowledge acquisition logic. The application asks the user for the noun of which they were thinking. The user types "rabbit". The app then solicits a question that distinguishes the noun the user had (rabbit) from the noun the program was expecting (turtle). The user can type some question like "Is it a reptile".

The app then saves the new knowledge back to the original data file, resets its internal pointer back to the root Question object, and asks the user if they want to play again. The XML data file is portable, and can be emailed around to people to play.

Talk is cheap and occasionally confusing. You can see how the object model (and the persistent XML which describes the object model) evolves through this simple example in Image 2.

The Code

There are two basic constructs in the object model, Question objects and Noun objects. Noun objects just have a Text property. Question objects have a Text property, and Yes or No properties that are followed based on the responses given by the user to the Text property of the Question. The Yes or No properties of the Question object can be other Question objects, or Noun objects. Since the nodes can be one of two different types, I created an interface both Question and Noun objects implement, called IBorgElement, and use that as the type of the Yes and No Question properties. I consolidated the common elements of Question and Noun types into the interface (a string Text property and a Serialize method) but I didn't have to.

C#

using System;
using System.Xml;

namespace Borg {
   public interface IBorgElement {
      string   Text {get;}
      void     Serialize(XmlDocument doc, XmlNode node);
   }
}

Noun Objects

The Noun object is really straightforward. It can be instantiated with an XML node to aid in deserialization, and it can be instantiated with just the string for the Text property:

C#

public Noun(string text) {
   _text = text;
}

public Noun(XmlNode node) {
   XmlAttribute   text     = node.Attributes[Noun.TEXT_ATTRIBUTE_NAME];

   if (text != null)
      _text = text.InnerText;
}

Noun.TEXT_ATTRIBUTE_NAME is just a private constant string describing the name of the Text attribute in the Noun node of the XML document. In this case, it's "Text". I didn't like having the literal "Text" scattered around the class for serialization and deserialization, so I made it a private constant. You'll see this in the Question class too.

The only other interesting aspect of the Noun class is the serialization code. The Noun and Question objects have to be serialized into an XML document after each new fact is added to the object model. Serialized Noun objects are pretty trivial and look like this in the XML file:

XML

<Noun Text="turtle" />

It is their position in the document which confers the relationship to other nouns. The code to serialize the state of the object looks like this:

C#

void Borg.IBorgElement.Serialize(XmlDocument doc, XmlNode node) {
   XmlNode        noun  = doc.CreateNode(XmlNodeType.Element, 
                                 Noun.NodeName, string.Empty);
   XmlAttribute   text  = doc.CreateAttribute(string.Empty, 
                                 Noun.TEXT_ATTRIBUTE_NAME, string.Empty);

   text.InnerText = _text;   

   // Add the attribute to the new Noun node.
   noun.Attributes.Append(text);
   // Add the Noun node to it's place in the master document.
   node.AppendChild(noun);
}

This code would get called by a Question object when it is serialized, if either the Yes or No properties are Noun objects. I'll show you that in the section below. The method needs a reference to the main XmlDocument object in order to create new nodes and attributes, and uses the XmlNode parameter to know where in the document to add itself. Noun.NodeName is a public, static property of the class and returns the name of the XML node for the Noun. It's public so other classes can know what the name of Noun nodes are too.

Question Objects

Since they implement the same interface as Noun objects, they share some similarities. They have a string Text property and can serialize themselves using the same parameters as passed to Noun objects. They can be constructed with either an XML node or with values for the properties. Question objects are different from Noun objects, though, in that they have Yes and No properties of type IBorgElement.

C#

public   IBorgElement      Yes {
   get {return _yes;}
   set {_yes = value;}
}

public   IBorgElement      No {
   get {return _no;}
   set {_no = value;}
}

These properties are used by the App class to move through the decision tree to either the next question or a noun, depending on the user input.

App Class

The Question and Noun objects are just smart buckets for data, with limited active functionality. The App class does the work of playing the game.

It first validates input, and makes some assumptions about the database ("collective" in Borg terminology) you want to use. It loads the file and passes the first question (the first XmlNode below the root) to the constructor of the root Question. That constructor parses the Question node and passes the Yes and No XmlNodes to Question or Noun constructors, depending on the name of the node. Questions are recursively constructed until Noun XML nodes end the new object creation.

Once the hierarchy is fully constructed, the App class asks the first question. It solicits an answer by passing control to a function that waits until the user has entered a "Y" or a "N":

C#

private static YesNoAnswer SolicitAnswer(string question, 
                                    ConsoleEx.Colour colour) {
   string answer  = string.Empty;

   // Keep prompting until the user presses "y" or "n"
   do {
      ConsoleEx.Write(question + " (y/n) ", colour);
      answer = ConsoleEx.ReadLine(ConsoleEx.Colour.Green); // User input in green.
   } while (answer.ToLower() != "n" && answer.ToLower() != "y");

   return (answer == "y" ? YesNoAnswer.Yes : YesNoAnswer.No);
}

Once the question is answered, App checks the type of the Yes or No IBorgElement object. If it's a Question object, it sets the current pointer to the new Question object and starts the process again. If the IBorgElement object is a Noun object, it launches into a new set of logic.

The App class asks the user if the noun they were thinking of was the Noun in the final object. If it was, the game pats itself on the back and checks to see if the user wants to play again. If the noun was not guessed correctly, the application asks for the noun the user picked. It then solicits a question that answers Yes to the old noun, and No to the new noun. This question is solicited in a deliberate way, because the application is going to put the old noun on the No side of the new question and the new noun on the Yes side of the new question. If the new question is phrased incorrectly, the answers will be switched the next time the question is hit.

Once the App class knows the old and new noun and the question that distinguishes them, it creates a new Question object with the Yes and No IBorgElement nodes set to the new and old nouns, respectively. It puts the new Question object back where the old noun was in the object hierarchy, and persists the data. Refer back to Image 2 for a graphical representation of this if you want.

The data is persisted by creating a new XmlDocument object with a dummy root ("Database" node), and passing it to the root Question object serialization routine.

C#

private static void SaveDatabase(IBorgElement data, string fileName) {
   XmlDocument doc = new XmlDocument();

   // Initialize the Xml document with the root node.
   doc.AppendChild(doc.CreateNode(XmlNodeType.Element, 
                   App.ROOT_NODE_NAME, string.Empty));

   data.Serialize(doc, doc.SelectSingleNode(App.ROOT_NODE_NAME));
   doc.Save(fileName);
}

App.ROOT_NODE_NAME is the name of the root node, "Database". The Question object serializes itself into the new XmlDocument at the root node, and starts serializing the Yes and No properties. This will force all of the objects in the hierarchy to create XmlNodes for themselves in the master document, and gives a complete representation of the knowledge tree with the new question and answer.

C#

void Borg.IBorgElement.Serialize(XmlDocument doc, XmlNode node) {
   XmlNode        question = doc.CreateNode(XmlNodeType.Element, 
                               Question.NodeName, string.Empty);
   XmlAttribute   text     = doc.CreateAttribute(string.Empty, 
                               Question.TEXT_ATTRIBUTE_NAME, string.Empty);

   text.InnerText = _text;
   // Append the Text attribute to the new Question node.
   question.Attributes.Append(text);

   XmlNode  yesNode  = doc.CreateNode(XmlNodeType.Element, 
                           Question.YES_NODE_NAME, string.Empty);
   XmlNode  noNode   = doc.CreateNode(XmlNodeType.Element, 
                           Question.NO_NODE_NAME,  string.Empty);

   _yes.Serialize(doc, yesNode);    // Serialize whatever's on the "Yes" side.
   _no.Serialize(doc, noNode);      // Serialize whatever's on the "No" side.

   question.AppendChild(yesNode);   // Append the Yes node to the Question node
   question.AppendChild(noNode);    // Append the No node to the Question node

   // Append the Question node to where
   // it goes in the master document.
   node.AppendChild(question);
}

The resulting XmlDocument gets saved over the old one, and the game asks if the user wants to play again.

Window Dressing

I realize not everyone will want to start with my root question ("Is it alive") with my super-creative nouns. I also realize that creating initial XML documents to serve as the database is a tedious and error prone process. The App class allows you to create your own seed databases by running the application with some command line switches. If you run with four parameters, and those parameters are /db:, /question:, /yes: and /no:, you can have it create your own root database. The order of the parameters does not matter.

borg /db:"c:\birds.xml" /question:"Does it fly" /yes:"sparrow" /no:"penguin"

That command line will create a new database in the root of c:\ called birds.xml, seeded with the initial question and nouns as specified, and will open it for running (if it was created successfully). Sorry about the animal bias in the examples, but my degree is in Zoology...

Conclusion

You can see that the Sith game exploits the same sort of engine, but with a larger number of directions to travel in from each question. Instead of "yes" and "no", the Sith game allows for a multitude of options. Limiting the choices to "Yes" and "No" as I have done here appeals to my logical, binary side, and results in less ambiguity in the data relationships generated. Not coincidentally, it is also much easier to code.

Points of Interest

Back in the Day...

Back before the Internet, USB and diskettes, back when only rich kids had 300 baud modems (when dinosaurs ruled the earth), nerds had limited access to application sharing mechanisms. I had to type the source code for the original game myself from a magazine, before I could save it to my cassette drive. You really had to pick interesting programs before you typed them in, because it was a major investment of time to bang out the source code for an application, and debug the inevitable typos. It's probably why I remember playing this game so clearly. All on a 32X16 screen. Good times...

Console Colour

I've been on a console app writing kick lately, and am interested in making it easier for myself and others to write decent interfaces for the console. I put some code in to do colour output here, and am writing a comprehensive library for console manipulation. A small subset of the code is included in this project in the ConsoleEx class.

Serialization

Each of the objects I've written know how to serialize and deserialize themselves. I know a lot of people who detest doing this, and prefer to decorate classes with the [Serializable] attribute, and let the framework deal with this. I've tried to do serialization and deserialization automagically with the framework often enough to come to hate it, though. For the sake of a little extra code, you gain an incredible amount of flexibility in processing, so I create and parse XML documents myself. Don't get sloppy when you're handling XmlNodes and attributes and the like in your [de]serialiation code and start fiddling with your objects as string data. Only use real XML objects, and you won't be caught up when some user starts sticking angle brackets and ampersands into their data.

Additionally, you can throw really accurate, context sensitive exceptions if there are errors in the document you're parsing to help people diagnose their problem with input files.

Use of App.Config

Putting your run-time settings into App.Config is a well known shortcut, and allows you to reduce a small amount of XML parsing into an even smaller amount of code and read your settings like this:

C#

Copy Code

fileName = 
  System.Configuration.ConfigurationSettings.AppSettings.Get("LastDBPath");

What it is not supposed to be used for, evidently, is re-writing those same settings. There are lots of people on the net who strongly advise against this, as the application folder (where the App.Config resides) may not be writable by the application for security purposes. The framework is prejudiced against this concept too, since it lets you read but not write to this file.

I specifically wrote XML parsing code in this project to update the App.Config at run-time, going against the best practice. I wanted to save the path to the last database successfully loaded, so the end-user wouldn't have to specify the path on the command line every time. They only have to specify it if they're changing databases.

If you want to save a tiny bit of data between program executions, what are you supposed to do? Registry, I guess, but it's fraught with its own security perils. INI files? I'm not going back there. What happened to XCOPY deployment? You can't do it if you're copying config files all over the hard drive...

New Console Pattern

A strategy I like to use when I write console applications is to put long stretches of boilerplate text into embedded resources in the executable, and stream them out at run-time when I need to show them. Good candidates for this technique are command line switch parameters and instructions for what to do once the application is running, as I have done in this project. The files CLIText.txt and Instructions.txt are both embedded into the executable and are displayed when necessary by calling the following function:

C#

Copy Code

private static string ReadResource(string resource) {
   Assembly       me    = Assembly.GetExecutingAssembly();
   string         res   = me.GetName().Name + "." + resource;
   StreamReader   sr    = new StreamReader(me.GetManifestResourceStream(res));
   string         data  = sr.ReadToEnd();
   sr.Close();

   return data;
}

Doing this avoids a lot of messy and hard-to-edit System.Console.WriteLine() calls at the start of the Main() method.

Post Build

Just by way of warning, the project uses a post-build step to copy the Borg.xml file from the project folder into the run-time folder, so if you run the app repeatedly in the IDE, any facts you add to the database will get overwritten on the next compile.

Horn Honking

Last but not least, to parse the command line parameters here, I use my Yet Another Command Line Argument Parser (YACLAP) library.