Compressing behavior into verbal descriptions
"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?
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.
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?
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?
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...
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...
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]
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]
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..).
"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..).
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.
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.
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]
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...
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...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
