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 snake
s 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: