November 08, 2005

Great Expectation-Formations

I’ve been thinking a lot lately (and by “lately”, I mean “for the past 5 years or so”) about AI and expectation-formation. One of my original posts (on the FSM tyranny) dealt peripherally with the subject, discussing “Occupancy Maps”, which I spun at the time I was writing my thesis as a form of location-expectation (and which is the subject of my article for AIGPW3).

Clearly I talk a lot about the Media Lab’s Synthetic Characters group, mostly because I think we were onto a couple of really cool/important ideas there, that unfortunately never get explored as much as they could/should have (damn you, graduation). Expectation-formation was one of those subjects.

(For those who don’t want to wade through the nonsense below, there is an important question for game developers at the bottom of this post.)

Forming expectations is a problem that is relatively easy to concretize: AIs have an internal knowledge model of the world. If the AI is able to provide an estimate for what that state is going to look like n ticks in the future, that’s an expectation – and naturally we’re going to want the AI to react not (or not just) to current world-state, but also to its expectation. React to its own expectation. I think that’s a neat idea, and architecturally it makes a lot of sense. Assuming we have a reactive behavior system of some sort already, we don’t, as a first pass, need to modify IT at all. All we need to do is provide future instead of current data. Great!

So where does the complication come in? Part of it – an oft-overlooked part of it – is in what I would call expectation-management. I can make a prediction about the world, but how is that prediction maintained over time in the face of new, potentially contradictory information? If our prediction is proved false (I expected to see the player at spot X, but I don’t see them there) what do we fall back on? (This is again, what I was primarily dealing with with Occupancy Maps).

The larger and more obvious question is, how do we generate predictions in the first place?

I’m going to be Media Lab-centric again in pimping the work of my friend and former colleague Rob Burke, who did an amazing thesis on this topic called It’s About Time: Temporal Representations for Synthetic Characters. In it, Rob systematized a lot of our ideas about expectations and learning, blurring in a great way the boundary between the two, and also with the very title pointed out what the real deficit is in current approaches: the lack of representations of time.

(If you don’t want to read Rob’s entire thesis, even though you should, check out a shorter version he wrote as a chapter for LifeLike Characters.)

HIS approach, in true SC fashion, was taken directly from the animal learning/psychology literature, in particular the work of Galistel (check out Time, Rate and Conditioning). Here’s the basic basic basic idea: experience is a soup of stimuli, some inherently salient, some subjectively salient (because they’ve been harbingers of good or bad things in the past) and some irrelevant. Learning is about finding correlations between these stimuli -- correlations that are temporal in nature. I.e. not just “A follows B” but “A follows B after 3 seconds”. This gives us a basis rejecting hypotheses, which we might do if, say, B still has not happened after 10 seconds. AIs in Rob’s world would therefore keep around a list of hypotheses about temporal correlations, and those hypotheses would compete to explain the ongoing state of the world. Hypotheses that were not successful long-term would be culled, those that were were reinforced.

(Somewhere out there Rob Burke’s ears are burning as I misrepresent or dramatically oversimplify his work. Rob, jump in with any corrections/clarifications/comments!)

