(This column originally appeared in the January 2011 edition of Game Developer Magazine.)
We have long been used to numbers in games. Thousands of years ago, when people first started playing games, the simple act of keeping score was dealt with in terms of numbers. Even before games, when people had to simply scratch by for food, numbers were an integral part. From how many rabbits the hunter killed to how many sling stones he had left in his pouch, numbers have been a part of competitive activity for all of history.
|âHeâs only mostly dead.â|
Coming back to the present, numbers are everywhere for the game player. Some are concrete values that have analogs in real life: How much ammo do we have? How many resources will this take to build? What is the range of that weapon? Some are a little more nebulousâif not contrived altogether: What level am I? What condition are my gloves in? What armor bonus does this magic ring afford? And, although the medical community might be a bit startled by the simplicity, games often parade a single number in front of us to tell us how much âlifeâ we have. (âHeâs only mostly dead.â) Suffice to say that we have educated our gaming clientele to forgive this intentional shredding of the coveted suspension of disbelief. Even though some games have attempted to obscure this relationship by removing some of the observable references to this numeric fixation, gamers still recognize that the numbers are still there, churning away behind the Wizardâs curtain.
Numbers in Games
As programmers, our fixation with numbers is not coincidental. After all, along with logic, mathematics is the language of our medium. Computers excel in their capacity to crunch all these numbers. Theyâre in their element, so to speak. This capacity is a primary reason that the pen-and-paper RPGs of the 70s and 80s computers so energetically made the transition to the computer RPGs of the 80s and beyond. Resolving combat in Ultima (1980) and Wizardry (1981) was far swifter that shuffling through charts, tables, and scribbles on scratch paper in D&D.
So numbers in games arenât going away any time soonâwhether in overt use or under the hood. The interesting, and sometimes even disconcerting thing, is that they arenât used more often. Even with all of the advances and slick architectures that artificial intelligence programmers use, we too often fall back on the most simple of logical constructs to make our decision code. The most obvious example is the venerable if/then statement. Testing for the existence of a criterion is one of the core building blocks of computational logic. âIf I see the player, attack the player.â Certainly, this sort of binary simplicity has its place. Left to itself, however, it can fall woefully short of even being adequate.
|The answer lies not in the existence of numbers in our world, but what those numbers represent and, ultimately, how we use them.|
We could extend the above example by putting a number in the equation such as âIf the player is < 30 [units of distance] away from me, attack him.â But really what have we gained? We are still testing for the existence of a criterion â albeit one that is defined elsewhere in the statement or in the program. After all, âsee the playerâ and âplayer < 30â are simply functions. There is still a razor edge separating the two potential states of âidleâ and âattackâ. All subtlety is lost.
So how might we do things differently? The answer lies not in the existence of numbers in our world, but what those numbers represent and, ultimately, how we use them.
Stop for a moment and do a self-inventory. Right now, as you sit reading this column, are you hungry? Sure, for the sake of simplicity, you may answer âyesâ or ânoâ. However, there is usually more to it than that. When my daughter was younger, she tended to cease using âhungryâ when she was no longer empty. (This usually meant that she ate two or three bites only to come back wanting more about 20 minutes later.) I, on the other hand, could easily see myself defining âhungryâ as âno longer fullâ. My wife has the penchant for answering somewhat cryptically, âI could be.â (This is usually less convenient than it sounds.)
All of this makes sense to us on an intuitive level. âHungerâ is a continuum. We donât just transition from âcompletely fullâ to âfamishedââit is a gradient descent. What we do with that information may change, however, depending on where we are in that scale. For example, we can make judgment decisions such as âIâm not hungry enough to bother eating right nowâŠ I want to finish writing this column.â We can also make comparative judgments such as âIâm a little hungry, but not as much as I am tired.â We can even go so far as use this information to make estimates on our future state: âIâm only a little hungry now, but if I donât eat before I get on this flight, my abdomen will implode somewhere over Wyoming. Maybe I better grab a snack while I can.â
|The subtlety of the differences in value seems to be lost on game characters.|
Compare this to how the AI for game characters is often written. The subtlety of the differences in value seems to be lost on them. Soldiers may only reload when they are completely out of ammunition in their gun despite being in the proverbial calm before the storm. Sidekicks may elect to waste a large, valuable health kit on something that amounts to a cosmetically unfortunate skin abrasion. The coded rules that would guide the behaviors above are easy for us to infer:
if (MyAmmo == 0)
if (MyHealth < 100)
Certainly we could have changed the threshold for reloading to MyAmmo <= 5, but that only kicks the can down the road a bit. We could just have easily found our agent in a situation where he had 6 remaining bullets and, to co-opt a movie title, all was quiet on the western front. DudeâŠ seriouslyâyouâre not doing anything else right now, might as well shove some bullets into that gun. However, an agent built to only pay homage to the Single Guiding Rule of Reloading would stubbornly wait until he had 5 before reaching for his ammo belt.
Additionally, there are other times when a rule like the above could backfire (so to speak) with the agent reloading too soon. If you are faced with one final enemy who needs one final shot to be dispatched, you donât automatically reach for your reload when you have 5 bullets. You finish off your aggressor so as to get some peace and quiet for a change.
|Very rarely do we humans, make a decision based solely on a single criteria.|
Needless to say, these are extraordinarily simplistic examples, and yet most of us have seen behavior similar to this in games. The faultÂ doesn’tÂ rest in the lack of informationâas we discussed, often the information that we need is already in the game engine. The problem is that AI developers donât leverage this information in creative ways that are more indicative of the way real people make decisions. Very rarely do we humans, make a decision based solely on a single criteria. As reasonable facsimiles of the hypothetical Homo economicus, we are wired to compare and contrast the inputs from our environment in a complex dance of multivariate assessments leading us to conclusions and, ultimately, to the decisions we make. The trick, then, is to endow our AI creations with the ability to make these comparisons of relative merit on their own.
Leveling the Field
So how do we do this? The first step is to homogenize our data in such a way as to make comparisons not only possible, but simple. Even when dealing with concrete numbers, it is difficult to align disparate scales.
Consider a sample agent that may have maximums of 138 health points and 40 shots in a fully-loaded gun. If at a particular moment had 51 health and 23 bullets in the gun, we wouldnât necessarily know at first glance which of the two conditions is more dire. Most of us would instinctively convert this information to a percentageâeven at a simple level. E.g. âHe has less than half health but more than half ammo.â Therein lays our first solutionâŠ normalization of data.
My gentle readers should be familiar with the term normalization in principle, if not the exact usage in this case. Put simply, it is restating data as a percentâa value from 0 to 1. In the case above, our agentâs health was 0.369 and his ammo status 0.575. Not only does viewing the data this way allow for more direct comparisonsâe.g. 0.575 > 0.369âbut it has the built-in flexibility to handle changing conditions. If our agent levels up, for example and now has 147 health points, we do not have to take this change into consideration into our comparison formula. Our 51 health above is now 0.347 (51 Ă· 147) rather than 0.369. We have detached the comparison code from any tweaking we do with the actual construction of the values themselves.
But What Does It Mean?
|Value expresses a concrete number. Utility expresses a concept.|
Normalization, however, only sets the state for the actual fun stuff. Simply comparing percentages between statuses like âhealthâ and âammoâ usually isnât sufficient to determine the relative importance of their values. For example, I posit that being at 1% health is measurably more urgent than being down to 1% ammo. Enter the concept of utility.
Utility is generally a different measure than simply value. Value, such as our normalized examples above, expresses a concrete number. Utility, on the other hand, expresses a concept. In this case, the concept we are concerned with is âurgencyâ. While it is related to the concrete values of health and ammo, urgency is its own animal.
|âWhat does this value mean to me?â|
The easiest way of doing this is by creating a âresponse curveâ. Think of passing the actual numbers through a filter of âwhat does this value mean to me?â That is what converting value to utility is like. This filter is usually some sort of formula that we use to massage the raw data. Unlike a lookup table of ranges (such as âammo â€ 5â), we have the benefit of continuous conversion of data. We will see how this benefits us later.
The selection of the formula needs to take into consideration specific contour of the translation from value to utility. There are innumerable functions that we can use, but they are all built out of a few simple building blocks. Each of these blocks can be stretched and squished in and of themselves, and combining them together results in myriad combinations.
The first filter that we can run our numbers through is simply a linear conversion. (For these examples, I will simply use the standard x and y axis. Iâll occasionally through in an example of what they could represent.) Consider the formula:
y = 0.8x + 2
This results in a line running from our co-maximum values of (1.0, 1.0) and arrives at y = 0 when x = .2. (See Figure 1.) Put another way, we want a steady descent in our utility (y) at a somewhat quicker rate than the decent of the actual value (x). We could have done something similar by changing the formula to:
y = 0.8x
As this point, the line extends from (1.0, 0.8) to (0, 0).
Obviously changing the slope of the lineâin this case, 0.8âwould change the rate that the utility changes along with the value (x). If we were to change it to 1.2, for example, the rate of descent would increase significantly. (See Figure 2.)
y – 1.2x âÂ .2
Itâs worth noting here that these formulas are best served by being combined with a clamping function that ensures that 0.0 â€ y â€ 1.0. When we take that into consideration, we have another feature to identify here: when x < 0.2, y is always equal to 0.
On the other hand, consider the similar formula:
y = 1.2x
This exhibits the same effect with the exception that now the âno effectâ zone is when x > 0.8. That is, the utility doesnât start changing until our value < 0.8.
These effects are useful for expressing the situations where we simply do not care about changes in the utility at that point.
Enter the Exponent
The simple formulas above merely set the stage for more advanced manipulations. For example, imagine a scenario where the meaning of something starts out as âno big dealâ, yet becomes important at an increasing rate. The state of the ammo in our gun that we illustrated above makes an excellent example. In this case, the value is simply the number of shots remaining whereas the utility value is our urgency to reload.
Analyzing this outside the realm of the mathâthat is, how would we behaveâgives us clues as to how we should approach this. Imagine that our gun is full (letâs assume 40 shots for convenience)âŠ and we fire a single shot. All other things being equal, we arenât likely to get too twitchy about reloading. However, firing the last shot in our gun is pretty alarming. After all, even having 1 shot left was a heckuva lot better than having none at all. At this point, it is helpful to start from those two endpoints and move toward the center. How would we feel about having 35 shots compared to 5? 30 compared to 10? Eventually, we will start to see that we only really become concerned with reloading when we our ammo drops gets down to around 20 shotsâat that below that, things get urgent very quickly!
In a simple manner, this can be represented by the following formula:
y = (xÂ â 1)2
As we use up the ammo in our gun (x), there is still an increase in the utility of reloading, but the rate that the utility increases is accelerating. (See Figure 3.) This is even more apparent when we change the exponent to higher values such as 3 or 4. This serves to deepen the curve significantly. Note that a version of the formula with odd exponents would require an absolute value function so as to avoid negative values.
Another quick note about manipulating these formulas. We could turn the above curves âupside downâ by arranging it as follows:
y =Â (1 â x)2
Looking at the chart (Figure 4) shows that this version provides a significantly different behaviorâan agent who has a very low tolerance for having an empty gun, for example!
By manipulating how the function is arranged, we can achieve many different arrangements to suit our needs. We can shift the function on either axis much as we did the linear equations above, for example. (See Figure 5.)
We can specify where we want the maximum utility to occurâit doesnât have to be at either end of the scale. For example, we might want to express a utility for the optimal distance to be away from an enemy based on our weapon choice. (See Figure 6.)
y = 2(1Â â |(x â 0.3)|2)
While we can certainly get a lot of mileage out of simple linear and exponential equations, one final class of formulas is very useful. Sigmoid functions, particularly the logistic function, can be used to define âsoft thresholdsâ between values. In fact, logistic functions are often used as activation functions in neural networks. Their use here, however, is much less esoteric.
The base logistic function is:
y = 1 / (1 + e-x)
While the base of the natural logarithm, e, is conspicuous in the denominator of the fraction, it is really optional. We can certainly use the approximation of 2.718 in that space, 2, 3, or any other number. In fact, by changing the value for e, we can achieve a variety of different slopes to the center portion of the resulting curve. As stated, however, the formula graphs out as shown in Figure 7.
Notice that, unfortunately, the graphâs natural range is not 0â1 as with our other examples. In fact, the range of the graph is infinite in that it asymptotically approaches both y=0 and y=1. We can apply some shifting to get it to fit the 0â1 range, however, so that we can use it with normalized values of x. We can also change the area of the graph where the threshold occurs by changing what we are adding to the exponent.
y = 1 / (1 +Â eâ(10x â 5))
Comparing and Contrasting
|We can line up dozens â or even hundreds â of utilities for various feelings or potential actions.|
The end result of all of this is that we can create very sophisticated response curves that translate our raw values into meaningful utility values. Also, because these end products are normalized, we can now easily compare and contrast them with other results. Going back to the examples I cited early on, we can decide how hungry we are in relation to other feelings such as tired (or too busy finishing a last-minute column for a magazine). In fact, we can line up dozensâor even hundredsâof utilities for various feelings or potential actions and select from among them using techniques as simple as âpick the highestâ to seeding weight-based randoms.
Compare this to what we would have to do were we not to use the normalized utility values. In our hungry/tired/busy example, we normally would have had to construct a multi-part condition to define each portion of our decision. For example:
If ( (Hungry > 5) && (Tired < 3) && (Busy < 7) ) then
If ( (Hungry < 4) && (Tired > 6) && (Busy < 3) )then
Ya know what? Never mindâŠ
Even if the above values were normalized (i.e. between 0 and 1), the complexity explosion in simply comparing the different possible ranges and mapping them to the appropriate outcome would get out of hand quickly. And thatâs just with 3 inputs and 3 outputs! By converting from value to utility, we massage what the data âmeans to usâ inside each response curve. We now can feel comfortable that a direct comparison of the utilities will yield which item is truly the most important to us.
The system is extensible to grand lengths as well. If we want to include a new piece of information or a new action to take into account, we simply need to add it to a list. Because all the potential actions scored and sorted by their relative benefit, we will automatically take newcomers into stride without much (if any) adjustment to the existing items.
|The Sims is an excellent example of how complex utility-based functions can be used.|
If calculating and measuring all of these feelings and desires is starting to sound a lot like The Sims, it is not a coincidence. The Sims is an excellent (but not the only) example of how complex utility-based functions can be used to simulate fairly reasonable, context-dependent, decision processes in agents. Richard Evans has spoken numerous times at GDC on this very subject. I wholeheartedly recommend reading his papers and viewing his slides on the subject.
The uses of these methods arenât limited to that genre, however. Strategy games, in particular, lend themselves to more nuanced calculation. Even in modern shooters and RPGs, agents are expected to make increasingly more believable decisions in environments that contain significantly more information. Our AI no longer has the luxury of simply leaning on âif I see the player, shoot him!â as its sole guideline and building static rulesets that address all the possible permutations of world state gets brittle at an exponential pace.
However, as Iâve illustrated (ever so briefly) the inclusion of some very simple techniques lets us step away from these complicated, often contrived, and sometimes even contradictory rulesets. It also allows us, as AI designers, to think in familiar terms of âhow muchââthe same terms that we often use when we think of our own (human) states. The numbers we need are there already. The magic is in how we use them.
You can find all of the above and more in my book, Behavioral Mathematics for Game AI.