Piano Tiles (Don't Tap The White Tile) - High Score 10.025!Bird - High Score 999!Click Here for more videos. Flappy Bird was similar to other games Nguyen had released on mobile devices, games like Shuriken Block or Super Ball Juggling. The graphics played cute homage to retro sprite art, the gameplay.
Introduction
AI is taking control of the whole world very rapidly. From diagnosing cancer to generating different & unique versions of 'Game of Thrones' ending, AI is in action everywhere. In March 2016, AlphaGo beat Lee Sedol in a five-game match with a final score of 4-1. The AlphaGo was trained by Reinforcement Learning. The basic idea behind Reinforcement Learning is to reward the 'agent' for his good decisions and punish him for the bad decisions. The reward will encourage him to take the similar decisions under the similar circumstances in future and the punishment will tell him not to repeat such actions in future. We are going to apply same mechanism to our flappy bird game and watch him play the game while we sit back & assume that we ourselves are playing this game so perfectly. The reward will be the increment in score whenever the bird succesfully crosses the pipe and the punishment will be his death whenever he collides with the pipe or ground or the sky( My Neural Network was unable to find some other word).
What is NEAT?
NEAT stands for Neuroevolution of Augmenting Topologies. As the name suggests, it is the evolution of neural networks, or the evolution of the weights of neural network. It mimics the process of natural evolution. Every generation starts with some number( 300 in our case) of population( bird). The first genration's individual are not smart, thier brain has random neural networks, but out of that randomness, there is a chance that some individuals might take some good decisions during their lifetime. When all the individuals of that generation die, the two individual are chosen based on their good decisions, and they are crossovered( mixing of the weights of both neural network), followed by mutation( random twerks in weights). After this process a new individual is born, same procedure goes on for all the individual of that population. Now we have a new genration with some traits from their parents and some acquired traits( due to mutation). This new genration again goes for the only goal in their life, which is to get maximum score before dying. Again after all the individual die, their traits are passed on to next generation. So by this way, every genration gets smarter as compared to their previous generation.
Now we will apply this theory to our flappy bird and make him immortal.
Implementation
Note: In this section we will not be focussing on the making of the game, our main focus will be on AI. If you want to know about the making of game, which I recommend, click here.
So, let's start the journey!
For implementing this algorithm, the first thing we need is the population of bird. So we initialize our program with appending the population of birds in our birds array.
The gameLoop() is our main function of the game, where the loop which controls the whole game, resides. But first, let's take a look at our Bird() class.
This is our __init__ function of Bird(). For now, ignore the other initialisations and focus on self.brain = NeuralNetwork(8,5,2).
Now, we will look at the __init__ function of NeuralNetwork() class.
As you can see, NeuralNetwork() takes three parameter, input_nodes, hidden_nodes, output_nodes, and then with these parameters we initialize 4 randomly generated matrices self.in_hidden_weights, self.hidden_output_weights, self.in_hidden_biases, self.hidden_output_biases. These function initialises a 3-layered neural network, the first layer be the input layer with number of nodes in it as input_nodes, the second layer as hidden layer with number of nodes in it as hidden_nodes and the third layer as output layer with number of nodes in it as output_nodes. And the 4 randomly generated matrices are the weights of the neural network with self.in_hidden_weights as the weights between input layer & hidden layer, self.hidden_output_weights as the weights between hidden layer & output layer, self.in_hidden_biases & self.hidden_output_biases as the biases between input layer & hidden layer, hidden layer & output layer respectively.
Now let's look at the variable self.brain of Bird() class. self.brain = NeuralNetwork(8, 5, 2)
So, this indicates that every bird object has a brain variable which is nothing but the randomly generated Neural Network.
Now let's look at the __init__ method of Game() class, where our program started.
So, what this particular block of code doing is appending 300 birds with their respective brain(Neural Network) into self.birds array and then calling the self.gameLoop() method which is the mainLoop handling our game.
Now, let's take a look at self.gameLoop() method.
So, what this self.gameLoop() method doing is traversing through every bird in self.birds list and performing some operations on them. Let's look at these operation one-by-one.
1. showBird()
Let's look at the method showBird method of bird class.
Apart from the self.brain, Bird() class also have some other variables such as it's x position, it's y position, it's radius(Since our bird is actually a circle XD) etc. So what this showBird() is doing is just drawing a circle at given x,y with it's radius.
2. think()
Let's see what think() method of bird do
Remember the self.brain = NeuralNetwork(8,5,2)? So our neural network takes 8 inputs, which are:
horizontal distance from the start of pipe
horizontal distance from the end of pipe
vertical distance from the upper pipe
vertical distance from the lower pipe
y position of bird
y velocity of bird
vertical distance from sky
vertical distance from ground
So, what this function does is calculate the inputs for the neural network and normalize them.
3. predict()
Let's see what the predict() method does.
So, as the name suggests, the inputs which was calculated in think(), the neural network takes it and predicts whether the bird should jump up or not.
Till now, bird was performing some action, like calculating the input and predicting whether it should jump or not, Now we will handle the consequences of the action performed by the bird in previous step.
This block of code checks that if the bird is colliding with walls(ground or sky) or with the pipes, then it deletes the bird from the self.birds list(which is equivalent to dying). Then if the list becomes empty then our NEAT algorithm comes in action.
nextGenration()
Since our list has became empty, which means our generation has died, now it's time to call the nextGeneration.
calculateFitness() calculates the fitness of each bird based on the distance travelled by him and and it's score. Let's see how it does.
So, we traverse through every bird object of the previous generation which is saved in our self.savedBirds list, and then call the method calculateFitness() of the bird class.
Note that this is not recursion, the current calculateFitness() is of GA() class which handles NEAT algorithm, and the method calculateFitness() it is calling is from Bird() class.
The calculateFitness() method of Bird() class calculates the fitness of bird. It is a function of score as well as distance, but more priority is given to score of the bird. So, the more the score and the distance, the more the fitness, & more chances of getting picked up for mating.
Now, we will see calculateFitness() method of GA() class again.
So, as a whole, what this method does is, it calculates the fitness of every bird and normalize them.
pickOne()
This method looks a little bigger. So, first, let's see what it is returning. return child
So, it returns a child. The job of pickOne() is to append the 300 children to our self.birds list. But before returning child, it will need his parents(2 birds of previous generation). So for each 300 birds, there will be a pair of birds who are crossovered.
But how does the pair is selected?
We select two parent one-by one, based on their fitness, the more the fitness, more is the probabiity of them to get selected. It's not necessary that the two parent will be different, sometimes, the parent can be the same bird, it all depends on the fitness value of the birds in the previous generation. After selecting the parents, the bird is crossovered. Which means, we take all the 4 matrices of parent 1 and mix them with the corresponding matrices of it's counterpart.
How do we mix them? We take the upper half rows of parent 1, lower half rows of parent 2 and combine them to return a matrix, which is a combination of both the matrices.
Now we have the 4 matrices of child bird which has the combination of traits of his parents, but the bird should acquire some new traits, so we mutate the 4 matrices.
What mutate() method does is ,it traverse through the matrix, and pick element based on the rate, which is the probability, in our case 30% and twerk the element by adding a random number between -0.1 to 0.1. The rate defines, the probability of the element getting twerked. In our case, while traversing through the matrix, the probability of twerking the particular element is 30%.
Flappy Bird Hacked
Now after mutation, the child is ready to get appended in our self.birds list.
Now let's summarize the nextGeneration() method.
In nextGeneration() method, we first calculate the fitness of every bird, then we check if the best bird is found, i.e if the any of the birds has surpassed the best score which is initially 0. If the best bird is found then we apeend the child with the brain of that best bird and the rest 299 birds by pickOne() method, otherwise, we append one random bird from the population and rest 299 by pickOne() method.
After this, our code again goes to gameLoop() method and the same whole process goes on for new generation.
Flappy Bird
Conclusion
Crossy Road
This is how the NEAT works, the full code is available on my GitHub.
After the DeepMind's AlphaGo has beaten Lee Sedol, who has won 18 International titles, the question that pops in my mind is, has the Artificial Intelligence already surpassed the human intelligence?