OK, so time for some technical stuff… inspired by GDC, I am going to post some articles on my ideas on game development, including some things that I teach in my classes.

**Utility Theory**

At the 2010 GDC AI Summit, Dave Mark spoke about Utility Theory. Hmm, I said, yep I have been doing that stuff for years, but I never knew what to call it. I realized that I have been using utility theory in some form all the way back to the earliest games I made.

Here is a wikipedia entry on Utility Theory. Good luck…

Anyway, to boil it down, it is applicable in game AI because given any situation you can provide some kind of score, and then cause behavior to change as a result of the way those scores change over time. As a crude example, let us look at weapon selection.

Each available weapon will have advantages and disadvantages… a set of attributes that makes them tactically useful in different contexts. So the question is, how do we make the AI decide which weapon to use?

The principle of utility theory is to evaluate the tactical situation and assign a utility value to each weapon. The AI then chooses the weapon with the highest utility.

For example, the utility of a rocket launcher when facing a target that is some way off is much higher than when the target is very close (too close and the weapon will inflict damage on you, severely reducing the weapon’s utility). Other factors influence the utility of that weapon. It is most effective on slow targets due to its slow rate of fire, and again more effective on large dangerous targets with plenty of armor which carry a powerful weapon.

A machine gun, on the other hand, is best suited for medium range targets which are maneuverable and perhaps less well armed.

Applying utility theory would mean calculating a score that takes into account the various factors that increase or reduce the utility of a weapon, and then choosing the weapon with the highest utility.

This can be applied to all kind of decisions, such as the utility of reloading, the utility of finding cover, the utility of retreating and so on.

In essence this is precisely the kind of stuff that is going on in probabilistic AI simulations, such as my bee hive simulation. In this, the behavior of the bees is determined by weighted probabilities, but the driving factor behind this is utility theory. The probability that a single bee begins or quits ventilation duty depends on the temperature of the hive. The higher the temperature, the more likely a bee will spontaneously start ventilation duty, and the less likely it will stop doing so.

The difficulty with such systems is that they need careful tuning. Should nature itself work by weighted random choices (a very plausible explanation of how bees decide to start or quit ventilation duty in my mind, but that’s a subject for another time), then through a process of evolution, the weightings will have been carefully tuned over millions of years. Unfortunately, the game designer needs to be a little faster than that.

It is thus important to be able to tune these weightings, and more importantly, be able to specify non linear relationships easily.

What do I mean by that? Take the temperature of the hive as an example. It is clear that the danger to the hive is not linear over a range of temperatures. There is likely to be a mid range where too little or too much ventilation will not make much difference. However, as the hive temperature increases away from the norm, at a certain point we might expect to see a major increase in the utility of ventilation due to a dangerous temperature inside the hive.

As an example, take a look at the following graph, showing a possible probability curve for a bee starting ventilation duty. Note that the temperature, t, is normalized to a range from 0-1.

You can see that the higher the temperature of the hive, the more likely a bee is to start ventilating. However, when I ran the simulation, I found that there was not enough urgency to the bees behavior when the hive was hot. Fine you may say, why not simply increase the probability? The problem was then that there were too many bees ventilating even when there was no real urgency… bees that should probably bee doing something else. Additionally, the system would often start oscillating, leading to a catastrophic swing of temperature that the bees would be slow to respond too.

What was needed was some way of changing from a linear relationship to some kind of exponential curve, so that doubling the temperature might, for example, quadruple the probability of starting to ventilate.

A simple way to do this is to relate the probability to the square of the temperature:

You can of course arrange to have all kinds of other formulae in there. Perhaps cubed. Or perhaps you could use a sigmoid function.

Here is the ‘official’ sigmoid function (although apparently this is a special case, and that all curves with an S shape are considered to be sigmoids).

A few problems, though: this curve goes the wrong way (for t from 0 to 5). Secondly it is not normalized. Thirdly, it is rather fixed in shape.

It would be much easier to use a kind of sigmoid function that is easily tunable (any amount of curve in either direction) and also would guarantee that 0 would give 0 and 1 would give 1. This way, we need not worry about the function changing the range of values being processed, and we would be able to fine tune the curve.

