Sign in to follow this  
Wavinator

Compressing behavior into verbal descriptions

Recommended Posts

"The calvary left Fort Hood three days ago. They crossed the River Peldon amd headed north, where they met General Sanchez's forces and were decimated. The survivors retreated west, into Red Rock Range and we haven't heard from them since." What if this description was the basis of an autogenerated mission, given to you from an NPC, that was the result not of a scripted sequence, but of independent entities interacting on a map in a freeform fashion? How could the AI summarize and encapsulate agent behavior into verbal descriptions?
How about using a concept similar to RLE compression? In graphics processing, of say an image that's all black with a white square in the middle, you encapsulate the highlights. You might have a run of black that last X length, then white, then black, etc. Behavior might, in turn, be summarized by highlights. It's not the individual steps you took on a journey, or the repeat actions, but the sum of what you did. So if you're describing movement, you capture the legs of the journey and the important events along the way. But since even this can be too much detail, you set a limit of what you're willing to preserve in summarizing. Interactions (battles, trades, visits), for instance, get a high weight, as do arrivals at landmarks. Start destinations get a higher weighting, and final states (dead, fled, missing) get the highest weighting of all. When you're talking with an NPC, you can ask them to "unpack" the compression, giving you more detail. Let's say that NPCs are limited to only three or four highlights. In conversation, you can say, "Tell me about 'that battle with Sanchez.'" Then, the events could be described in even more detail.
From here, you could place filters on what they know, provide misinformation, rumor and bias. You might then be able to follow a trail of past interactions, from NPCs that must be dealt with in different ways. Thoughts?

Share this post


Link to post
Share on other sites
Quote:
Original post by Wavinator
"The calvary left Fort Hood three days ago. They crossed the River Peldon amd headed north, where they met General Sanchez's forces and were decimated. The survivors retreated west, into Red Rock Range and we haven't heard from them since."


What if this description was the basis of an autogenerated mission, given to you from an NPC, that was the result not of a scripted sequence, but of independent entities interacting on a map in a freeform fashion? How could the AI summarize and encapsulate agent behavior into verbal descriptions?

Thoughts?


I don't know, but I'm going to have to find out, because it's a problem that I need to solve to make my games eventually. [grin]

Well, actually, I do have some idea, because I have seen stuff like this before, it's just I'm feeling a bit too sick today to coherently remember all that stuff on language grammars that I learnt a couple of years ago, but since I don't really have the energy to do anything else for a while I'll see what I can dig up from my memory.

Share this post


Link to post
Share on other sites
Been thinking for a bit. One application which may be comparable is the automated generation of sports commentary. I've seen some stuff like this when I was involved with Robocup. I've found some work on an automated commentary on a project called RoCCo back in the nineties which may or may not be what you are looking for.

However, there must be heaps of stuff applicable to this area in the field of natural language generation. It's not really my field of expertise though. Maybe some of the A.I. guys can help?

Share this post


Link to post
Share on other sites
Hmmmm... Your idea of summarizing things as highlights could be a good one. To look at it a bit more programmerly, the important parts are the transitions or changes in state. "The cavalry left Fort Hood": Some object went from "fortified" to "moving". "They met General Sanchez's forces and were decimated": it interacted with another object. "The survivors retreated west into Red Rock Range": the object went into "retreat" mode and found itself a route to follow. "...and haven't been heard from since": No further contact between the object and whoever's doing the talking.

When you look at it like this, it seems like a pretty cool idea. Now I'm tempted to try to write a program to apply dialog like this to, Civilization or Master of Magic, to use your example of military action. However, it could probably be applied equally well to Nethack, Uplink, or Black and White...

Of course, now I'm thinking about about how the same fundamental rule applies to drinking games, so...

Share this post


Link to post
Share on other sites
I've researched quite a bit on this topic. Some of my ideas might be useful to you:

Movement has to be fairly abstracted, you don't want to record how many steps the character/party/whatever has walked in any direction, you only need to record its location when something happened. If it went through 3 towns with nothing happening there, it's not important. If in the third town there was a fight, it's recorded, so then you can say that it travelled from X to Y, where there was a fight.

