You ever find yourself in a situation where you have too many good ideas? And you just don't know
which one to pick? This isn't just something that plagues poor fleshy human brains, but it impacts
Artificial Intelligence too. And sometimes for AI in a video game, this can be a bit of a burden.
There's so many different things they could do right now, many of them seem like a bad idea,
but quite a few them seem like they have some promise. The player is running towards
a non-player character, they could go to cover, they could attack, throw a projectile, run away,
what do they do? One of those actions might seem like a good idea in some situations,
but in others it could be suicide. How do we know how good this idea
is at a given point in time? I'm Tommy Thompson and this episode of AI 101, we're going to take
a look at Utility AI - a process of scoring just how good that idea is, before you try and do it.
So why would you have something like Utility AI? Well a lot of the other systems that we've
explored throughout this channel, be it in episodes of AI and Games or here in AI 101,
are largely focussed on selecting actions based on context.
Finite State Machines change what action is being executed based on an event in the world
transitioning the state of the system. So we may go from an NPC in Half-Life patrolling the
environment to attacking the player because they saw us. Meanwhile both the Behaviour Trees of
the Halo series, and the Goal Oriented Action Planning system of F.E.A.R. are very good at
finding different opportunities we can explore and validating whether they're going to be the best
thing for us to do. Behaviour Trees have paths of execution that that dictate what to do based on
the conditions of the world, whereas Goal Oriented Action Planning will try to satisfy a long-term
goal by coming up with a bunch of actions that - when executed in a sequence - will help attain it.
So in amongst all of this, there is an explicit idea that some actions
are more valuable than others and whether those actions are valuable to us is going
to be impacted by the current circumstance. An action to throw a grenade can be great
if the player is in front of us behind cover, but is completely useless outside of combat,
beyond the throwing range of the character or if the players location is unknown.
In theory, every action designed in a game has value, but that doesn't make it useful. Games
are highly volatile, dynamic and random systems: there are so many different things that happen
and anticipating them can be almost impossible. This is where the idea of utility comes into play:
we can consider an actions utility to be its desirability given the current context of play.
What does that mean? Well say we have a non-player character who can use an action
to attack the player with a ranged weapon to do 30 damage, or to use a melee attack with 50 damage.
If we consider their value in applying damage, then the melee attack is more powerful. But,
the utility of these actions is highly dependant on things like ammunition for the ranged weapon,
the distance of the target, the probability that the attack will be successful,
and whether the player is going to damage the NPC before we finish the attack.
So the melee attack will have much higher utlity if the player is closeby and ready to apply,
but a very low utility at a distance. Meanwhile, the ranged attack's utility
is going to vary depending on the location of the player the ammunition and 101 other
things happening in the game. Ultimately, the value of each action never changes:
one does 30 damage, the other does 50. But while those values can influence their utility,
the context within which we want to execute them will also have an impact.
As a result, a lot of AI systems actually have a Utility layer in them somewhere,
while using the likes of Finite State Machines, Behaviour Trees or Planning.
Because while those systems identify the state of the world and handle the execution of actions,
sometimes there are lots of totally valid and sensible actions to take and you just
need to pick the best one. As we'll see later in this video, sometimes a game will
use utility AI to run an entire AI decision making system, because it means as a designer
you can decide just how useful that action is going to be at different points in time.
Now that we have an idea of utility, how do you design and calculate it?
The key thing to understand is that utility is just a number.
You design an algorithm that calculates an output that is designed to represent the
utility of the action in that situation. It's really that straightforward, you can take a
piece of information about the current state of the game, and apply a function on it in order to
determine a number. But the art of the process is really all about the mathematics behind it.
Now, I appreciate this can be a little boring,
but you can build those mathematical functions such that the utility values being generated
can change differently based on how we process the information.
Consider for example, we have a simple utility calculation for attacking an enemy.
We can attack anyone we like, but we're only going to prioritise targets based on how far away
they are from the non-player character. It's useful to set a maximum distance,
that way you set the upper limit of what is going to score any value.
By doing this, you actually normalises it between 0 and 1. So now you can create
a utility that scores a value closer to 1 when the character is closer to the player,
the higher the value. By doing this, you create a linear equation that looks like this.
It slowly ramps up and shows this gradual line from low to high value.
But of course you can do so much more with it, you can add an exponent that will enable a curve.
This flattens out the more distant values, and places a stronger emphasis on closer distances.
With a bit of math, you can create a variety of linear, quadratic or logistic curves.
You could even make it piecewise linear, meaning you custom build the curve, setting the x values
and then calculate the y by linear interpolating between the two x values closest to your input.
This is a really simple example, but you can continue to build it,
you could factor in movement speeds, enemy health values, defense ratings and more.
You don't even have to normalise it between 0 and 1 (though that sometimes helps).
So to give you some more context of how it's actually used,
let's look at a couple of examples from popular AAA games that use Utility AI systems.
Arguably the most high-profile title that has used Utility AI over the years is The Sims:
the life simulation series that is one of the most successful video game franchises of all time.
The Sims live their lives in these rich and interesting worlds full of
activities for them to complete. They interact with the world around them,
be it objects in the environment or other Sims and this brings us to how Utility AI is used:
it helps the Sims figure out what they should actually be doing.
The Sims adopts utility AI for a variety of different functions,
be it the activities player has suggested,
or the urgent desires they may have at that time. But an interesting design challenge of
the Sims is that having them simply do the thing with the highest utility every time is going to
deny them of the more realistic, bordering on human-like behaviour that players expect.
The solution to this is a process known as bucketing. Possible actions such as eating
at the table, watching tv, or strutting your stuff on the dance floor have different priorities based
on the current context of the game. So in the Sims, motives are bucketed based on utility value.
Then only the highest priority motives are considered. The action then selected is devised
by looking at all the possible interactions in proximity that satisfy that motive,
and are also scored accordingly. This ensures that a thirsty or hungry Sim always seeks to
address that first, and won't wind up dying of hunger cus they were wasting away on the couch.
The use of Utility AI is but one of several systems that run under the hood of The Sims.
But fear not, we will be back at a later date with a full episode on AI and Games
going into much more detail on the range of different AI systems adopted in the series.
Next up, let's take a look at a real-time combat game and an interesting example can
be found in BioWare's 2014 release Dragon Age: Inquisition and the companion AI characters.
Each of your companion characters have a variety of different abilities at their disposal. They
use a combination of weapons and magic attacks to help you bring the fight to your aggressors,
and the player can hot-swap between them during combat.
One of the big challenges in making effective companion AI like this is ensuring they're doing
something that proves useful to the larger fight, while also not exhausting their own
resources. Each character has health, stamina and mana like the player does,
and they need to use that sparingly. So knowing whether it makes sense to exhaust their remaining
stamina or mana is critical to survival. Plus it's useful if they can identify different
ways in which an action can be executed. A good example of this is the 'charging bull',
an ability used by the warrior class. It's a useful action for getting yourself
into the heat of battle, doing some damage and knocking the enemy off balance. But conversely,
it's also a useful ability when you're overwhelmed and need to escape. So utility AI is used not just
to assess whether an action makes sense given your available stamina or mana, but it also
helps to establish how abilities can be applied to help the character based on their situation.
Dragon Age's solution to this is a system known as behaviour snippets. Each character in the game can
register interest in a behaviour snippet based on a weapon or ability that they have equipped.
Each behaviour snippet provides all the information needed to evaluate an ability
at a given point in time, as well as the utility equation to calculate its worth.
The are dozens of these behaviour snippets put together by designers, with the average
AI character in the game equipping anywhere from 10-20 snippets at any one time.
The utility calculation in Dragon Age Inquisition for each behaviour snippet is actually achieved
through use of a modified behaviour tree. It includes all the logic needed to calculate
the utility score for that ability. Plus if an ability can be used on a particular enemy, it will
calculate the score for using that ability against each enemy in proximity. Hence while a particular
action might be useless against that enemy at distance, it can be extremely useful up close.
What's more, all utility scores in Inquisition have a much broader scale of possible values.
With idle actions are capped at low values of around 20, combat moves have a higher lower and
upper limit. This is because designers have a lot of control and fleixibility in the design
of each ability and it's usefulness in context and capping specific abilities at certain thresholds
means that characters won't do something completely inappropriate in the heat of battle.
And last but not least, let's take a look at a more contemporary example
found in Total War: Three Kingdoms released by Creative Assembly in 2019.
Total War's diplomacy systems are built to consider forging alliances or trade
agreements with other players. To do this, the diplomacy AI has an entire deal generation
and evaluation system, that is designed to consider a variety of facets of each faction
and the current condition of the world. These deals result in specific actions
that are then evaluated using utility AI to determine their overall importance.
The deal generation process considers elements such as their current relationship with another
faction, the diplomatic consequences of forging this deal (given it may upset other allies or
nearby factions), the potential strength that ally would bring to their overall
tactical and diplomatic capabilities and much more. Each deal type consequently
has a mechanism to evaluate it by calculating its overall utility.
One of the interesting challenges faced for this system is that number of possible actions
the deal generation could make is so large, the designers worked to prune out specific deals it
could try to generate. The reason for this is twofold: on one hand there is some logic that
prevents specific deals being evaluated because the designers consider them irrelevant but it's
also a performance optimisation. Given there are so many possible deals it could create,
the overall decision making time would balloon to ridiculous proportions and slow down the turn time
for the AI players. Hence by preventing certain deals being generated, it keeps those wait times
down, because of course the only thing worse than a Total War player, is a grumpy Total War player.
In the GDC 2021 presentation by Csaba Toth and Duygu Cakmak, the developers make it a
point to highlight they do not consider the utility score as the value of that action,
but rather it's importance in the context of the current game circumstances. While this
might sound like a trivial distinction, it's critical to the evaluation process
given these actions are compared against one another when deciding the best one to choose.
So it could be a deal that looks good on paper is ignored because in the context of the game state,
it's not as important as others given the long term ramifications of the diplomacy at play.
This is of course not the first time we've looked at the AI of the Total War series on this channel.
And if you're interested in seeing how the AI of the franchise evolved from 2000's Shogun:
Total War all the way to Total War: Warhammer in 2015, then be sure to check out episodes
21 through 25 of AI and Games, as I walk you the big changes that took place.
But of course it isn't just games such as these that embrace Utility AI,
given as mentioned it can appear in other games with existing AI systems.
As detailed in our AI 101 on FEAR, the game has a mechanism on scoring the validity of
the goals that the NPCs should be trying to solve. This is essentially a utility system,
given the highest scoring goal in the codebase is then selected for the planner to try and solve.
Plus in that small little indie game you've probably never heard of - Alien
Isolation - utility is used in the behaviour tree to determine the significance of a given proposed
task that has been offered or a stimulus it has observed, dictating its priority for response.
But also the higher priority tells us a little more about how it should respond. When the alien
is more passive, the movement is slower, the animation blends are more gradual and it takes
its time completing actions it was already doing. However, high priority actions such as responding
to gunshots and other loud noises, or seeing the player directly, will resultin in a high priority
score, meaning it drops what its down and moves to the point of disturbance as quickly as possible.
Utility AI provides a unique means to assess the value of a given action for an AI player.
It can provide designers with a mechanism to more effectively express just how useful
a given action is in a game and allow it to adapt to changes as they happen.
Thanks for watching this episode of AI 101 on Utility AI. As mentioned earlier, there
are a variety of different approaches to allow AI characters to make intelligent decisions in games,
and that's what this series is all about. Be sure to check back on the other episodes
in this series on the likes of finite state machines, behaviour trees, AI planning and more.
This episode of AI 101 was voted for by our crowdfunding supporters.
To have your say on future episodes, watch them early and more,
please support the AI and Games patreon via the links on screen and in the description.