This is, of course, basically an implementation of conditioning, and the Gallistel/Burke model also accounts for some of the secondary effects of conditioning, like blocking and overshadowing. They also make the strong argument that classical conditioning (a tone is followed by an electric shock) and operant conditioning (if the AI DOES X, the result is Y) are the same thing (hence the blurring of the line between learning and action-selection. I think lots of game-ai developers will be familiar with the basics of the latter (“learning is almost always taken to involve some action on the part of the agent), but I suspect that the former is a little less familiar (why learn about correlation between events that don’t involve me?).

One of my favorite parts of Rob’s thesis was his discussion of a “curiosity drive” – basically the idea that the desire to figure out which correlation-hypotheses are correct can be an end unto itself. Thus if my agent has a recently-formed rule (based on one observation) that says “if I pull the lever, food appears 2 seconds later”, the agent, having eaten its fill (and therefore no longer being driven by hunger) might well pull the lever a few more times, just to see whether its hypothesis about the relationship between the lever and the food really holds. Awesome idea, huh?

(An aside: I think a common theme that runs through many good works on expectations is that it is never enough to simply annotate a hypothesis with “amount of expected reward” – we also have to provide some degree of confidence that the hypothesis we’re considering is valid at all! To combine our confidence with expected reward is a fatal oversimplification that conflates two very different concerns. The curiosity drive discussed above would, for example, specifically look for high-reward, low-confidence hypotheses. If we can turn that into high-reward high-confidence, we’re golden!)

Of course being that this is a blog for game developers, we come back to the 23.2 billion dollar question: how do we work the idea of expectation-formation (through whatever mechanism) into games? And like all such pricey questions, my answer is “I dunno, but I’m thinking about it.”

One way I like to tackle such problems is to pull up the Halo source code, squint my eyes and tilt my head and ask myself, what are some examples of the phenomenon that we’ve ALREADY implemented (probably in an informal way)? Having made a short list, can we generalize on them? Maybe make a separate system to handle them? Extend the use of that system to other arenas? Call if revisionism if you want, but I think it’s a useful way to catalog the examples of problems (in this case expectation-related problems) that we HAD to solve, and therefore avoid wandering into an academic-style wouldn’t-it-be-cool-if la-la land.

Well immediately a few examples come to mind (and they’re probably going to sound stupid, but I think they still count): how about leading a target when firing a burst of slow-moving projectiles? Or, the fact that target positions are cached in the brain of each individual agent, thereby providing an “expectation” about the target’s position even when the agent is no longer observing it?

So I promised an important question and this is it: What are some examples of expectations or predictions made by agents in your game, or games you’ve played? I’m interested to know, because I think, as I’ve said before, that expectation-formation is important, perhaps even essential to our own intelligence – and I think it’s also REALLY intuitively perceived and understood by a player, since the player is making the same kinds of predictions – perhaps even about the same things – as they run around the world killing things.

Posted by naimad at November 8, 2005 10:41 PM
Comments

I have to say that of all of the ideas that came out of the Synthetic Characters Group, the work of Damian, Chris Kline, and Rob Burke tackling various issues around the formation, exploration and use of expectations probably has the most profound implications of any of them.

-bruce

Posted by: bruce blumberg at November 9, 2005 07:14 AM

One thing that has perhaps stymied deeper modeling of the related issues of time, causation and expectation in games is the legacy of game programming techniques. Back in the old days, the idea of keeping a running memory of what had happened in the world was technologically unfeasible for realtime games. RAM was tight, and synthesizing useful conclusions from all of that data required more processing than was available.

That mindset has trickled down over time into all sorts of design assumptions. A 3D renderer, for instance, has no concept of time... everything must be recalculated and re-painted each time the clock ticks forward. Bad example maybe, because that obviously works fine for 3D rendering. Goose, gander, etc.

Game simulations obviously deal with changes over time, but the dynamics of that change are always condensed / aggregated into a single, eternal "present tense" (how very Zen). A moving object doesn't move so much as its velocity is stored and retrieved over time to determine its position. This is very different from the way that we as reasoning (pattern-recognizing, especially) beings seem to conceptualize the world. Even on a low cognitive level, the phenomenon of Persistence of Vision suggests an inherent sequentiality: A, then B, but B exists very much in the context of A. If all you can know/remember is the present, then persistence of vision is impossible.

So it seems like you'd need to build that sort of sequential thinking very deeply into your system for AIs to be able to truly understand causation and consequence. And of course for a 3D action game that means tying it into other systems like physics, visibility etc. I get the impression that most of the people doing software engineering in the industry are still concerned primarily with getting everything running fast and reliably. AI is, sadly, often developed as a non-core adjunct system that queries the world only on terms set by the other systems.

Sequential reasoning and memory are things I'm experimenting with in a personal project, though it's very primitive at the moment. I honestly can't think of many examples from existing games, though it's the kind of thing that might be difficult to spot "in the wild" without source access or intimate knowledge of the systems.

On the pure game design side, you're absolutely right, the player is doing exactly this kind of thinking. Doug Church coined the term "Perceivable Consequence" to describe the know-ability of a potential player action - if I press the big red button, can I infer ahead of time, through memory, context etc, what the result will be? If a game exhibits strongly perceivable consequence, players can make informed choices, and so they're able to strategize deeply. They feel "in touch" with the system, and they can inhabit it intellectually and experientially, as opposed to a system that just takes their input and ignores it or spits out random feedback. Aubrey Hesselgren uses the term "perceivably random" to describe systems where the causative links are sufficiently opaque that the player cannot know what will result from a given action (and thus might as well throw a die to decide what to do next).

Sorry for the verbosity; I feel like I don't have the vocabulary to express half of what I want to. Thanks for the great post, I really enjoy reading this blog and have since its inception.

Posted by: JP at November 9, 2005 12:41 PM

> What are some examples of expectations or predictions
> made by agents in your game, or games you’ve played?

That's a great question, Damian. Here are a few off the top of my head, mostly of informal representations that were useful for specific kinds of expectations:

-AIs firing ranged weapons should always do line testing before they fire, but the line tests are often only a rough estimate -- the ever-changing game environment and the non-linear paths of some types of projectiles (e.g. homing projectiles, spiraling missiles, and projectiles with ballistic trajectories, such as arrows and grenades) can seriously limit the usefulness of line-tests in many cases. In some previous games (most notably MechWarrior 4: Vengeance, if I recall correctly) I've added a callback from the projectile itself to inform the AI that fired it so that the AI can know if it's hitting the wrong game objects or impacting the static game world either in front of the intended target or behind it. This helps avoid situations where an NPC with a bow and arrow can stand in place continually firing at the player and not noticing that all of his arrows are hitting the chandelier. The first arrow hits the chandelier, the NPC checks it against his prediction, realizes the line test was flawed, and concludes that he needs to move or fire at a different target point.

-Obviously pathfinding is another case. In any game environment that's not fully static, you can't make any perfect guarantees about the validity of a path over time, so each AI needs to track its expected progress along its path against its actual progress so it can take countermeasures if it gets stuck.

-Civilization 4 has an interesting built-in prediction system for combat that will give you the odds for any unit attacking another unit, taking into account things like terrain bonuses, promotions, fortifications, etc. The surprising thing is that the computer player AI doesn't seem to have used this in the games I've played -- I've seen many cases where enemy cavalry will charge out of their well-defended fortifications in a city to attack my stack of 20 modern armor units sitting outside the city walls (which are on a hill with a 25% defense bonus, no less!). Maybe I don't have the difficulty level set high enough ...?

-In strategy games and games in sufficiently similar genres that you can leverage strategy game AI techniques, you can also do a lot of interesting near-term expectation formation with influence maps. For example, with a bit of tweaking, an influence map can tell you that an opposing player is likely to expand into specific unoccipied territory, that he's most likely to send his forces through a certain choke point, or that he's most likely to attack from a certain direction. I used this to some extent in 'WarBreeds' way back in '97, but the concept can be taken a lot further than I ever did, and again, has a lot of potential applications outside of strategy games.

- For my own gameplay when I play Battlefield 2, I find I use expectations frequently for constructing immediate action plans (yes, it's not really an 'AI' per se, but I think it's still very relevant, since I've found I have an extremely structured play style in BF2 that involves very little conscious thought and which I have to analyze from the outside to understand). A high-level player is continually building plans on several levels of abstraction and resolving them against each other, but the most immediate plans in particular are often based on expectations. You can't react to what's happening right now; you have to react to what will happen in the next 5 seconds. I see a jeep tearing down the road toward me at high speed, but there are land mines right in front of me, so I jump out of the way just in time to watch the jeep go up in a big ball of flame.

Usually this sort of thing happens when confronted with multiple opponents at the same time: I spot two opponents, and I evaluate whether I can take one of them out more quickly than the other. If so, I prioritize them to allow me to take out the weaker opponent first.

From some of the analysis I've done recording FRAPS movies of my own BF2 and BF1/DC gameplay sessions, I've noticed that if I happen to be in a tank, I'll almost always take out the opposing infantry nearby before confronting enemy armor in the same area since I expect to be able to take them out much more quickly and reduce the enemy threat more effectively in a shorter time frame.

(An interesting question here is how one deals with confidence measures in a situation like that. I'm tempted to think that my own mental algorithm for BF2 is usually just selecting the predicted world state with the highest confidence value and reacting to that -- certainly in the case of the jeep careening toward the land mines, that seems to be what's going on. However, it seems that in many cases I'm really exploring a much broader tree of expectations as I play -- say, any expectations above a certain baseline confidence value -- and compiling a set of inferences based on those to let me build a plan. More interestingly, I seem to have a confidence value for each such inference based on the expectations that comprised it. For example, if I see an enemy jeep and helicopter approaching my position, and I duck behind the building and enter an empty tank, it seems to me I'm mentally evaluating the combined influence of both the helicopter and the jeep on the future game state, and the combined benefits of taking cover behind the building and entering the unoccupied tank. Additionally, the path I follow around the building to the tank ends up being the one that will give me the best possible cover from the expected positions and firing arcs of both the the jeep and the helicopter within that time frame.

Again, this is something I do automatically and almost unconsciously as a player, so I am approaching this as a reverse-engineering problem and trying to figure out how I would build an AI that plays the way I would.)

By the way, I really like your thoughts on the "curiosity drive." Hope it won't make me sound too much like Peter Molyneux if I say that that could lead to some really interesting new game design concepts.

Posted by: Paul T at November 9, 2005 01:29 PM

One other interesting Battlefield 2 moment that came up as a result of an FRAPS-recorded gameplay session that I think has some interesting ramifications for expectation formation:

At a certain point I was in a tank battle with another player. I damaged his tank heavily and he jumped out of the tank and ran off and ducked behind an L-shaped wall of sand bags. I noticed that I drove up to to sand bags, but rather than driving around with the tank up to the opening in the sand bag wall (the right side of the 'L'), I stopped the tank, went around behind the sandbags (the left side of the 'L'), and shot him in the back with my M16 -- specifically because I knew he expected me to turn around behind the sandbags in my tank, and he would almost certainly be lying prone facing toward the right side waiting for my tank to come in.

So part of the expectation-formation process has to be taking into account the reasonable expectations of the other players -- particularly, what they expect you to do in the near term -- and reacting to that.

Posted by: Paul T at November 10, 2005 10:52 AM

--------------
[Does anyone else have trouble seeing where new comments start? They all run together for me.]

The tricky thing about modeling expectation in game AI is the low fidelity of the NPC’s simulated vision, and the lack of higher level understanding of his situation.

When an NPC is tracking a target, and suddenly fails to see the target at the expected (x,y,z), how do we know if it is because the target is really not there, or because we just can’t see the target through our pin-hole of a vision system (aka ray cast)? Sure, we could try to remedy this by sampling random offsets, or casting additional rays, but this doesn’t guarantee better results.

If the Player steps behind a telephone pole, we don’t want the NPC to suddenly wonder “Where did he go?” It’s common sense that a pole cannot totally obscure a human, so regardless of what the vision system says, the NPC should still have perfect knowledge of the Player’s position when partially obstructed by a pole. So maybe we should cheat, and let NPCs see through skinny things like poles.

But what if instead the Player steps behind a crate in a warehouse? (because all good games have warehouses and crates!) Should the NPC still have perfect knowledge of the Player’s position? Well, that depends on higher level understanding of the situation. If the warehouse has only one crate, and there are no exits, the NPC should not wonder where the Player is, once obscured by the crate. It’s common sense that there’s only one place the Player could be. We might want the NPC to throw a grenade, or shout “Come out of there!,” or do something else that illustrates the NPC’s persistent awareness of the Player’s position. On the other hand, if there are many crates, or an exit to a hallway behind the crate, then the NPC should become uncertain of the Player’s position once obscured.

So, what does this have to do with expectation?? Since the NPC’s vision is unreliable, it does not produce believably human behavior when the NPC is totally reliant on expectation whenever vision fails.

In NOLF2 and FEAR, we wanted the NPCs to be able to lose track of the Player, but only when it would make sense for real humans to do so. We didn’t want NPCs to lose track of targets in unrealistic ways in the heat of battle, emphasizing weaknesses of our sensory systems. Our solution was to flip the problem around. Rather than saying that when an NPC loses sight of a target, the NPC has no knowledge until vision says otherwise, we decided NPCs retain perfect knowledge until a designer says otherwise. Designers annotated the map with data specifying where it would make sense for real people get lost (e.g. at doorways, or where multiple hallways meet). This gave us the best of both worlds: if the Player ducks into a closet, he can watch a pursuing NPC run straight by (relying on his expectation that the Player kept running straight), but if the Player stands behind a bush, the NPC does not suddenly ask “Where did he go?!”

Damian’s “Occupancy Maps” article is excellent, and the ideas described within should definitely be applied to games, but any implementation of Occupancy Maps is going to run into the same issues with ray-based vision. How can we be sure we cannot see the target in a particular node of the occupancy grid, when we are only testing line of sight to one point?

Posted by: jorkin at November 10, 2005 08:15 PM

Hmm, I really like the action tuple representation in Burke's work! The "future result" bit of data has been missing in classic behavior-based modeling - but it would make it so much easier to do any kind of a reaction to the future. For example, agents that have behaviors with long-term consequences, as well behaviors with short-term ways of mitigating these consequences: the agent knows that having jumped off this cliff will cause pain in 1s, so it starts a muscle-relaxing behavior in .85s to offset this effect. Now that would be a cool effect! :)

BTW, can you recommend any of Burke's shorter papers on the subject? (ed. the LifeLike Characters link doesn't seem to be working for me...)

Posted by: Rob at November 12, 2005 12:00 PM

----------------------------------------------------------------

This is kind of off-topic since it's more about general conditioning than expectation formation per se ... Kindly forgive my indulgence in yet another wild tangent :)

I had an interesting dream last night where I was in some kind of a space station. In several of the rooms there were small, mostly helpless creatures (sort of like the "Tribbles" from Star Trek) which were intelligent enough to form associations by watching me do things. I would use a control panel to open a door and walk through, and behind me, the creatures would jump up onto the door panel and mess with it until they could follow me through -- and soon enough, all the creatures would stream through that door as well as any other doors in the environment that they could unlock in this way. They would jump up and down in a funny dance to communicate their entire knowledge base with each other, so that any knowledge would quickly propagate throughout the species. If I wasn't very careful, they'd learn all sorts of tricks for navigating around the environment and end up in all sorts of terrible places where they could never survive.

It struck me as interesting because in the back of my mind I've been playing around with the question of how this all fits in with game design. How we can ensure that expectation-management remains useful and interesting to the player and not just a hidden cognitive process inside the AI's head ... or something that produces results that are interesting but have minimal impact on the actual gameplay?

I thought my dream was interesting because it forced me to look at the question from the opposite direction. I had a knee-jerk tendency to think of the growth of the AI's knowledge model as something that the player must manage to his own benefit, as in a game like Black & White. But in this model, learning becomes a dangerous thing. Let the AI's knowledge model grow just a bit too far, and my army of lemmings would very quickly end up exploring the wrong territory and become so much dross between the teeth of much larger and deadlier creatures.

I often had to go to great lengths to hide from these creatures when I was doing something interesting -- this was classic stealth gameplay a la Thief/NOLF, except that rather than hiding myself, I was only trying to hide a particular action in a fixed time interval. Sometimes I had to distract them (say, with food) in order to get past an obstacle without them learning too much.

From there, it evolved into something like a strategy puzzle game, where I had to explore the environment on my own and then figure out what areas I wanted these creatures to end up in. The creatures were like a fluid, and the abilities I allowed them to learn became like specific types of valves I could open.

Putting it a bit more formally: we have some set of discrete set of explorable "areas" of the game world, where each area can be classified as "desirable" or "undesirable." Also assume the areas form a fully connected graph such that each transition between two areas is enabled for my lemmings by zero or more "abilities" they can learn. The question posed to the player then becomes: What combination of abilities do I need to allow these creatures to learn in order to channel them into as many of the desirable areas as possible while keeping them from all of the undesirable ones?

Posted by: Paul T at November 13, 2005 10:44 AM

Paul, I only wish I had such potentially lucrative dreams. I want to play the game you just described.

Yes, I was thinking more about your question -- you know, the important one, about how do make sure the player sees/understands/appreciates/benefits from our expectation engines. Maybe once again, expectations should be thought of not as a technique to make agents look smart (5% of our jobs as ai engineers) but to stop them from looking stupid (95%).

I think of one example in particular: guys in Halo are always getting out of your vehicle at the most ridiculous, inopportune times. As in, you stop your warthog, with your two AI passengers, on a long sandy beach with no enemies immediately nearby to pick up the rocket launcher on the top of the sand dune. Out you hop, you run and pick up the weapon and turn around only to find that your marines have concluded that you no longer wanted the vehicle, and have taken off to the next encounter without you, and you, obviously, are left exclaiming "OMG WTF?!" or something equivalent.

It's a stupid example, but figuring out the model for "it's useful for me to stay here because the player is not coming back" vs. "the player is clearly not interested in this anymore" was quite a tricky, regrettably ad hoc process -- we more or less solved it eventually by hand-writing situation classifiers based on player movement, proximity, aiming direction and so on. But we never got as far as the true solution requires, namely a full player-model, that is actively seeking out explanations for the player's movement and actions and then REacting appropriately. In a sense, a player-model would also be an expectation-generation engine that predicts what the player is going to do next. In this case, the player is not going to notice anything smart going on, but the deceptively complex social contract of riding-in-a-car-together will be navigated a little more smoothly (and, hopefully, be a little more general in implementation than our hand-coded piece of nonsense).

It seems clear, in any case, that expectations are easier to apply and more meaningful when we give the Ai more meaningful/complex actions to perform, especially when they are multi-step actions involving the player.

Posted by: naimad at November 13, 2005 07:04 PM

Great thoughts! The Halo Warthog-exiting problem puts it in great perspective.

Thinking back to the work I did on the lancemates in MechWarrior 4, there were a lot of similar problems that would have benefited from many of the kinds of expectation-formation described here. As I recall, we only gave lancemates dead-reckoning for the player's position, but they would have done a much better job of avoiding the player or selecting targets to attack if they'd been given some ability to model the player -- determining what targets the player was likely to select, what weapons he was most likely to use, and how he was most likely to torso-twist his 'Mech. It also would have helped a lot of we'd done some amount of prediction of the player's position relative to the terrain, since dead-reckoning alone often returns invalid or unrealistic results.

Posted by: Paul T at November 14, 2005 09:47 AM

Wow, I really enjoyed reading this discussion - and feel like a slacker for taking this long to respond! Hello to all of you from a long-time listener, first-time caller :)

