-
Notifications
You must be signed in to change notification settings - Fork 14
Genetic Algorithm (Flappy Bird Game Explanation)
MLKit provides an example project where you can observe a Flappy Bird Game, repeatedly, running on it's own. This is done through the use of genetic algorithms and a neural network. Below you'll see a step by step explanation of how the game was constructed.
Disclaimer: I did not build the game, rather I used MLKit on top of what has already been built.
In order to begin the game I created a population of flappy birds. On line 37 of the GameViewController class you'll see the use of a struct to represent a Genome.
// Genome that represents a Flappy Bird
public class FlappyGenome: Genome {
/// Genotype representation of the genome.
public var genotypeRepresentation: [Float]
public var fitness: Float = 0
public var brain: NeuralNetwork?
public init(genotype: [Float], network: NeuralNetwork) {
self.genotypeRepresentation = genotype
self.brain = network
}
public func generateFitness(score: Int, time: Float) {
self.fitness = Float(Float(score) + time)
}
}
FlappyGenome conforms to the Genome protocol in the framework. You should use this protocol to define your genomes. Note that the protocol does not provide a method to generate fitness as there are multiple ways to evaluate the fitness of your genome. It is suggested that you implement this based on your needs. In this particular case the fitness of a flappy bird is the score that the bird earned as well as how long it was able to last (time in seconds) in the game without losing.
Moving forward on line 67 I generated a population of 19 birds each with their own neural network.
// Create First Generation of Flappy Birds
var generation1: [FlappyGenome] = []
for _ in 1...19 {
// Bias already included
let brain = NeuralNetwork(size: (6, 1))
brain.addLayer(layer: Layer(size: (6, 12), activationType: .siglog))
brain.addLayer(layer: Layer(size: (12, 1), activationType: .siglog))
let newBird = FlappyGenome(genotype: GeneticOperations.encode(network: brain), network: brain)
generation1.append(newBird)
}
The 20th bird is a bird with weights that I manually implemented. This particular bird, during my tests, had the best fitness after 30 generations. It was saved in order to potentially speed up the process of getting a generation with decent birds.
// Best Bird Weights & Bias
let brain = NeuralNetwork(size: (6, 1))
brain.addLayer(layer: Layer(size: (6, 12), activationType: .siglog))
brain.addLayer(layer: Layer(size: (12, 1), activationType: .siglog))
brain.layers[0].weights = Matrix<Float>(rows: 12, columns: 6, elements: ValueArray<Float>([1.14517, 0.691113, -0.938394, 0.798185, -1.20595, 0.732543, 0.174731, -1.0585,-0.500974,-1.02413,0.841067, -0.530047,-0.336522, -1.68883, -1.47241, 0.907576, 0.71408, 0.646764, -0.331544, 0.141004, 2.42381, 0.0683608, 1.01601, 1.42153, -0.672598, 0.889775, -1.55454, -0.530047, 0.307019, -0.483846, 0.0292488, 0.478605, 0.000960251 , -0.379445, -0.336532, -0.17253, 0.892149, -0.301041, 1.06579, -0.230897, 0.39673, -1.93952, 1.69516, 0.185731, -1.48985, -0.17253, -0.336532, -0.379445, 2.12388, 0.0292488, -0.483846, 0.307019, -1.29687, 0.941488, -1.50857 , -1.47241, 0.594132, 1.69516, 0.185731, -1.48985, -0.17253 , 1.06579, -0.301041, 0.892149, -1.15464, 1.15181,0.000960251, 0.478605, 0.0292488 , -0.483846, 0.307019, -1.29687]))
brain.layers[1].weights = Matrix<Float>(rows: 1, columns: 12, elements: ValueArray<Float>([1.10186, -1.68883, -0.336522, -2.54774, 0.202769, 1.50816 , -3.25252, 0.830278 , 0.104464, -1.26191, 0.698875, -0.447793]))
brain.layers[0].bias = Matrix<Float>(rows: 12, columns: 1, elements: ValueArray<Float>([0.941488, -1.50857, -1.47241, 0.594132, -0.189659, 0.804515, -1.60174, 0.741886, -0.811568, 0.0985006, -0.863954, -0.729362]))
brain.layers[1].bias = Matrix<Float>(rows: 1, columns: 1, elements: ValueArray<Float>([0.440734]))
let bestBird = FlappyGenome(genotype: GeneticOperations.encode(network: brain), network: brain)
generation1.append(bestBird)
Here we are using the NeuralNetwork class provided by the framework. Each "brain" has 6 neurons for the input layer, 1 hidden layer with 12 neurons, and an output layer with 1 neuron. The activation function for the input layer and the hidden layers is using SIGLOG (sigmoid function) and the same goes for the output layer.
Note that the GameScene.swift file contains the main game logic. There is an attribute in the GameScene class called flappyBirdGenerationContainer. This attribute holds a list of FlappyGenome objects. Coming back to GameViewController.swift on line 98 we set the flappyBirdGenerationContainer attribute of the GameScene class to be equal to our newly generated population that was generated and stored within the generation1 variable (code above).
if let scene = GameScene.unarchiveFromFile("GameScene") as? GameScene {
// Set the first generation of Flappy Birds
scene.flappyBirdGenerationContainer = generation1
...
}
For this example project to work I added a few additions to the game itself. Before we move on I'd like to present all of the attributes used in the game:
GameScene.swift
/// Container for our Flappy Birds
var flappyBirdGenerationContainer: [FlappyGenome]?
/// The current genome
var currentBird: FlappyGenome?
/// The current flappy bird of the current generation (see 'generationCounter' variable)
var currentFlappy: Int = 0
/// Variable used to count the number of generations that have passed
var generationCounter = 1
/// Variable to keep track of the current time (this is used to determine fitness later)
var currentTime = NSDate()
/// The red square (our goal area)
var goalArea: SKShapeNode!
/// The pipe that is in front of the bird
var currentPipe: Int = 0
/// The best fitness throughout the whole game
var maxFitness: Float = 0
/// The best bird throughout the whole game
var maxBird: FlappyGenome?
/// A variable to hold the best birds from the previous generation
var lastBestGen: [FlappyGenome] = []
Starting on line 216 I implemented a SKShapeNode to indicate the area that each bird had the pass through. Specifically the area between each pipe. This will be used later in determining the fitness of a particular bird:
goalArea = SKShapeNode(rectOf: CGSize(width: 10, height: 10))
goalArea.name = "GOAL"
goalArea.fillColor = SKColor.red
goalArea.position = pipeUp.position
goalArea.position.y += 230
Moving on to the resetScene method we see the code that is used to reset the game once the AI (or player) has lost the game. In this method we calculate the birds fitness and generate a new population of birds. Let's go through this step by step. Recall that our generateFitness method within the FlappyGenome struct contained two parameters score and time. Moreover, we created a variable that stored the current time var currentTime = NSDate() and on line 295 we calculate the total elapsed time:
let endDate: NSDate = NSDate()
let timeInterval: Double = endDate.timeIntervalSince(currentTime as Date)
currentTime = NSDate()
The score has already been conveniently implemented in the game and is stored in the score variable within the class. With these two attributes we can now generate our fitness (line 299).
// Evaluate the current birds fitness
if let bird = currentBird {
bird.generateFitness(score: score, time: Float(timeInterval))
...
Recall that there were 20 FlappyBird genomes created and stored in the flappyBirdGenerationContainer attribute. Our job is to cycle through these birds, give them a fitness value and once we are done processing the fitness of 20 birds we create a new generation. In order to do this I created an attribute called currentFlappy. It's a counter that helps us count how many birds have lost the game so far. If this counter reaches 20 then we create a new generation of birds.
// If we have hit the 20th bird, we need to move on to the next generation
if currentFlappy == 20 {
print("GENERATING NEW GEN!")
currentFlappy = 0
// New generation array
var newGen: [FlappyGenome] = []
newGen = lastBestGen
if let bestBird = maxBird {
flappyBirdGenerationContainer?.append(bestBird)
}
while newGen.count < 20 {
// Select the best parents
let parents = PopulationManager.selectParents(genomes: flappyBirdGenerationContainer!)
print("PARENT 1 FITNESS: \(parents.0.fitness)")
print("PARENT 2 FITNESS: \(parents.1.fitness)")
// Produce new flappy birds
var offspring = BiologicalProcessManager.onePointCrossover(crossoverRate: 0.5, parentOneGenotype: parents.0.genotypeRepresentation, parentTwoGenotype: parents.1.genotypeRepresentation)
// Mutate their genes
BiologicalProcessManager.inverseMutation(mutationRate: 0.7, genotype: &offspring.0)
BiologicalProcessManager.inverseMutation(mutationRate: 0.7, genotype: &offspring.1)
// Create a separate neural network for the birds based on their genes
let brainofOffspring1 = GeneticOperations.decode(genotype: offspring.0)
let brainofOffspring2 = GeneticOperations.decode(genotype: offspring.1)
let offspring1 = FlappyGenome(genotype: offspring.0, network: brainofOffspring1)
let offspring2 = FlappyGenome(genotype: offspring.1, network: brainofOffspring2)
// Add them to the new generation
newGen.append(offspring1)
newGen.append(offspring2)
}
generationCounter += 1
// Replace the old generation
flappyBirdGenerationContainer = newGen
// Set the current bird
if let generation = flappyBirdGenerationContainer {
if generation.count > currentFlappy{
currentBird = generation[currentFlappy]
}else{
if let bestBird = maxBird {
currentBird = maxBird
}
}
}
} else {
// Set the current bird
if let generation = flappyBirdGenerationContainer {
if generation.count > currentFlappy {
currentBird = generation[currentFlappy]
}
}else{
currentBird = maxBird
}
}
On line 321 we increment currentFlappy by 1 to indicate that a bird has lost the game. On line 323-339 I added some code to remove any bird that didn't meet a specific fitness threshold. On line 333 I track the best bird so I can place them back into the population in order to, possibly, increase the chances of getting a successful generation of birds.
Coming back to line 341 if the currentFlappy counter reaches 20 it's time for us to generate a new population. Here's how this is done:
- First we reset the
currentFlappycounter to 0. - We then create an array to hold our new generation of birds. See
newGenvariable (above) - We append the best individuals from the last generations (via
lastGen) and we also include the best bird overall (maxBird).
While our newGen array is still generating a population of 20 individuals...
- Select two of the best parents in the previous generation and obtain their offspring
- Perform one-point crossover on the genes of the offspring
- Perform scramble mutation on the genes of the offspring
- Convert the genes of the offspring to a
NeuralNetobject. This is done by thedecodemethod in theGeneticOperations.swiftfile. Thedecodemethod takes an array of floating values and uses those values as weights for each layer in our neural network. This was carefully crafted for this particular application. - Create a
FlappyGenomeobject for each of the offspring - Append the offspring into the new generation (
newGenattribute).
We then increment the our generation counter generationCounter and set the current bird (the bird that will be playing the game).
update method
override func update(_ currentTime: TimeInterval) {
let endDate: NSDate = NSDate()
let timeInterval: Double = endDate.timeIntervalSince(currentTimeForFlappyBird as Date)
self.fitnessLabel.text = "Fitness: \(NSString(format: "%.2f", timeInterval))"
checkIfOutOfBounds(bird.position.y)
/* Called before each frame is rendered */
let value = bird.physicsBody!.velocity.dy * ( bird.physicsBody!.velocity.dy < 0 ? 0.003 : 0.001 )
bird.zRotation = min( max(-1, value), 0.5 )
// If the pipes are now visible...
if pipes.children.count > 0 {
// Check to see if the pipe in front has gone behind the bird
// if so, make the new pipe in front of the bird the target pipe
if pipes.children[currentPipe].position.x < bird.position.x {
currentPipe = closestPipe(pipes: pipes.children)
}
// Distance between next pipe and bird
let distanceOfNextPipe = abs(pipes.children[currentPipe].position.x - bird.position.x)
let distanceFromBottomPipe = abs(pipes.children[currentPipe].children[1].position.y - bird.position.y)
let normalizedDistanceFromBottomPipe = (distanceFromBottomPipe - 5)/(708 - 5)
let normalizedDistanceOfNextPipe = (distanceOfNextPipe - 3)/(725-3)
let distanceFromTheGround = abs(self.bird.position.y - self.moving.children[1].position.y)
let normalizedDistanceFromTheGround = (distanceFromTheGround - 135)/(840-135)
let distanceFromTheSky = abs(880 - self.bird.position.y)
let normalizedDistanceFromTheSky = distanceFromTheSky/632
// Bird Y position
let birdYPos = bird.position.y/CGFloat(880)
// Measure how close the bird is to the gap between the pipes
let posToGap = pipes.children[0].children[2].position.y - bird.position.y
let normalizedPosToGap = (posToGap - (-439))/(279 - (-439))
if let flappyBird = currentBird {
// Decision AI makes
let input = Matrix<Float>(rows: 6, columns: 1, elements: [Float(normalizedDistanceOfNextPipe), Float(normalizedPosToGap), Float(birdYPos), Float(normalizedDistanceFromBottomPipe), Float(normalizedDistanceFromTheGround), Float(normalizedDistanceFromTheSky)])
let potentialDescision = flappyBird.brain?.feedforward(input: input)
if let decision = potentialDescision {
print("FLAPPY BIRD DECISION: \(decision)")
if (decision.elements[0]) >= Float(0.5) {
if moving.speed > 0 {
bird.physicsBody?.velocity = CGVector(dx: 0, dy: 0)
bird.physicsBody?.applyImpulse(CGVector(dx: 0, dy: 30))
}
}
}
}
}
if canRestart {
// If the game ends...
// record the current flappy birds fitness...
// then bring in the next flappy bird
self.resetScene()
}
}
Now comes the fun part. The update method contain the main game logic. On line 352 I used the method checkIfOutOfBounds to check whether the bird goes too high or not. The original game had a bug where if you jumped a lot you could essentially go over the pipes and so I made a way to stop this from happening. On line 459 I check whether there are any pipes visible within the view itself. On line 463 I check for the closest pipe. This helps with identifying the distance between the bird and the pipe that is directly in front of the bird. The closestPipe method on line 431 handles this particular situation. Now let's discuss the Neural Network part:
// If the pipes are now visible...
if pipes.children.count > 0 {
// Check to see if the pipe in front has gone behind the bird
// if so, make the new pipe in front of the bird the target pipe
if pipes.children[currentPipe].position.x < bird.position.x {
currentPipe = closestPipe(pipes: pipes.children)
}
// Distance between next pipe and bird
let distanceOfNextPipe = abs(pipes.children[currentPipe].position.x - bird.position.x)
let distanceFromBottomPipe = abs(pipes.children[currentPipe].children[1].position.y - bird.position.y)
let normalizedDistanceFromBottomPipe = (distanceFromBottomPipe - 5)/(708 - 5)
let normalizedDistanceOfNextPipe = (distanceOfNextPipe - 3)/(725-3)
let distanceFromTheGround = abs(self.bird.position.y - self.moving.children[1].position.y)
let normalizedDistanceFromTheGround = (distanceFromTheGround - 135)/(840-135)
let distanceFromTheSky = abs(880 - self.bird.position.y)
let normalizedDistanceFromTheSky = distanceFromTheSky/632
// Bird Y position
let birdYPos = bird.position.y/CGFloat(880)
// Measure how close the bird is to the gap between the pipes
let posToGap = pipes.children[0].children[2].position.y - bird.position.y
let normalizedPosToGap = (posToGap - (-439))/(279 - (-439))
if let flappyBird = currentBird {
// Decision AI makes
let input = Matrix<Float>(rows: 6, columns: 1, elements: [Float(normalizedDistanceOfNextPipe), Float(normalizedPosToGap), Float(birdYPos), Float(normalizedDistanceFromBottomPipe), Float(normalizedDistanceFromTheGround), Float(normalizedDistanceFromTheSky)])
let potentialDescision = flappyBird.brain?.feedforward(input: input)
if let decision = potentialDescision {
print("FLAPPY BIRD DECISION: \(decision)")
if (decision.elements[0]) >= Float(0.5) {
if moving.speed > 0 {
bird.physicsBody?.velocity = CGVector(dx: 0, dy: 0)
bird.physicsBody?.applyImpulse(CGVector(dx: 0, dy: 30))
}
}
}
}
}
if canRestart {
// If the game ends...
// record the current flappy birds fitness...
// then bring in the next flappy bird
self.resetScene()
}
Recall that a FlappyGenome struct has the attribute brain which represents a NueralNetwork object. Each FlappyGenome has a neural network that has 6 input layer neurons, 1 hidden layer with 12 neurons and an output layer with 1 neuron. The 6 inputs that we are going to take to evaluate whether or not a bird jumps includes the distance between the bird and the pipe directly in front of the bird, the distance from the bottom pipe, ** the birds Y position **, ** the distance between the bird and the gap between the pipes **, ** the distance between the bird and the sky (y position limit)*, and the distance between the bird and the ground sprite. Note that these values have also been normalized. Here is how the bird makes a decision:
let input = Matrix<Float>(rows: 6, columns: 1, elements: [Float(normalizedDistanceOfNextPipe), Float(normalizedPosToGap), Float(birdYPos), Float(normalizedDistanceFromBottomPipe), Float(normalizedDistanceFromTheGround), Float(normalizedDistanceFromTheSky)])
let potentialDescision = flappyBird.brain?.feedforward(input: input)
if let decision = potentialDescision {
print("FLAPPY BIRD DECISION: \(decision)")
if (decision.elements[0]) >= Float(0.5) {
if moving.speed > 0 {
bird.physicsBody?.velocity = CGVector(dx: 0, dy: 0)
bird.physicsBody?.applyImpulse(CGVector(dx: 0, dy: 30))
}
}
...
The NeuralNetwork class has a method feedforward which simply takes in inputs and passes them through the network once ,using the activation function you specify, and produces an output. The input to the Neural Network is stored as a Matrix object in the variable input which contains the normalized values mentioned earlier.
In order for the bird to jump I have set an arbitrary criteria. If the decision variable produces a value greater than or equal to 0.5 the bird will jump, otherwise it will do nothing (which is equivalent to letting the bird fall).
The game resets on it's own and brings forth a new bird. I hope you enjoyed the tutorial and the example project. Feel free to ask any questions in the issues tab.