Marketing Interactive Art In The Age Of Video Games

Posted on October 31, 2013 by Scott

In honor of Halloween I took a break from writing about chatbots and bought a copy of Amnesia: A Machine For Pigs. It tells the story of a man with severe memory problems (hey, that’s half the title) who, pre-memory loss, invented an automatic pig slaughtering machine (hey, that’s the other half of the title). This poor man then has to explore his own creepy, blood-stained factory while being haunted by his own memories and the piercing squeals of some horrible monster.

And let me tell you, it is a wonderful and terrifying… whatever it is. If you’re a fan of slow paced psychological horror with a touch of cosmic dread thrown in I highly recommend it. It starts out as a simple tale about a butcher looking for his memories but the scope and the horror of the story just keeps growing and becoming more epic until… well, I’m not going to spoil anything here.

Don’t want to go down that hall. Don’t want to go down that hall. Don’t want to go down that hall!

But as much as I enjoyed A Machine For Pigs I’m not sure exactly what to label it. “Video game” seems like the obvious choice since it’s full of video game stuff like fully explorable 3D environments, first person camera angels and a physics engine that lets you throw things about with wild abandon. I mean, how can something with an interactive pool table not be considered a game?

On the other hand “game” suggests rules and challenges and most of A Machine For Pigs was just linear exploration of a big curving path. Explore a creepy room (so creepy!), read a few journal fragments (so cryptic!), jiggle all the locks and then leave through the only door that opens. Walk down a hallway and do it all again in the next room. Maybe once an hour you’ll be asked to spend a few seconds avoiding a monster or sliding an item into a nearby slot but for the most part you’re having an experience more than you’re playing a game. A wonderful, epic, terrifying and yet morbidly beautiful experience that uses game technology to create a story that couldn’t be told in film or writing, but still not exactly a terribly gamey experience. It would probably be more accurate to call the thing “Interactive Art”.

Now I’m not saying that A Machine For Pigs doesn’t deserve to be called a video game. Like I said earlier, it has an interactive physics engine: They can call it a game if they want. But from a marketing perspective I think they might have had more success if they had invented a new term.

See, based on what I’ve heard from the online gaming community almost everybody that “played” A Machine For Pigs really really liked the horror story and atmosphere. But a huge number of players were also really disappointed at the way it dropped almost all of the game elements found in the original Amnesia.

So the problem wasn’t that the product was bad. The problem was that it wasn’t what people expected from something labeled a “horror game” and an “Amnesia sequel”. For them A Machine For Pigs was like buying a carton of chocolate ice cream and finding out it’s actually filled with mint. Nothing wrong with mint, but it might have been better to admit that’s what it was right on the lid.

Now to be honest I’m not sure how this problem could have been avoided. Looking back at their marketing materials they actually claimed to be “exploring the outer reaches of what games can be” which is a pretty honest way to admit that A Machine For Pigs probably wasn’t going to be a traditional survival horror experience. They even specifically advertised that the product was driven by story and exploration more than anything else.

But they also used the word “game” and that is a powerful word with inescapable connotations. It easily overpowered all the disclaimers and promises of a story and drove people to expect certain types and amounts of game play. It’s the unspoken contract between gamer and developer. And while I don’t mind too much when developers break the contract to develop new types of stories I can understand why it leaves some people feelingly subtly annoyed, even betrayed.

But what can you do? Interactive art has always been sort of a niche product: Too gamey for people in the mood for a film or book while not being gamey enough for someone in a genuine gaming mood. You’ve got to find those weird people who are in an in-between mood. So no matter what the developers labeled their game/experience/interactive story they probably would have attracted some of the wrong customers and scared away some of the right customers. That’s just the sad reality of marketing for any semi-unique product that falls into the gap between the words we’re used to using.

But if you are a gamer who doesn’t always have to be gaming or a movie fan who occasionally thirst for a little more immersion… why not pick up A Machine For Pigs?

Happy Halloween.

Let’s Program A Chatbot 6: Don’t Fear The Regex

Posted on October 26, 2013 by Scott

Demystifying Regular Expressions

The time has finally come to talk about the regular expressions that I’ve been using for the pattern matching part of this pattern matching chatbot. Regular expressions are just a special way to describe patterns of symbols. A regular expression engine, like the one inside Perl, can then compare strings and text to a regular expression and figure out whether they match that pattern or not.

Although regular expressions are really useful they have a bad reputation as being hard to read and write. And to be honest it can be hard to remember all the dozens of rules involved in regex pattern matching. I personally would never dare write anything but the simplest of regex without a cheat sheet on hand.

Even more frustrating is the fact that “wrong” regular expressions don’t throw errors. They just don’t match what you expect them to match. And figuring out why they aren’t matching what you want can be difficult. The worst errors happen when your regex does match everything you want… but also matches things you don’t. So it looks like it’s working properly at first but if it ever comes across a false match your program will suddenly break and you won’t know why.

This is one reason I’m using test driven development for DELPHI. The automatic tests should catch most of my regex mistakes, so I don’t have to worry too much about forgetting a single character and breaking my entire program. The tests will also point out the mistakes as soon as I make them, letting me fix them while the code is still fresh in my mind and before forgetting what the broken regex was supposed to do.

So… Talking About Regular Expressions

I’m going to briefly briefly cover the bare minimum or regex knowledge you need to follow along with me as I program DELPHI. This is a probably a bad idea on my part. If you don’t understand regular expressions this won’t be nearly enough information to teach you how they work. And if you do know how regular expressions work this will be a boring reminder. I honestly should probably have just included a link to a real regular expression tutorial and left it at that.

Well, whatever. This is my Let’s Program. I can waste space talking about regular expressions if I want.

But before we go anywhere we need to cover how to mark a regular experesion in Perl. By default you create a regular expression by putting an ‘/’ symbol before and after the regex pattern you want, very similar to how you mark a string by putting double quotes before and after.

/understand?/

Boring And Simple

The most boring and simple use for regular expressions is to check whether or not a string contains a specific substring. Maybe you’re trying to find every sentence in a book that includes the word “inconceivable”* or are searching through a bunch of code for comments with a “TODO” reminder.

Searching for specific substring is really easy. You just type that substring up as a regex and you’re good to go. Example: /inconceivable/ and /TODO/.

Powerful And Complex

If the only thing regular expressions could do was find specific substrings there would be no reason to use them. We would just use the substring function that almost all languages already have. The real reason to use regular expressions is because of all the powerful tools they give you to find generic patterns instead of specific strings.

Now get ready for a whirlwind tour of the most useful and common regular expression special pattern techniques.

First up are the + and * symbols, which let you find a single symbol or phrase multiple times. So while /abc/ will only match “abc” you can create phrases like /ab+c/ that will match “abc”, “abbc”, “abbbc” and so on. ‘*’ works almost the same as ‘+” except that ‘*’ indicates an optional match. So /ab+c/ and /ab*c/ will both match “abc” and “abbc” but only /ab*c/ will match “ac”.

