Archive for the ‘Game AI’ Category

Normalized tunable sigmoid functions

April 5, 2010

Don't leave home without it

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.

Linear probability curve for bee starting ventilation duty

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:
Squared probability curve for bee starting ventilation duty

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).

Sigmoid Function

Sigmoid Function plot

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:

half Tunable sigmoid (from 0 to 1).

half Tunable Sigmoid plot

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:

k = 0.01

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 😉

Don't leave home without it

%d bloggers like this: