Sign in to follow this  
Followers 0
priyesh

help me understand utility AI

35 posts in this topic

I've been designing a survival game while taking inspiration from the NPCs of RimWorld and Prison Architect. (And to some extent more AAA examples like The Sims, as well as rougher examples like Dwarf Fortress).

It seems like a utility or needs based AI might be a good way to help the AI manage a variety of goals, and lead to some dynamic behaviors.

Pardon my meanderings, but I'm trying to understand how this works, and if utility AI is even the right approach

FOOD

Let’s just say I have a “hunger” function that helps AIs manage their food supply.

On a basic level, hunger gets low enough (high enough?) then the character should eat from their food supply.

But what if they have no food? Obviously they should look for some. But you’d be pretty dumb if you waited until you had absolutely no food before you started looking.

The answer is that the AI should look for food BEFORE they’re out of food.

So now my utility function isn’t hunger. My character is going to eat regularly and this can be an automated (unintelligent) behavior. My utility function should be supply.

My utility function for supply: as my food supply goes down, the utility of food goes up. At a certain threshold, it pushes a character to look for food.

But is that dumb as well? The real key is if I have enough food to make a safe journey.

So I design the supply function as: only look for food if I don’t have enough to make the journey.

But this sounds a lot more like a very static behavior tree than a utility function. The agent isn’t really figuring anything out so much as I’m figuring it out for him, and hard coding it.

What am I missing?

RETREAT

Another example I’m having trouble with…

I create a utility function for retreating from battle. On a basic level, it compares the defending NPC’s hitpoints to the attacking NPC’s damage per second. If the threat of death is high enough, then flee.

But an NPC shouldn’t flee if it can kill the enemy before the enemy kills them. So I factor that into the function. Compare the NPC’s “time to die” against another NPC’s “time to die”. Maybe scale the function so the difference matters more when my time to die is small, but allows more uncertainty and risk taking when my time to die is big.

But then I need to factor in the other idiots on the battlefield. Being surrounded by a friendly militia is no reason to flee, whereas I’d feel differently if I saw an enemy army coming over a hill.

What happens if alliances and relationships can change? I suppose an NPC could walk into a trap, thinking they are safe around their friends, when actually it’s a mutiny waiting to happen.

But some smarter NPCs should be able to estimate the threat by looking at the souring mood of their estranged allies and say “I’m going to get out of here before it gets really ugly”.

Does this make my utility function for retreat so convoluted that it no longer represents anything? I’m not sure I understand the best way to do this.

0

Share this post


Link to post
Share on other sites

What am I missing?

 

You're missing the fact that you're attempting to be more intelligent than most of these games are. :) In the first case, you're mostly talking about simple planning behaviour, where the need for X causes an agent to consider several actions to see which ones might satisfy X, or which might open up successive actions to get to the same goal. That's a reasonable approach but is not necessary in most cases. Frob has pointed out how, with a few simple hard-coded rules from the developers, a single motivation or need can increase the desire to perform the action most likely to solve that need.

 

In the combat case, you seem worried about the complexity of the retreat utility, but why? Put in as many factors as you feel are relevant. The hard part is balancing them together, and then balancing them against other potential actions.

0

Share this post


Link to post
Share on other sites

In The Sims there are a set of motives.  The player sees six or eight of them, but there are a bunch of hidden motives never visible to the player. It slowly grew over time, at the end of The Sims 3 I seem to recall into the hundreds. There are also the sets of buffs/debuffs, including an enormous number of hidden ones, added for all kinds of subtle and non-subtle conditions.

...

 

As for your retreating function, it sounds like similar motives could easily be used. Maybe a buff when surrounded by 3+ allies ("military support") , and another buff when surrounded by 10+ allies ("feeling invincible"), and maybe another for special orders ("last stand").  You might have a buff added when fighting if you are doing more damage than you are taking ("winning fight"), and conversely, a buff when you are taking more than you are giving ("losing fight").  The the character's motivation for leaving the fight (low HP, losing fight buff) gets compared against the motivation for staying in the fight (feeling invincible, last stand) to determine if they fight to the death or flee with the last shred of HP.  You could even put in combinations: last stand + losing fight + feeling invincible means that since there are 10 other people around you should back off and let others fight. 

 

 

The breakdown of the Sims makes a ton of sense and lines up with some very surface level breakdowns I've read. It's crazy to think the most detailed explanation I've read was in a reply on a forum post less than a day after I asked.

Also thanks for applying it to my example. This is supremely helpful.

 

