¶ Evolution
¶ Tutorial 6 of Implementing Flappy Bird game to understand mathematical fundamentals behind neural networks
¶ Optimization
Optimization is an essential and useful tool of mathematics. Basically, it means getting the best possible solution. Imagine you want to optimize your profit by selling ice cream cones. You have to take into account that it also costs you money to buy the supplies. Then you want to know how many ice cream cones you need to sell to get the highest profit. This is a simple example of an optimization problem. The way to solve this problem is to make a function of your profit and maximize this function. There are many ways to optimize a function, and there are many ways to use optimization in a neural network. More about this will follow in the next tutorial.
¶ Optimization in flappy bird
In the implementation of the flappy bird, we need optimization to optimize and change the weights of the neural network after every step. We want to find the best possible bird, and in order to do that, we improve the bird after every step (in each new generation) to get a little closer to the perfect bird. In our current network we use a very simple (but probably not the fastest) method for optimizing the bird, namely evolution.
¶ General idea of AI evolution
To get the AI flappy birds to a point where they can play the game themselves, we have to evolve the pack of birds by keeping the best performing birds and replacing the worst performing birds with new birds. This happens each time we create a new generation of birds.
¶ Fitness of the birds
The performance, and therefore fitness, of a bird is determined by two factors:
What could be the factors to determine the performance of the bird?
Solution
The two factors are:
- The distance to the gap of the pipe
- The time that the bird has been alive
The second factor (time) is more important, so it will receive more weight when calculating the fitness.
¶
¶ How do we make a new generation?
We will make the AI keep, discard and mutate (combining the properties of two birds) birds. For this basic implementation, we have the following division:
¶ Evolution code
¶ Set-up
To set up our evolution, we need new definitions and some functions coming from the neural network. In this part we will gradually set up the parts that are still missing.
In defs.py, we need to create our final definitions. This time we need the following:
The percentage of chance that the weights of a bad bird will be changed next generation
The mix percentage, meaning the percentage of each of the two birds taken to create a new bird
The percentage of birds that will be kept
The percentage of birds that are kept on the bad side
The probability that birds that are created from two parent birds have their weights changed.
Solution
MUTATION_WEIGHT_MODIFY_CHANCE = 0.2
MUTATION_ARRAY_MIX_PERC = 0.5
MUTATION_CUT_OFF = 0.4
MUTATION_BAD_TO_KEEP = 0.2
MUTATION_MODIFY_CHANCE_LIMIT = 0.4
¶
In bird.py import the numpy library.
Solution
import numpy as np
In bird.py initialise a property for the fitness of the birds
Solution
self.fitness = 0
¶
The following functions will be put in nnet.py.
In nnet.py, create a function to modify the weight of a bird and include all the nodes. Make sure to modify both layers of nodes.
Solution
def modify_weight(self):
""" Function to modify weights of the bird
"""
# Modify the weights from the input to the hidden layer
Nnet.modify_array(self.weight_input_hidden)
# Modify the weights from the hidden to the output layer
Nnet.modify_array(self.weight_hidden_output)
¶
Create a function to modify the weights of the neural network. For every weight, check if it should be changed based on the modification chance. If this is the case, replace the weight with a rendom float from -5 to 0.
Solution
def modify_array(a):
""" Function to modify a weight array
:param a: numpy array, containing floats representing weights
"""
# Use a multi-dimensional iterator to read all values in the array
for x in np.nditer(a, op_flags=['readwrite']):
# Generate a random float number and check if this is lower than the set modification chance
if random.random() < MUTATION_WEIGHT_MODIFY_CHANCE:
# Change the weight with a random float numbers from [-5, 0)
x[...] = np.random.random_sample() - 0.5
</>
¶
Create a function that will mix the weights of two parent birds. Before the contents of the function are written you should think of what input to put in this function.
Solution
def get_mix_from_arrays(ar1, ar2):
"""
:param ar1: numpy array, 2-dimensional containing floats numbers representing weights
:param ar2: numpy array, 2-dimensional containing floats numbers representing weights
:return:
res: numpy array, 2-dimensional containing floats numbers representing weights
"""
Define the total number of weights. Then define the number of rows and the number of columns of one of the birds.
Solution
# Get the total number of weights
total_entries = ar1.size
# Get the number of row weights
num_rows = ar1.shape[0]
# Get the number of column weights
num_cols = ar1.shape[1]
First define how many weights should be kept and modified. Then give every weight an index of true or false depending on whether they should be modified.
Solution
# Define how many weights should be modified
num_to_take = total_entries - (int(total_entries * MUTATION_ARRAY_MIX_PERC))
# Set the index numbers of the weights to modify
idx = np.random.choice(np.arange(total_entries), num_to_take, replace=False)
Fill an array, with the same number of rows and columns as the birds neural network, with random weight values.
Solution
# Fill a new array with random weight values
res = np.random.rand(num_rows, num_cols)
For every weight, for every piece in the whole array (depending on number of rows and columns), check the true/false index you made. Then fill the the weights with a false index with weights from parent one. The weights with a true index should be replaced with weights from parent two. Then return the array.
Solution
# For every weight
for row in range(0, num_rows):
for col in range(0,num_cols):
# Get the index position of the specific weight
index = row * num_cols + col
# Check if the weight should be changed by checking the index
if index in idx:
# Get the weight of the first parent when the weight should be changed
res[row][col] = ar1[row][col]
# Else get the weight of the second parent
else:
res[row][col] = ar2[row][col]
# Return the array having weights of the child bird
return res
def get_mix_from_arrays(ar1, ar2):
"""
:param ar1: numpy array, 2-dimensional containing floats numbers representing weights
:param ar2: numpy array, 2-dimensional containing floats numbers representing weights
:return:
res: numpy array, 2-dimensional containing floats numbers representing weights
"""
# Get the total number of weights
total_entries = ar1.size
# Get the number of row weights
num_rows = ar1.shape[0]
# Get the number of column weights
num_cols = ar1.shape[1]
# Define how many weights should be modified
num_to_take = total_entries - (int(total_entries * MUTATION_ARRAY_MIX_PERC))
# Set the index numbers of the weights to modify
idx = np.random.choice(np.arange(total_entries), num_to_take, replace=False)
# Fill a new array with random weight values
res = np.random.rand(num_rows, num_cols)
# For every weight
for row in range(0, num_rows):
for col in range(0,num_cols):
# Get the index position of the specific weight
index = row * num_cols + col
# Check if the weight should be changed by checking the index
if index in idx:
# Get the weight of the first parent when the weight should be changed
res[row][col] = ar1[row][col]
# Else get the weight of the second parent
else:
res[row][col] = ar2[row][col]
# Return the array having weights of the child bird
return res
¶
Create a function that will use the function to mix the weights of two birds to make new weights for the neural network.
To do this there should be two separate calls to the get_mis_from_arrays function. One for the weights between the input and hidden layer, and one for the weights between the hidden and output layer.
def create_mixed_weights(self, net1, net2):
""" Function to mix weights of two birds
:param net1: class, containing neural network information
:param net2: class, containing neural network information
"""
# Mix the weights from the input to the hidden layer
self.weight_input_hidden = Nnet.get_mix_from_arrays(net1.weight_input_hidden, net2.weight_input_hidden)
# Mix the weights from the hidden to the output layer
self.weight_hidden_output = Nnet.get_mix_from_arrays(net1.weight_hidden_output, net2.weight_hidden_output)
¶
Create a function in bird.py in the Bird class, that creates an offspring from two good birds. These birds will mix their weights to create one new bird. Then return the just made bird.
Solution
def create_offspring(p1, p2, gameDisplay):
""" Function to create a child bird from two parent birds based on their neural net weights
:param p1: numpy array, 2-dimensional containing floats numbers representing weights
:param p2: numpy array, 2-dimensional containing floats numbers representing weights
:param gameDisplay: pygame window size
:return:
bird: class, containg information of the bird
"""
# Create a new bird
new_bird = Bird(gameDisplay)
# Give the child bird a defined set of weights
new_bird.nnet.create_mixed_weights(p1.nnet, p2.nnet)
# Return the child bird
return new_bird
¶
Create a function in bird.py in the Bird class, that resets the birds and their properties.
Solution
def reset(self):
""" Function to reset the bird and its properties
"""
# Set all bird properties to the defined starting values
self.state = BIRD_ALIVE
self.speed = 0
self.fitness = 0
self.time_lived = 0
self.set_position(BIRD_START_X, BIRD_START_Y)
¶
¶ General evolution
From here, we will make one big function in bird.py in the BirdCollection class to evolve the birds each generation. We will divide the code in parts, but in the end it should be one big function.
Open the function in the BirdCollection class to evolve the population. Make a list of birds and sort them based on fitness. (The time that the bird was alive should still be added to the fitness)
Solution
def evolve_population(self):
""" Function to evolve the birds each generation
"""
# For every bird in the list
for bird in self.birds:
# Update the bird fitness determined by living time and the distance to the gap of the pipes
bird.fitness += bird.time_lived * PIPE_SPEED
# Sort the birds by their fitness
self.birds.sort(key=lambda x: x.fitness, reverse=True)
Make definitions of the part of birds from the list that will be cut off, the good birds, the bad birds, and the bad birds that should be kept. Use the definitions made in defs.py to make a distinction between the diffent parts of the list.
Solution
# Set the cut off value
cut_off = int(len(self.birds) * MUTATION_CUT_OFF)
# Set the good birds which are the top performing birds
good_birds = self.birds[0:cut_off]
# Set the bad birds, which is the rest
bad_birds = self.birds[cut_off:]
# Set the number of bad birds that should be kept
num_bad_to_take = int(len(self.birds) * MUTATION_BAD_TO_KEEP)
For every bad bird, call the function modify_weight to modify the weights. Make a list of new birds and make an index of birds that should be kept and from this index, exchange the birds that should be removed for new birds.
Solution
# For every bad bird
for bird in bad_birds:
# Modify the neural network weights
bird.nnet.modify_weight()
# Create a list of new birds that are needed for every deleted bad bird
new_birds = []
# Pick the birds to take to the next round
idx_bad_to_take = np.random.choice(np.arange(len(bad_birds)), num_bad_to_take, replace=False)
# Add the birds to take to the next round to the bird list
for index in idx_bad_to_take:
new_birds.append(bad_birds[index])
The missing birds should be replaced. While the list is not full, pick two different good birds with which new birds will be made. Call the function create_offspring to create offspring with these two birds. Include the chance that the weights of these new birds will be modified. And then create the new bird.
Solution
# Extend the new bird list with the good birds to keep
new_birds.extend(good_birds)
# When more birds are needed
while len(new_birds) < len(self.birds):
# Pick random parents from the good birds
idx_to_breed = np.random.choice(np.arange(len(good_birds)), 2, replace=False)
# Make sure the parent birds are not the same
if idx_to_breed[0] != idx_to_breed[1]:
# Create a offspring bird from the two parent birds
new_bird = Bird.create_offspring(good_birds[idx_to_breed[0]], good_birds[idx_to_breed[1]], self.gameDisplay)
# There is a chance that the weights of the neural network are changed
if random.random() < MUTATION_MODIFY_CHANCE_LIMIT:
new_bird.nnet.modify_weight()
# Add the created bird to the list
new_birds.append(new_bird)
Finally, every bird has to be reset and the bird list should be updated.
Solution
# Reset the birds for every bird in the new list
for bird in new_birds:
bird.reset();
# Update the bird list
self.birds = new_birds
def evolve_population(self):
""" Function to evolve the birds each generation
"""
# For every bird in the list
for bird in self.birds:
# Update the bird fitness determined by living time and the distance to the gap of the pipes
bird.fitness += bird.time_lived * PIPE_SPEED
# Sort the birds by their fitness
self.birds.sort(key=lambda x: x.fitness, reverse=True)
# Set the cut off value
cut_off = int(len(self.birds) * MUTATION_CUT_OFF)
# Set the good birds which are the top performing birds
good_birds = self.birds[0:cut_off]
# Set the bad birds, which is the rest
bad_birds = self.birds[cut_off:]
# Set the number of bad birds that should be kept
num_bad_to_take = int(len(self.birds) * MUTATION_BAD_TO_KEEP)
# For every bad bird
for bird in bad_birds:
# Modify the neural network weights
bird.nnet.modify_weight()
# Create a list of new birds that are needed for every deleted bad bird
new_birds = []
# Pick the birds to take to the next round
idx_bad_to_take = np.random.choice(np.arange(len(bad_birds)), num_bad_to_take, replace=False)
# Add the birds to take to the next round to the bird list
for index in idx_bad_to_take:
new_birds.append(bad_birds[index])
# Extend the new bird list with the good birds to keep
new_birds.extend(good_birds)
while len(new_birds) < len(self.birds):
# Pick random parents from the good birds
idx_to_breed = np.random.choice(np.arange(len(good_birds)), 2, replace=False)
# Make sure the parent birds are not the same
if idx_to_breed[0] != idx_to_breed[1]:
# Create a offspring bird from the two parent birds
new_bird = Bird.create_offspring(good_birds[idx_to_breed[0]], good_birds[idx_to_breed[1]], self.gameDisplay)
# There is a chance that the weights of the neural network are changed
if random.random() < MUTATION_MODIFY_CHANCE_LIMIT:
new_bird.nnet.modify_weight()
# Add the created bird to the list
new_birds.append(new_bird)
# Reset the birds for every bird in the new list
for bird in new_birds:
bird.reset();
# Update the bird list
self.birds = new_birds
¶
Finally, we need to call that big function in main.py. Every time the counter of living birds is 0, we need to call the evolution function. We already have the if statement in main.py, so we only need to update it.
Solution
# Every time the bird dies
if num_alive == 0:
# Create a new set of pipes
pipes.create_new_set()
# Restart the game time
game_time = 0
# Create a new set of bird population
birds.evolve_population()
# Update the number of iterated games
num_iterations += 1
¶
¶ Summary
In this tutorial, you optimized the bird according to the evolutionary algorithm. This procedure aims to improve the bird after every step to get to the perfect bird. To accomplish this, we kept making new generations of birds by mutating the birds. Although this algorithm works, it might not be the most efficient in terms of speed. There are various optimization techniques available for machine learning, and evolution is but one of them. Therefore, we will discuss another optimization technique called Gradient Descent in the next tutorial.
¶ Code at the end of this tutorial
Preview the full code that you should have after this tutorial from GitHub