I haven't thought of this stuff in ages, and since the halcyon SC days, my head's been all sorts of other places. But reading this stuff again, I still believe strongly in the importance of expectation and expectation management to building adaptive characters. And I envy you dudes a little for being in the fray :)

JP, you raise a good point about memory costs coming between the gaming world and prediction. But I think we can manage that. I heard a performance expert recently quip, "what do you call a cache without a good lifecycle policy? The answer: a memory leak." Love him or hate him, but one of Minsky's old faithfuls I still especially like is this notion that forgetfulness can be a virtue. One of the tenets of the ActionTuple prediction hypothesis generation in my thesis was that predictions should only be generated when we have reason to believe they'll be relevant to us in future. When we realize a hypothesis is particularly lacking in confidence, or particularly irrelevant, we can purge it from our memory with extreme prejudice. (Mind you, in real life we experience this strange phenomenon of "I know I KNOW it, but I can't remember it!!" What a strange place to be...)

OK, so I’m not a game developer these days, but I have to say, The Warthog example is EXCELLENT! It also illustrates another point I wanted to make, especially to this audience - that for the purposes of gameplay, you could pre-bake the hypothesis generator to be disposed to observe and detect certain types of causality. So, leaving a vehicle (or perhaps subsequent behavior after leaving the vehicle) could trigger a hypothesis generator based on an assessment of whether the player wants to keep traveling. The challenge, as always, is in registering the feedback for the AI: the player needs to subsequently be able to indicate to his AI cronies something like "you shower of eedjits, where are you going?!" if the AI is expected to learn what constitutes "hold on a sec lads, I'm going for some ammo" versus "carry on, this is my stop."