A player doesn't see the code, he/she only sees what the AI actually does, ie the result of those computations.

 

 

In the combat case, you seem worried about the complexity of the retreat utility, but why? Put in as many factors as you feel are relevant. The hard part is balancing them together, and then balancing them against other potential actions.

 

I like how The Sims shows you what an NPC's motives are. Now that I understand that The Sims is actually way more complex "under the hood" and only reveals a few of the key utility functions, I should just figure out which utility functions to reveal, and which to leave "under the hood".

 

My last question is the best practice for manage multiple behaviors from the same utility function. For example, what if I wanted the "retreat" motive to trigger three different behaviors: "call for help", "take cover and heal", "get the actual hell out of there". Would I just wait until the "retreat" motive becomes high enough and then trigger some kind of behavior tree or planner, which would then decide from that list of three actions? Or could I do this entirely from utility just based on different thresholds? Or is this the reason that I might separate the  "retreat" motive into separate utility functions for summoning vs healing vs retreating?

Edited by priyesh
0

Share this post


Link to post
Share on other sites

what if I wanted the "retreat" motive to trigger three different behaviors: "call for help", "take cover and heal", "get the actual hell out of there"

 

There are many ways to approach this.

 

One way would be to have a concept of a high level activity ("Retreat") which contains a sequence of low level actions ("Call for help", "Take cover", "Heal", "Leave the area"). If you have a lot of systems that tend to have these sequences or something similar, there is a good argument for using utility systems to pick basic high level activities and for behaviour trees to handle the individual actions.

 

Another way would be to incorporate these behaviours into the utility system. The desire to call for help will be affected by whether there is anybody around to hear it. The desire to take cover will depend on whether there is any available. The desire to flee the area will depend on how dangerous the current area is. Once you feed these into the system, you have a variety of different ways to respond to the current situation.

1

Share this post


Link to post
Share on other sites

Since I (and Apoch) am buried at GDC right now, I'm glad we have people like Kylotan and Frob to help. Thanks guys... it's getting to the point where I can't answer every utility question myself!

0

Share this post


Link to post
Share on other sites

Posted (edited)

But this sounds a lot more like a very static behavior tree than a utility function.

 

no - when "go get groceries" gets a high enough score, that's what you do - just like in real life! i just got back from a run to food king myself! <g>   That's how all behaviors in a utility system work. A properly programmed one is REALLY efficient, pretty much always making the "best" move -  so good in fact, apparently the scores are sometimes kept close to introduce some random behavior other than "best move always".  IADaveMark could probably tell you more about that.  I think there may be something on Gamasutra about that as well. I remember seeing something somewhere.

Does this make my utility function for retreat so convoluted that it no longer represents anything? I’m not sure I understand the best way to do this.

no, it just makes your scoring formulas a bit more complex and in-depth - probably leading to "better" choices.

this can be implemented using a number of different systems. i personally handle such things with a hierarchy of decision trees and/or state machines.  similar to a utility system, but instead of scoring all possible moves, then selecting the winner, you consider the moves one by one from most to least important, and take the first move that is appropriate.   considering moves in order from most to least important is akin to assigning higher scores to more vs less important moves in a utility system. IE you get the same basic results.

>> Or is this the reason that I might separate the  "retreat" motive into separate utility functions for summoning vs healing vs retreating?

think about the situation. you're in a firefight. its not going well.  what rules apply?

1. if you have backup, call for help.  

2. if you're taking fire, seek cover.  

3. if you need to heal, try to heal. i say try because you may be out of potions or mana or whatever.

4. if you're way outnumbered / outgunned, retreat.

so there are the rules for four different behaviors: call for help, seek cover, heal, and retreat. 

they can be implemented via a utility system, if-then-else statements, or whatever.

with my ai, i would first do the call for backup, if i had backup, and hadn't already called them.   then it depends on whether you can heal and move at the same time. if you can heal and move at the same time, i would try to heal if necessary, while seeking cover or retreating if needed.  if you can't heal and move, then retreat to heal would probably come first, followed by retreat from superior forces, followed by seek cover if taking fire, followed by non-retreat behaviors, such as reload or attack.   Note that retreat from superior forces takes precedence over seek cover from taking fire. unless you want to get REALLY smart - and take cover until a break in the fire, then retreat.   This is actually quite easy. instead of triggering a "run away!" behavior, and perhaps getting shot in the back - you trigger a "covered retreat" behavior that uses the algo:  if taking fire, seek cover, else retreat, until reached safe area.

 

