At the forefront of Artificial Intelligence

Home » Articles » Neural Networks » Gaming

Realtime Evolution of Agent Controllers in Games

By Forrest Briggs

Abstract

Realtime evolution gives agents in games progressively increasing intelligence the more the game is played. Agents can adapt to new situations and changing strategies, leaving them much less prone to being tricked or having their simple behavior exploited. After introducing the abstract concepts behind realtime evolutionary control of game agents, this paper discusses the application of these techniques to space invaders and a realtime strategy game similar to Warcraft.

Realtime Evolution of Controller Parameters

Realtime evolutionary control of agents is primarily applicable to realtime games that have a lot of agents. For example, space invaders has a lot of invaders. It is helpful, but not necessary that the invaders die often and are then replaced by new individuals, allowing many generations of evolution to occur and aiding the formulation of a fitness function.

In order to control an agent, we will link its sensory input and action output to a controller. Input is generally sensory information available to the agent, such as the location of the player, other agents, obstacles or resources. Output is actions that the agent can perform, such as movement or attacking. The controller accepts sensory input and produces response output in realtime. In order to apply realtime evolution, the controller's mapping from input to output should be governed by a set of parameters. This system resembles a biological organism. Sensory organs send input to the brain, which sends output to the body, which manifests the outputs as action. The controller could be a neural network, in which case its parameters would be its weights, however realtime evolution can be used to enhance the performance of any realtime controller that has undetermined variables.

At the beginning of a game or round, agents have controllers with either random parameters or parameters that have already been chosen by other means. As the game progresses, the parameters of the controllers evolve. The parameters of the controllers of the population of agents can be changed in different ways. When a new agent is created (such as when a new enemy spawns,) the parameters of its controller should be either a mutation and/or mating of one or more desirable parent agents. Parent parameters can simply be drawn uniformly from all of the living agents, which would lead to evolution towards survival. Alternately, parent parameters can be selected favoring certain parents according to a fitness function. When using a fitness function, it is not necessary for agents to die and re-spawn to evolve their controllers. Low fitness agents can have the parameters of their controllers replaced by a mutations and/or mating of higher fitness agents at any time.

NeuroInvaders

NeuroInvaders[1] uses realtime evolution to adapt the behavior of space invaders to survive against the player. The player controls their ship's position with the mouse and can shoot a laser that will kill any invader it touches by clicking. The controller of each invader is an 8 neuron spiking neural network[2] (continuous time, recurrent pulse base network). In this model of neural network, information is conveyed by the firing time of the neuron. The parameters of the network are weights, which control how much energy each pulse sends to other neurons and delays, which determine how long pulses take to arrive.

When the player's ship is in the invader's field of view, the invader's visual neuron fires. When the invader's turn left neuron fires, it turns left by a small number of degrees. When the accelerate neuron fires, the invader accelerates. When its fire neuron fires, it shoots a laser. Three neurons are left without any input or output assignment to allow for hidden calculations.

Each invader's brain initially has random weights and delays. When an invader is killed, it is replaced by a new invader with a neural net with parameters that are copy with slight mutation of one of the living invaders. Mutations consist of adding random gaussians to the weight and delay parameters of the spiking neural net controllers. In this way, the invaders that are not shot by the player pass on their behavior with some modifications to the next wave of invaders.

Figure 1: The input and output mappings for a space invader to a spiking neural net. The network has a visual input neuron and output neurons that control motion and shoot lasers.

Figure 2: A screen shot from NeuroInvaders showing the player, invaders and their lasers.

Peon Gold Miners

Online Interactive Neuro-evolution[3] shows how realtime evolution can be used to control peons who must find gold mines while avoiding enemies in a real time strategy game similar to Warcraft. Peons start at their base and try to find as many mines as possible while avoiding enemies. The peons are controlled by a feed-forward neural net with 8 inputs and 2 outputs. The network has 2 inputs for visual stimulus in each of 4 quadrants. At each time-step, the average distance to mines and enemies in each quadrant is computed and sent as input to the net. The output of the net is the horizontal and vertical distance that the peon moves in that time-step.

Figure 3: Peons start at their base and then try to find as many mines as possible while avoiding enemies [3].

Figure 4: The visual input to the peon is divided into 4 quadrants, each of which sends the average distance to mines and enemies in the quadrant as input to a feed forward neural net. Output from the neural net is a horizontal and vertical displacement for the peon to move [3].

The peons are ranked according to the fitness function

fitness =	mines found · reward per mine - cost of being born

	age

This fitness function rewards peons that find many mines and live a long time. When a peon is killed by an enemy, it is replaced by a new peon with neural net parameters that are either a copy of another high fitness peon with gaussian noise or a single point cross over mating between two peons.

Their results show that populations of peons that are evolving in realtime outperform populations with fixed parameters. These populations are more adaptable to changes in strategy by the enemies as well.

Conclusion

NeuroInvaders and the peon miner game demonstrate the simplicity of using realtime evolution to control agents. In both cases, sensory input for the agent is sent to a neural network, which outputs actions for the agent to perform. Replacing dead agents with agents with neural net parameters that are simple mutations and/or matings of the best or simply the only living agents allows the population of agents as a whole to evolve. Such populations can adapt to changing circumstances and outperforms agents that do not evolve. Games with agents that do the same predictable thing over and over again are boring. Realtime evolution can make game-play more fun for longer with enemies that learn behavior that specifically targets the individual player of the game.

In both of the examples discussed in this paper, the evolution of agents in the game is localized to a single computer. However, it is also possible to apply realtime evolution in a distributed network. Different computers playing the same game could share the results of realtime evolution. This could enable a vast amount of computational resources to be seamlessly devoted to improving the AI of the game for everyone.

Source Code

The java source code for the NeuroInvaders applet is available.

References

[1] NeuroInvaders by Forrest Briggs 2003.

[2] Spiking Neural Nets by Forrest Briggs 2002 - 2004.

[3] Online Interactive Neuro-evolution by Adrian Agogino, Kenneth Stanley, Risto Miikkulainen 1999.

Submitted: 07/07/2004

Article Toolbar

BibTeX entry