Next up are anchors, which let you mark when a specific phrase absolutely has to end up at the beginning or end of a string. \A means that the next symbol has to be at the very start while \z means that the previous symbol has to come at the very end.

For example: /\AWhy/ only matches sentences that start with the word “Why”. Having a “Why” in the middle isn’t enough. Similarly “/\?\z/” only matches sentences that end with a question mark. Note that in this case we have to type ‘\?’ instead of just ‘?’ because the plain question mark is actually a special regex symbol**.

Next I want to mention symbol groups and the wild card. These let you search for generic types of symbols instead of specific substrings. You can search for any one digit with [0-9]. You can search for any letter with [a-zA-Z]. Then there is the wildcard ‘.’ that matches just about anything except the newline character. So if you really want a number followed by a letter followed by at least one more something you could write /[0-9][a-zA-Z]./

The last thing I want to mention are parenthesis. Parenthesis let you group multiple other symbols together into one pattern. For example, suppose that you wanted to find sentences where the phrase “abc” repeats. Trying /abc+/ won’t work because that focuses on the ‘c’. It will match “abc” and “abcc” but not “abcabc”.

Instead you want to try something like /(abc)+/. Now the regex engine knows to look for a repeat of the entire group, not just the last word.

And of course you can mix all these things together. /\A(abc)+[0-9][0-9]/ will match with any string that starts with one ore more groupings of “abc” followed by two digits. So “abc11” and “abcabc45” but not “aabc11” or “abc123” or “123abc12”.

Capture Groups

Remember three mini-paragraphs ago*** when I talked about how you can use parenthesis to match entire groups of symbols? Well it turns out that parenthesis have a second purpose too: they set up capture groups.

Capture groups are important because they signal for the regex engine to not just find a match but also to save those matches for later. This is very useful for all sorts of reasons. For instance, it lets you build complex regular expressions that match the same phrase in multiple locations.

/([a-zA-Z]+) is \1/

The \1 means “the same as the first capture group in this regex”, so this pattern will match any string where the text on the left of the word ‘is’ exactly matches the text on the right of the word, like “A is A” or “Perl is Perl”.

But that’s not all capture groups can do. You can also ask the regex system to give a copy of the capture groups to your non-regex code. This lets you pull information out of text patterns and then use the full power of your programming language to interpret and manipulate it as much as you want.

Imagine you were writing a program that was supposed to read scientific papers, look for metric weights and then convert those weights to pounds for your American boss.

First you would use a regular expression to look for numbers followed by metric weights abbreviations (g, kg, mg, etc…). By wrapping this search into a capture group you could then pull those numbers into your program, convert them into pounds and then insert them back into the document.

The regex for this metric conversion system might include something like /([0-9]+)kg/. This pattern doesn’t just match the phrase “500kg”, it extracts the 500 and passes it back to our program. How does it pass it back? That depends on the system. In Perl a pattern with capture groups will store the captures in numeric variables. The first capture goes in $1, the second in $2, the third in $3 and so on.

You can also assign capture groups directly to an array like this:

