-
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: NeuralNet?
public init(genotype: [Float], network: NeuralNet) {
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 it had obtained as well as how long it was able to last in the game without losing.
Moving forward on line 67 I generated a population of 20 birds each with their own neural network.
// Create First Generation of Flappy Birds
var generation1: [FlappyGenome] = []
for _ in 1...20 {
let brain = NeuralNet()
brain.initializeNet(numberOfInputNeurons: 3, numberOfHiddenLayers: 1, numberOfNeuronsInHiddenLayer: 4, numberOfOutputNeurons: 1)
brain.activationFuncType = .SIGLOG
brain.activationFuncTypeOutputLayer = .SIGLOG
let newBird = FlappyGenome(genotype: GeneticOperations.encode(network: brain), network: brain)
generation1.append(newBird)
}
Here we are using the NeuralNet class provided by the framework. Each "brain" has 3 neurons for the input layer, 1 hidden layer with 4 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 89 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 add 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 266 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 271).
// Evaluate the current birds fitness
currentBird?.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.
// Go to next flappy bird
currentFlappy += 1
// Filter out the worst birds after gen 6 (can be adjusted)
if generationCounter >= 3 {
// Experiment: Keep some of the last best birds and put them back into the population
lastBestGen = (flappyBirdGenerationContainer?.filter({$0.fitness >= 4}))!
}
if (currentBird?.fitness)! > maxFitness {
maxFitness = (currentBird?.fitness)!
maxBird = currentBird
}
// 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
newGen.append(maxBird!)
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.scrambleMutation(mutationRate: 0.5, genotype: &offspring.0)
BiologicalProcessManager.scrambleMutation(mutationRate: 0.5, 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)
}
...
On line 293 we increment currentFlappy by 1 to indicate that a bird has lost the game. On line 296-300 I added some code to remove any bird that didn't meet a specific fitness threshold. On line 303-306 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. Starting on line 309 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).
...
generationCounter += 1
// Replace the old generation
flappyBirdGenerationContainer = newGen
// Set the current bird
currentBird = flappyBirdGenerationContainer?[currentFlappy]
} else {
// Set the current bird
currentBird = flappyBirdGenerationContainer?[currentFlappy]
}
update method
override func update(_ currentTime: 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 normalizedDistanceOfNextPipe = (distanceOfNextPipe - 3)/(725-3)
// 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))
/*
print("======================== \n")
print(" DIST: \((finalDistanceOfNextPipe))")
print("PIPE POSITION: \(finalPosToGap)")
print("Bird POS Y: \(birdPos)")
print("======================== \n")
*/
// Decision AI makes
let decision = (currentBird?.brain?.forward(input: [Float(1), Float(normalizedDistanceOfNextPipe), Float(normalizedPosToGap), Float(birdYPos)]))!
print("FLAPPY BIRD DECISION: \(decision)")
// 0.95 was arbitrary, tweaking is recommended
if decision[0] >= Float(0.95) {
if moving.speed > 0 {
bird.physicsBody?.velocity = CGVector(dx: 0, dy: 0)
bird.physicsBody?.applyImpulse(CGVector(dx: 0, dy: 30))
}
} else {
}
}
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 399 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 406 I check whether there are any pipes visible within the view itself. On line 410 I check for the closest pipe. This helps with identifying the distance between the bird and the pipe that is directly in from to the bird. The closestPipe method on line 382 handles this particular situation. Now let's discuss the Neural Network part:
// Distance between next pipe and bird
let distanceOfNextPipe = abs(pipes.children[currentPipe].position.x - bird.position.x)
let normalizedDistanceOfNextPipe = (distanceOfNextPipe - 3)/(725-3)
// 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))
/*
print("======================== \n")
print(" DIST: \((finalDistanceOfNextPipe))")
print("PIPE POSITION: \(finalPosToGap)")
print("Bird POS Y: \(birdPos)")
print("======================== \n")
*/
// Decision AI makes
let decision = (currentBird?.brain?.forward(input: [Float(1), Float(normalizedDistanceOfNextPipe), Float(normalizedPosToGap), Float(birdYPos)]))!
print("FLAPPY BIRD DECISION: \(decision)")
// 0.9c5 was arbitrary, tweaking is recommended
if decision[0] >= Float(0.95) {
if moving.speed > 0 {
bird.physicsBody?.velocity = CGVector(dx: 0, dy: 0)
bird.physicsBody?.applyImpulse(CGVector(dx: 0, dy: 30))
}
} else {
}
}
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 NueralNet object. Each FlappyGenome has a neural network that has 3 input layer neurons, 1 hidden layer with 4 neurons and an output layer with 1 neuron. The 3 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 birds Y position **, and ** the distance between the bird and the gap between the pipes **. Note that these values have also been normalized. Here is how the bird makes a decision:
let decision = (currentBird?.brain?.forward(input: [Float(1), Float(normalizedDistanceOfNextPipe), Float(normalizedPosToGap), Float(birdYPos)]))!
The NeuralNet class has a method forward which simply takes in inputs and passes them through the network once ,using the activation function you specify, and produces an output. The first parameter represents the bias value (which should always be 1), the second parameter is the normalized value for the distance between the bird and the pipe directly in front of it, the third parameter represented the normalized value for the distance between the bird and the gap in between the closest pipes, and the last parameter is the normalized value for the birds Y position.
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.95 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.