as you can see, often you may want to do multiple behaviors simultaneously, such as issuing orders, moving, and healing all at once. i often find it best to have a little AI system for each set of independent behaviors.  I also find it helps to have an overall AI system that determines general moves, and then lower level AI systems that implement the general moves in the best way possible. for each of these systems in the hierarchy, i select the most appropriate (and simplest possible) AI type, which is usually a decision tree for prioritized behaviors, or a finite state machine for non-prioritized (IE random sandboxing type) behaviors. but utility systems are a perfectly valid option as well - perhaps a main system, with subsystems, and a few small side systems for certain behaviors that can occur in parallel.  so a main utility system may choose heal over attack, then a healing utility sub-system might decide spells vs various potions in the player's inventory, or whatever - IE how to heal.

Edited by Norman Barrows
1

Share this post


Link to post
Share on other sites

Posted (edited)

Getting some incredible feedback here. It's greatly appreciated. While I have so many brilliant people, I wanna ask...

How do you handle "two birds, one stone" types of problem solving using utility AI? That is, there are two completely different utility functions competing for an NPC's attention, and in isolation, they will act on the highest one. But in actuality, there is a solution that allows them to maximize their utility in aggregate: doing both.

Imagine something inspired by the Nemesys system from Shadows of Mordor. The AI calculates the utility of fighting different peers for status, and ranks them:

  • Fight Captain Cameron: 70 (not a sure thing, but fairly good chance of beating him and rising up)
  • Fight Captain Donald: 60 (almost as good)
  • Fight Captain Ernest: 30 (too tough)

But in addition to fighting for rank within the military... there is also the issue of fighting for rank within your family. Sort of a Game of Thrones / Crusader Kings fight for succession.

  • Kill Brother Adam: 65 (some risk, but still good)
  • Kill Brother Donald: 58 (slightly less good)
  • Kill Brother Garth: 20 (very easily goes wrong)

Now, on a very superficial level, the best chance to rise in the military is to challenge Cameron, and the best chance to rise in the line of succession is to murder Adam. But there's a two-birds-one-stone solution here: challenge Donald -- a rival captain and also your brother. Challenge him for military rank, and then fight him until death/exile for your birthright.

Challenging Donald doesn't make sense when you consider those goals separately, because he doesn't have the highest utility for either goal. But when I consider them together, I might realize that two fairly challenging fights doesn't have as much utility as going for one slightly harder fight.

This might not be the best example, but I can think of others. There's a high utility on combat training, but right now I'm starving, so there's a higher utility on finding food. But in theory, if I hunted a wild boar, it might take me a little longer to find food, but I'd also get my combat training in.

Another example: there's a high utility on recruiting an ally, but I have so many enemies that the utility of eliminating an enemy is higher. But in theory, there is one enemy who hates me over a misunderstanding that could be cleared up, and then he might be willing to hire himself out as my ally. I could eliminate an enemy and gain an ally within the same interaction.

Is this where a planning-AI needs to come in?

Edited by priyesh
0

Share this post


Link to post
Share on other sites

Those are not typically done by the game AI.

 

Instead, those choices are usually given to the player in order to give the player a better experience.  The computer AI generally doesn't care about that sort of thing.  The AI usually is not the one playing the story, they're the ones being acted upon by the player.

 

If there is a need for something specific like that in the game design, the specific requirements should be identified and communicated. Then the individual tasks will be given a scoring function that matches their flow relative to the story's rules.

0

Share this post


Link to post
Share on other sites

Posted (edited)

I mean, something I've frequently hacked together (and frequently heard) is that randomness can sometimes appear intelligent. If the NPC occasionally picks the second best choice in a computational sense, they might actually stumble onto the actual best choice in a strategic sense, and appear to outwit the player (not to mention other AIs).

Still, I'm curious if there is a computational way to notice when there's more utility in doing the second best thing because it actually helps advance you towards another goal.

Edited by priyesh
0

Share this post


Link to post
Share on other sites

How do you handle "two birds, one stone" types of problem solving using utility AI?

That's really a question for AIDaveMark, he's the local expert here. 

I would think that you might have 3 functions, one for 2 birds one stone, one for military advancement, and one for succession advancement.  2 birds would of course score highest of the three. That way it would go for 2 birds first, or fall back to military or succession targets if appropriate. 

Looks like Kylotan has the 2 birds part for you already.

if I hunted a wild boar, it might take me a little longer to find food, but I'd also get my combat training in.

figure both "chance to find food" and "combat training gained" into a scoring function. and weight that vs just eating or just training. chance of success will be the decision point.