Many years ago I went searching for such a thing, and came up with the following function:

The above plot shows this “half sigmoid” (because we are only going from t = 0 to 1) with k=0.2.

It turns out with this function that for large values of k, you get a straight line (in theory you need an infinite value of k, but in practice it converges to a straight line very quickly. If you really want a straight line, then it is best to turn this off).

As k approaches 0, the curve gets increasingly sharp, however it always remains normalized:

This is great. But how about making the curve go the other way? Well it turns out that for values between minus infinity and -1, that is precisely what you get. Again, as you approach minus infinity you get a straight line. With k = -1.2, you get the mirror image of the curve for k=0.2. If you set k to somewhere between 0 and -1, the result you get is nonsense (the curve is still normalized, but no longer generates a sensible curve). However this simple, fast function gives me all the control I want.

Here is a plot with k = -1.2:

To actually turn this into something resembling a sigmoid function, it is simply necessary to repeat the function for negative values, to get the range from -1 to +1. This is easily achieved by giving the function the absolute value of t, and then changing the sign of the result back to the same sign as t.

Doing this results in a fully tunable, normalized sigmoid that can be used to change boring linear relationships anywhere in your code to curves. I have used this for all kinds of things, from figuring out how hard to kick a soccer ball when dribbling at different speeds, to adjusting the input curves from a joystick, to utility theory style decision making. It is simple, fast, versatile and robust, and I don’t leave home without it 😉

March 5, 2011 at 9:35 pm |

Like you said in the 2nd example. What is the downside of using an n-exponential function as in:

y = x ^ n (starts at 0, ends at 1)

y = 1 – (x ^ n) (starts at 1, ends at 0)

where x ranges from 0 to 1.

for n > 1, the function accelerates, for n between 0 and 1 the function decelerates.

This also gives normalized ranges.

See also:

http://www.wolframalpha.com/input/?i=y+%3D+x++5,+y+%3D+x+3,+y+%3D+x++100

and

http://www.wolframalpha.com/input/?i=y+%3D+1+-+(x++0.2),+y+%3D+1+-+(x+3),+y+%3D+x++100

March 5, 2011 at 10:32 pm |

There are a few downsides in comparison to my solution, although of course which solution you might wish to use depends on your application.

In no particular order:

1) x^k is complex floating point function (when k is not an integer), and depending on application can be slower than my solution which uses basic arithmetic. For fine control, k will need to be a real number.

2) I present a single function who’s constant controlling it provides a complete range of curves in both directions (i.e. curving up or curving down), without the need for different formulae or special cases.

3) x^k does not create a symmetrical curve. Using x^k means that the differential (that would be the slope) of the curve is always zero at zero, no matter the value of k. As you can see in my plots, k also changes the slope at zero and thus allows for slight curves. In my solution, the angle of the slope at x = 0 and x = 1 has symmetry. Depending on your application this can be a desirable characteristic> I find it to be so for pretty much all tuning applications

4) x^k requires very large powers to generate sharp curves, which has the potenital for floating point inacuracy. My formula on the other hand provides such sharp curves with small values in a reasonable range. It makes it very suitable for implementation in fixed point for instance, as well as being more robust.

As far as I know, there are no disadvantages to my formula compared with x^k.

Thank you for you interest, and I hope you find this useful.

March 6, 2011 at 4:54 pm |

[…] was playing with my sigmoid function, and Wolfram Alpha, seeing how the formula integrated and differentiated and so on. One thing […]

January 7, 2012 at 9:51 pm |

[…] was (in my opinion irrationally) challenged recently on my claim that I ‘invented’ my normalised tunable sigmoid function. This challenge prompted the following post. It got me thinking. It is all very well and good […]

October 31, 2012 at 8:06 am |

Reblogged this on Youniteme's Blog.

June 6, 2013 at 1:10 pm |

tested on a 3d racing game for mobile (joypads/bluetooth) and this input adjustment perfectly fit … it’s the finetune-juice that we missed till now 😀

Thanks Dino!

June 6, 2013 at 1:13 pm |

Great, glad it is working for you 🙂