How I Built an Intelligent Agent to Play Flappy Bird
Introduction
Have you ever played Flappy Bird? In this animation, you are looking at a skilled player playing the game Flappy Bird. However, this player is not a human being. It is an Intelligence Agent (IA) I built using the NeuroEvolution of Augmenting Topologies (NEAT) algorithm.
In September 2019, an article released by OpenAI called Emergent Tool Use from Multi-Agent Interaction demonstrated how agents learn to use sophisticated tools and strategies progressively in a simulated hide-and-seek environment. I found it particularly interesting and would like to learn more about Reinforcement Learning (RL).
During my study, I came across a paper by Uber AI Labs titled Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning, where researchers presented empirical evidence that a simple Genetic Algorithm (GA) can perform amazingly well for RL problems. Besides the hide-and-seek example we saw above, RL has been successfully applied to various games such as Atari, Snake, and Dino Run. What if we could build a game IA using GA instead? This thought triggered my keen interest in building a Flappy Bird IA using NEAT, a GA developed by Ken Stanley in 2002.
Why Flappy Bird?
For those who are not familiar with the game Flappy Bird, it is a popular mobile game developed by Dong Nguyen in 2013. Flappy Bird received a massive influx of players and achieved great success in a short period. Players tap the screen to navigate the bird, which has to jump at the right moment to get through a set of Mario-like pipes.
Flappy Bird is a reasonable choice for beginners interested in building a game from scratch, because the game’s mechanism is straightforward and the only gameplay action is to jump. Also, creating an IA won’t be too complicated, since we just need a few inputs to get a binary output (I will talk about it later). Last but not least, Flappy Bird is one of my favorite mobile games ever! So, when it comes to building my first game, Flappy Bird is a no-brainer.
How to build Flappy Bird in Python?
The main module that I used is Pygame. There are tons of tutorials available online, and here are some of my favorites:
- A Newbie Guide to Pygame
- PyGame Tutorials: Simple Introduction to Game Programming
- YouTube Playlist for PyGame Tutorials by thenewboston
In terms of building Flappy Bird in Pygame, there are also a lot of tutorials. Here is a list of tutorials that I found very useful. I took notes from them, summarized their methods, and tried to build my code on top of theirs. Please check them out if you would like to learn more about this.
- AI Plays Flappy Bird Using NEAT Python by Tech with Tim
- Neural nets with Flappy and Pygame by Bluefever Software
- Flappy Bird Python Tutorials For Absolute Beginners by CodeWithHarry
Before coding, I always draw a mind map to guide me through the process. Here is the demonstration of the mind map:
To make Flappy Bird, we need three Python objects: the bird, the pipe, and the floor. We also need a few functions to check collision, display, and run the game. Like most games, the game options section allows us to alter some game features according to our preference.
Now, let’s dive into code!
First of all, import packages, initialize Pygame, and set up the screen to display the game.
Here are some game options that will be used later.
- How to build a bird?
We need a few class methods to mimic the movement. Recall what we learned in our middle school Physics classes, the equation to calculate the displacement d of a body that starts with a non-zero speed v from time 0 to time t is: d = vt + 1/2at², where a is the acceleration. If the bird jumps, it obtains an upward velocity. Then we update the bird’s position according to the displacement calculation.
- How to build a pipe?
The pipe is more straightforward than the bird. Pipes move horizontally with a fixed velocity. A simple move method is shown below. Another class method we need is to randomize the position of pipe gaps. Because the size of each gap is the same, we can simply randomize the height of the top pipe, and then the height of the bottom pipe will change accordingly.
- How to build a floor?
The floor is the simplest one. It moves horizontally with a fixed velocity. We can duplicate three images and tie them together. Once the first image moves out of the screen, we append it to the right of the last image. The same applies to the second and the third image.
- How to check collision?
If the image of a bird overlaps with the image of a pipe, then we say the bird hits the pipe. There are mainly two ways to check overlap. One is called Rectangle Collision Detection by pygame.Rect.colliderect function. The other is called Pixel Perfect Collision Detection by pygame.mask.Mask.overlap function. Note that we also say the bird collides if it hit the upper limit or the ground.
- How to display the game?
Here is the function to display the game. We draw a background, a moving floor, a set of pipes, and a flock of birds. We also add a few text messages to show some additional information.
Now the game is almost done, let’s see how to build an IA.
NeuroEvolution of Augmenting Topologies (NEAT)
NEAT stands for NeuroEvolution of Augmenting Topologies, which is a genetic algorithm designed to efficiently evolve artificial neural network topologies. It’s an awesome technique that addressed some challenges of Topology and Weight Evolving Artificial Neural Networks (TWEANN). Before we go deeper into NEAT, let’s take a look at two key concepts: Artificial Neural Network (ANN) and Genetic Algorithm (GA).
What is an artificial neural network?
An artificial neural network (ANN) is a brain-inspired computing system that consists of interconnected nodes and weighted connections. A typical ANN architecture contains an input layer, some hidden layers, and an output layer. Each node in the hidden layer and the output layer consists of an activation function that transforms the weighted sum of input values to output. In most cases, an ANN can learn by properly adjusting its connection weights through backpropagation, a technique that performs gradient methods to minimize loss.
If you would like to learn more about ANN, here are some resources that may be helpful:
- Wikipedia: Artificial Neural Network
- Introduction to Artificial Neural Networks(ANN)
- YouTube Playlist for Neural Networks Tutorials by 3Blue1Brown
What is a genetic algorithm?
“We see beautiful adaptation everywhere and in every part of the organic world.” — Charles Darwin, On the Origin of Species.
In 1859, a theory of natural selection introduced by Charles Darwin lay the first stone of evolutionary biology. The essence of this theory is that those most adaptable to change are most likely to survive. Since then, the notion of “Survival of the Fittest” provided a new way for people to understand species evolution.
If biological evolution is able to generate amazing species like human beings and many others, is it possible to combine modern genetics with machine learning techniques to solve a problem? Genetic algorithms open the door of opportunity and shine the way to possibilities.
By definition, a genetic algorithm is a heuristic technique that simulates the process of natural selection to solve a vast variety of optimization problems, especially those with a nondifferentiable or stochastic objective function.
Here are some of the key terms:
- Fitness function: In many cases, a fitness function is the same as an objective function. It is a function that takes the solution as input and generates a fitness score as output to evaluate the quality of each solution. It is an essential element of a GA. We should tailor the fitness function based on each specific problem.
- Population: In GA, the population is the subset of all the candidate solutions to a given problem.
- Chromosome: Each candidate solution in the population is a chromosome, sometimes referred to as a genome.
- Gene: Each element position within a chromosome is a gene, which has a specific value and determines the genotype and the phenotype of the solution.
- Generation: At each iteration, GA performs a set of genetic operators (selection, crossover, mutation, etc.) on the current population to generate a successive generation.
- Selection: Selection is the process of filtering and retaining solutions according to fitness score. Solutions with higher fitness are more likely to be pushed forward into the next generation. A pair of selected solutions could be chosen as parents to breed and propagate their genes to the subsequent generation via crossover.
- Crossover: Crossover is the way parent chromosomes produce child chromosomes. Genes of parents are reassembled based on a set of crossover points to formulate new offspring.
- Mutation: Mutation in GA is a small random tweak of the genes in chromosomes. It allows GA to explore the solution space and avoid falling into local minima.
Here is a demonstration of how a typical GA works:
In the beginning, we randomly generate N solutions as our initiated population. We then move on to the evaluation stage, where we assign tasks and calculate the fitness score for each solution. Next, we determine whether to terminate the literation based on the following conditions: Did we obtain an acceptable solution? Did we reach the time or generation limit? Are we stuck in the performance stagnation? If no, we will proceed and conduct genetic operators to reproduce offspring for the next generation.
To help illustrate the workflow, here is the “Hello World” problem for GA, the Knapsack Problem.
Imagine that you are given five items with different weights and values. You want to maximize the total value of the items included in your bag. However, your capacity is 15 kg. The optimal collection in this example may seem intuitive to you, but let’s see how a GA approaches this problem.
In this case, we define the fitness function as the summation of the value of each item included in our bag. In other words, we believe a collection is better if its total value is higher. Besides, the total weight should not exceed our capacity. At the beginning of the iteration, we randomly generate four solutions (population) as our first generation. For each solution (chromosome), we denote whether an item is included (“1”) or not included (“0'), representing a gene. Each proposed solution has a fitness score. The top-scored solutions are more likely to be chosen as parents (selection). The two selected chromosomes exchange some of their genes based on crossover points (crossover). Moreover, there is a small probability that some genes of the new offspring will change (mutation). Finally, a new generation is born. The loop will continue until termination requirements are met.
Now that we have some basic knowledge of ANN and GA, let’s dive into NEAT!
What is the NeuroEvolution of Augmenting Topologies?
In short, NEAT is a GA designed to evolve ANN. One big question you may have is what makes NEAT special? I believe the answer to this question can be found in this brilliant 6-page paper written by Kenneth Stanley in 2002. The following discussion is based on this original paper.
The process of evolving an ANN using GA instead of backpropagation is also known as Neuroevolution (NE). The beauty of NEAT is that it renders solutions to tackle three main challenges for NE:
- Is there a genetic representation that allows disparate topologies to crossover in a meaningful way?
- How can topological innovation that needs a few generations to optimize be protected so that it does not disappear from the population prematurely?
- How can topologies be minimized throughout evolution without the need for a specially contrived fitness function that measures complexity?
Here are the key concepts that underpin NEAT:
- Genetic Encoding: Genetic encoding is the process of representing the chromosomes in a GA. NEAT uses a direct encoding scheme that each genome consists of a list of node genes and a list of connection genes. Node genes indicate all the input, hidden, and output nodes that can be connected, while connection genes store the connection information and an innovation number for historical markings. By doing so, NEAT can line up the corresponding genes quickly during the crossover process.
- Growth: NEAT grows and evolves the topology by structural mutation. Mutation can be adding a new node in an old connection or adding a new connection between two unconnected nodes. Therefore, NEAT is able to improve genome diversity, explore solution space, and avoid local minima.
- Historical Markings: Historical markings is the process of tracking genes. NEAT uses a global innovation number that represents a chronology of a gene in the system to perform historical markings. A new innovation number will be assigned to that gene whenever a new node or connection is created. During crossover, the offspring randomly choose genes with the same innovation number (matching genes) from either parent and inherit those with different innovation number (disjoint or excess genes) from the more fit parent. Accordingly, NEAT ensures the crossover is meaningful and resolves competing convention, a situation that parents with a similar phenotype produce damaged offspring.
- Speciation: A topological innovation usually comes with reduced fitness and requires time to optimize its performance. However, if competing with the overall population directly, a new topology is likely to be eliminated before it reaches its best fitness. This is why speciation plays a critical role in NEAT. NEAT measures a compatibility distance between two genomes. Compatibility is calculated by a linear combination of the average weight differences of matching genes and the number of excess and disjoin genes. Genomes are clustered into different species based on a compatibility threshold. By doing so, each genome competes with those within the same niche. Therefore, a new species will be protected.
- Minimizing Dimensionality: NEAT always begins with a uniform population and without any hidden nodes. A new structure is introduced by structural mutation and protected by speciation. Then fitness evaluation determines whether the innovation is useful. So, NEAT increases the complexity only when needed and thus decreases training time.
Here is an overview of the dependencies among these important components of NEAT:
To sum up, NEAT (1) utilizes historical markings to tack genes and avoid competing conventions, so that a meaningful crossover could happen and less topological analysis is required; (2) separates the population into species based on compatibility distance, so that competition is primarily within the same niche and innovation is protected; (3) starts from the simplest structure and grows only as necessary through mutation, so that it’s faster to find a solution.
Now we know how NEAT works, let’s see how to use it.
How to apply NEAT to Flappy Bird?
It’s fairly simple to implement NEAT in Python, because there is a well-developed NEAT module that we can install by pip install neat-python. The documentation of this module clearly explained how to run NEAT in Python. So, check it out!
First, set up some parameters that will be used later.
We also need a configuration file for NEAT. You can find more explanation here.
Here are a few important parameters in the configuration file:
- fitness_threshold: A parameter used to check whether we obtain an acceptable solution. The evolution process will terminate if the calculated fitness meets or exceeds this threshold.
- pop_size: the number of genomes in each iteration.
- survival_threshold: for each species, the percentage of genomes allowed to be selected for reproduction.
- activation_default: the activation function assigned to each new node.
- conn_add_prob: In mutation, the probability of adding a new connection.
- node_add_prob: In mutation, the probability of adding a new node.
My configuration file for this project is shown below.
The fitness function is the combination of the game score, the alive time, and a collision punishment.
For each frame, the inputs of the models are:
- delta_x: the horizontal distance between the bird and the pipe
- delta_y_top: the vertical distance between the bird and the top pipe
- delta_y_bottom: the vertical distance between the bird and the bottom pipe.
The output is whether to jump or not.
Note that all the input information comes from the upcoming pipe, so we need a function to get the index of the closest pipe in our pipe list.
We also need a few functions for visualization. You can check an example here.
Then, we integrate NEAT into the game loop. The game runs by looping. Each loop is one frame. In each frame, we move the three objects we created, jump the bird if needed, check collision, and calculate the game score. The game will update according to game inputs and game logic.
Finally, we show learning progress in the terminal, visualize it, and check the statistics of the best model.
Results
Since Flappy Bird is a simple game (from a computer’s standpoint), it only takes NEAT ten generations to crack the game (Generation 0 is our first population). Let’s take a look at the species distribution and fitness improvement.
Note that all individuals belong to the same species because we found a solution before any topological innovation occurred. From generation 0 to generation 4, all birds almost immediately hit the ground or the upper limit. From generation 5, NEAT started to know how to keep the bird flying, but it still didn’t figure out how to get through the pipes. At generation 9, a huge breakthrough happened: a bird learned how to pass the pipes and became a skilled player you saw at the beginning of this article.
Here is the architecture of our best model. A solid line indicates an enabled connection, whereas a dashed line indicates a disabled connection. A green line indicates that the weight of the connection is positive, while a red line indicates that the weight is less than or equal to zero. The linewidth indicates the magnitude of the connection weight.
The final architecture only includes an input layer and an output layer. Recall that NEAT always evolves the structure from a minimal starting point (Minimizing Dimensionality), so NEAT is able to find a low-dimensional solution efficiently. Besides, the weights of delta_y_top and delta_y_bottom are both positive, while the weight of delta_x is non-positive. The magnitude of each connection weight is pretty much the same.
Although the population is very small (5 chromosomes/generation), NEAT mastered Flappy Bird within ten iterations. It proved that NEAT is a robust technique for the efficient evolution of network structure.
Thank you so much for reading!😄 I hope you enjoy this article. Don’t forget to check out the source code for this project. Feel free to use, modify, or contribute! More interesting projects that I’ve done could be found here.
Don’t hesitate to leave your feedback in the comments section below. I’d love to share any thoughts about Pygame, GA, or NEAT with you! You can also reach me on LinkedIn. I am always up for a chat!😃
And if you like this article, please hit the clap button👏 so others may stumble upon it.
References
- Efficient Evolution of Neural Network Topologies by Kenneth O. Stanley
- Evolving Neural Networks through Augmenting Topologies by Kenneth O. Stanley
- Efficient Evolution of Neural Networks through Complexification by Kenneth O. Stanley
- NEAT-Python Documentation
- NEAT: An Awesome Approach to NeuroEvolution by Hunter Heidenreich
- Neuroevolution of Augmenting Topologies (NEAT) by Henry AI Labs
- Emergent Tool Use from Multi-Agent Interaction by OpenAI
- Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning by Uber AI Labs
- A Newbie Guide to Pygame
- PyGame Tutorials: Simple Introduction to Game Programming
- YouTube Playlist for PyGame Tutorials by thenewboston
- AI Plays Flappy Bird Using NEAT Python by Tech with Tim
- Neural nets with Flappy and Pygame by Bluefever Software
- Flappy Bird Python Tutorials For Absolute Beginners by CodeWithHarry