One last thing, for those of you who have read Damian's great thoughts on spatial learning: one of the coolest things about our two pieces of concurrent work was how incredibly synergistic the spatial and temporal prediction paradigms were. The occupancy maps and spatial reasoning in naimad’s work would have been perfect for both FORMING expectations, and "explaining away" expectation violations, in the time-rate conditioning model.

Apologies for the broken link above. The Great Expectations paper from the LifeLike Characters book, stored in zipped Word format, is now also at http://heroicsalmonleap.members.winisp.net/GreatExpectations.zip


Posted by: Rob Burke at November 15, 2005 01:35 PM

>the player needs to subsequently be able to indicate to his AI cronies something like "you shower of eedjits, where are you going?!"

In Halo2, you did this using the only voice you had in the game: your gun. As in, when you saw a group of mischeivous marines making off with your ride, you ping 'em a few times and they come right back! :)

Posted by: naimad at November 15, 2005 02:17 PM

When you've got a gun in your hand, everything looks like a target, eh? :)

All of this raises another complication I didn't address before: you might want to include a degree of confidence on the FEEDBACK you receive about your outcome of your prediction. I mean -- you may be only modestly confident that that bullet in the back of the head really meant "you shouldn't have taken off on me."

Note that that's different from the degree of confidence in the PREDICTOR itself -- meaning, in this example, the mechanism that used some context to trigger the prediction that the player was NOT going to return to the vehicle...

