I have for the last month or so been working on a neat little self learning asteroids game. The game itself is very basic. There are a few ships flying around in 2D trying to shoot each other. Which in and of itself is not super exciting but the neat part is that the ships learn how to behave without the need of any human intervention. This is accomplished through the use of a genetic algorithm.
All the source code(Java) for this project can be found here.
Lets start with the basics. First of all the space in which everything happens is a closed rectangle. So when things collide with the walls they either die or bounce. There are only three kind of objects: Ships or Crafts as they are referred to in the code, Missiles and Asteroids. Since the ships are the objects where the cool things happen I will focus mostly on them. I have also found that including asteroids yield less cool results so we wont discuss them or use them in any example.
The Ships
Lets go in to some detail of how the ships work.
Input
The only input that the ship receives is what the ship can see which is three cones: one cone looking straight forward, one to the left and one to the right. And in each of these cones only one thing can be chosen as input. Even though several objects can reside in the cones only the object that has the highest priority will be chosen. In practice this is fairly boring since we only have ships and we let the missiles have 0-priority so they get ignored. So the ship can at any one time see at most three different objects. For each of the objects seen only three attributes are recorded: The type of the object, its heading(relative to the observer) and weather or not it is within firing distance.
The AI
The AI is very simple in its construction. It simply just maps a input to a decision. Each decision is just a set of actions such as move,accelerate,fire etc. This is represented as a hash-map using the input as keys and the decision as values. When the ship encounters a input it has not previously seen a random decision will be mapped to that input. Each ship will have its own AI.
The Genetic Algorithm
So, on to the fun part. The genetic algorithm here is the thingamagoop which makes the ships AI get better(or it’s at least supposed to do that). This is done in a fairly trivial way. The algorithm chosen for this project uses tournament selection, random crossover and a fitness function defined as the total score(the score accumulated through it entire life) of the ship divided by the age of the ship. The age of the ship is the number of times it has been in a tournament.
Lets go through the algorithm step by step.
- First a set of ships is created. This set will be referred to as the phenotypes.
- Then a series of "warm-up rounds" are played. These are played in order to fill the decision hash-map with some entries before the actual tournaments get started.
- A tournament is started.
- Chose N distinct ships from the set of phenotypes.
- Have these ships battle each other in several battles of epic proportions. With each these N ships partaking in only one battle.
- From these N ships. Find the two ships with the highest fitness and the one ship with the lowest fitness.
- Let the two best ships get on with some sweet sweet love making. The resulting offspring will have a combination of the two parents decision-map. This is accomplished trough a random crossover.
- Sacrifice the crappiest ship in public to set an example for the other ships and let the new offspring take its place.
- Return to step 3.
Conclusion
Well.This project has turned out pretty crappy. For several reasons. First of all, i suck at coding. This project has been full of serious bugs. Especially really dumb things in the code which makes me wonder why my parents didn’t just say “No hes going to be shit at coding. Throw it away” when I was born. Also the genetic algorithm has been really annoying. I have had a lot of problems getting it right. Both due to bugs in the code and other stupid stuff such as poor choices of fitness functions etc.
Lessons learned:
- I suck at programming. This was something I already knew but this project has really shown me the extent of my incompetence.
- Be careful when you copy paste your own code!! Several serious bugs in the program has been due to me copy pasting some loops and such and forgotten to change all of the details.
- Don't do humpty-dumpty half assed refactoring. A lot of bugs has been introduced through me saying "ouu I should change all of this to do things better" and only changed some of that and ended up breaking things.
- Fix ugly code when you realize that it's ugly and not later when you have forgotten how that ugly code actually works.
- Never underestimate how annoying genetic algorithms can be. You might have to tweak seven thousand different parameters to get good results.
And here is a little video.
It looks cooler than it is.