An Introduction to Neuroevolution

How a Neural network found a loophole in my game?

Evolved an AI to play a game, but it chose to mock it!

Photo by Adam Muise on Unsplash

Before you look into how an AI trolled my game, let’s get familiar with the basics of ‘Neuroevolution’ to understand why it happened.

There are 2 main things involved in neuroevolution
1. Genetic Algorithm
2. Neural Network

Genetic Algorithm

The concept behind this algorithm is inspired by Darwin’s Theory of Evolution.

These are the major stages of Genetic algorithm…

1. Generate a random population
2. Calculate the fitness of each member of the population
3. Perform natural selections
4. Perform crossover with naturally selected members
5. Randomly apply mutation on offsprings as a result of crossovers
6. The new population is created, discard old generation and go to step 2

See, you may take an intuition of this from the real world evolution of human or other living beings, but after all, do keep in mind that Genetic Algorithm is basically a search algorithm.

Consider this graph, let’s say here you want to search for an (x,y) point such that ‘z’ value at it is maximum. Initially, the graph would be totally unexplored, so you aren’t really sure about ‘z’ value for any other points in the graph but the initial point.

We can apply many search algorithms to do this for us, but let’s see how Genetic Algorithm would do it.

Step: Random population

First, in GA(Genetic Algorithm) we will start with a few random points or we can say random guesses from the solution space. For example, in the above graph, we see that ‘x’ value can be anything from -3 to +3, and the same range goes for ‘y’.

So our random guesses might look like…

If we talk in terms of GA, that was random population generation. We basically generated a random population of (x,y) pairs, each will have some ‘z’ value. These ‘x’ value and ‘y’ value can be considered as genes.

Step: Fitness calculation

Now comes the fitness calculation, this is because we want to judge which of the random guess is better than other and we need something to compare concretely.
So we have to define a fitness function, which will say how fit is that random guess. In this example, it’s pretty simple as we need (x,y) pair with maximum ‘z’ value, so for some random guess, their ‘z’ value can act as their fitness score.

fitness(x, y) = z-value

So, now considering that fitness function we look up z-value for each point and we get a relation between them as shown below.

fitness(-2.2, 2.3) > fitness(0.1, -2.4) > fitness(2.0, 1.4) > fitness(1.0, 2.0)

Step: Natural Selection

Now we perform natural selection, which means randomly picking one of the random guesses, but the random pick is based on probability distribution. That means the ones which has higher fitness value will be more likely to get naturally selected. Ones with very low fitness may not get selected.

“Survival of the fittest” — Charles Darwin

For example, let’s say pairs (-2.2, 2.3) & (0.1, -2.4) get selected.

Step: Crossover

Next step is crossover or simply saying, those 2 naturally selected pairs’ genes get mixed up and forms a new hybrid pair, aka offspring!

( Crossover )

The diagram above illustrates how crossover may take place in this example. It mixes genes from both parents to form a single offspring.
We repeat natural selection multiple times and do cross over to generate offsprings.

Step: Mutation

Now, on these new offsprings, we perform ‘Mutation’, which means randomly changing it’s genes’ values. Though the occurrence of mutation depends on the mutation rate, if the mutation rate is 100% then all offsprings generated will get mutated, if the mutation rate is 5%, then only 5% of offsprings will get mutated.

( Mutation )

Above illustration shows how ‘y’ value was randomly mutated to -2.3.
The mutation is done to maintain diversity in the population, because if the population stays pretty much the same then we won’t be able to explore the graph as much as we need, and as a result, we won’t reach the highest point.

Now, after mutation is applied, we have a brand new population of offsprings, which is probably better than the previous population or we can say the previous generation, as we tend to select better members from a population (through natural selection) and then mix up their genes(through crossover).

At this point, we will discard the old generation and start performing the same steps again from fitness calculation on this new generation.

(that’s the rough big picture of GA)

As this loop keeps going, after some time all members will converge to the same point, which will be the highest point in the solution space and that’s our goal and that’s when this algorithm stops.

👇 Recommended videos on this topic 👇
Genetic Algorithm: Introduction | The Coding Train
Learning: Genetic Algorithms | MIT OCW

Neural Network

Biological Neuron (Image source: Wikipedia)

The idea of the neural network is derived from the human brain itself. This concept explains how we learn stuff based on that we can apply the same concept to make a computer learn things!

The Artifical Neural Network(ANN) is based on Biological Neural Network, though they’re not exactly same, ANN can be seen as an abstraction of actual biological neural network.

Neuron