Can anyone give some good examples of where degrees of confidence are being used in your games? Are they just a bridge too far? We used to use them to modify the extent to which we were adapting and changing our minds about things.

Posted by: Rob Burke at November 16, 2005 03:02 AM

> [Rob Burke]
> Can anyone give some good examples of where degrees
> of confidence are being used in your games? Are
> they just a bridge too far?

No, they're quite useful, particularly for things like stealth gameplay, which generally revolves around the confidence measures of the NPCs as to whether you're really there or not.

The sensory awareness system I originally developed on for Thief 3 and Deus Ex 2 was built a database of all of the stimuli an AI agent received in the recent past (seeing the player or other relevant game objects, auditory stimuli, seeing dead bodies, receiving damage, seeing another AI in an alerted state, etc.), and included a confidence measure for each stimulus. For example, seeing the player's foot far in the distance, at the corner of your field of view, in a dark room, would receive the lowest confidence measure that something was awry. Taking an arrow to one's shoulder, on the other hand, would give the highest confidence value. Each AI would change its alertness level based on the total confidence value computed from all the stimuli put together. Different kinds of stimuli declined in importance at different rates (since a guard won't as soon forget about the arrow to the shoulder as he will the vague shape he saw in the distance out of the corner of his eye).

[Disclaimer: These comments only apply to the initial design of the AI, not the final products, which for reasons still unknown to me turned out entirely differently.]

If I recall correctly, Jeff created something very similar for the stealth gameplay in No One Lives Forever 2.

> [naimad]
> In Halo2, you did this using the only voice you had
> in the game: your gun. As in, when you saw a group
> of mischeivous marines making off with your ride,
> you ping 'em a few times and they come right back! :)

Ah, so *that's* why everyone has such terrible vehicle etiquette in multiplayer Halo! It all makes sense now :P

Posted by: Paul T at November 16, 2005 09:47 AM

>I mean -- you may be only modestly confident that that bullet in the back of the head really meant "you shouldn't have taken off on me."


Ha ha! Savvy, Rob, very savvy. Indeed, the whole bullet-based feedback system (tm) had to be made tolerant of general splash-damage - you didn't want after all, a warthog of allies to disengage from the encounter completely just because they happened to cross your stream of bullets. THIS led us to develop ANOTHER player-model -- a player-is-focusing-on-me model (again based on aim direction, movement, etc.) So only when the player damages me AND he's focused on me do we go back to pick him up. Once again it's interesting that a practical problem we faced (to which we developed a hand-crafted solution) has an analog in the hypothetical more formalized system we're thinking about. In this case the feedback-evaluation system.

You ask a good question re the role of confidences. One interesting use of confidences (sort of) in Halo is, as you might imagine, the target position tracking system. Like we used to have in SC, each agent has an internal representation of the overall states (including positions) of other agents (mostly enemies) and associates a confidence with that knowledge. There are I think two interesting features of this confidence:
(1) The confidence is discrete. One of the guiding principles of Halo AI design (that comes down from Chris Butcher and Halo1) is that discrete/modal decisions/behaviors are always better than analog/floating-point/squishy decisions/behaviors (because ultimately better-understood by the player). Target-state confidence is the same way. The confidence can be IMMEDIATE, if you're currently seeing the target, CERTAIN, if you only very recently lost sight of the target, UNINSPECTED, if you think you know where the target but have not had a chance to check that position, or INSPECTED, if the target is not in the place where you lost track of him. The interesting and useful thing, of course, is that each of these perceptual/knowledge states map almost directly to behaviors. As in, given an UNINSPECTED target, it's pretty clear that you should try to uncover the last place you thought he was hiding.

(2) Because the confidence is discrete, there's really no mathematically-principled basis to it. Instead some of the transitions between confidence-states is time-based (e.g. CERTAIN->UNINSPECTED) while others are observation-based (e.g. UNINSPECTED->INSPECTED when you look at the point where you lost track of the target and still cannot see it).

In general, the idea of discrete knowledge-states is an interesting one. It strikes me as something we were kind of scared of in SC.

Posted by: naimad at November 16, 2005 09:49 AM

> Damian: In general, the idea of discrete knowledge-states is an interesting one.

I like the idea of discreet knowledge states, as a tool for communication with designers. We had something similar in FEAR to what damian is describing, where we divided awareness levels into relaxed, suspicious, alert, and ImmediateThreat. These awareness levels affect the selection of walk/run animation sets, so an AI would sprint if alert, but slow to a tactical run and look around more if aware of an immediate threat. Our implementation actually managed to completely confuse designers though – “I just want him to run into the warehouse. Should he be alert? Or ImmediateThreat??” But I think if done right, this idea could work well.

> PaulT: If I recall correctly, Jeff created something very similar for the stealth gameplay in No One Lives Forever 2.

yep, NOLF and NOLF2 had something similar, but we used confidence much more extensively in FEAR. Confidence was an integral part of our working memory system, as a direct result of reading papers about C4 (nice work fellas!). Working memory is filled with “facts” that the AI has observed, and each attribute in a fact has an associated [0,1] confidence value. So like Paul describes, we could use this to determine how confident an AI is in something he has seen or heard (and confidence decays with lack of stimulation). This made target selection (aka attention selection) really easy – when an AI needs a new target, he attacks or investigates the thing who’s position he is most confident in. We also leveraged confidence in tactical position selection. The AI have sensors to find potentially valid cover positions, and the sensors sort them by proximity and assign a relative confidence value. The AI goes for cover at the position he is most confident in – he is most confident that he will safely get to closer cover than to something farther away (and most confident that someone else will not get there first, or invalidate the cover). The function to assign confidence values could take more factors into account than simply proximity, but we never did anything more than that.

> RobB: When we realize a hypothesis is particularly lacking in confidence, or particularly irrelevant, we can purge it from our memory with extreme prejudice.

Early on in FEAR, we actually tried to more closely replicate your percept memory tree, and retain multiple facts about the same stimulus, to create a temporal history for later analysis. The idea was that, for example, if we stored a sequence of facts for footstep sound stimuli, we could use this history to predict the position of a threat that we had never seen. We ran into problems with garbage collection in working memory, and found it wasn’t so easy to determine what was relevant and what could be purged at a given time. We found working memory was quickly filling with thousands of facts, as an AI listened to lots of gunfire, shouting, etc. So, under the pressure of the project schedule, we ditched the idea, and just stored the most recent fact per object per stimulus. It’s nice though that the underlying working memory system still supports multiple facts per object/stimulus (unless monolith scraps the whole thing now that my reign of terror is over).

Posted by: jorkin at November 17, 2005 07:01 AM

> (unless monolith scraps the whole thing now that my reign of terror is over).

Not likely. ;) I'm already training two new AI programmers on the systems.