Keep the events in chronological order, and assign each one a "weight" of how important it is. Simple movement is not that important, battles can have different importance depending on the strenght of the enemies, if anyone died or was severely injured in it (fighting the 100th common road thief is not very important when compared to an encounter with a dragon).

Now here's the meat of the whole thing: limit the events that the NPC talks about to only the 10 most important ones (this is a made up number). An epic voyage will focus on huge battles and how the hero defeated Sauron, not every little town he went through (unless the player asks for more). The story of a merchant going from one town to another will focus on more meaningless details. This is enforced by the "10 most important events" rule.

The player can ask for more details if he wishes: about specific points in the journey ("tell me more about -this- event" -- tell the 10 most important events within a '30-events radius' around that one), the whole thing in general ("tell me more" -- tell the 50 more important events of the whole story) or applying a filter disguised as a question ("did you meet a strange merchant wearing purple clothes?" -- look for an event that matches these criteria).

[Edited by - Jotaf on July 10, 2005 1:44:49 PM]

Share this post


Link to post
Share on other sites
This sort of thing sounds pretty good now, but feed it into a generator and you'll end up with this:

"The cavalry left Fort Hood three days ago. The cavalry returned to Fort Hood two days ago. The cavalry left Fort Hood yesterday. The cavalry traveled west for three miles. The cavalry traveled north for three miles. The cavalary traveled east for a mile. The cavalry returned to Fort Hood this morning. The cavalry left Fort Hood this afternoon."

The nice thing about scripting these things is that people know whats interesting, what matters, and how to communicate it to other people. The rules by which we do this are fairly complicated. Unlike generators, people purposefuly avoid and find creative ways around using (and abusing) similar and repetitive patterns (reusing words, saying the obvious, repetitive quests, etc..).

Share this post


Link to post
Share on other sites
For this specific example, with multiple repeated events (arriving/departing), it might be best to only have "speaking" characters remember the most recent instance, and have a vague notion that it's happened before. "They come and go from Fort Hood; it's the base of their operations. They last departed at 11:30 this morning." If you want more than that, check the logs.

It might be better to restrict the amount on info in any one rendition of the story than to try to come up with an elegant way for an NPC to tell an epic saga.

Share this post


Link to post
Share on other sites
Quote:

The survivors retreated west, into Red Rock Range and we haven't heard from them since.


If you intend to generate interesting text such as that, you'll have to teach your text generator a lot about context. That same sentence could mean "The survivors" = {"Fort Hood Cavalry survivors", "General Sanchez forces survivors", "Survivors from both parties"}.

It's easy to introduce AN ambiguity, but it's hard to make sure your reader understands the intended meaning.

Also, I have a theory for a pretty interesting sentence comparison technique that you may be able to use for user-asked-questions:

Let's say the user enters some text, and you're able to parse it into a parse tree/forest using a GLR parser (such a technique simply stores ambiguities rather than trying to solve them). Now, your NPC conversation engine has stored some similar tree-like structures that explain its knowledge, which you can autogenerate. If you match up the leaves of the two trees (the tokens of the user input against the word/idea tokens of each tree/forest in the NPC conversation table) and start performing operations based on tree nodes that match or are similar (such as annihilating matches and reducing both trees), you're left with information that compares/contrasts the trees, which you can probably analyze to figure out what the user's saying in relation to what the NPC knows, and forumate a relevant answer that doesn't reiterate the factual information that the user asked:

NPC: ((the cavalry) left (Fort Hood)) (three days ago)
Player: "(When) did (the cavalry) leave?"

