Genetic Algorithms in games

Question

I have to do a term project on Genetic Algorithms, and I had the idea of tuning the traits (i.e. weapons to be used , etc) of a first person shooter bot. For example, I would represent the traits in the form of a string, with first 10 bits representing probability of choosing weapon1, next 10 bits representing probability of choosing weapon2, etc. I would thus get the optimal string and thus be able to figure out what should be the optimal set of weapons i should use.

The obvious problem that I am facing is how to find the fitness values. My idea would be that if I want to find the fitness of a string, I force the bot to use the corresponding weapons and play a game against it and use the final score of the bot as the fitness. The problem is that I would need to play a LARGE no of games.

Is there some sort of simulation that I can do? For example, can i somehow get a function f where I would feed in the bot's traits (ex : weapons, etc) and it would return the corresponding fitness values? Do open source FPS games provide such a library?

The other option would be to go into the source code of the game and then keep on simulating various scenarios and noting the score in each scenario. I would prefer not to have the added complexity of going into the source of the game, since this is a short(1 month) project.

Thanks.

Answer 1

I think your project is very complex for a one month project.

It's not quite so exciting but perhaps you could look at playing strategies for a board game or card game instead. This is a much simpler situation and and many games can easily and quickly be simulated allowing you to use a genetic algorithm to find a good playing strategy. It will teach you the principles of genetic algorithms without requiring you to understand the huge body of source code that would be necessary to simulate a first person shooter.

Answer 2

Your fitness function can be how much DPS a given bot deals against a sitting duck opponent. E.g. have the bot attack the player, and don't fight back.

You can memoize the fitness, so duplicate individuals don't have to be retested.

---

Alternatively, you can make survival of the fittest be literal by putting 2 individuals on opposite teams and seeing who kills who.

Because technically you don't need a fitness function, just a way to compare individuals.

In order to reduce the number of comparisons, the individuals from each generation can be compared via a tournament, like

A 
  }-> A
B
        }-> C
C
  }-> C
D

which shows that the top two individuals are C, then A.

Answer 3

You could use an already existing bot to generate data, if one is available and if this is possible.

Alternatively, you could use Autohotkey (search google) to generate a sequence of key&mouse presses and make the bot somehow play automatically in a dumb way.

Answer 4

I agree with Mark Byers, it's a bit too ambitious for a 1-month project.

Anyways, you may want to check out NERO (Neuro-Evolving Robotic Operatives), which is a game based on Ken Stanley's algorithm NEAT (NeuroEvolution of Augmenting Topologies).

You may also want to have a look at Stanley's papers:

• Evolving Neural Networks Through Augmenting Topologies (PDF)
• Efficient Reinforcement Learning Through Evolving Neural Network Topologies (PDF)
• Real-Time Learning in the NERO Video Game (PDF)

Several implementations of NEAT exist for different languages, so that may be a start.