Posted by: BrianL at November 17, 2005 02:19 PM

As a designer, I would normally try to counter-balance Damian’s egghead tendencies, but I guess it can’t do any harm if it is just a thought experiment 8)

Five random ideas:
1 – Better combat dialog – “(The Player looks like) he is going for a tank!” “We’re not going to make it (past that grenade before it explodes)!” “This (attack the Player is leading us on) is suicide!” “Stab him once for me (Player that is running forward with a sword)!”
2 – Battle-awareness – A group of AI decides to retreat immediately because if it doesn’t move now the Player is going to get between them and their base with a tank and cut off their escape, or snipers that reposition to set up a crossfire where they expect the enemy to be.
3 – Pre-emptive tactics – An AI guesses what the Player is going to do, and tries to stop it, ie throwing a grenade under a vehicle the Player is heading toward, locking a door that the Player might use to escape, switching to a close-combat weapon if the Player looks like he might be about to charge.
4 – Ally Anticipation – This is the opposite of a pre-emptive tactic suggestion, trying to facilitate the Player’s predicted action, ie pressing against the wall so he can drive a vehicle past you, flushing out targets that a Player is trying to snipe, providing covering fire when the Player starts to move to a new cover position.
5 – Setting Traps or Ambushes – The AI guesses where the Player is going and tries to place a landmine, hide around the corner with a shotgun, cling to the ceiling and drop down on him, etc.