NPC (annihilates graph, finding (Fort Hood) unlinked, (left) and (did leave) matching, and (When) attached to (three days ago). Since "when" is the question, it uses (Three days ago) as the answer.

[Edited by - Nypyren on July 25, 2005 2:18:59 AM]

Share this post


Link to post
Share on other sites
This is a really cool idea. I like the idea of triggers (enter/leave town, deaths, etc.). I was just thinking of an "auto-importance-metric" concept, taking potentially isolated events, and deciding when it meant something. I haven't thought too much on this, so here's the rough:

As a generic concept, events are not isolated when they occur

* close in time: 1 guy dying at 5pm is just one event, 50 characters dying within 1 minute would constitute an event, even (especially?) if spread out geographically

* close geographically: 100 deaths at the mouth of a dragon's lair means the location is important

* other: things like crossing the intersection when the light is green = no deaths, but when red = many deaths


The 1st 2 concepts would be easy compute:

1) each individual event has a predefined importance weighting, when something happens its weight is added to a variable (time_importance += event_importance), which is constantly diminishing (time_importance -= dt*diminish, or even an exponential function). I would do this for a few different diminishing constants, translating to different windows of importance...giving short-term and long-term importance metrics.

2) there are plenty of globbing algorithms in use for machine vision applications, not that any of them are very simple. Just a simple regular grid, where each events importance is added to the grid square where it happened, would be extremely easy to implement. Defining regions (not necessarily square) would be important for naming the locations anyway.

3) I have no idea how to approach this rigorously...some kind of auto-correlation, obviously, but for that to work, you'd need variables for each potential factor.


In terms of what is actually important (determining a threshold) I would keep track of the maximum value for each metric. So the probability that a NPC would talk about an event would involve the event's value, the maximum value ever, and the time since it happened ("it's the biggest flood since '94"). For a news-report type thing, set a percentage theshold over a time window, or a maximum number of events over a time window ("in today's news...")


OK, time for bed, sorry for 93% of the typos...

Share this post


Link to post
Share on other sites
As I think some responses have highlighted, there's a great range of depths that you can take this feature to - producing interesting responses to questions is still considered a serious challenge in the domain of artificial intelligence.

So another interesting related question would be to ask what the depth of NPC conversation in an RPG should be, given practical considerations and the value of the feature.

Given the depth, it's a lot easier to work out an optimal implementation - like Risujin says, up to a certain depth, basic scripting does pretty well.


Share this post


Link to post
Share on other sites
Hmmm...I just thought of an interesting way to account for ambiguities and poor translation. The report you get depends on who you talk to. Different NPC's have different outlooks on what constitutes an important event and what isn't worth mentioning. Therein, if one NPC chooses to mention an insignificant detail or two, due to the limitations of the parser, it can be attributed to that NPC's 'personality.'

This would allow some mistakes in interpretation of events - covering up computational error with a human face.

Now, you wouldn't want the player to run around to various NPC's looking for different sides of the same story to make up for parser errors - you'd want to first make sure that errors are limited to things that don't neccesarily impact the message being sent, and use the concept that each NPC has a different personality to smooth over the minor errors, like mentioning an insignificant event, or understating an important event. Claim that the NPC at fault is biased against, let's say, cavalry men, so he understates their actions while overstating those of the infantry. Just weight the NPC's differently to give the illusion that they are each quirky in their own ways as a way to account for errors.

But, if they do something out of character, you're probably SOL.

Share this post


Link to post
Share on other sites
Quote:
Original post by Risujin
This sort of thing sounds pretty good now, but feed it into a generator and you'll end up with this:

"The cavalry left Fort Hood three days ago. The cavalry returned to Fort Hood two days ago. The cavalry left Fort Hood yesterday. The cavalry traveled west for three miles. The cavalry traveled north for three miles. The cavalary traveled east for a mile. The cavalry returned to Fort Hood this morning. The cavalry left Fort Hood this afternoon."