A neural network is made up of a bunch of interconnected neurons. So, before looking at the neural network, let’s take a look at a single ‘neuron’ that we use in ANN. We have named this artificial neuron as Perceptron, as they are implemented slightly differently, still let’s just keep calling it a neuron to keep the biology analogy for now.

( Artifical neuron )

Imagine this neuron as a function which takes a bunch of inputs (real number) and gives a single output. So now the question is what this function does to its inputs to produce the output.
You see in the above illustration of the neuron each input value is passed to the neuron through an edge, and this edge has a ‘weight’ associated with it.

i.e. when input ‘x1’ goes to the neuron through an edge which has weight ‘w1’ as shown in the diagram, value at the neuron becomes x1 * w1.

( Operations happening inside a neuron )

Then all such values received from the different input edges are summed up and then there’s also a value called ‘bias’ associated with neuron which gets subtracted from that sum and then this result is passed into the activation function.

What is this activation function? There are many options for this, let’s say it is a sigmoid function.

Sigmoid function (Image source: Wikipedia)

This function takes any real number and squashes it between 0 and 1.

So, the output of this activation function is the output of the neuron. That bias is used to set a threshold value before entering the activation function.

Ok, a neuron is fine, but what’s the use of it?
For instance, you can implement AND Gate with a neuron!

As the output is value given by the sigmoid function, it can range from 0 to 1. So, if we get output < 0.5, we will consider the result = 0
Similarly if output > 0.5, we will consider the result = 1

let w1 = 2.0, w2 = 2.0 and bias = 3.0

Now let’s test this with all inputs

if x = 0, y = 0
output
= sigmoid(x*w1 + y*w2 -bias)
= sigmoid(0*2 + 0*2 -3)
= sigmoid(-3)
= 0.04743

output < 0.5, result = 0

if x = 0, y = 1
output
= sigmoid(x*w1 + y*w2 -bias)
= sigmoid(0*2 + 1*2 -3)
= sigmoid(-1)
= 0.26894

output < 0.5, result = 0

if x = 1, y = 0
output
= sigmoid(x*w1 + y*w2 -bias)
= sigmoid(1*2 + 0*2 -3.5)
= sigmoid(-1)
= 0.26894

output < 0.5, result = 0

if x = 1, y = 1
output
= sigmoid(x*w1 + y*w2 -bias)
= sigmoid(1*2 + 1*2 -3.5)
= sigmoid(1.0)
= 0.73106

output > 0.5, result = 1

But how did we find such weights and bias? This ‘setting up weights and biases’ part is all where the learning logic goes. After setting up inputs and outputs schema, all we need to do is to just find appropriate values for those weights and biases! Basically, that’s what learning is in nutshell! We will get back to learning part soon.

Now, probably you are feeling like, “AND gate is boring… Can’t we do a bit more cool stuff?”
Of course! We sure will, but before that let me tell you that a single neuron is not enough to solve all kinds of problems, as they are capable of solving only linearly separable problems.

Informally saying, you need more neurons to do cool stuff!

Multilayer Artificial Neural Network

Multilayer ANN to the rescue!
It has 3 kinds of layers :

1. Input Layer
2. Hidden Layer
3. Output Layer

( Multilayer artificial neural network )

There can be more than one hidden layer, it depends on the use case. The number of neurons in each layer is also use case dependent. Each neuron is connected to all neurons of the next layer (though they can be partially connected). Each neuron has a bias value and each connection has associated weight with it. The process of processing from inputs to outputs layer by layer is called feedforward.

To understand it, imagine this whole neural network thing as a function, which can take inputs and returns outputs.
For example, You can design ANN to take sides of a rectangle as input and area of the rectangle as output, but that we can do on our own with simple logic.
But we use the neural network when deriving a straight forward logic is not as easy. Consider the problem of writing a computer program which takes pictures of handwritten digits and guesses what digit it is. In that case, input neurons would be all pixels and outputs would be 10 neurons for all digits and you can experiment for hidden layers.

Handwritten digit classifier ANN’s feedforward (Source: 3blue1brown)

Okay, this input and output part is fine, but what’s with the weights and biases? That’s the thing which will make these outputs possible, without the right weights and biases, a neural network is just a stupid thing!

ANN with random weights and biases (Source: 3blue1brown)

So, how does a neural network learn?

There are several approaches to this. One of them is to initialize ANN with random weights and train it with some labelled data set and based on errors we keep adjusting its weights and biases through backpropagation which uses a concept called gradient descent. This type of learning is called Supervised Learning.