It seems obvious in retrospect, but the only thing in the world worth having expectations about is the Player, because everything else is under direct control. An AI doesn’t need to predict where another AI is going, it can just ask. Also, most of the suggestions I came up with seem to be about anticipating an event so the AI can perform an action either before it happens or at the same time it happens, which is probably good because then they will be much easier for the Player to understand.

It seems like the main difficulty is that most of these ideas require long-term predictions of the Player, on the order of 5-10 seconds, which is going to pretty unreliable under most conditions.

Posted by: Jaime at November 17, 2005 11:53 PM

> [Jaime]
> It seems obvious in retrospect, but the only thing
> in the world worth having expectations about is
> the Player, because everything else is under
> direct control. An AI doesn’t need to predict
> where another AI is going, it can just ask.

It's under direct control, yes, but still subject to a dynamic and unpredictable game world. I can see how player-expectation could be the only aspect of this that seems useful from a game design perspective, but it's very important -- even essential -- in many cases to form expectations regarding other AIs and themselves simply because game worlds are inherently dynamic and complex.

Sure, I can ask an AI, "where will you be 10 seconds from now?," but he might get shot along the way, the footbridge he intends to walk over might get destroyed by a rocket, he might get distracted and decide to re-pathfind, or he might get knocked aside by a rolling boulder or who knows what else.