This is a good potential problem to point out. The two chief aspects of it are repetition of the same end result and (as you've phrased it) gross and robotic repetition of too much detail.

So lets look at summarization: Ultimately, when listening to a story you care most about the punch line. Often we tell stories with the start, a quick dose of the middle, and ultimately, the end.

Now if the end and the beginning are similar, we use a different form of summarization. We might say, "They left a couple of days ago and came back this morning."

I think it's crucial to keep to the purpose of what this would be used for, that is to give situational awareness of events on a an open map to the player without them having to look at the map. So maybe it's best to try capturing the three or four most significantly weighted events and then trying to see if there are grammar rules that can apply for repeat circumstances.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nypyren
NPC (annihilates graph, finding (Fort Hood) unlinked, (left) and (did leave) matching, and (When) attached to (three days ago). Since "when" is the question, it uses (Three days ago) as the answer.


Wow, that certainly sounds like a cool possibility. Do you know where I might get more info on this? I'd like to better understand the risks involved.

Share this post


Link to post
Share on other sites
Quote:
Original post by lonesock
1) each individual event has a predefined importance weighting, when something happens its weight is added to a variable (time_importance += event_importance), which is constantly diminishing (time_importance -= dt*diminish, or even an exponential function). I would do this for a few different diminishing constants, translating to different windows of importance...giving short-term and long-term importance metrics.

2) there are plenty of globbing algorithms in use for machine vision applications, not that any of them are very simple. Just a simple regular grid, where each events importance is added to the grid square where it happened, would be extremely easy to implement. Defining regions (not necessarily square) would be important for naming the locations anyway.


I like a grid or node based approach better because it translates closer to what I've seen done in strategy games. I think this would call for defining significant events and significant locations then weighting both so NPCs can sort through what to mention. I don't want to approach this as a complete solution-- scripting would still be required, even scripting to vary the description of events. But I think capturing actors and major actions, then summarizing the top three or four events would be a step in the right direction. And it would be less robotic if personality and color were added as adjectives / adverbs to to text.



Quote:

In terms of what is actually important (determining a threshold) I would keep track of the maximum value for each metric. So the probability that a NPC would talk about an event would involve the event's value, the maximum value ever, and the time since it happened ("it's the biggest flood since '94"). For a news-report type thing, set a percentage theshold over a time window, or a maximum number of events over a time window ("in today's news...")


Good idea. It's already a lot of data to deal with, but events need expiration tags. Also, I think rather than swelling the data into a huge history log (which over time will degrade search speed) events need to be either bumped or summarized, and conversation interaction UI will have to compensate for why you can no longer query NPCs on details for older events.

Share this post


Link to post
Share on other sites
Quote:
Original post by Jotaf
Movement has to be fairly abstracted, you don't want to record how many steps the character/party/whatever has walked in any direction, you only need to record its location when something happened.


Yes, this is exactly as I was thinking. With movement, you're recording variations in vector, but you also have to ultimately calculate final destination. Even if you zig zag heading north, you've still gone north.

Quote:

Keep the events in chronological order, and assign each one a "weight" of how important it is. Simple movement is not that important, battles can have different importance depending on the strenght of the enemies, if anyone died or was severely injured in it (fighting the 100th common road thief is not very important when compared to an encounter with a dragon).


As to repetition again, I think either it gets discarded as you say, or gets folded into some calculation which hooks into special (incidental) repetition grammar. "They went north, fighting trolls and orcs all along the way," for example, or "They fought their way north."


Quote:

The player can ask for more details if he wishes: about specific points in the journey ("tell me more about -this- event" -- tell the 10 most important events within a '30-events radius' around that one), the whole thing in general ("tell me more" -- tell the 50 more important events of the whole story) or applying a filter disguised as a question ("did you meet a strange merchant wearing purple clothes?" -- look for an event that matches these criteria).


Hmmm... okay, this is an interesting way to do it. I sounds like it calls for a hierarchical tree of information. However, if the data gets too large, I think even summarization will do.

One way to do it might be to create and store different log files for different units/locations, and then a common log file for units and locations that are part of something larger. The common log file would contain, in chronological order, the biggest events for the army/nation, while the individual log files would contain the info for factions/units and towns.

I can see this quickly becoming overly complex, so I think the key here is to focus on summarization and to limit the storage to only special entities. So you wouldn't be able to get the story of every single entity, it's just asking for too much.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this