Some Notes on Weighted Sums

Extending Simple Weighted-Sum Systems

Decision making is one of the key functions of every AI engine. There are many decision-making strategies available, but a straightforward and powerful one is the weighted sum system, in which you simply weight the available options and select the one with the highest score. This is a very flexible technique that can be applied to situations that can't be easily modelled with more traditional approaches.

It is easy to write a naïve implementation of a weighted-sum system using only a direct combination of factors. Such an approach, however, is not easily adaptable to a number of situations that appear frequently during typical game development. The result is that much time is spent tweaking and tuning weights, often by trial and error, until the observed behaviour resembles the expected one.

Much research has been devoted to decision-making in the field of artificial intelligence. Utility theory is a formalization of the intuitive process of choosing the most desirable alternative when making a decision. Utility is a number used to measure desirability for all the possible outcomes of the decision. The rational choice then is to select the option with the highest utility.

Finding a value for the utility of a decision is highly subjective: different people might assign different values to the same situation. However, calculating an exact utility value is not possible in the presence of uncertainty, which is the norm in nearly every game. If you cant predict exactly what the result of a decision is going to be, you wont be able to evaluate how much you will like it. The traditional approach in this situation is to estimate the utility according to the probability of each possible outcome. This value is called expected utility.

Each situation demands a specific algorithm to calculate the expected utility of a decision. Typically, for games we have to resort to heuristics. A general method is to observe the factors that might affect the outcome, try to predict their influence on the result (whether positive or negative), and combine them using a mathematical formula. For instance, chess programs sometimes assign a payoff value to each piece. Each piece is a factor that helps calculate a value for the state of the board. By summing these payoff values, utility scores can be computed for every board configuration.

Unlike chess, most games have several different factors. Moreover, not all factors have the same influence in the outcome: some factors are more important than others are. A simple formula for combining factors that works fairly well is the weighted sum. Factors are multiplied by weights that represent their relative importance and then added together to calculate the expected utility:

EU(A) = (SUMOF) WiFi(A)

In practice, the exact factors that affect a decision depend heavily on the specific problem domain. A factor can be anything that can be measured in the game and has some kind of influence on the result of a decision. It is the programmer's responsibility to ensure the combination of factors represents an accurate measure of the desirability of making that decision.

One of the best features of this technique is that it is very robust in the face of emergent situations. Because the factors that define the game world are considered when making decisions, the AI will be coherent and act appropriately in nearly any circumstance. Contrast this with a heavily scripted AI, which has to explicitly take into account every single possible situation. The result is either incorrect behaviour when faced with an unexpected situation, or long and complex scripts, which take a lot of time to write and debug.

TO be finished