@captureArray = ($string =~ /(regex) (with) (captures)/

You’ll notice that this is the method I use in DELPHI.

Speaking of DELPHI, capture groups are a key component to our chatbot. By using capture groups we can extract useful bits of the user’s original input and use them to customize the chatbot’s output and make it seem more human.

So when the user asks “Is regex awesome?” DELPHI doesn’t just answer “Yes/No”, it uses capture groups to grab “regex” and “awesome” and glues them together to create the intelligent answer: “Regex is awesome.”.

Dissecting A Regular Expression

Feeling a little more comfortable with regular expressions? No? Then let’s spend some time dissecting a regular expression symbol by symbol.

/\AWhy (.+)\?\z/

You might recognize this as one of the three basic rules that I programmed into DELPHI when first testing the response generating system. Now let’d look at it’s individual parts.

The regex starts with \AWhy . The ‘\A’ means that the pattern has to happen at the beginning of the string. The ‘Why’ just means the exact phrase ‘Why’. Together this means that this regex pattern only matches phrases that start with ‘Why’.

After that there is a blank space. This tells the regex to match an actual blank space. So this means that there has to be a space directly after the ‘Why’.

After the space we get to (.+). The wildcard matches anything and the plus sign means that we want to match at least one thing. So the idea here is that after the ‘Why ‘ we want to see at least one more symbol. After all, a good question should be “Why something?” not just plain “Why?”.**** We also wrap this bit in a capture group in case we want to further analyze the exact sort of why question the user was asking.

Finally we have /\?\z/, indicating that matching strings absolutely have to end with a question mark.

Add them together and this pattern more or less matches any sentence of the pattern “Why X?”. Things like “Why is the sky blue?” or “Why are we using regex?”. But it will not match things like “Why?” (which doesn’t have enough text after the Why). It also won’t match “Why is this wrong” (no question mark) or “I wonder why this is wrong?” (doesn’t start with Why).

Conclusion

Congratulations, you’ve survived an entire article about regular expressions. Hopefully you’re feeling ready for the next post of this Let’s Program where I start writing new regular expressions to help DELPHI react to new communication patterns.

* I do not think it means what you think it means

** ? in regex means “find the previous symbol zero or one times but never more than once”.

*** If you can’t remember something you read three paragraphs ago you may want to consider seeing a doctor about your short term memory problems.

**** On second thought, maybe we should have a response pattern specifically for plain “Why?”. Let’s see if you can figure out the regex for that before I officially add it to the bot.

Let’s Program A Chatbot 5: Finally, Code!

Posted on October 19, 2013 by Scott

When Perl != Perl

It just occurred to me that before I go any further I should probably mention that when I say I’m using “Perl” I mean Perl 5. More specifically, Perl 5 version 14 subversion 2 (5.14.2).

This is important because there is a major project called Perl 6 in the works that will change so many features of Perl that it could really be considered a new language instead of an upgrade. This means that Perl 5 code probably won’t work with a Perl 6 system.

So if you’re reading this in a Perl 6 dominated future be warned that you’ll also need Perl 5 if you want to follow along with my sample code. Or you could just rewrite all the sample code in Perl 6 as you read along.

Starting The Chatbot With generateResponse

We’re finally finished with all the design work, tests and background knowledge needed to really start the programming portion of this Let’s Program. So let’s get started!

The core of our system is going to be a function called “generateResponse”. It will be given strings representing user input and then generate a response based off of DELPHI’s pattern matching rules. It will then return this response to whatever piece of code called the “generateResponse” function in the first place.

Last post, as part of our test driven development, we created an empty “generateResponse” function for the testing software to talk to. Today’s goal is to fill that function in.

The Basics Of A Perl Function

One of the more unusual aspects of writing Perl functions is that you don’t have to explicitly list the arguments that will be passed to the function. Instead you are given the freedom to pass as many arguments as you want. Perl then packages those arguments into an array called “@_” for the function to use.

Here’s an example of what I mean:

In C you would define an addition function like this:

int add (int arg1, int arg2)
{
    return arg1 + arg2;
}

But in Perl you would do something more like this:

sub add{
    my $num1 = $_[0];
    my $num2 = $_[1];
    return num1 + num2;
}

or maybe even this

sub add{
    return $_[0] + $_[1];
}

Packaging arguments into an array allows for a lot of really cool tricks, like writing flexible functions that can sort or process unlimited numbers of arguments. But none of that really matters right now because “generateResponse” needs to be passed exactly one input. No flexibility needed (although it’s good to know that’s an option if we change our mind).

To function properly “generateResponse” will also need access to our list of DELPHI input patterns and response patterns. For now I’m just going to include those patterns inside of the function*. This will probably change later on, especially as the list starts getting bigger.

 sub generateResponse{
    my $userInput = $_[0];
    my @chatPatterns;

    $chatPatterns[0][0]=qr/\AIs ([a-zA-Z]+) (.+)\?\z/;
    $chatPatterns[0][1]="Fate indicates that UIF0 is UIF1";

    $chatPatterns[1][0]=qr/\AWhy (.+)\?\z/;
    $chatPatterns[1][1]="Because I said so";

    $chatPatterns[2][0]=qr/.*/;
    $chatPatterns[2][1]="I don't want to talk about that. Please ask me a question";

    #Pattern Processing Code Goes Here
}

Following along so far? We grab the string input argument with $_[0] and set up our array of regular expressions and output patterns. Don’t worry if the regular expressions still look like gibberish, I’ll go over it more in depth next time.

Looping And Comparing

We have the user input and the list of patterns to match. All that’s left to do is compare the input to the patterns until we find a match. Which makes this an obvious place for a foreach loop.

As for printing out the response, we actually already wrote code for that back in the experimental “Should we use Perl?” stage of this project. All it takes is a little modification for that code to fit perfectly.

sub generateResponse{
    my $userInput = $_[0];
    my @chatPatterns;

    $chatPatterns[0][0]=qr/\AIs ([a-zA-Z]+) (.+)\?\z/;
    $chatPatterns[0][1]="Fate indicates that UIF0 is UIF1";

    $chatPatterns[1][0]=qr/\AWhy (.+)\?\z/;
    $chatPatterns[1][1]="Because I said so";

    $chatPatterns[2][0]=qr/.*/;
    $chatPatterns[2][1]="I don't want to talk about that. Please ask me a question";

    foreach my $chatPattern (@chatPatterns){

        if(my @UIF = ($userInput =~ $chatPattern->[0])){
            my $response = $chatPattern->[1];
            for(my $i=0; $i<@UIF; $i++){
                my $find = "UIF$i";
                my $replace = $UIF[$i];
                $response =~ s/$find/$replace/g;
            }
            return $response;
        }
    }
    return "Base Case Failure Error!";
}

Let’s walk through this code really quick. The foreach grabs items out of the test pattern array and stores them in the $chatPattern variable. We then use an if-statement and the regex equals (=~) to try and match the regex pattern inside the first half of $chatPattern against the user’s input inside of $userInput.

If we don’t find a match then we start the loop over, grab the next pattern in the array and try again. If we go through the entire list without ever finding a match we warn the user that something has gone wrong since the pattern matching list should have at least one emergency base case that will match anything.

Things get a bit more complicated when there is a match. First, we pull some User Input Fragments of the input and place them in the @UIF array using some regular expression magic that I’ll cover in the next post. We then look for UIF keywords in our output pattern and replace them with the proper bits of user input. For example, if the output pattern has the string “UIF0” inside of it we replace it with the first entry in the @UIF array. This lets us create chatbot responses that include some of the same words as the user’s input. Once we’re finished searching and substituting we break out of the loop and return the now complete response string.

Breaking out of the loop is very important. Remember that DELPHI is supposed to use prioritized pattern matching to break ties. We can achieve this by placing high priority items near the beginning of our array and then stopping the pattern search the first time we find a match. This means that when an input matches more than one pattern it will naturally match against the highest priority pattern without ever even seeing the lower priority pattern it also would have matched.

The Sweet Smell of Successful Tests

Now that we’ve filled in generateResponse with some guts it’s time to run our tests…

Passed 2 out of 11 tests
Test Failure!!!

Two successes! More specifically the tests we are passing is the “nonsense” test and the basic “Yes/No” question test.

Input: Pumpkin mice word salad

Output: I don’t want to talk about that. Please ask me a question

Input: Is Perl a good choice for this program?

Output: Fate indicates that Perl is a good choice for this program

Anybody that was confused by the User Input Fragments idea during response generation should take a close look at the second test case. When the user asks DELPHI “Is Perl a good choice for this program?” their input gets split into fragments: “Perl” and “a good choice for this program”. We can then glue those into the output pattern of “Fate indicates that UIF0 is UIF1” to create an intelligent response of “Fate indicates that Perl is a good choice for this program”.

Conclusion

Believe it or not I’m now done with almost 50% of this project’s Perl code. Most of the real work on DELPHI will actually come from thinking up all the regular expressions that we’re going to use to pattern-match the user input.

Which is why next post is going to jump into regular expressions, analyzing the three rules I’ve already presented and writing one or two more.

* Bonus points** to anyone who can point out why declaring and populating a predictable array in the middle of a function that’s going to be called dozens or hundreds of times is a bad idea.

** Bonus points are not redeemable for cash or prizes and do not, in fact, exist.

Let’s Program A Chatbot 4: Let’s Talk About Test Driven Development

Posted on October 14, 2013 by Scott

Get it? Let’s “talk” about test driven development? Because we’re designing a chatbot. It’s funny*! Yes? No. Okay. Moving on.

What Is Test Driven Development?

Testing is the process of proving that a program can do what it is supposed to do without crashing or generating incorrect output. Good tests also help you find bugs in your programs before your users do. It is very embarrassing to deliver a piece of software that freezes your customer’s computer the first time they start it up. So testing is definitely important.

Software testing is an art unto itself, but the general idea is to come up with a list of sample program inputs that match what you expect real users to try. Then you figure out, by hand, what the program should do for each of those inputs. Finally you feed your inputs into the program one item at a time and double check that the computer does the right thing.

For example, suppose you are programming a bank calculator that figures out monthly payments for car loans. You set up your first test by talking to an accountant and finding out that a $10,000 loan should have a $300 monthly payment. So you feed $10,000 into the loan calculator and make sure it answers correctly. If it doesn’t generate the correct $300 payment then you know you have a bug.

Once you have run the test and fixed any bugs that show up you move on to your next test by talking to your accountant again and generating a new test case. Maybe your bank doesn’t give loans for more than $100,000 at a time so the calculator should return a “Too Large Loan” warning if the user asks for $150,000. So you go back to your calculator, plug in $150,000 and then make sure it prints the warning.

Then it’s back to your accountant, boss or customer for a few dozen more tests to run.

You might have noticed that this sounds really boring and tedious. Who wants to spend an hour feeding input into a program and then going over the output line by line looking for bugs? I don’t!

That’s where automated testing comes in. Instead of running your tests by hand you write a new test program that knows how to talk to your software. You then give your test input and expected output to the test program and let it run all the tests for you. It feeds the input to your program, checks the output for accuracy and then prints up a pretty report letting you know if there were any problems. You still have to come up with the tests on your own, but at least you don’t have to run them.

Automated testing can run thousands of tests with a single click. It’s easier than testing by hand. It’s faster than testing by hand. It’s more accurate than testing by hand. It’s much much less boring then testing by hand. The only real weakness is that it’s hard to automate UI testing or certain types of database driven programs.

You Still Haven’t Mentioned What Test Driven Development Is

Oh, right. My bad. I was having too much fun talking about automated software testing.

Test Driven Development is just the idea that you should setup your automated testing software before you start writing your actual program. You should then run your automated test at least once per day so you can keep track of exactly how much progress you’re making.

It is called “test driven” because the tests are the main driver and motivator of your software project. Your first goal is to write good tests and then the rest of your project focuses on writing code that can pass those tests. This is the opposite of code first development where your first goal is to write your program and only then do you start worrying about how to test it.

Of course, writing the tests before you write the software to be tested means that you are going to be seeing a lot of “errors” the first few times you run your tests. In fact, a test that doesn’t show 100% errors on a blank program probably has a few errors of its own**.

But the 100% error stage doesn’t last long. Once you know your testing software works you can start writing your actual program and before you know it you’ll pass your first use case and change from 100% failure to 1% success. And then you just keep writing and testing your software until the tests finally return zero errors. At that point you can feel very confident that your program really works, that you didn’t forget any features and that your code is as bug free as possible.

Why Would I Want To Use Test Driven Development?

Automatic tests sound cool, but why would anyone build the test before the thing to be tested? Isn’t that a little backwards? Why bother writing a test if you know it’s going to just return 100% failure? Although not a good fit for ALL programming tasks there are several advantages to starting with tests:

First, it lets you catch mistakes as soon as you make them. If your code used to have a 60% success rate but your latest “improvement” dropped that down to 40% then you know there is a big bug somewhere in your most recent code. This makes it easy to find and fix the bug because you only have a few dozen lines to examine. If you had waited to test until your program was “done” you would have had to search the entire code base to find that bug.

Second, writing tests is a good way to double check that your design document is complete. Imagine that you are writing a test to make sure that the program can handle negative numbers in the input. You flip to the design document to look up the “negative input” use case and realize that you forget to decide what should happen. Whoops! Better go back and discuss that with your manager / customer / alter-ego before you go any further.

Third, testing can help schedule your programing. Not sure exactly what to program next? Just find a test that is failing and write the code it needs to succeed.

Finally, test driven development can give you an emotional boost by letting you see progress as it happens. Sometimes in software we can spend weeks writing code without feeling like any progress is being made. This is especially bad if your boss also thinks progress isn’t being made. Having a set of automated tests lets you watch the completion rate climb with every new function and gives you something to show management. “Sure, the user interface is still incomplete but these tests show that we have made significant improvement in the invisible database layer.”

Tools For Tests

Testing software brings with it all the questions associated with normal software. Should you program your own testing suite or use an existing tool? Open source or proprietary? Do you need a powerful tool with all the bells and whistles or will a simple testing tool be enough? Do you want your testing tool to integrate with your programming environment or be a standalone program?

You get the idea. Lots of options to fit every coding scenario you run into.

As for this Let’s Program, we probably don’t need much power. DELPHI is going to be a very simple program that does nothing but listen to user input and then generate output. So instead of messing around with existing testing tools I’m just going to write my own mini-test. Shouldn’t take more than an hour.

The DELPHI Test Suite

As I mentioned, DELPHI only does one thing: process user text input and generate response text. So to test DELPHI all we need to do is come up with a list of sample input along with the DELPHI response we hope to get. Then we just cycle through all the input and raise a warning every time DELPHI says the wrong thing.

Doing the same thing again and again on slightly different pieces of data suggests our test program should involve some sort of loop. And for the sake of convenience it would be great if we could put all the test input and expected responses into a big list.

After thinking about that a little I came up with the idea of putting all of the input/response pairs into one big two dimensional array; basically a two column table where every row will be a different test. The first item in each row will be the sample input and the second item will be the expected response.

Now we can run all of our tests from inside of a single loop. I’ll be using a foreach loop that will run our test code once for every single row in our test array.

Inside the testing loop I will ask DELPHI to come up with a reply based on the input from the current test row. I’ll then compare that response to the expected response from the test row. If they’re the same I’ll tally up a success for DELPHI. If they’re different I’ll print a nice error message to the screen that lets me know which input failed, what response I was expecting and what DELPHI actually said.

With that background knowledge even a non-Perl programmer should be able to make sense of the following test code. A few Perl tricks to look out for though:

“use strict” tells the compiler to yell at me if I bend the rules. Without it Perl will let you get away with bad code. Ignoring strict is useful for quick experiments, but on a serious project you always want “use strict”
$ indicates a variable with only one value, like a number or string or an individual item in an array
@ indicates an entire array
You’ll notice that I create the array with the @ symbol and then switch to the singular $ syntax when filling it’s individual members with data. This is because individual array slots only have one value
In Perl strings and numbers have different comparison operators. ‘ne’ is the string version of ‘!=’
You might notice that within the for loop I access array values with $test->[0] instead of just $test[0]. This is because $test is actually a reference to an array instead of being a true array. Don’t worry about it too much.

With that Perl trivia out of the way here is Version 1.0 of the DELPHI Tester:

#! /usr/bin/perl -w

use strict;

my @testCases;

$testCases[0][0] = "Will this test pass?";
$testCases[0][1] = "I predict that this test will pass";

$testCases[1][0] = "Is the sky blue?";
$testCases[1][1] = "Fate indicates that the sky is blue";

$testCases[2][0] = "Does this program work?";
$testCases[2][1] = "Fate indicates that this program works";

$testCases[3][0] = "Do computers compute?";
$testCases[3][1] = "Fate indicates that computers compute";

$testCases[4][0] = "Do my readers enjoy this blog?";
$testCases[4][1] = "Fate indicates that your readers enjoy this blog";

$testCases[5][0] = "Is it better to be loved or feared?";
$testCases[5][1] = "Fate indicates the former";

$testCases[6][0] = "Why is natural language processing so hard?";
$testCases[6][1] = "Because of reasons";

$testCases[7][0] = "Pumpkin mice word salad?";
$testCases[7][1] = "I'm sorry, could you try rewording that?";

$testCases[8][0] = "Pumpkin mice word salad";
$testCases[8][1] = "I don't want to talk about that. Please ask me a question";

$testCases[9][0] = "Why do you say things like that";
$testCases[9][1] = "Did you forget a question mark? Grammar is important!";

my $testCount=0;
my $successCount=0;

foreach my $test (@testCases){
    my $output = generateResponse($test->[0]);
    if( $output ne $test->[1] ){
        print "Test Case $testCount Failed!!!\n";
        print "Input: ".$test->[0]."\n";
        print "Output: $output\n";
        print "Expected: ".$test->[1]."\n";
    }
    else{
        print "Test Case $testCount Passed\n";
        $successCount++;
    }

    $testCount++;
}

print "--------------------";
print "\n";
print "Passed $successCount out of $testCount tests\n";
if($testCount == $successCount){
    print "All Tests Passed!\n";
}
else{
    print "Test Failure!!!\n";
}

sub generateResponse{
    return "";
}

The ten test cases in this first test represent a pretty good sample of yes/no questions, either or questions, why questions and non-question input. I also tried to get a good mix of singular, plural, first person and third person questions. I’ll probably add a few more tests as the project continues and I realize new conversation patterns that need to be supported.

The First Run

Now that I have a test I should run it and make sure it works. Except that it obviously won’t.

Why not?

See that line inside the foreach loop where it asks for DELPHI to “generateResponse”? That function doesn’t exist yet so my test code won’t even compile.

The best way around this is to write a temporary place-holder function that will pretend to be DELPHI until we can write some actual DELPHI code. Place holder and prototype functions are the only bits of code you are allowed to write before your tests in Test Driven Development. For example, a test driven loan calculator would probably start out with an empty “caluculatePayment”.

Anyways, here is our DELPHI place holder.

sub generateResponse{
    return "";
}

This DELPHI dummy just responds with a blank string no matter what you say to it. Obviously worthless, but it gives the tests something to talk to and allows our code to compile. And now that the code compiles we can run our first test:

Test Case 0 Failed!!!

Input: Will this test pass?

Output:

Expected: I predict that this test will pass

Test Case 1 Failed!!!

Input: Is the sky blue?

Output:

Expected: Fate indicates that the sky is blue

Test Case 2 Failed!!!

Input: Does this program work?

Output:

Expected: Fate indicates that this program works

Test Case 3 Failed!!!

Input: Do computers compute?

Output:

Expected: Fate indicates that computers compute

Test Case 4 Failed!!!

Input: Do my readers enjoy this blog?

Output:

Expected: Fate indicates that your readers enjoy this blog

Test Case 5 Failed!!!

Input: Is it better to be loved or feared?

Output:

Expected: Fate indicates the former

Test Case 6 Failed!!!

Input: Why is natural language processing so hard?

Output:

Expected: Because of reasons

Test Case 7 Failed!!!

Input: Pumpkin mice word salad?

Output:

Expected: I’m sorry, could you try rewording that?

Test Case 8 Failed!!!

Input: Pumpkin mice word salad

Output:

Expected: I don’t want to talk about that. Please ask me a question

Test Case 9 Failed!!!

Input: Why do you say things like that

Output:

Expected: Did you forget a question mark? Grammar is important!

——————–

Passed 0 out of 10 tests

Test Failure!!!

We failed all the tests! Which means we succeeded! All those blank output lines show that the DELPHI placeholder is doing it’s job and the 100% failure rate means that our test code is correctly flagging mistakes for us.

Conclusion

Now that the testing framework is done the stage is set for starting to actually work on the chatbot. Finally, after four posts, we’re going to “Let’s Program A Chatbot” for real.

* Bad jokes are an important part of computer programming. If you can’t handle this you may want to consider a career in a different field. Like accounting.

** Yes, you have to test your test programs before using them. But please try to avoid falling into an infinite loop of testing the tests that test your tests for testing tests.

Let’s Program A Chatbot 3: Choosing A Programming Language

Posted on October 10, 2013 by Scott

How To Choose A Programming Language

Modern programming languages are 99% interchangeable. If you can do something in C you can also do it in Java, Lisp, Visual Basic, Python and so on. There are very few scenarios where you absolutely “need” to use a specific language.

But that doesn’t change the fact that every language has strengths and weaknesses. A program that would be difficult to write in Java might be easy to write in Python. A program that runs slow in Lisp might be easy to optimize in C.

But the language’s strengths and weaknesses aren’t the only thing you need to think about when starting a project. You, as a programmer, have strengths and weaknesses too. If you have ten years of experience with C++ but have never touched Ruby then odds are you should stick to C++, especially if you have a deadline coming up and can’t spare the time to learn a new language*.

So when trying to choose a programming language you need to ask yourself three questions:

How well does this language match my problem?
How comfortable am I with this language?
How much time can I spare for learning new language features?

Sometimes you get lucky and find out that your favorite language is a perfect match for the problem you need to solve. Hooray!

But other times you’ll have to make a tough choice between a familiar language you know you can *eventually* succeed with and a less familiar language that has some really great features that would instantly solve all your problems if you could just get your code to stop throwing weird errors.

And sometimes the choice is so hard you just give up, eat a gallon of ice cream and decide to join an isolated community where computers are illegal and speaking jargon is punishable by death.

Perl: A Good Pattern Matching Language

With all that theory out of the way we can move on to choosing a language for our chatbot. Since our chatbot is going to be based primarily off of pattern matching we’re going to want a programming language that makes matching patterns easy. And pattern matching should make you think of regular expressions**. And regular expressions should make you think of Perl.

I can see a few of you getting a little nervous. Doesn’t Perl have a reputation for being a hard to read language? And aren’t regular expressions famous for causing more problems than they solve? Weren’t we supposed to choose a language we feel comfortable with?

Well don’t worry. I use both Perl and regular expressions at work and while I’m no guru I can at least get my code to work 9 times out of 10. Furthermore, I promise to write clean code and will do my best to avoid the Perl code shortcuts that are responsible for making it hard for newcomers to understand.

Side note: Although Perl and regular expressions work together really well I should point out that you can also use regular expressions with other languages. In fact, most languages have either built in support for regular expressions or easy to find regex libraries.

So if you like C# you can regex in C#. If you’re a Java guy you can regex in Java. Just because I chose Perl for my chatbot doesn’t mean you have to. In fact, porting my chatbot to your favorite language might be a fun exercise for beginning programmers looking for a challenge.

Although I suppose I’ll have to actually write this thing before anybody can port anything.

Proof of Concept: Can We Really Perl Up A Chatbot?

On paper Perl looks a really good pattern matching chatbot language. It has built in support for regular expressions, tons of text processing functions and cross platform support makes it easy to share code with other people (like you, my wonderful readers).

But I still feel a little twinge of doubt. Is this really a good idea? I figure the best way to find out is to write some Perl and see if I can make it do what I want.

Spoilers: The answer is yes. You can now safely skip to the next post without missing anything. But if you want to see the tests I hacked together to prove this, feel free to read on. Just don’t be surprised if the code is hard to follow. This isn’t production code or even reader education code, just a quick and sloppy experiment.

Test 1: Pattern Matching And Response Generation… in Perl

The core feature of our chatbot will be the ability to check whether or not the user’s input matches a specific pattern and then build an appropriate response. So that seems like the most logical thing to test first. And so here is my first test:

#! /usr/bin/perl

$testInput = "Is Perl a good choice for this program?";

if($testInput =~ /\AIs ([a-zA-Z]+) (.+)\?\z/){
   print "DELPHI: Fate confirms that $1 is $2\n";
}
else{
   print "Didn't work\n";
}

This also marks the first bit of code in the Let’s Program and OH MY WHAT IS WRONG THAT IF STATEMENT!?

Well, wonderful reader, that if statement happens to be a regular expression. I’ll talk about those more later on. For now just trust me when I say that that bizarre list of characters and symbols translates to “Match a sentence that begins with ‘Is’, ends with ‘?’ and has at least two words in between them”.

That regular expression also gives us a copy of the words that it found between the ‘Is’ and ‘?’, which we then slip into the output. That’s what the symbols $1 and $2 are doing.

Don’t worry if that didn’t make sense. This is just a test. I’ll explain things more in depth when I start actually programming the chatbot. For now the important thing is that running this program produces this output:

DELPHI: Fate confirms that Perl is a good choice for this program

Test 1 is a success. We managed to write Perl code that matched user input and transformed it into an appropriate chatbot response.

Test 2: Can We Make A List Of Regular Expressions… In Perl?

Now we know that Perl can help us match user input to one pattern. But for our chatbot we’re going to need to try and match the user’s input against at least a dozen different patterns. Is there an easy way to do this or is our program going to turn into a giant pile of if and elsif? Time to find out:

#! /usr/bin/perl

$testInput = "Is Perl a good choice for this program?";
$testInput2 = "Why is Perl a good choice for this program?";

$inputPatterns[0]=qr/\AIs ([a-zA-Z]+) (.+)\?\z/;
$inputPatterns[1]=qr/\AWhy (.+)\?\z/;

if($testInput =~ $inputPatterns[0]){
   print "DELPHI: Fate confirms that $1 is $2\n";
}
else{
   print "Didn't work\n";
}

if($testInput2 =~ $inputPatterns[1]){
   print "DELPHI: Because I said so\n";
}

if($testInput1 =~ $inputPatterns[1]){
   print "This shouldn't match!\n";
}

if($testInput2 =~ $inputPatterns[0]){
   print "This shouldn't match either!\n";
}

Once again, don’t worry if you didn’t catch all that. In this test I basically just stored the regular expressions inside an array instead of writing them directly inside of the if statements. If this works then we can write our chatbot with a nice, clean pattern matching loop instead of endless if statements. But does it work?

DELPHI: Fate confirms that Perl is a good choice for this program
DELPHI: Because I said so

Success!

Test 3: Connecting Output Patterns To Input Patterns… In Perl!

Last test proved that we can move our regular expressions out of the if statements and into a nice, clean array. Can we do the same thing with our responses? Here goes nothing…

#! /usr/bin/perl

$testInput = "Is Perl a good choice for this program?";
$testInput2 = "Why is Perl a good choice for this program?";

$chatPatterns[0][0]=qr/\AIs ([a-zA-Z]+) (.+)\?\z/;
$chatPatterns[0][1]="DELPHI: Fate confirms that $1 is $2\n";

$chatPatterns[1][0]=qr/\AWhy (.+)\?\z/;
$chatPatterns[1][1]="DELPHI: Because I said so\n";

if($testInput =~ $chatPatterns[0][0]){
   print $chatPatterns[0][1]
}

if($testInput2 =~ $chatPatterns[1][0]){
   print $chatPatterns[1][1];
}

Which produces this output:

DELPHI: Fate confirms that is
DELPHI: Because I said so

Uh oh. Everything matched up properly but something went wrong with the response generation. I was actually expecting this. I want to build DELPHI’s responses using information from the user’s input, but the response array is being built before the user gets a chance to say anything.

So if I want to store response patterns in an array I’m going to need to add a little extra code in order to splice the user’s input into the response after it is pulled out of the array but before it gets printed to the screen. Hmm… let’s try this:

#! /usr/bin/perl

$testInput = "Is Perl a good choice for this program?";
$testInput2 = "Why is Perl a good choice for this program?";

$chatPatterns[0][0]=qr/\AIs ([a-zA-Z]+) (.+)\?\z/;
$chatPatterns[0][1]="DELPHI: Fate confirms that UIF0 is UIF1\n";

$chatPatterns[1][0]=qr/\AWhy (.+)\?\z/;
$chatPatterns[1][1]="DELPHI: Because I said so\n";

if(@UIF = ($testInput =~ $chatPatterns[0][0])){

   $response = $chatPatterns[0][1];
   for($i=0; $i<@UIF; $i++){
      $find = "UIF$i";
      $replace = $UIF[$i];
      $response =~ s/$find/$replace/g;
   }

print $response;
}

if(@UIF = ($testInput2 =~ $chatPatterns[1][0])){

   $response = $chatPatterns[1][1];
   for($i=0; $i<@UIF; $i++){
      $find = "UIF$i";
      $replace = $UIF[$i];
      $response =~ s/$find/$replace/g;
   }

print $response;
}

You’re still not allowed to panic, this is just a test. What I’ve basically done is change the code to generate a list of individual pieces from the original input (Which I call User Input Fragments or UIF). When a match is found the program uses a special type of regex to find every place that the input has a special UIF word and then replace it with data from the actual input.

Don’t look at me like that. I said I’ll explain it better later. Just wait one or two more posts. For now the important thing is that running my new test code produces this beautiful output:

DELPHI: Fate confirms that Perl is a good choice for this program
DELPHI: Because I said so

Success! I can store responses in an array right alongside the input patterns they are related to. This means that I can teach the chatbot new conversation tactics by just adding new patterns to the master array. No need to write new code!

Conclusion

Our test have all passed and the language of this Let’s Program is going to be Perl. With that final piece in place we can finally jump into some actual coding. Are you excited? I’m excited!

…

Please be excited.

* I once failed a mildly important college project because I decided it would be fun to code everything in a new language that I knew almost nothing about. By the time I realized I would have been better off sticking with a language I knew it was too late. Don’t let the same thing happen to you!

** Regular Expressions are a sort of miniature programming language that specialize in pattern matching. They are a powerful tool for all sorts of text analysis programs.

Let’s Program A Chatbot 2: Design Before You Code

Posted on October 9, 2013 by Scott

My Obsession With Design Documents

Design documents are an important part of writing software. How important? So important that Jesus used the software design process in one of his parables!

28: For which of you, intending to build a program, sitteth not down first, and counteth the requirements, whether he have sufficient time and skill to finish it?

29: Lest haply, after he hath written much code, and is not able to finish it, all that behold it begin to mock him,

30: Saying, This man began to code, and was not able to finish.

Luke 14:28-30

OK, I may have paraphrased that a bit. But you get the idea. The first step in a successful project is sitting down and deciding exactly what you’re trying to accomplish and then figuring out whether or not it is actually accomplishable.

Careful planning also gives you a chance to notice problems while they are still theoretical and easy to fix. Realizing that you need to add sound effects to a program that is 99% complete requires you to rewrite and debug painfully large amounts of code. But if you realize that you need sound effects during the planning stage you can naturally add them into the code as you work. Much easier.

Example: The Chatbot That Probably Would Have Never Been Finished

Now it’s time for a real life example of how good design documents made my life easier.

When I first started this Let’s Program the one big question was what exactly my chatbot should chat about. Usually when I can’t figure out a topic for a practice project I default to table-top fantasy gaming on the basis that most computer geeks have played Dungeons and Dragons, played a Dungeons and Dragons inspired computer game or at the very least seen a fantasy movie where people hit monsters with swords.

So my first idea was to create a chatbot that could help Dungeon Masters design new adventures. A chatbot that could talk about plot hooks and dungeons and even automatically generate treasure hordes and room descriptions.

And I was so excited by this idea that I was very tempted to just jump straight into playing with code. But I resisted the urge and spent some time doing a nice requirements write-up for all you lovely people in the audience. And during that write-up I realized that I didn’t have nearly enough free-time to build this thing.

Writing a pattern-matching bot that can intelligently talk about fantasy adventures was going to be hard. Programming functions for generating treasures and rooms was going to be tedious. And linking input patterns to function calls instead of output patterns was going to involve advanced coding techniques that I felt would unfairly draw attention away from the simple “chatbot” focus I had planned for this Let’s Program.

So I’m saving that project for a future date.* Thanks to the power of design documents I’ve avoided an embarrassingly ambitious project and you’ve been spared the pain of watching me fail.

Design Document 2: The Fortune Teller Chatbot That I Can Build

I’ve already thrown away one project for being too complex for a good example of introductory chatbot design. What am I going to do instead?

Well, I’m going to write a fortune teller. Where by “fortune teller” I actually mean “random guessing machine”. The basic idea is to create a chatbot that can recognize when it’s being asked a question and then makes a wild guess at what the answer should be. If the user doesn’t ask a question the chatbot will prompt them to do so.

I also plan to make the chatbot as goofy and sarcastic as possible. Not only because I enjoy funny computer programs but also because the humor will hopefully disguise the fact that the chatbot isn’t actually smart enough to know what’s going on. But I’ll talk about that more in the future when I get to the ELIZA effect.

I shall call the chatbot DELPHI because I was an extreme mythology geek in my youth.

UI Design

The user interface is one of the most important parts of a good design document. It should include mockups of every page on a website, every screen on an app and a clear explanation of what every single button should do. It should give you a good idea of everything the user will be able to do and everything they should expect to see.

A good UI design can take up a lot of space!

But this is a text based program so our UI Design will only take a couple paragraphs. What a relief!

Official UI Design: The user opens the program via the command line. The program will print a line prompting them to begin communication. The user is allowed to type text. After they hit enter the program will generate a new line of text that responds to the user’s input as relevantly as possible.

Computer output will be proceeded by the string “DELPHI: ”.

User input will be prompted by the ‘>’ symbol.

Program Interface Mockup:

DELPHI: Welcome! What soul searching questions have you brought me today?

>Will Scott post his next Let’s Program soon?

DELPHI: The stars say it is very unlikely that Scott will post his next Let’s Program soon.

>Why not?

DELPHI: Because space aliens are interfering with the astrological radiation from Jupiter.

> You’re making that up.

DELPHI: I sense you’re not being honest with me. What questions do you really have?

>Goodbye

DELPHI: Until next time

Use Cases

Use Cases rank right up there with thorough UI design when it comes to valuable software development tools. For those few of you who aren’t familiar with the technique the whole point of use cases is to come up with a big list of how you expect your users to user your program. Then you write down what the program should do.

So let’s consider a few of the major question types we expect to see.

Use Case 1: Yes/No Questions

The most obvious questions that a fortune teller will encounter are those that have a simple yes or no answer. Most of these inputs will start with the word “Will”, “Is” or “Do” and end with a question mark. Example:

Will I get a promotion?
Is my code bug free?
Do androids dream of electric sheep?

In this scenarios DELPHI should respond with a randomly chosen positive or negative answer that includes appropriate portions of the user’s question. Example:

The stars agree you will get a promotion.
Ether vibrations suggest it is impossible that your code is bug free.
Fate calculations show that androids dream of electric sheep.

Use Case 2: Why Why Why Why?

Another popular type of question is the “Why” question. As in “Why won’t my code compile?”, “Why is the sky blue?” or “Why won’t my toddler stop asking me why questions?”.

In these scenarios DELPHI should respond with a randomly chosen excuse. The list of possible explanations should be large enough that casual users don’t catch on that answers are being chosen randomly. Explanations might include:

Because of the alignment of the stars.
Because great Cthulhu is beginning to awaken.
I would tell you but it is a secret to everyone.
I used to know, but I forgot.

Use Case 3: A or B?

Users may ask DELPHI to choose between multiple options. This will be signified by the word “or” as seen in these sample inputs:

Should I buy a sports car or a motorcycle?
Do I want chocolate or strawberry ice cream?
Is that a moon or a space station?

In these cases DELPHI should generate a response that randomly agrees with the first or second option. By actually using the words first and second DELPHI will not need to actually include information from the original post. Consider these sample responses:

I've got a good feeling about the first one.
My prognostication engine suggests the later.
Definitely the former... assuming you trust Saturn.

Use Case 4: Goodbye

If the user types “Goodbye” the program will exit.

Default Use Case

It is very very likely that users will say things that do not fit any of our specific use cases. Especially if the user decides to not actually ask a question. In these scenarios DELPHI should generate a random response that urges the user to try again with a question. Possible responses might include:

Chatting is nice, but please ask me question instead.
I'm bored. Go ahead, ask me why I'm bored.
Sorry, I didn't hear you. What was you're question?

Conclusion

I feel like I have a really good grip on what DELPHI version 1.0 needs to do and I hope you do too. Which means the only thing standing between us and some actual programing is choosing an implementation language.

Three guesses what my next post is going to be about.

* Possibly after a zombie apocalypse has left me trapped in my own basement with nothing but months of bleak free time ahead of me.

Let’s Program A Chatbot 1: Introduction And Theory

Posted on October 7, 2013 by Scott

What Is Let’s Program?

You’ve probably heard of “Let’s Play”, where someone plays a videogame and then posts their experience online. There are usually plenty of screen-shots or even videos with the player’s voice dubbed over the game.

They can be a lot of fun.

This has inspired me to try and create the first (that I know of) “Let’s Program”. I am going to write a program and blog about the process. There will be code samples and screen-shots. (UPDATE: A few months after writing this I stumbled upon a bunch of older coding blogs with titles like “Let’s Code” which just goes to show that no matter how much online research you’ve done for your “original idea” you probably still haven’t done enough)

I can hear your complaints already. “Scott,” you hypothetically ask, “How is this any different from the thousands of other code tutorials online like that handy MongoDB series you wrote last month?”

Good question. “Let’s Program” is different because it’s going to be much less formal than a normal tutorial. Also, I’m calling it something different. That’s two whole differences! More than enough for != to return true.

Sure, you might argue otherwise… but you’re on the other side of the Internet and I can’t hear you. Take that hypothetical complaining reader!

Anyways, let’s get things started!

Chatbots A.K.A. How To Make Friends And Imitate People

A chatbot is a program that simulates human conversation. Usually typed conversation. For example, here is a sample of someone interacting with ELIZA, a classic program that pretends to be one of those annoying psychiatrists that does nothing but parrot back everything you say in the form of a question. The program is the one talking in all caps:

Men are all alike.

IN WHAT WAY?

They're always bugging us about something or other.

CAN YOU THINK OF A SPECIFIC EXAMPLE?

Well, my boyfriend made me come here.

YOUR BOYFRIEND MADE YOU COME HERE?

He says I'm depressed much of the time.

I AM SORRY TO HEAR YOU ARE DEPRESSED.

ELIZA is a little stiff but not obviously inhuman. Pretty good for a bunch of ones and zeros zipping through a chunk of silicon. My goal is to build something similar. Which shouldn’t be too hard since the creator of ELIZA was nice enough to publish a paper on how he did what he did.

How Do Chatbots Work?

There are tons of theoretical ways to simulate human conversation, but the most popular and widely used technique is simple pattern matching. If the user says X the computer says Y. If the user says A the computer says B. If the user says “I need a vacation” the computer says “Why do you need a vacation?”.

But that seems really tedious. If we need a different rule for every single thing the user might say we would have to program billions and billions of rules. Isn’t there a better way?

Yes there is! Instead of matching specific user inputs to specific computer responses we can just look for generic patterns. So instead of creating a rule for “I need a vacation”, “I need a sandwich”, “I need a nap” and so on we just create a single rule for “I need X”.

We use the same technique for generating computer responses. Instead of writing responses like “Why do you need a vaction?”, “Why do you need a sandwich?” and “Why do you need a nap?” we just write one response “Why do you need X?” where X is pulled straight out of the user’s original input.

Strengths And Weaknesses Of Pattern Matching Chatbots

There is one super huge advantage to pattern matching: it’s easy to program.

And that is a really huge advantage. A program isn’t good for anything until it actually works. A medium quality program that takes a month to develop is much more useful than a high quality program that is so complex that it never actually get’s completed.

But while pattern matching is probably the most pragmatic way to build a simple chatbot it does have a few downsides.

First, a simple pattern matching bot has no memory. You could build a pattern where the user says “My name is X” and the computer responds “Hello X”. But if the user’s next line was “What is my name?” there is no way for the computer to respond appropriately. The name variable X has already disappeared.

Second, pattern matching bots tend to panic when people don’t talk exactly like the program expects. If the user types “I really need a vacation” but the program only has an “I need X” pattern it won’t recognize the match. That extra word “really” breaks everything.

The same problem shows up with contractions. If the program is looking for “I can not” and the user types “I can’t” then we’ve got a problem.

Third, pattern matching bots aren’t smart enough to deal with context. As a human you know that there is a huge difference between the phrases “I am Scott” and “I am sleepy” but to a pattern matcher both of those sentences just look like “I am X”.

There are ways around most of these problems. For instance, with a little extra work you can give your bot the ability to remember simple facts like the user’s name and then use those facts as part of it’s pattern matching and responses. And you can fix the contraction problem by having the program expand “can’t” into “can not” before trying to find a matching pattern.

Pattern Matching Priority

There is one final trick to pattern matching chatbots that we need to think about. What if the user’s input matches two different patterns? Let’s imagine we have three rules:

“I feel sick” => “You should see a doctor.”

“I feel X” => “Why do you feel X?”

“I X” => “Is it always about you?”

Hopefully you can see that if the user types “I feel sick” it will match all three input patterns. How do we decide which response to use? The solution is to assign every pattern rule a priority. When user input matches more than one pattern we use the response from the highest priority rule.

In this situation we would probably decide that “I feel sick”, being a very specific rule, should get a higher priority than the more generic “I feel X”. And we would probably give the super-generic “I X” a very low priority since we only want to use it as a last resort when nothing else matches.

Now we can use these priorities to determine that the appropriate response to “I feel sick” is “You should see a doctor”. These priorities also help us figure out the right response to input like “I feel sad” (Why do you feel sad?) and “I don’t want to talk to you anymore.” (Is it always about you?).

Hey, I Found A Bunch OF Chatbot Programs Online! Why Write Another One?

One of the best way to get better at programming is to practice programming. Whether or not the final product is useful really doesn’t matter; the important part is what you learned during the development process.

It’s actually a lot like jogging. You spend thirty minutes running around the block only to wind up back where you started. What a waste! Except for the fact that all that “pointless” jogging is keeping your heart, lungs and legs healthy.

So no, this chatbot isn’t going to ever be used for anything important. But the process of writing it will hopefully help me and my readers to become better software developers.

Plus, programming is fun and I always wanted to be able to say “I wrote an AI capable of basic human speech”.

Conclusion

Tune in next time as I take this Let’s Program to the next level with some actual design documents outlining where I hope to take this program.

References

Finding a good book on chatbot design is surprisingly hard. I personally had the most luck with Paradigms of Artificial Intelligence Programming: Case Studies In Common Lisp by Peter Norvig.

Chapter 5 is an in-depth study of ELIZA, the ancestor of pretty much all pattern matching chatbots. Later chapters also tackle the much more difficult problem of natural language processing, which could be interesting to anyone who wants to go beyond simple chatbots and explore the heavy duty problems and techniques involved in getting a computer to really handle human language.

Plus it has a chapter on writing an advanced AI for playing Othello. And who doesn’t love boardgames?

One warning: This book is a little on the difficult side and is written in a very formal, academic tone that takes some getting used to. It also focuses entirely on the programming language Lisp, which (unfortunately) isn’t exactly super popular anymore.

So if the idea of learning an entire new language with some very unique syntax seems overwhelming you might want to pass on this particular book. But that’s where I learned the techniques I’m going to use in this Let’s Program so I felt I owed it to Mr. Norvig to mention his excellent book.