Evolutionary Algorithm to Teach a NeuralNetwork to Play a Snake Game

• Download source - 59.5 KB

Introduction

An organism’s genetic code, in human beings and other higher organisms does not wholly account for the physical differences such as finger prints, blood capillaries and other intricate structure of brain, even in twins, which can be accounted for so called ‘phenotype-genotype’ differences. But in this small simulation of automatic evolution of behavior driven by selection of individuals of a specific fitness, we consider the genes to contain the full behavioral information, specifically, the weights of neurons in the artificial neural networks connected to the sensors of the snake. This information can be passed down to the offspring or can be mutated by random changes in the weights.

Keeping this in mind, we now create a Snake with its own Neural Network, using a NeuralNetworks library about which I discussed in my previous article about a character detector, which can travel in only 4 directions, smells the food by sensors on its head, has no idea how to find food, because the neural weights are initially random, but slowly as we subject it to the process of selection learns to find food on its own. Here, I discuss the creation of such a simulation.

Snake

Firstly, the Snake is our classic Nokia 3310 type object which can only go in four directions and can take only three decisions, TurnLeft(), TurnRight() and MoveForward() and in our application are taken by a DispatcherTimer in our WPF application. Each Snake generates by itself the lines needed to draw it, which are used by a method RefreshCanvas(), to render its location and shape on a 'Canvas’ in the MainWindow. It dies when it eats itself or when it touches the canvas border.

Snake Sensor

Snake has a food sensor, with four double variables,  Front, Back, Left and Right, which tells the neural network the location of food, it is similar to smelling the food's direction via sensors on its head.

public void ReadSensor(Snake snake, Food food)
{
    switch (snake.HeadDirection)
    {
        case Direction.E:
            Front = (food.Position.X - snake.HeadPosition.X) /
                    GetDistance(snake.HeadPosition, food.Position);
            Back = (-1) * (food.Position.X - snake.HeadPosition.X) /
                    GetDistance(snake.HeadPosition, food.Position);
            Right = (food.Position.Y - snake.HeadPosition.Y) /
                    GetDistance(snake.HeadPosition, food.Position);
            Left = (-1) * (food.Position.Y - snake.HeadPosition.Y) /
                    GetDistance(snake.HeadPosition, food.Position);
            break;
        case Direction.W:
            Back = (food.Position.X - snake.HeadPosition.X) /
                    GetDistance(snake.HeadPosition, food.Position);
            Front = (-1) * (food.Position.X - snake.HeadPosition.X) /
                    GetDistance(snake.HeadPosition, food.Position);
            Left = (food.Position.Y - snake.HeadPosition.Y) /
                    GetDistance(snake.HeadPosition, food.Position);
            Right = (-1) * (food.Position.Y - snake.HeadPosition.Y) /
                    GetDistance(snake.HeadPosition, food.Position);
            break;
        case Direction.N:
            Right = (food.Position.X - snake.HeadPosition.X) /
                    GetDistance(snake.HeadPosition, food.Position);
            Left = (-1) * (food.Position.X - snake.HeadPosition.X) /
                    GetDistance(snake.HeadPosition, food.Position);
            Back = (food.Position.Y - snake.HeadPosition.Y) /
                    GetDistance(snake.HeadPosition, food.Position);
            Front = (-1) * (food.Position.Y - snake.HeadPosition.Y) /
                    GetDistance(snake.HeadPosition, food.Position);
            break;

        case Direction.S:
            Left = (food.Position.X - snake.HeadPosition.X) /
                    GetDistance(snake.HeadPosition, food.Position);
            Right = (-1) * (food.Position.X - snake.HeadPosition.X) /
                    GetDistance(snake.HeadPosition, food.Position);
            Front = (food.Position.Y - snake.HeadPosition.Y) /
                    GetDistance(snake.HeadPosition, food.Position);
            Back = (-1) * (food.Position.Y - snake.HeadPosition.Y) /
                    GetDistance(snake.HeadPosition, food.Position);
            break;
    }

    if (Front < 0)
        Front = 0;
    if (Back < 0)
        Back = 0;
    if (Left < 0)
        Left = 0;
    if (Right < 0)
        Right = 0;
    }

Playing the Game

FoodGenerator is another class which randomly generates food inside the canvas, which is a of  600*600, which also generates lines to be used by RefreshCanvas() to update them in the UI. How it's being done is open to inquisition in the code provided with this article, because the main purpose is the explanation of the implementation of the Evolutionary Algorithm.

In the timer Tick event handler in the MainWindow.cs, we write the logic for the game to run, where in succession, first, the snake's sensors are updated, the sensor values are then fed into a neural network and the network's output is calculated. The outputs are then compared for snake to take the decision regarding whether to MoveForward(), TurnLeft() or TurnRight().

