Utility Systems and Game AI

Overview

So over the past month or so I have been talking with several people at Digipen about AI and I started to get a lot of blank stares when I brought up the term utility. I would mention that I used it in my game and the response I would get was "Utility? what's that? How does that work?" So I figured if not a lot of people know about it maybe I should write about it to help educated and interest people about a potential AI system that can be used in their games.

I will talk about a general overview of utility, the basics behind utility, and how it's used and how it works.

Utility

So utility has been used in games before and isn't anything super new, which was surprising when I found out not a lot of people had heard of it, unless we are talking about Dave Mark's infinite axis utility system which I found out at this years GDC (2013) then it might be a little newer, but we will talk about this later. Some games that use utility are The Sims 3, Section 8, and the new XCOM: Enemy Unknown game that exclusively used this for their game AI, so it's a very practical system to use in your game. Also I mentioned in my last post but there is a whole book about it called Behavioral Mathematics For Game AI by Dave Mark where I learned the most about this system as well as some lectures at GDC.

The Basics of Utility

Core Concept

The core concept behind utility is to take an arbitrary action and rate it using arbitrary values. What to you mean by this you might be asking?

Well let me give you an example, suppose that you are very hungry and you are deciding to order food or cook it yourself. On one hand you have  higher quality food (provided you are a good cook :) ) but it takes time and work that you might need, and on the other hand you can sacrifice said quality to order food and saves you some work. So how do you choose which one and based on what principals? Well maybe it depends on how hungry you really are, how much time you have, or how much work you are willing to put into making food. You then would combine all of these factors together all weighted differently and make a decision based on how low or high you felt in each of these categories. If you weren't very hungry, didn't might taking some time out of the day, and have plenty of time then you will probably cook food yourself, but on the other hand let's say those were all the same but this time maybe you don't have any time you might weight your time more valuable then the others and now maybe you don't eat or you order food. This is the idea behind utility is the scoring of these actions based on other factors in a real life example how about we look at how it could be applied in games.



Suppose you are making a Shooter or Adventure game where you have enemies choosing targets or taking cover. You will most likely have a list of potential targets or cover points to look through. For our example we will use target selection. Some things you might take into account are the target's current health, the threat level of the target, how many allies you have, how many allies the enemy has, and how far away the target is. You then search through all of the potential targets and score them based on these factors and how much they mean to your AI. For example maybe you have an AI that targets stronger enemies for you, then you might score higher values for each attribute so you would want the closest enemy with the highest threat level the most allies and the most health, and in this case your allies wouldn't need to be factored in. Each target would get rated and pushed into some container and then chosen based on which target had the highest score. Now you are probably saying now well this all makes sense in theory, but how do you actually score these attributes?

Because actions are scored based on many different variables it can lead to interesting results and can often lead to emergent behaviors. Make sure when you do this you have a method to debug and check the scores of each attribute where if something goes wrong you can see what attributes are skewing your results if the emergent behaviors are negatively affecting your game.

How Utility Works

Scoring Actions

Scoring these actions is easier then you might think and for my game Nexus it boiled down to four simple functions to actually score things. The idea behind scoring each attribute is to use graphs. The 4 graphs I've seen used are Quadratic, Linear, Logistic (or sigmoid), and Logit.


You may be unfamiliar with the last two so I'll explain them a bit. The Logistic graph is a S-shaped graph represented with the function  y = 1 / (1 + e^-x) also know as the sigmoid graph because of it's S-shaped curve. the special thing about this graph is it's natural asymptotes approach 0 and 1 in the y-axis and x increases which then yields a normalized result. The Logit is the same but the graph is rotated and the the range is in the x-axis and y increases and is represented using the function y = log( x / 1 -x). (I linked the graphs so if you want a better idea of what these graphs look like just click them).


The graphs are a crucial part of utility system in how it works and the most important part of it is keeping the values normalized. Finding the un-normalized or natural bounds of each attribute is up to you and your designers, for example distance can be different with no clear max value like health might have. In this case you must create a cut off value where any value greater then said max value is treated the same. This allows you to create a nice cut off point and make sure all of your values are normalized which should be done before you graph the function.


Another key component is making sure you understand how your graphs work and how you can manipulate the graphs by scaling, rotating, and translating them. This will allow you better control over the values, and since you want your values to be between (0,1) (which I will explain shortly) ideally you should experiment to see how your graph looks for normalized values. For example if you want the lowest score to yield 0.5 make sure you can transform your graph to represent that result.


You are probably wondering why do I care about keeping things normalized? Why not just graph them and combine the scores at the end without normalizing? Keeping the values normalized keeps each action in a standardized system i.e. between [0, 1]. This comes into to play also when you go to combine variables. You combine the variable you simply multiply each variable together and since everything is between [0, 1] you will only get results between [0, 1]. After you score and combine all of these factors together you can then store that value into the action as a score value and if you want you can even weight the actions by multiplying the score at the end. This will un-normalize the score but it's ok because the final score has been determined and this is used to prioritize the actions. For example you might weight attacking a target a higher priority then running away. These action will be sorted by score now and the action with the highest score is the action your AI should pick because it's the most appealing to your AI :)

Infinite Axis Utility System

 This was an idea that Dave Mark talked about during GDC to make the utility system more of a stand alone system. It follow many of the ideas mentioned above and I kinda explained utility in an Infinite Axis system to begin with, but I'll elaborate it a little more. The idea is that any action can have an infinite amount of axis (or variables or as I think of them sometimes as attributes/variables the action takes into account when scoring). My impression of this system and may not be the intention of the creator is it allows designers freedom to add whatever they need to use to tweak the AI. For example as the AI programmer I would create the set of actions that designer can chose from or that is needed for the game. Then functionally is then created so that they can register new axis or variables to the action and the appropriate graphs for each axis. Variables can be added or removed whenever needed and tweaked on the fly and the actions follow the same idea as before so they are selected by score based on whatever axis were created. 

Conclusion

Utility systems are a very interesting way to examine your AI and can put some interesting behaviors in your AI. If you are thinking about writing a Utility system for your game and found this interesting I highly recommend Dave Mark's book Behavioral Mathematics For Game AI. This is a good system for AI and I would like to see different types of games use this system or elements from it, and as I mentioned above XCOM almost exclusively used this system for their game.


As always if there are any questions feel free to post a comment or send me and e-mail at justinmaio01@gmail.com and I hope you enjoied reading this or at least learned something new :)

-Justin Maio