Monday, 25 February 2008

The challenges of a natural query engine


Thanks to the people who have given me feedback on the natural conversation engine in flash prototype that I put up online last week. It has been interesting to discover what people's thoughts on this have been, so I figured a follow up article is really required. Note that I'm now calling it a natural query engine and not a natural conversation engine; I have a different use for it in mind than I originally did (more on this later).

  • The first challenge : Accuracy

As the engine, on a basic level, analyses what the player has keyed in and tries to deliver an appropriate response, the most obvious was of achieving this is to use keywords on the responses. This is an incredibly basic, but somewhat effective, way of delivering responses but it has a number of large flaws. The biggest of which is that the player must know (or guess) what they keywords are, in order to get the responses out of the engine's database. If the player cannot do this, then he will get frustrated pretty quickly and move onto something else. That got me thinking about using word synonyms. Synonyms help solve this, but bring with them their own issues. Word can have multiple meanings, so synonym lookups can be very wide.

Keywords are very narrow, but synonyms are very wide.

Somewhere within that band is the correct meaning of the sentence that the player has keyed in. In the analysis for that, we need to throw away lots of common words (such as "a", "the", "there") as they will not be too relevant to the keyword searching. Although, at some point if I need to get the engine to recognise nouns, these words may come in handy.

A second problem with accuracy is word endings. For example, the engine has to understand plurals, case endings and so on. The keyword transform should match the keyword entry transformation or our search is not wide enough to pick up on what to a human is an obvious hit. The engine generates multiple variations of words by looking for common word endings and creating new potential matches by joining them onto the base stem of the word. This approach will match transformation with transform (note this is only an example, there is no keyword transform in the prototype).


  • The second challenge : Sequencing

The engine has a number of topics that are in its database. Within each of these topics are a number of responses that the engine can deliver, but each topic has a single entry point. For example, asking the character where he is from will deliver a short response about that. The player can then query further into that topic because the entry point to the topic unlocks other responses. This prevents the engine matching the player's response with something that hasn't even come up in the conversation yet. I also lock responses that the player has accessed, as pretty early on I realised that if the engine keeps delivering the same response to the player, it looks pretty stupid pretty quickly.

  • The third challenge : Context

This is something that I have put into the engine more recently. I'm evolving the engine daily and trying to make up for its shortcomings and getting it to understand context has helped this tremendously. Essentially, when the player has triggered a topic, any other responses within the topic that are unlocked will get top priority for selection. This is making a big assumption - that the player is likely to continue talking about this topic, which seems to be generally what happens. It definitely stops the engine from looking so dumb when it matches the player input with a totally different topic, yet the player was clearly continuing the same subject. I'd definitely like some feedback on this aspect as it's new in the protoype.

  • The fourth challenge: Richness

By richness, I'm referring to how much rich the knowledge the system has is. No matter how smart the code gets, it's using a rule system to select a response from a database and so the end experience is only as good as the database is. If there simply are no response for the input that the player has entered, then the whole thing will look dumb. I have some ideas of how to populate this (I'm using them already in then engine) and I plan on blogging about this at a later point.

At the moment, I'm building up general character background traits and this is essentially what the engine is searching. However, this would be only one layer in an actual game. A second layer would be things that every character would know, such as facts about the world, the time of day, what the weather is and so on. A third layer would be an emotional state layer (note, I model one emotion only at present - a general annoyance level which allows the other character to terminate the conversation if he gets fed up) which would add a lot to the believability of the interaction, I feel. A fourth layer would be specifics that only that character would know, such as a barkeeper with his problem with rats.

Use for an engine like this

I'm not thinking of replacing a conversation tree with this engine, but I am thinking about supplementing a conversation tree with the natural query engine. This will allow players to deviate from the limited selections in the tree and allow them to query the character on basically anything (providing the engine can match an appropriate response from the input to the database, of course). This, to me anyway, would be a step closer to real roleplaying. One of the things I really love about the game Mass Effect is how the characters in the game feel more rounded out than in other roleplay games I have played, but I'm still constricted by a limited tree to do this. I can't ask the characters about what their favourite food is, for example, and generally fool around in that possibility space. Utilising a natural query engine with a conversation tree opens all of that up...

In addition, a natural query engine could be used to reward the player. Hints and tips could be present for problems in the game, within this. So, if a player gets stuck, he may return to a character in the game and ask for help or more information. Not putting that kind of information in the conversation tree would be controversial for some, but more natural for others. After all, we don't want to give the player help when he doesn't need it, we can hold her hand but we don't want to treat her like an idiot.

The prototype
Try out the prototype here. I'm very interested in any feedback or comments you may have.

Thursday, 21 February 2008

Natural language conversations in Flash


I've been working on a role-play engine in Flash and thinking a lot about how to interact with characters within a role-play game. 

I'll rewind somewhat and put this in context. Back in my old school days, I used to play AD&D with a group of friends. I was normally the DM, the guy who designed the quests and took on the role of the monsters and other characters that the heroes would interact with. This was great fun, and led to some memorable scenes that even today, over a decade later, we will still sometimes discuss fondly. So why have those imaginary experiences stood the test of time within this group of old friends?

I believe that part of the reason is that, being an intelligent human being, I could react to their interactions with the characters in the adventures in a believable way. I had to improvise a lot, going off-script, and inventing back stories as we played. Now computer based role-play games do not really try and tackle this tricky problem in a believable way. Probably the best, most believable characters I have come across are in the computer game Mass Effect, which (like the classic Baldurs Gate series and numerous other RPGs) use conversation trees. Now these work well, but you cannot stray from the possible options that the game's designers have come up with and so when you run out of possibilities (or just want to say something else that hasn't been scripted), well, um, you can't - it's just a game. So there isn't too much role-playing actually going on in computer based role-play games, unless you involve real people like MMRPGs do, but then again, I don't think too many people are staying in character in those games. Correct me if I'm wrong.

So this brings me back to single player games and how conversation trees are good but don't really allow you much freedom. In discussing this with a work colleague a while ago, he alerted me to an old Ultima game that would allow you to free type keywords in to the characters. This (and the excellent Facade  AI demo) got me thinking about the possibilities of this approach. Of course, the problem with this is that you have to know the keywords which will trigger the correct reactions in the NPC's, but this can be solved by involving synonyms and also if you know the issue of second time around playing, where if you know the keyword you can get the correct response right away (my colleague gave the example of a grappling hook that you needed to scale a wall, when you know this, you just said grapple to the NPC and he gave it you right away whether or not you'd even discussed it with him), but this is solvable using an unlock list on the topics themselves.

So here is the results of about four days work in experimenting with this approach. V1.1 of my demo is available here. It is extremely basic; there is no preloader (wait a few seconds and something will actually appear). Type in the light grey box and click the dark grey box to send your query. Treat it as a query engine, where you can ask the character various things. I'd love to solicit feedback on this, so if you have any thoughts, feel free to share them.