#4: Game Playing with Genetic Algorithm

published on

This was a project me and my project partner developed for our 3rd year Computer Graphics course. This project is based on OpenGL and is completely written in C++. I decided using C++ over Javascript, the language I had most experience in at that time, for multiple reasons. Firstly, OpenGL is itself written in C and thus has a stable, well written implementation for C++ and secondly, after working on a high level language like Javascript, I wanted to try out something different to gain a new perpective and C++ seemed like a good option.

In my 2nd year, I had worked on a basic demonstration of Genetic Algortihm and thought it would be a good idea to extend the project. Me and my project partner decided to create a Flappy Bird like game with a focus on using genetic algorithm to train the computer to play the game.

The link to the source code can be found at the bottom of the post.

Overview

The development of this project was divided into 2 major phases:-

  1. Creating the Game Using OpenGL

    The game consists of a simple rectangular bird-like object which only has the ability to jump. The aim is to time the jumps so as to cross the randomly generated obstacles without colliding. The user is scored based on the number of obstacles crossed, much like the original Flappy Bird game. The first phase involved implementing the logic and developing methods to render the game.

  2. Implementing the ANN and Genetic Algorithm

    The second phase involved laying out the code to enable the computer to understand and learn to play the game. This was done by attaching the bird with an Artificial Neural Network(ANN) that determined when to jump. Now, the challenge here was to train the ANN to achieve desired results. This training was done through genetic algorithm(GA) which was used to tweak the hyper paramaters of the network in order to maximise the final score.

The Game

Although this article will be more focused towards the genetic algorithm part of the project, I’ll be quickly going through the interesting parts of designing and implementing the game. For more information you can go through the source code linked below.

The game has 2 major entities whcih are implemented as C++ classes:-

  • The Obstacles

    The Obstacles are defined in the Obstacle object that can be found in /includes/obstacles.h with the corresponding definitions in /osbtacles.cpp. The Obstacles have a position attribute corresponding to their position as well as an opening indicating the height at which the opening in the obtacle is present.

class Obstacle {
public:
  ...
  int position, opening;
  Obstacle *next_obs;
  Obstacle *prev_obs;
  ...
}

As we notice, the class has self referencing pointers to next and the previous obstacles in the list.

Another class ObstacleList defined in the same files holds all the obstacles as a doubly linked list with pointers to the first and last Obstacle object of the list named obs_list_head and obs_list_rear. It also implements the add_rear() method to insert new obstacles to the rear of the list.

class ObstacleList {
public:
  Obstacle* obs_list_head;
  Obstacle* obs_list_rear;

  ObstacleList();
  void add_rear(Obstacle *obs);   //adds obs to the rear of the linked list
  void generate_obstacles();    // generate obstacles with random openings
  void update_pos();    //update position of obstacles after each display cycle
  ...
};

  • The Bird

    The Bird is defined in the Bird object that can be found in /includes/bird.h with the corresponding definitions in /bird.cpp

    The following snippet shows the important data memebers and variables of the Bird class.

class Bird
{
public:
  ...
  Obstacle* next_obs = NULL;
  ...
  /* update bird's position for the next frame based on gravity and
   * user input */
  void update_pos(Obstacle* o = NULL);
  void jump();
  /* Check if the upcoming obstacle has been crossed */
  bool has_crossed(Obstacle* o = NULL);
  bool has_collided(Obstacle* o = NULL);
  ...

The bird has a next_obs variable the points to the upcoming object in the ObstacleList. Further, it has has_crossed() and has_collided() members to determine wether bird has crossed or collided with next_obs

The Neural Network

Now that the game was ready, the next phase involved adding some kind of intelligence to the bird so it could start jumping through the obstacles on its own. This was done through the use of an ANN. To implement the ANN we used a C++ library called Fast Artificial Neural Networks. FANN allows us to initialize a neural network by passing the number of input, output and hidden layers. Initially the neural network has randomized weights and returns a random output between 0.0 and 1.0 everytime the network is run.

With the neural network set up, we attached the ANN to a new class named NeuralBird inherited from Bird. The ANN was now acting as the brain of the bird telling it when to jump based on the distance from the obstacle. This was done using the should_jump() method which ran the neural network for the given input and based on the output, decided whether the bird should jump or not. The following code snippet shows the partial implementation of should_jump() method which takes the x and y distance from the Bird.next_obs data memeber as input.

bool NeuralBird::should_jump(fann_type* input)
{
  ...
  ...
  /* fann_runn runs the given ANN to produce an output which is
   * then stored in jump_decision data member
   */
  this->jump_decision = fann_run(this->ann, input);

  // if the output is greater than 0.5 jump, else do nothing
  if (this->jump_decision[0] > 0.5 && last_time >= time_bw_jumps) {
    last_time = 0;
    return true;
  } else {
    last_time++;
    return false;
  }
}

At this point, we had a NeuralBird class which could play the game on its own but its ANN still had random weights. The output of the ANN was unreliable which caused the bird to flap around randomly not making any progress whatsoever. We needed a way to train and modify the hyperparameters in order maximise the score.

Genetic Algorithm and the Training Phase

Now conventionally, one of the most popular ways to train an ANN is backpropogation but I wanted to experiment with training the network using solely genetic algorithm. I won’t be going into the detailed workings of GAs as there are many other good resources out there, rather I’ll be focusing on the parts that are relevant for the project.

So, the implementation of the GA is in the /includes/genetic.h and genetic.cpp files in the source code. The following code snippet shows the important data memebers and methods of the GA class which implements the algorithm and the rest of the training is done in train.cpp located in the root directory.

class GA {
public:
  ...
  // A population of NeuralBird objects used for training
  NeuralBird **population, **last_population;
  ObstacleList ol;
  ...
  void init_rand_pop();
  // Simulate the game for the bird nb over the obstacle course ol and register the score
  int simulate_game(NeuralBird *nb, ObstacleList ol);
  // Simpulate the game for the current generation
  void simulate_game_gen();
  // Crossover 2 parents to create an offspring with qualities of both parents' ANNs
  void crossover(NeuralBird *nb1, NeuralBird *nb2, NeuralBird **child);
  // Use crossover() to create a new generation from the previous one
  void evolve();
};

The implementation can rougly be grouped in the following steps which are repeated after every iteration.

