9

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.

Improve this question

4 Answers 4

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Hmm.... point taken. But if only I could figure out how to simulate an FPS, I think I might be able to do it in a month. Or some other kind of game, like a soccer game. Are there any libraries to do that, without going into the code of them game?
Are there any open source FPS games?
@Dane: Yes, you can find many on this page: en.wikipedia.org/wiki/List_of_freeware_first-person_shooters - All the ones with a GNU GPL license are open souce, and some of the others are open source too.
Basically I should test it out for a game which I can actually code up quiet easily, or a game whose code i can understand easily, right? Because that way I would be able to simulate the game and get the fitness value(score).
Another observation : I think i should work on a game in which only 1 player(cpu) plays, because otherwise while i'm simulating by playing aginst the bot, it would cause uncertainity because sometimes i might play welll and sometimes i might not.
2

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:

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

Improve this answer

2 Comments

Alright. I've thought of another idea, which isn't too ambitious. How about i design a GA which is able to play snake on its own? I'm worried this might be too easy of a project. What do you think?
@user280454: That would be fun, you may always implement an "extended" version of snake where, for instance, you would have teleports around the screen, or bombs or whatnot, so to make it a bit more complex :) Anyway, if I remember well, one of the examples you will find in the NEAT webpage deals with something similar (a bot finding its way through a labirint or something like that).
0

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.

Improve this answer

1 Comment

The problem with using an already existing bot is that to make it use certain weapons, I will need to get into the code of the bot, isn't it?
0

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.

Improve this answer

3 Comments

If I do it like this, I will still need to simulate a fight between 2 bots, and I would need to do whole lot of these smulation which would take a lot of time. If there is a library function which does this for me (i.e, takes weapons of the bots as input and returns who won the fight), then it would be really awesome, since I won't always have to see the whole frigging fight, I'll just get the result instantaneously.
@user280454: You can speed things up by making certain assumptions, like that a bot with a gun will always beat a bot with only a knife.
@user280454: I added a new alternative to the top of my answer: let fitness = the DPS an individual does against a sitting duck player.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.