We can also use Reinforcement learning. Here agents start performing in its randomly initialized state and based on results of their actions they keep adjusting. We can apply the Genetic Algorithm to achieve this kind of behaviour, let’s see this in the next section.

👇 Recommended video on this topic 👇
But what is a Neural Network? | 3blue1brown

Neuroevolution

Evolving neural networks using genetic algorithm is ‘neuroevolution’.
That being said, the term ‘Neuroevolution’ makes sense, right?

Neural Network + Evolution = Neuroevolution

First, we identify the problem statement and design a suitable neural network architecture. But to make it work right, we need to find the right weights and biases for it, so now GA comes into the picture.

We generate multiple ANNs initialized with random weights for their connections, thus a random population of ANNs. So, here all of these randomly generated weights would result in just some stupid ANNs, but since it’s random, some ANNs would be less stupid and some would be more stupid. We know what this neural network is supposed to do, so by its performance, we can calculate its fitness. Here weights and biases would be genes of ANN. Based on fitness values and probability distribution natural selection will occur. For crossover, naturally selected ANN’s weights and biases would be mixed to form a hybrid ANN. During mutation, some weights and biases get randomly changed slightly. Through natural selections, crossovers and mutations as we move forward with new generations, ANNs start to improve in the direction guided by the fitness function.

(Basic neuroevolution algorithm)

It’s still a search algorithm though. Earlier, when we were trying to find best (x, y) point using GA, we were actually exploring the 2 dimension space of X-axis and Y-axis. Similarly here assume a dimension for the weight of each connection of an ANN and bias of each neuron, It’s hard to imagine that visually, but basically we are exploring dimension space of all weights & biases and trying to find best weights and biases vector in that space.

As we keep this loop running, eventually the ANN should behave the way we expected.

👇 Recommended video on this topic 👇
Introduction to Neuroevolution | The Coding Train

The mischief of a neural network

I got inspired by this Flappy Bird with Neuroevolution coding challenge where they use neuroevolution to let the computer learn to play the game on its own. check the live version of their project.

So, I wanted to do a similar project on some other game, so I started looking for a simple game where I could apply this algorithm.

After a bit of research, I decided to make my own game 😛 and then use this algorithm on that.

Now this project had 2 parts:

1. Design and implement the game
2. Apply neuroevolution algorithm on it

Now, designing the game… long story short, I came up with this game called ‘escape jump’ (a friend helped me with the name 🙃 )

(Me playing the escape jump game)

Here you control that red ball with arrow keys, and you have to escape through or jump through the space between the pipes (black bars) before it squeezes you (the red ball), at which point both pipes will close is unknown in the beginning, so you have to make a quick judgment when they appear. If you are on a desktop, you can try this game right now from this link. Try it and see how much you can score, and later see how much the AI scored on its own!

Ok, I know that the game is not so decent looking, though I think it’s good enough for this experiment, isn’t it? it’s not too easy neither too hard, a fair game I thought.

But life never went the way I feel 😅, yet I went with it anyway to see where it goes.

(ANN architecture I used)

For neuroevolution, we initialize the game with multiple balls each having their own ANN (as shown in the above diagram) which makes the decision for them. ANN takes input at each frame and takes action based on ANN output.

(Inputs and Outputs of ANN in code)

That function above is from the ‘Ball’ class. It shows how it is passing inputs to the ANN and how it’s using outputs of ANN to make the decision of whether to jump or to move.

We let all balls play together in the same game. Number of seconds the ball survives in the game can be considered as their fitness. A ball dies when it gets squeezed in between the pipes. When all of the balls die, we would have fitness score for each ball, based on that we can perform natural selection, crossover, mutation and then the new generation emerges.

(Initiating neuroevolution algorithm)

So, that’s how it looks, now if you have seen how that flappy bird was learning to play on its own using this algorithm, you can kinda imagine how this game should have gone. It should have learned to play like we normally would, something similar to what I was playing in the first animation shown.

So, I ran it for a few generations and was surprised by what it did to the game, it felt like the computer was making fun of my game 😂

Here’s what it learned after a few generations (animation played at 4x speed)

So, this algorithm found a place where it can keep jumping at regular intervals and beat the game! Wow! Though initially, I was a bit sad realizing my game was too easy to play, then I realized that an AI told me that, I realized that I just accidentally used an AI to find a loophole in a game, it felt better that way.

I never fixed that loophole though 😜, probably I’ll just keep the code this way.

That’s it!

If you want to see this simulation and play around with it, Checkout this
If you want to take a look at this code, here’s a link to its GitHub repository