Genetic Programming Mario

I have started to work on genetic programming a couple of month ago with the idea to develop program structures which are human readable and evolve based on actual play data.

During the first couple of weeks I was reading Poli&Langdon's great introduction to genetic programming and after that started to work my head around Koza's pile of GP books.

I think GP is still underrated in game AI. In contrast to neural networks, you are able to learn meaning of actions. You do not end up with a network which just performs well you are able to derive a structured representation of the learn behaviour. This is what motivated my work.

It still is slow and if a useful meaning is evolved largely depends on the training data but the potential is there.

I am currently using the platformerAI code written in JAVA and JGAP as a GP library. Though I have to say that JGAP was a good starting point but I should have followed the advise in Langdon&Poli to implement my own GP. This will be the next step for my POSH# codebase I will implement a grammar-based GP to work with unity3D.

For my current implementation I am using a genotype containing 20 genes (actions and senses). In contrast to GA I am not fixing the size of a chromosome which is quite neat as your chromosomes basically grow and get more sophisticated during evolution. The genes are fairly simple and for the platformer resemble possible user in and output.

The current results with the platformer are promising and within a couple of 100 generations good chromosomes(mario-bots) emerge. The only issue I am facing is that the bot is learning the levels but it is not actually performing like an average human player.

To address combinatorial issues: GP's explore the domain in a lot broader way than GA's so they take a lot longer to find decent solution the advantage however is, that they explore fractions of the space which would have been potentially overlooked by a GA. My understanding is that GAs are great for finding solution fi you know what you are looking for. GPs however allow you to canvas the search space looking for the right questions to ask and presentation you with directions for where interesting solution sand problems are.

The workload on my machine is quite small so I can run a decent amount of players in parallel which is impressive. For an industrial application however my approach is not good enough... yet. I think after refining the GP approach this can help reduce the testing times of games using less alpha testers than currently used. Also it allows to better explore what is possible in a level so it could be useful approach to finding bugs.

More on that later maybe even with a couple of screenshots and actual code snippets.

The main goal is to get my approach documented so that other people are able to see where I struggled or where I found some interesting stuff.