• FEATURED

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

## help me understand utility AI

35 replies to this topic

### #1priyesh  Members

Posted 28 February 2017 - 12:25 AM

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.

### #2Alberth  Members

Posted 28 February 2017 - 01:04 AM

A player doesn't see the code, he/she only sees what the AI actually does, ie the result of those computations. If a simple if-tree does the job, it's fine. I'd throw in some random, to get a little variation in behavior. For example, there is some x% chance it will go find more food, where x increases as the supply decreases.

Note that it is unlikely a player will see any pattern in AI behavior even without random, as there should be enough other problems in the game to distract him/her

For longer term planning-ish things, you can take a look at planners, where you attach points to each option that you have, and throw it all in an A*-like routine to find an order of next actions to do.

As for true intelligence, nobody managed that so far, so at some point any AI relies on hard-coded rules in some way eventually. It's thus mostly a matter of sufficiently hiding that from the player.

Edited by Alberth, 28 February 2017 - 01:04 AM.

### #3frob  Moderators

Posted 28 February 2017 - 01:29 AM

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.

Every object's interactions had a score function that looked at the motives chosen by designers. Some of the core interactions had score functions attached to hundreds of conditions, motive levels, and buffs. You see the hunger motive, and that gives an incentive to eat. You see a "hungry" buff added when the sim gets a little more peckish, and that adds yet another number to the score.  An additional buff when starving not only makes it more likely, but is also a default test in most interactions that causes non-nourishing interactions to be rejected or cancelled.  A starving sim will drop out of nearly every interaction except the few marked as things you can do while starving, like travel to location or eat or die.  But a sim that is merely hungry just gets a big multiplier to drive the motive up into the hundreds, then into the thousands, far outweighing nearly every other activity preference.

Another example is the sim's fatigue motive. It isn't visible, but when exercising the sims acquire or lose fatigue. Get too fatigued and the invisible motive kicks in, causing the sim to reject the action even if it isn't visible to the player.  A fatigued sim won't run home from the gym, but a sim that isn't fatigued and has a buff for running may prefer to jog home.

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.

Sometimes there are games that rely on machine learning, artificial neural nets, and other adaptive and training algorithms, but I feel they are best avoided. Those are difficult to tune and hard to make fun. Game designers just see a random-looking set of training data results and cannot adjust them in meaningful ways.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I occasionally write about assorted stuff.

### #4Kylotan  Moderators

Posted 28 February 2017 - 03:58 AM

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.

### #5priyesh  Members

Posted 28 February 2017 - 09:36 AM

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, 28 February 2017 - 09:37 AM.

### #6Kylotan  Moderators

Posted 28 February 2017 - 09:57 AM

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.

Posted 01 March 2017 - 09:47 AM

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!

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #8Norman Barrows  Members

Posted 01 March 2017 - 01:51 PM

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, 01 March 2017 - 02:39 PM.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

Posted 02 March 2017 - 11:18 AM

Just dropping this here.

http://www.gdcvault.com/play/1021848/Building-a-Better-Centaur-AI

http://intrinsicalgorithm.com/IAonAI/2013/02/both-my-gdc-lectures-on-utility-theory-free-on-gdc-vault/

Edited by IADaveMark, 02 March 2017 - 11:20 AM.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #10priyesh  Members

Posted 02 March 2017 - 03:12 PM

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, 02 March 2017 - 04:51 PM.

### #11frob  Moderators

Posted 02 March 2017 - 05:12 PM

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.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I occasionally write about assorted stuff.

### #12priyesh  Members

Posted 02 March 2017 - 07:39 PM

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, 02 March 2017 - 07:39 PM.

### #13Kylotan  Moderators

Posted 03 March 2017 - 04:40 AM

The "two birds one stone" example is formed strangely. For some reason you have split it up by Captain or Brother but that is not a property of the action, but a property of the motivation. Motivations are meant to be captured by the utility function, not the selection of actions. The real actions on offer here are:

• Kill Cameron: 70 + 0  = 70
• Kill Donald: 60 + 58 = 118
• Kill Ernest: 30 + 0 = 30
• Kill Adam: 0 + 65 = 65
• Kill Garth: 0 + 20 = 20

The first value in the sum is the status gain, the second value is the family rank gain. Applying a simple sum of the different motivations in this case (where killing non-family members gives you zero family rank, and killing family members gives you zero status by default) shows that Donald is clearly the best target.

(You don't have to use a simple Sum here; but you do need to consider all the motivations for performing a given action, and combine them in some way.)

Select between actions to perform; don't select between reasons to perform them.

### #14Norman Barrows  Members

Posted 03 March 2017 - 10:01 AM

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.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

### #15priyesh  Members

Posted 03 March 2017 - 10:45 AM

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.

### #16frob  Moderators

Posted 03 March 2017 - 10:55 AM

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, 03 March 2017 - 10:57 AM.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I occasionally write about assorted stuff.

### #17priyesh  Members

Posted 03 March 2017 - 07:04 PM

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?

Posted 04 March 2017 - 04:22 PM

You're over-complicating this.

Did you watch the videos I linked above?

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #19priyesh  Members

Posted 05 March 2017 - 01:43 AM

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.

Posted 05 March 2017 - 01:45 AM

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.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"