Flappy Bird Neuroevolution
Genetic Algorithm
This is a simple example of the power of artificial intelligence. In this program, the computer "learns" as it
"evolves" to find an optimal solution to the problem, in this case, to make it through as many pipes as possible.
This process is based off natural selection and Darwinism, otherwise known as survival of the fittest. The
program starts out by asking the user for a population size. There is a tradeoff between the population size and
how fast a solution is found. The larger the population, the fewer generations are required to find a solution, but
each generation takes more time to compute. Likewise, a smaller population size will require more generations
to find a solution, but each generation will go by faster. It is important to find the happy medium between the
generations and time required. I found that a population size of 200 works really well. Each generation, all birds play the game simultaneously. Every frame, each bird that is still alive gets one more fitness, which is a measure of how well it performs. When every bird dies, certain parents are selected at random, based on their fitness, to “breed” a new generation using the biological process of crossover. What this means is that the higher the fitness of any given bird is, the more likely it is to be picked as a parent. For this example, I have simplified the crossover to just copying the parent’s brain exactly. Next, each new child’s brain is “mutated”. What this means is that some numbers inside the new brain will change to a random number based on a mutation rate that is predetermined. For this example, it was 1%. This process is repeated for many generations until an optimal solution is found. This diagram below shows a simplified explanation.
"evolves" to find an optimal solution to the problem, in this case, to make it through as many pipes as possible.
This process is based off natural selection and Darwinism, otherwise known as survival of the fittest. The
program starts out by asking the user for a population size. There is a tradeoff between the population size and
how fast a solution is found. The larger the population, the fewer generations are required to find a solution, but
each generation takes more time to compute. Likewise, a smaller population size will require more generations
to find a solution, but each generation will go by faster. It is important to find the happy medium between the
generations and time required. I found that a population size of 200 works really well. Each generation, all birds play the game simultaneously. Every frame, each bird that is still alive gets one more fitness, which is a measure of how well it performs. When every bird dies, certain parents are selected at random, based on their fitness, to “breed” a new generation using the biological process of crossover. What this means is that the higher the fitness of any given bird is, the more likely it is to be picked as a parent. For this example, I have simplified the crossover to just copying the parent’s brain exactly. Next, each new child’s brain is “mutated”. What this means is that some numbers inside the new brain will change to a random number based on a mutation rate that is predetermined. For this example, it was 1%. This process is repeated for many generations until an optimal solution is found. This diagram below shows a simplified explanation.
Neural Network
A neural network is way to simulate the way a real brain works, but for specific tasks. Modern technology isn't there yet but with enough computational power, they can be used to simulate a human brain. Neural networks have a few parts to them. They are made up of nodes, weights, biases, and an activation function. For this neural network there are three layers: an input layer, a hidden layer, and an output layer. The inputs are given to the input nodes, there is one for every input. The six inputs are the bird's y-axis location, falling velocity, upward velocity, the pipe's x-axis location, the height of the top part of the pipe, and the height of the bottom part of the pipe. These numbers are given to the six input nodes. The next layer is the hidden layer. Here the hidden layer has 10 nodes. There is a weight connecting each of the 6 input nodes to all of the 10 hidden nodes. Each weight is a number between -1 and 1. The values from the input nodes are put into a matrix and so are the weights. Then the dot product of the two matrices is computed, which will result in a new matrix with 10 values in it. These are the 10 values for each of the hidden nodes. Then a bias, which is also a number between -1 and 1, is added to each node. Then the value for each node goes into an activation function. For the activation function I used the Rectified Linear Unit (ReLU). The value of each node is replaced with the output from the ReLU function. The next layer is the output layer. Since the output of the neural network is binary, meaning there are only 2 options (jump or don't jump), there is only one output node. If this node is on, meaning the number is greater than 0, the bird will jump. Likewise if it is off, which is a value of 0 (the value of any node can never be less than 0 because of the activation function I chose), the bird won't jump. Next, all the values from the hidden nodes are put into a matrix and then the dot product is found with the matrix of weights between the hidden layer and the output layer. This will result in a matrix with one number in it, the value for the output node. Then a bias is added to this value and the resulting value is given to the ReLU function to get one last number. This number determines whether the bird jumps or not. The picture below shows a diagram of the neural network used for each bird's brain.