  • Generating Random Population of NeuralBird Objects

    First, around 10 NeuralBird objects were generated with random ANNs. These would act as our starting generation. Each NeuralBird had its own ANN and same instance of ObstacleList was passed to each of the birds to keep the training fair.

  • Assigning a Fitness to Each Member of the Population

    We ran a simulation of the game for each of the NeuralBird and assigned a fitness to it. In genetic algorithm, fitness of an organism is the measure of how close it is to the desired solution. In our case the fitness was simply the final score of the bird after the simulation was run. The function simulate_game() is responsible for running the simulation for one bird which is then repeatedly called by simulate_game_gen() to do it for the whole generation. Their partial implementations are as follows.

int GA::simulate_game(NeuralBird *nb, ObstacleList ol)
{
  ...
  ...
  // play till score exceeds 100 or the collision occurs
  while (!nb->game_over && nb->score < 100) {
    ol.update_pos();
    nb->Bird::update_pos();

    // Run the ANN after each loop to determine whether the bird should jump
    if (nb->should_jump()) {
      nb->Bird::jump();
    }
  }
}

  • Performing Selection Operation

    Selection and crossover lie at the core of every genetic algorithm implementation. Selection involves selecting 2 parents from the current population to produce an offspring. The parents are selected in such a way that organisms with better fitness are more likely to be selected for crossover(explained in next section). That being said, we should also give other low performing organisms a chance to be selected to ensure randomness to some extent.

    Our implementation involved selecting a certain number of winners from the population based on their fitnesses. Next, we selected some parents from the winners exclusively, and rest from all the organims randomly. This ensured that better genes were being propogated to next generation and at the same time maintained a factor of randomness by giving a chance to less fit organisms.

  • Performing Crossover Operation

    The next step involved taking the selected parents and combining their characteristics into a new organism that would become a part of our next generation. This operations is known as crossover and is vital to the success of any GA. Selection and crossover must be performed multiple times until we get a whole new population.

    In our case, we perforemed a single point crossover over the biases of the ANNs of the parent keeping rest of the connections same. This resulted in a new ANN which was then attached to a child NeuralBird object and added to the new population.

    Both, the selection and crossover are done in the evolve() function of the GA class defined in genetic.cpp.

  • Repeat the Previous Steps

    Now that we had a new population, we again simulate the game and assign fitnesses and repeat the selection and crossover process. The stop condition is implementation dependent and could be after certain iterations or after a certain fitness is achieved. We stoped the evolution process as soon as any bird attained a score of 100. At which point we used a FANN to save the ANN of the winning bird to a file. This saved ANN could later be imported to be used to play the game.

Future Improvements

Although we got our project working successfully, we are well aware that our implementation is pretty naive. There are still a lot of factors that need to be considered while tuning the hyper paramaters. I stumbled upon the following paper which gives some great insight about better ways to crossover 2 neural networks. Further, genetic algorithms in itself are usually not enough to successfully train a network for practical use and are usually combined with other traditional training algorithms.

I also came across a method of reinforced learning called Q-Learning which provides a way of training the ANN using back propogation even in absence of test data. This is done thorugh special equations used to calculate rewards and penalties that are ultimately used to tweak the weights of the network. I have started working on a Q-Learning implementation of the same Flappy Birds game and plan to compare its results and efficiency with the GA approach.

Snapshots

I’ll be attaching a gif of the AI in action below along with the source code of the whole project. Feel free to go through the code and get back to me with any questions, doubts or suggetions!

Flapy Bird AI

Source Code: https://github.com/OjaswinM/flappy-bird-ai/tree/master

References