void timer_Tick(object sender, EventArgs e)
{
    foreach (SnakeInstance snake in evolution.SnakeInstances.Where(r=>r.IsDead == false))
    {
        snake.snake.FoodSensor.ReadSensor(snake.snake, snake.food.Food.First());
        if (PlayNetwork.IsChecked == true)
        {
            snake.snakeNet.ApplyInput(new double[]
            { snake.snake.FoodSensor.Front, snake.snake.FoodSensor.Back,
            snake.snake.FoodSensor.Left, snake.snake.FoodSensor.Right });
            snake.snakeNet.CalculateOutput();

            IEnumerable<double> outputs = snake.snakeNet.ReadOutput();

            if (outputs.ToArray()[0] > Math.Max(outputs.ToArray()[1], outputs.ToArray()[2]))
                snake.snake.MoveForward();

            if (outputs.ToArray()[1] > Math.Max(outputs.ToArray()[2], outputs.ToArray()[0]))
                snake.snake.TurnLeft();

            if (outputs.ToArray()[2] > Math.Max(outputs.ToArray()[1], outputs.ToArray()[0]))
                snake.snake.TurnRight();
        }
    }
    RefreshCanvas();
}

Evolutionary Algorithm

Each snake in the evolutionary race has its own food to feed on, so there is no competition in the feeding case, the only competition, the selection criterion, is that the snake which fed the most gets to propagate more. Hence, each SnakeInstance has a Snake, FoodGenerator and a BackpropogationNetwork, snakeNet of its own. To mutate the snake as it propagates, the class has a method MutateNetwork().

public void MutateNetwork()
{

    if (randon.NextDouble() > 0)
        int layerindex = 0;
        int nodeindex = 0;

        layerindex = randon.Next(snakeNet.Layers.Count() - 1);
        nodeindex = randon.Next(snakeNet.Layers[layerindex].Neurons.Count());
        int nodeindex1 = randon.Next(snakeNet.Layers[layerindex + 1].Neurons.Count());
        double sign = randon.NextDouble();

        if(sign>0.5)
            snakeNet.Layers[layerindex].Neurons[nodeindex].Connections.Find
            (r => r.toNeuron == snakeNet.Layers
    [layerindex + 1].Neurons[nodeindex1]).Weight = randon.NextDouble();
        else
            snakeNet.Layers[layerindex].Neurons[nodeindex].Connections.Find
            (r => r.toNeuron == snakeNet.Layers
    [layerindex + 1].Neurons[nodeindex1]).Weight = (-1)*randon.NextDouble();
    }
}

And a method to reproduce by copying other snake’s neural weights, by the method 'ReproduceNetwork()'.

public void ReproduceNetwork(NetworkData net2)
{
    snakeNet = new BackPropogationNetwork(net2);
}

When a snake dies by touching itself, touching the wall or by exhausting itself, an event, SnakeDead is fired, which is used to update a variable IsDead in our SnakeInstance, this variable is used in the evolutionary process. Now, many instances of this snake are initialized and simulation runs until all the snakes are dead and then sorted according to the number of times the snake fed, and the genes (or the neural weights) are propagated and mutated according to the following code, which is written in the event handler to the SnakeDead event.

void snake_SnakeDead(object sender, SnakeDeadEventArgs e)
{
    SnakeInstances.Find(r => r.snake == (Snake)sender).IsDead = true;
    SnakeInstances.Find(r => r.snake == (Snake)sender).Length = e.Length;

    if (SnakeInstances.Where(r=>r.IsDead==false).Count()==0)
    {
        IEnumerable <snakeinstance> topinstances =
            SnakeInstances.OrderByDescending(r => r.Length).Take(5);

        generation++;

        MainWindow.Current.textBlock_generation.Text =
            "Generation"+ ": " + generation.ToString();
        MainWindow.Current.textBlock_maxlength.Text =
            "Length:" + topinstances.ElementAt(0).Length.ToString();
        MainWindow.Current.graphwindow.AddDataPoint
    (generation, topinstances.ElementAt(0).Length*2);

        int count = 0;
        foreach (SnakeInstance instance in SnakeInstances)
        {
            if (count % 3 == 0)
                instance.ReproduceNetwork(topinstances.ElementAt(0).GetNetworkData());

            else if (count % 3 == 1)
                instance.ReproduceNetwork(topinstances.ElementAt(0).GetNetworkData());

            else if (count % 3 == 2)
                instance.ReproduceNetwork(topinstances.ElementAt(0).GetNetworkData());

            instance.IsDead = false;
            instance.Length = 0;

            if (count > 5)
                instance.MutateNetwork();

            if (count > 50)
                instance.MutateNetwork();

            if (count > 70)
                instance.MutateNetwork();

            if (count > 80)
                instance.MutateNetwork();

            if (count > 99)
                count = 0;

            count++;
        }

        DeadCount = 0;
    }
}

Hence, the simulation is run and re-run, and the result plotted out into another window. Here is a plot of the fitness parameter, the length of the biggest snake, plotted against generation. We can see the fitness increases rapidly initially, then oscillates due to random nature of the food generation.

External Links

The neural network library used is on GitHub at:

• https://github.com/hemanthk119/NeuralNetworks