Another example: there's a high utility on recruiting an ally

recruit action gets a higher score when it turns an enemy to your side, high enough that it beats attacking.   then you weigh recruiting vs attacking. you will always recruit all enemies you can before attacking the remaining ones.

As you can see, the how-to is usually pretty straight forward.  getting the numbers to all work out, perhaps a bit more work.  I personally find translating rules to decision trees to perhaps be a bit more straight forward. but the two are very similar. tweaking the conditions of a decision tree is akin to tweaking the functions of a utility system. in some cases the condition checks and utility functions might even be more or less identical in their effects. the only real difference in behavior is that utility systems score all moves every time, which means you don't have to worry about doing the checks based on behavior priority. instead, you have to worry about the ranges of the scores produced, which determines the priorities of behaviors.  two different ways to achieve the same basic thing.

1

Share this post


Link to post
Share on other sites

This is incredible guys. Open to other solutions and ideas, obviously. But I can work with this.

The idea that I might have special utility functions that look for synergies seems like a good enough solution. I'm getting used to the idea that I might have hundreds of utility functions. It's going to be a daunting thing to tweak and balance... but in some ways, fairly straightforward to program.

0

Share this post


Link to post
Share on other sites

Posted (edited)

Usually only a few are needed, but they need to be based on data to be shared.

 

Generally each interaction has a collection of data for the motives that drive it, there is only a single scoring function needed.  The function takes a collection of motivators and the actor being compared, runs through the list, and computes a single number indicating motive for the action.

You don't need hundreds of utility functions, instead you need data values you can pass to a single function.

Edited by frob
0

Share this post


Link to post
Share on other sites

That's an important distinction, yeah. Maybe a 20 or so utility functions, but perhaps hundreds of "motivators".

A thought occurred to me because I really like the architecture that Kylotan suggested:

 

There are many ways to approach this.

 

One way would be to have a concept of a high level activity ("Retreat") which contains a sequence of low level actions ("Call for help", "Take cover", "Heal", "Leave the area"). If you have a lot of systems that tend to have these sequences or something similar, there is a good argument for using utility systems to pick basic high level activities and for behaviour trees to handle the individual actions.

 

Having separate utility functions for every action is going to be highly redundant. This might be a moment where I could bring in some of those synergies.

Let's say I have a utility function called "challenge someone for rank". It's calculated as the largest expected value of victory against someone my rank or higher. If I reach a certain threshold, I trigger a behavior tree that selects between several actions.

The obvious action is "challenge the best option for victory".

But the system would also consider actions that challenge the second best option under a few circumstances, effectively aggregating the motivations. Maybe the next best challenge would also kill someone I hate, or also kill a rival on the line of succession.

Similar idea for the food vs combat example. If I'm starving, trigger a behavior tree that selects from several food-finding options. But in addition to "go run around looking for food", the system would also consider "if you're in a combat quest to kill something that is made of delicious meat, just carry on".

I'm reluctant to invent my own solutions because I'm not arrogant enough to think I've figured out something no one else has. But this seems in line with what a few other people are suggesting, and so probably has some basis in good design?

0

Share this post


Link to post
Share on other sites

You're over-complicating this.

 

Did you watch the videos I linked above?

1

Share this post


Link to post
Share on other sites

I did, actually, and it's much appreciated. It seems like common practice is to come up with a utility function for every action... but that seems like a LOT of actions. Let alone if I start creating utility functions for "two-in-one" actions.

0

Share this post


Link to post
Share on other sites

So how would you incorporate a potential decision into the rest in order to pick the one with the best score if you don't score it in the first place? You have to score them somehow. And the most relevant thing to do is to score them on what might be important regarding whether you would make that decision or not. That's pretty much the entire point of utility based AI. 

0

Share this post


Link to post
Share on other sites

It seems like common practice is to come up with a utility function for every action... but that seems like a LOT of actions. Let alone if I start creating utility functions for "two-in-one" actions.
 

 

You can create functions like that, just like you can create unique classes for everything rather than using data variables, you can hard code all data, you can write programs that avoid standard data functions at all.

 

But most developers choose not to.

 

Most developers choose to create a small number of functions that operate on data, then allow other people --- in this case game designers and level designers and such --- to modify the data.  The simple function takes whatever data it is given and computes a score from the data.

 

The AI's job is to look at the top few scores, maybe the top 1 score or maybe the top 1% or 5% of the scores, and use that as the decision.

 

