What is SnakeGen?

snakegen demo gif

SnakeGen is a neuro-evolution of the snake game, built from the ground up, with just html, css and js. A basic genetic algorithm is used to evolve a neural network. Tensorflow.js is used to simplify the Neural Network definition, but it could easily be replaced as the architecture is fairly simple.

An environment is created and will evolve multiple generations. Each of them has a certain amounts of agents, that have their own genes (a neural network) to play snake.

Goal

With this project we are first trying to have a better understanding of genetic algorithms (GA) and how they can be used to find the optimal weights of a neural network on a given task. The task here is the game snake. The goal for the agent, is to maximize its score (number of fruit eaten).

The interesting about GA is the ability of letting agents evolve to find themselves the best way to resolve a problem. In our approach, we are trying to be "as real" as possible, by giving kind of a realistic vision of the snake's environment to the agent. We want to give the agent the most unbiased view possible, in hope that it's going to be able to create a good internal representation of its environment and objective.

Inputs / Outputs

The agent is the snake, and uses multiple inputs to make its decision.

snake inputs

When you want an agent to play a human game, you have to think about what vision of the game your agent will have. Us human, see the entire grid of the game at once, with the position of our snake and the food. That could be a way for our agent to see the world, each cell of the grid or even every pixel could be an input.

In our case, we chose the second opton, which is to take the snake's perspective. This case is closer to what a robot would see. We wanted to give it a more realistic view and that's why we went with a combination of "lines of sight", "cones of sight" and a sens for fruit presence. That gives us a total of 11 inputs (3 lines of sight, 4 cones of sight, 4 cones of fruit presence). Let us explain you what they are precisely.

Lines of sight

From the snake's head, 3 "beam" will travel to its left, its right and forward, giving him a sense of the distance between its head and an eventual obstacle. These lines of sight are basically infinite in our case, but they could easily be limited, to simulate a more real environment.

Cones of sight / Fruit presence

To give our agent a more "realistic view", we wanted to add some kind of "continous" vision of the world. We added what we call "cones of sight" which are basically 4 cones. The inputs are simply the area of each cones. On the same principle, 4 more inputs will have the fruit presence in the 4 previously defined cones.

By having 4 separate inputs for the fruit presence we give the agent the ability to prioritze what is important for him. The cones of sight could be used to determine the best path (where there are more space to move) while the fruit presence input give the agent a general direction towards the goal.

Outputs

The outputs are pretty straight forward, again we use the snake's perspective. The agent can go forward, left and right. Going backward is not possible for multiple reasons, but basically because it's not useful and would result in the snake dying instantly when its size is at least two.

Genetic algorithm

There are a lot of implementation of the idea of genetic algorithms. We went with something simple, that mimics what we can observe in nature. The algorithm is as follows:
  • 1. Create an initial generation of agents with random genes (random weights in the neural net)
  • 2. Let the agents play or train on the task you assigned and keep track of how they're doing (their **fitness**)
  • 3. Judge the agents based on their **fitness** and class them in descending order
  • 4. Select X% of the fittest agents
  • 5. Use these selected agents to breed a new population (create offsprings)
  • 6. (Optional) Keep the selected agents untouched for the next generation (elitism)
  • 7. Randomly mutate X genes of Y amount of the newly bred agents
  • 8. Goes to 2 and repeat until goal is reached

Selection

The selection process is quite important as the selected agents will breed the entire next generation. First of all, we selected a low selection percentage. From 6 to 10% should yield good results.

Secondly, we introduced roulette-wheel selection. To understand what it is, simply picture a wheel, where each part is bigger in proportion of the agent's score. The best agents will have a bigger section of the wheel, and thus a higher chance of being a parent. This method ensures that the best parents will make more children, thus spreading better genes to future generations.

We also chose to use elitism. This means the selected parents will be passed to the next generation without any genes modification. Because they are the best, they should have the chance to perform again without restriction. This can help to create better invidividuals faster and avoid losing potentially good genes.

Breeding (crossover)

To breed a new population you basically breed an offspring by mating two parents together. This called a gendered breeding, and it's what we decided to use. Note that other types of breeding exist (non-gendered breeding for example).

More specifically, the breeding process makes use of crossover. This is the process of mixing part of parent A's genes with parent B's genes to create the offspring. By doing that randomly you ensure your offspring is king of unique and will, by chance, keep the good genes of its parents.

There are multiple ways of doing crossover. We chose to implement two types:

  • • Line/Row: A (or multiple) line(s) (or row(s)) are randomly selected from parent A to be swapped with parent B's genes.
  • • Patch: A randomly sized and placed patch is selected from parent A to be swapped with parent B's genes.

Mutation

If we were to only select and breed offspring the way we described above, our population would not really evolve because the genes in itself would not evolve, they would just get mixed infinitely.

That's were mutation comes into play! By adding a small chance for a gene to randomly mutate, we make it possible for genes to evolve. In practice, after the crossover, each genes will have a chance to mutate by a small amount.

In our case, that mutation probability is fixed at 1% by default. It must be kept relatively low, otherwise, the genetic patrimony would be destroyed by random mutation at each breeding and the selection process would be useless.

Wrapping up

By doing the three steps described above, you should have a descent genetic algorithm capable of mimicking what's happening in nature. If your selection is right you should see your agents converge to a descent result. The convergence can be very long depending on the complexity of your task but also on your population size.

By allowing a bigger population, you have more chance to encounter good genes for you task. The downside is that it requires more processing power.