Genetic RTS

In the previous post I wrote about the problems of adapting a genetic algorithm to work inside the constraints of a video game. In some cases it is possible, and quite easy, to reshape and reduce the "problem" at hand in order for the GA to be able to solve it and pretend to be an intelligent adversary.

During our tests at Urbino we built a couple of prototypes, one of which is Genetic RTS (yep, I know, not the most creative of titles ). It's essentially a simplified "Defense Grid" game where the player must build up the defense of his base while the computer attacks it and tries to overcome the defensive structures.

The game

Genetic RTS is limited to a little square terrain with the player's base at its center. At the start of the game, the player can place a certain number of defensive structures around the base (in the blue area):

The game terrain. Marked in blue, the area where defensive units can be placed.
You'll notice the base graphics are stolentaken directly from "Dune II".

There are two different defensive structures: cannons, which shoot quickly but cannot target airplanes, and anti-air rockets, which are slower but of course only target planes. Each defensive tower has a limited range and a limited rate of fire, but never misses the enemy.

The objective of the computer is to destroy the player's base (which has 20 "health" points) by trying to get its units to touch the base (each hit costs one health point). When the base reaches 0 points the player loses. The player's goal instead is to place his defenses correctly and resist to the attack waves as long as he can.

The computer can generate a certain number of units, that will start on the edge of the map and then move towards the base. A unit can be either a land unit (a tank) or a flying unit (an airplane): each unit will be shot at by the corresponding defense tower type and not by the other. Moreover, each single unit can choose its "toughness" (the number of hits required to destroy it). A tougher unit will also be slower, so there's a trade-off to find, based on the number of defensive towers and their rate of fire.

Solving the problem genetically

In order for the computer to succeed and to beat the human player, it will have to carefully choose which units to create and where to deploy them, adapting to the player's base and how it changes (every other attack wave the player may re-deploy his base). The best way to do this in Genetic RTS is to identify each single attacking unit as a "genetic individual" with certain genetic properties (its genotype) that determine where the unit will start, its type and its toughness. The GA will then pick the "best" individuals (those with better success of reaching the base) and favor them in the next generations (the attack waves).

The genome

So, the computer needs to pick a winning combination of the properties seen above (direction of approach, type of unit, speed, toughness). In order for the GA to work we first need to define how to encode those properties, i.e. how to define a genome for each individual.

The starting position is encoded as a cell on the terrain grid, indexed with a 4 bit integer.

The unit's starting position can be chosen by picking one of the, arbitrarily defined, cells on the edge of the game terrain. Each cell has an index, and since the cells are 16, this information can be efficiently stored using 4 bits in the individual's genome.

Whether the unit is a tank or an airplane can also be very easily encoded by a boolean value. In our case we used a full fledged enumeration instead of a bit to allow us to plug-in new types if necessary...

Finally, the toughness/speed can be encoded by an integer on a scale: in our case on the scale [1-5], where 1 stands for incredibly tough and slow and 5 for fast but very easily destroyed.

Fitness

Using the genome defined above, the genetic algorithm can generate a number of random units, place them on the map and let them attack the base. This step is simulated like a standard game: the turrets fire and destroy the attacking units following the rules of the game and there is no interaction, neither from the computer nor from the player (a better game would let the human player do something here, but this is just a prototype ).

The fitness points assigned to two units, based on euclidean distance from the base.

This simulation step is important to evaluate the "goodness" of the generated individuals: each one of them will be judged using a certain well defined metric. In this case, the more a unit gets close to the player's base, the more points it will earn (and the higher a fitness it will have in the genetic selection process). If the unit actually manages to hit the base, this will double its fitness.

Do the evolution, baby!

Following the standard GA procedure, the best individuals will be picked and their genome used to create the next generation of attackers. The next enemy wave will be unleashed against the base, and so on - until the weaknesses in the player's defenses are discovered and overcome through natural selection.

In pratice

The prototype we built was written in C#, using WPF for the graphics (which worked quite well, in spite of me knowing nothing about it). We noticed that the adaptation to the strategy used by the player is very quick usually: in literally a couple of generations the GA is able to generate a population that can destroy the base. This is probably due to the simple genome and the lack of balancing of the game (it's actually quite hard to get through the first 5 generations).

Already at generation #2, the GA sends most of his troops as tanks from the left side of the map, where there are less anti-tank turrets. Anti-air defenses were well placed, so less airplane units are generated.

You can download Genetic RTS now, but please remember this is a simple prototype, only meant to prove that GAs can be applied to games, strategic ones in particular. If I had more time, I'd like to spend some time writing a "real" game (in XNA perhaps) using similar evolutionary AI.