Overview

Action games often feature computer-controlled non-player characters (NPCs) that attempt to oppose the human-controlled player character (PC). The NPCs can appear in many forms, but they usually are limited to fairly simple interaction with the PC. That is, the NPCs appear with weapons in their hands, with the sole purpose of hindering the PC.

Classical computer game artificial intelligence (AI) has striven to make the NPCs as dangerous to the PC as possible: the NPC is considered to perform well if it causes the human player a hard-to-solve problem. However, making a NPC deadly isn't very difficult: adding hit points or making the NPC more accurate shooter does the trick easily.

In my M.Sc. thesis I aimed to make the gameplay experience better by making the NPC AI more plausible. To really enjoy the game, the human player needs to have a mind-state that is sometimes called the suspension of disbelief. It just means that the human player accepts the game's internal logic and transfers some of the player character's feelings and emotions to himself or herself. If the AI does stupid things or acts machine-like, the player might remember that he or she is just playing a computer game. Plausible NPCs therefore give the human player a sense of immersion in the game, which direcly contributes towards the overall game enjoyment.

One way of creating more life-like NPCs is to make them act individually rationally. Rationally in this context means that a NPC always takes the action that is most profitable to it. When extended to the group AI, the NPCs no longer form a group which aims to be as efficient as possible. Instead the NPC group is composed of a number of individual NPCs, who act towards the group's objectives only as long as it directly profits them. Of course, working as a part of a team towards the team's goals might still profit the NPC. The NPCs' rational attitude might give the human player a being there sensation.

Artificial intelligence in action games

The classic way of programming the NPC AI is to use scripts to trigger different actions from the NPCs. The script can be, for instance, something like this: 

    if (player character is too threatening):
        flee
    else:
        run towards the player character
        start shooting
However, scripted AI is quite limited, and if the number of NPCs is large, their interaction may be difficult to script correctly. Also, if the PC does something unexpected, such as arrives from different direction than the game designer assumed, the script may cause non-intended consequences.

A more advanced way of handling NPC AI is to use utility functions. Utility functions return a number, called utility, for each possible action the NPC might take. The utility numbers therefore represent the 'goodness' of each action. The NPC then chooses the action that gives it the most utility.

The utility functions may even include the other NPCs' states in the utility calculation. This way one NPC can get more utility if the other NPCs do things which work well in combination with the NPC's chosen action. But how do the NPCs select a combination of actions, which suits all NPCs so well that no one wants to deviate by choosing another action? The group action choice from which nobody can deviate to get better utility is called a Nash equilibrium. Nash equilibria form the backbone of game theory.

Game theory

Game theory studies the interactions of rational agents. A game in game theoretic sense is one round of decisionmaking, in which each player chooses one strategy of playing actions. A strategy can be a pure strategy, in which an agent plays one action, or a mixed strategy, in which one agent selects an action from a set of agent actions according to a probability distribution.

John Nash proved in 1950 that every finite game has at least one Nash equilibrium. The Nash equilibrium consists of each player playing a strategy so that no agent can have greater utility by changing its strategy. A Nash equilibrium is not always the way to get the absolutely largest sum of combined agent utilities from a game, because no agent can be made to play a strategy which gives the agent a sub-optimal personal utility. Still, it is guaranteed by the definition of the Nash equilibrium that the agents' actions will be the rational-looking.

The focus of the thesis

The main theme of the thesis is the NPC group action selection using the Nash equilibrium. The utility functions, which lead to intelligent-looking behavior, are considered. The thesis also introduces one modern algorithm for finding suitable Nash equilibria from a game. Finally, the thesis contains some experimental results from a simulation using the Nash equilibrium finding technique. The results include examples of agent movement and statistics of the time needed to find a Nash equilibrium in some example game settings.