Neural Network + Genetic Algorithm + Game = ❤

This is how I created an A.I. that beat this game completely!

The Game: Rules and Moves

First of all, let me describe the game. As you have probably guessed from the gif, the goal of this game is to avoid the red bars and move the green creature forward. The further you go the more your score will be. To make the game realistic, I’ve implemented gravity which means if the creature moves up it must come down with the given acceleration. But how/when does it jump? To be able to jump it must be on the ground. At this position, the creature can apply an action force on the ground and the ground will apply a reaction force on it. This reaction will help it to jump (just like how we jump). The x-component of this force will produce an acceleration in the x-direction and the same is true for y-direction.

Note: For the sake of simplicity I’ve not implemented the action-reaction mechanism instead I’m working with the accelerations only. When the creature is on the ground it can decide it’s x and y accelerations!

The challenge is to find the values of these accelerations such that it can safely jump over the next red bar! It is to be noted that the creature can’t change it’s velocity when it’s in the air (why? left for the readers). The collisions with the ground are inelastic hence it doesn’t bounce automatically.

Building the AI

There are many ways to approach these kinds of problems. Here, I am applying something called Neuroevolution, which is a combination of Neural Network and Genetic Algorithm .

I. Neural Network (NN)

To be able to ‘think’ ( when and how to jump) the creature needs some kind of decision-making model. In my approach, I’m using a neural network as the brain of our little friend. I’ve used a small nn containing 6 nodes in the input layer, 8 in the hidden layer and 2 in the output layer. But what goes in those 6 input nodes and what comes out of the 2 output nodes? Let’s first see the output nodes. 2 nodes decide the values of acceleration in two directions. As I’ve stated earlier, the creature just needs to decide it’s x-acceleration and y-acceleration.

For the input nodes, there can be many sets of possible features. The aim is to provide as much information to the brain about the creature’s current state and its surroundings as possible. I am using this 6 information (can you come up with a better set of features?)

II. Genetic Algorithm (GA)

As the name suggests, it has something to do with genetics. It is one kind of Evolutionary Algorithm where we try to mimic biological evolution to find an optimal solution for a given problem. We start with a set of solutions and choose the best ones out of them and let them evolve. Loosely speaking, every genetic algorithm follows 5 steps.

• Initial Population: The initial set of solutions. Each solution has certain genes (set of parameters) that determine its behavior. The genes vary among the individuals and this is known as variation .

Note: If there is no variation in the initial population then each solution will evolve exactly in the same way and we will fail to explore orher solutions!

• Fitness Function: A mathematical function to determine how fit (optimal) a solution is by assigning a fitness score to every solution. This will be helpful in the next step.
• Selection: In this step, we select the fittest individuals and allow them to pass their genetic information to the next generation.
• Crossover: Combining the genes of two (or more) parents to produce one individual of the next generation.
• Mutation: While transferring genetic information from the current generation to the next one a very small percentage of the information is changed randomly.

Note: Because of mutation, some new traits (properties) will be introduced that will ‘hopefully’ make our solution more optimal. ‘Hopefully’ because mutaion is random and can affect negatively too!

III. Combining NN with GA

Now is the time for the big reveal. How would you combine these two completely different algorithms? The main idea is to consider the weights of the nn (brain) as genes. Initially, we start with a population of 250 creatures each with its separate brain. To have variation in the population we initialize the weights for these neural networks randomly. We will pass the best weights to the next generation. How would you determine which balls are better? We will use the fitness score. In my case, the fitness score is a linear function of distance covered by the creature. So, the creatures who have covered the largest distances will have a greater probability of creating offsprings. Thus their nn’s weights will be transferred to the next generation. Now, let me mention a couple of details here…

i) I’ve not used the concept of crossover so one creature can create its offspring without mating with another one.

ii) Creating offsprings (in this case) means copying the weights of one creature’s nn and making a new one with the previous creature’s weights after adding some mutation.

iii) The mutation is nothing but changing a small percentage (generally less than 2% ) of weights randomly by a small amount.

Doing this process over and over again mimics the biological evolution and after many generations, we hope to obtain some creatures with optimal weights. In other words, after many generations, we will have some little guys who can decide the values of x and y accelerations such that it can jump over the next red bar. In terms of Machine Learning, we have successfully trained our model :D

But we never used backpropagation!

In traditional Deep Learning we use a gradient based optimization technique (aka backpropagation) to train neural networks. In that case we take the last layer’s error and propagate it backwords and in each layer we calculate the gradient and based on this we change the corresponding layer’s weights. But in this case (GA+NN) we can’t perform backprop. Why? Because we can’t calculate error from the last layer (as we don’t know the ground truths). We are solely dependent on the selection and mutation for learning.

Want to watch the A.I. learn? Here’s the video…

Visit the web app…

https://suji04.github.io/jumpingameAI/

Code for the game and AI…

https://github.com/Suji04/jumpingameAI