The source code for this article can de downloaded here: https://github.com/LisburnLad/ArtificialLife/releases/tag/v1.0
Instructions on getting up and running are given at the end of the article.
How To Create Intelligent Life
So how do you actually go about creating intelligent life? To be honest I don't actually know. However, I do know (look away now all of you with a fundamental religious belief) that life came about through evolution. So a computer program that models evolution would be a good place to start.
Luckily such a program already exists: Genetic Algorithms model the natural selection process. They start with a set of instruction strings, each of which is used to form an object that can then be evaluated to see how well it performs at the task in hand. So, in our case, each instruction string would be used as the blue-print of our life form, which we would then create and evaluate to see how good it is at the problem we set it. The instruction strings in the Genetic Algorithm represent biological chromosomes.
Once the object created from each chromosome has been evaluated, to give it a fitness score, the chromosomes are then ordered by these scores. The worst performing chromosomes are discarded and the best are used to form a new generation of chromosomes. When forming the next generation, the best chromosomes are combined together in the hope of producing new chromosomes that contain the best features of their parent chromosomes. So, for our life forms, the instruction strings from two parents would be spliced together to form the instruction string for a new child which would, hopefully, outperform its parents.
When the next generation of chromosomes has been created, each is again evaluated in the same way as before, and the process continues in this way. This "survival of the fittest" selection approach should result in populations that are successively better adapted to solve the problem for which they are being evaluated. For more information on Genetic Algorithms check out the seminal book by David Goldberg.
In addition to knowing that life came about through evolution, I also know that the most evolved computer scientist brains have created C#, the finest programming language known to mankind (or to me anyway). Given this knowledge, a C# Genetic Algorithm is what we need and this looks perfect for the job:
Luckily such a program already exists: Genetic Algorithms model the natural selection process. They start with a set of instruction strings, each of which is used to form an object that can then be evaluated to see how well it performs at the task in hand. So, in our case, each instruction string would be used as the blue-print of our life form, which we would then create and evaluate to see how good it is at the problem we set it. The instruction strings in the Genetic Algorithm represent biological chromosomes.
Once the object created from each chromosome has been evaluated, to give it a fitness score, the chromosomes are then ordered by these scores. The worst performing chromosomes are discarded and the best are used to form a new generation of chromosomes. When forming the next generation, the best chromosomes are combined together in the hope of producing new chromosomes that contain the best features of their parent chromosomes. So, for our life forms, the instruction strings from two parents would be spliced together to form the instruction string for a new child which would, hopefully, outperform its parents.
When the next generation of chromosomes has been created, each is again evaluated in the same way as before, and the process continues in this way. This "survival of the fittest" selection approach should result in populations that are successively better adapted to solve the problem for which they are being evaluated. For more information on Genetic Algorithms check out the seminal book by David Goldberg.
In addition to knowing that life came about through evolution, I also know that the most evolved computer scientist brains have created C#, the finest programming language known to mankind (or to me anyway). Given this knowledge, a C# Genetic Algorithm is what we need and this looks perfect for the job:
This Genetic Algorithm (GA) Framework allows us to simulate evolution. All we need to know now is what to evolve. Unfortunately my knowledge is once again lacking. I do know that there are a load of different Artificial Neural Network models out there, the best known of which is probably the Backpropagation Algorithm. However, while all of these Neural Networks have much to offer, I'm not 100% sure if they're the exact component required to give true Artificial Intelligence.
Therefore I'll start with something a lot simpler: a NAND gate. Basically this can be thought of a very simple switch, whose output will be turned on, unless all of its inputs are turned on. Additionally, it has the desirable property of being a "universal" logic gate, meaning that any other logic function can be implemented by using combination of these NAND gates. Although these logic gates do give a very simple building block, they do differ from the human brain in that they are binary components, working only in 1's and 0's, whereas the brain, or the Backprop Algorithm, are analogue. Hopefully this difference wont stop us in our quest for Artificial Life!
The other thing I know about the brain is that it is massively parallel. Millions of neurons are all working at the same time to process the input signals and to generate the output responses. Unfortunately my PC has only got a couple of processors, so I'm going to have to simulate a massively parallel architecture. Similarly, the brain is a 3-dimensional object, but this sounds a bit tricky to implement, so to start with I'll stick to a simple 2-dimensional grid and see how far this get take us.
In traditional Artificial Neural Networks (ANNs), such as Backpropagation, all the connections have the same direction and information moves through the network from input to output - these are known as Feed Forward networks. Recurrent Neural Networks allow information to move in the opposite direction, so that feedback loops can take place. Which is best? Yet again I don't know (this is becoming a theme!), so I'll let the Genetic Algorithm decide on the direction of each node in the network. Since we're going to have a simple 2-dimensional grid of nodes, each node can have 4 possible directions (let's call these North, East, South and West to make things easy to visualize).
Defining the Chromosome
So, we now have a Genetic Algorithm (GA) that can simulate Evolution and a plan for a very simple Neural Network to which we can apply this evolutionary process. However, GA's don't work directly with Neural Networks, instead they work on Chromosomes that, in this case, represent the structure of the Neural Network (NN). We therefore need to encode our NN structure to give us a Chromosome.
Since each node of our network has 4 possible directions, a very simple encoding is simply to have 2-bits for each node (i.e. 00 = North, 01 = East, 11 = South and 10 = West). If we begin with a small grid of 5 x 5 nodes, then we'll have a chromosome of 50 bits in length.
So, for example, the chromosome:
01101000001110000010101000100110100001010100011111
Gives a network with the following directions:
→ ← ↓ → ↓
↑ ↑ ↑ ↑ →
← ← ↓ ↑ ↑
↑ ↑ → ↓ →
↓ → ↓ ↑ ↑
This is a very simple chromosome, with each node being represented directly. It's what's referred to as a "strong specification scheme" or "direct encoding". As the network grows in size a "weak specification scheme" or "indirect encoding" method would be more appropriate, as these tend to allow modules to be defined, but for this simple structure, the direct encoding should be sufficient.
Evaluating the Structure
Each node in the grid represents a single NAND gate and this will receive input from the 3 adjacent squares in the grid that are not the output square. So for a North orientated gate, as shown below, it will get its inputs from either side (A and B) and from below (C).
A node at the edge of the grid will have a reduced number of inputs, so a corner node will potentially only have a single possible input. Additionally, an input will only occur if the output of the gate in the adjacent square is pointing into the current square. So, for the centre node in the grid below, it's output points South, so its potential inputs are the East, North and West nodes, shown by the red circles. However, none of these point into the centre square, so this node has no inputs. In this case all inputs are considered to be zero and the node will have a constant output value of 1.
Running the program
To run the program, do the following:
1. Download the source code from here:
https://github.com/LisburnLad/ArtificialLife/releases/tag/v1.0
2. Open the ArtificialLife.sln solution in Visual Studio (I'm using VS2012 but I presume that this will work in any newish version).
3. Install the Genetic Algorithm Framework for .Net 4.0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
1 1 1 0 1
1 1 1 1 1
1 1 1 1 1
0 1 1 1 1
1 1 1 0 0