You can, if you choose, write a unique utility function for every possible action in your game.  I would advise against it, instead preferring the pattern of having everything driven by simple pieces of data.  A collection of modifiers as data along with a collection of the system's state as data, the result is a scalar value. But even so, you can do it as a bunch of functions if you choose.

0

Share this post


Link to post
Share on other sites

Posted (edited)

 

It seems like common practice is to come up with a utility function for every action... but that seems like a LOT of actions. Let alone if I start creating utility functions for "two-in-one" actions.
 

You can, if you choose, write a unique utility function for every possible action in your game.  I would advise against it, instead preferring the pattern of having everything driven by simple pieces of data.  A collection of modifiers as data along with a collection of the system's state as data, the result is a scalar value. But even so, you can do it as a bunch of functions if you choose.

 

Yeah, I think that makes more sense to me. Use utility to set goals, which drive a "family" of actions. Goals like "find food", "fall back", "rise in rank", and "take revenge".

  • "Find food" might simply eat what the NPC has, or hunt or forage, or even try to ration what food the NPC has left, depending on availability.
  • "Fall back" might just take cover or call for help if those options make sense, but full on retreat is always a last resort.
  • "Rise in rank" might challenge a weak peer in the hierarchy, or might build an army to ambush him, or might detour the NPC to train up until they're ready.
  • "Take revenge" might attack someone on the spot if no enemies/guards will stop them, but otherwise they might order an assassination if they have that power, or consider them an enemy and bide their time, or simply deal with it through insult or humiliation.

 

So how would you incorporate a potential decision into the rest in order to pick the one with the best score if you don't score it in the first place? You have to score them somehow. And the most relevant thing to do is to score them on what might be important regarding whether you would make that decision or not. That's pretty much the entire point of utility based AI. 

 

... but then I'm sort of seeing the other point. Once I have determined a suitable goal, am I going to pick a suitable action for that goal from a behavior tree -- essentially hard coded logic? Or should I look at a more fluid series of utility scores? The latter makes sense: once the NPC decides their goal is to rise in rank, I do a more detailed utility scoring of the top two or three people they could challenge, and discover that one of them is also a hated enemy.

(I really appreciate all this guidance, btw.)

I guess my last question: is this sort of "two stage analysis" something that actually has logical problem solving value, leading to better decisions and reducing computational complexity? Or will implementing it be mathematically equivalent to just considering it all at once -- all the ways of finding food vs all the ways of taking revenge vs all the was of rising in rank (etc)?

Edited by priyesh
0

Share this post


Link to post
Share on other sites
It is one function, you pass data for the motives, you pass data for how the action satisfies the motives.

If your motives indicate food satisfies the goal, they will score high. If your motives indicate hunting one satisfies the goal, they will score high. If your motives indicate that targeting a specific character for attack satisfies the goal, those actions will score high.

The videos linked to earlier explain it all well enough, and it is quite portable. Pass in the motives, pass in the current state, and the result is a number that say how strongly the two match. Take the highest score, or perhaps choose randomly among the top few highest scores.
0

Share this post


Link to post
Share on other sites

Let's say I have a utility function called "challenge someone for rank". It's calculated as the largest expected value of victory against someone my rank or higher. If I reach a certain threshold, I trigger a behavior tree that selects between several actions.
The obvious action is "challenge the best option for victory".


You didn't understand my previous post. I thought I was quite specific in that you would not have different actions for different motivations. You have different actions and they each may satisfy any, some, or all of your motivations, and it's that which is represented in the utility function.

This is why your fear about having to maintain too many utility functions is misplaced; you don't need a different function for every combination of action and motivation. Each action has a function, and that includes all motivations or other influences on utility.

Note that 'utility function' uses the word function in the mathematical term; i.e. it maps an input (the action, and the current environment) to an output (utility score). It doesn't mean function in computer programming terms, where there must be 1 coded function for each one.
 

But the system would also consider actions that challenge the second best option under a few circumstances


No, it should consider them under ALL circumstances. The whole point is that the system considers all these possibilities, then picks the one that scores the highest.

0

Share this post


Link to post
Share on other sites

Thanks guys... this is helping me to get passed my intuitions.

Processing the problem myself, I'd want to break it apart into two stages (1: what's the goal that satisfies my main needs? 2: what's the action that satisfies the goal, and maybe even knocks off a few other needs in the process). But it seems like I could just flatten it / skip right to stage two: (for every action i could take, what is each action's impact on my needs/goals)

Like I said, it seems like a lot of functions -- one for every action. But it seems like any method of problem solving would get to that level of detail eventually.

0

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  
Followers 0