Playing with neural networks and genetics

I finally got around to mucking with artificial neural networks. ANN are an area of AI that have always fascinated me. My naive understand was that you could create a 'brain' of sorts and train it to any task. Unfortunately, this isn't the case... ANN are normally used in situations that have a distinct solutions to given inputs, such as character recognition or pattern tracking. I still have enough naivety to think they can be applied to games, so let's get this started!

The goal of this experiment is simple: get a critter to move. The critter starts in a random position on a grid, and must navigate to a target position. The only input it has is a normalized vector that points toward the target position. The output of the net will be four variables, each mapped to move left, move right, move up, and move down. Now, this may seem a simple task since we're pointing the critter at exactly where it needs to go, but the trick here is we don't tell the critter how to move! The critter must learn to associate the input vector with its output bits so it can move in a specific direction.

I'm gonna go pretty light on ANN theory here because there are much better tutorials here and here. Basically the net is made up of nodes that represent how neurons work in the brain. Each node goes through this process:

• Receive input from multiple sources
• Apply a weight individually to each source
• Sum these weighted values
• Output a value based on this sum

The network adapts by changing the weights on each input which in turn gives a different output signal. There are many different kinds of network layouts, and the one I chose is the most basic (and easiest) called feedforward. This just means the nodes always send signals in one direction and never backward. My final network layout looked like this:

So we have a pretty looking network in place, but how does the critter actually learn? I chose to use a genetic algorithm which isn't exactly a learning technique... it is more like a brute force attempt to find a correct solution. The algorithm is simple:

• Create a population with random genomes
• Sort the population based on a 'fitness' value
• Breed a new population favoring those that are fit
• Repeat until desired behavior is reached

There are a lot of parameters to tweak here, such as crossover rate and mutation. Crossover rate is the percent chance that two mates swap chunks of genome, and mutation rate is the chance a part of the genome will randomly change. These values are very sensitive to the application and population size! For example, if your mutation rate is too high, you will never converge on a solution because the population is too unstable. Too low a mutation and the population will converge on an incorrect solution because they don't have enough diversity.

As I mentioned earlier, the net learns by altering the weights attached to each input. For this experiment, the genome will be a serialized list of these weights. The fitness value I used for the critter is the reciprocal of its distance to the target position when its turns are up. So a perfect fitness would be '1' and drops pretty quickly.

I arbitrarily chose 50 as a population size, and 150 generations. The solution was reached in far fewer, but more generations makes a prettier picture :) In the following image the critter starts in the lower left and the yellow dot is the target position. The attempted paths start blue and end up red as the generation gets higher. The paths highlighted in white are the final generation.

Woohoo! Good for you, critter. This has scratched my AI itch for now, but there is a ton that can be improved upon and explored. For example, I want to eventually try a 'real' learning technique such as backpropagation. Also, more complex behavior would be fun such as a ship that can turn and fire (asteroids, anyone?). If you have any questions about this stuff feel free to give me a shout!

Source code and win32 binary here:
http://sinoth.net/code/neural_test.zip