Or take my previous example of a guard with a bow and arrow that needs to form an expectation of where his arrows will land. His line-testing isn't perfectly accurate and the game world is always changing, and he needs the arrows to tell him if they're landing in the wrong place.

To take a broader example, let's say you have two AI players in a real-time strategy game that are trying to coordinate their activities to attack the player. Furthermore, assume the implementation is such that each AI is running on a different client's machine in order to balance the load, so they have to communicate through network packets. In that case, computer player A might ask computer player B what its forces are doing, and B will answer "I'm sweeping northward toward coordinate (x,y = 297,118) with a force of attack value (a = 503.87) and expect them to arrive at time (t = 69.05)." Computer player A can then take that knowledge into account when it's planning its own attack and trying to coordinate with B ... but the fact of the matter is, B's troops may get crushed or substantially delayed, or they might arrive at the destination well ahead of schedule. Computer player A needs to then take those results into account.

So I agree that forming expectations of the player is one of the most important topics, particularly for a game like Halo. But there are also many cases where AIs need to form expectations of the results of their own actions and the plans of other AIs simply because a complex and dynamic game world -- involving plenty of randomness, lots of outcomes that can't feasibly be computed in advance (expensive physics calculations, for example) and one or more unpredictable human players -- will constantly interfere with even the best plans an AI can create.

Posted by: Paul T at November 18, 2005 09:52 AM

I suppose I should have said that the only thing worth making guesses about is the Player. You don't have to analyze the AI's movement vector and where the resources on the map are to fiure out that an AI is heading toward a vehicle because you told him to go there in the first place. Even if something stops him from getting there, you will know about it as soon as he does.

The same is true of the arrow that could be blocked in-flight. You have the world state and the simulation code. The arrow has no will of its own; It is completely predictable.

The only entity that is unpredictable and unknowable is the Player, so he is the only thing you have to guess about. Well, assuming there isn't a ton of actual randomness in your physics code... but that would belong in another blog.

Posted by: Jaime at November 28, 2005 10:40 PM

Let's say the chandelier in my example is swinging back and forth on a chain, such that my guard's line-testing indicates that he has a clear shot at the moment he decides to fire, but when the arrow is actually in flight 2.3 seconds later, the chandelier has swung back such that the arrow hits it.

You're saying I should run the physics system for all the potentially colliding objects in the game world (since I have no way of knowing exactly which objects the arrow could potentially hit) for several seconds forward in time at the moment I do my raycasting ... rather than simply going with line-testing, assuming that will be good enough in 99% of all cases, and telling the arrow "hey, let me know if you hit anything" as a backup plan?

I don't think it's realistic to perform physics simulation as part of AI decision-making code except in highly constrained special cases. As game worlds grow more complex and include larger numbers of complex physically-simulated interacting game objects and larger numbers of AIs that need to make decisions in real-time, that sort of thing seems enormously costly for very little return. Even if a PS3/Revolution/Xbox360 is able to handle that sort of thing without a frame rate hit, I'd argue that the processing power is probably better spent on things the user will notice.

Posted by: Paul T at November 29, 2005 04:48 PM

...

Of course not. My point is that when your callback from the arrow informs the AI that it is not hitting the intended target, it's not a _guess_. Therefore you are not, strictly speaking, forming an expectation, you are just using information available in the world state.

I guess you could call deciding to change position based on the fact that your bullets are not hitting your target an "expectation" that you will contine to fail to hit your target in the future, but that seems like a stretch. Even in a case where you _did_ use the physics code to predict the future (say, so you could avoid the eventual landing place of a grenade that was being thrown at you) I wouldn't call it a proper expectation.

Maybe the key factor is that in order to be really interesting, an expectation needs to have a chance of being wrong, and therefore being manipulated. If the Player can trick an AI into exposing itself out of cover because that AI expected him to try to pick up the Rocket Launcher, then _that_ is an expectation worth creating.

Posted by: Jaime at November 29, 2005 11:35 PM

> My point is that when your callback from the arrow
> informs the AI that it is not hitting the intended
> target, it's not a _guess_. Therefore you are not,
> strictly speaking, forming an expectation

Right -- The "expectation" in this case is the guard's initial belief that if he fires the arrow, it will hit the player (or at least, hit the intended target point). The feedback from the arrow back to the guard saying "whoops, I hit the chandelier" is just a violation of that expectation.

Posted by: Paul T at November 30, 2005 08:36 AM