Cellular automata is a model of artificial intelligence involving the creation of single-celled programmatic life forms, within a computer program. John von Neumann, the first scientist to implement cellular automata, came about the discovery while in search of a way to create self replicating robots. He devised a specific set of rules guiding the life, death, and reproduction cycle of each cellular automata cell. When put into action, cellular automata can create increasingly complex patterns, which seem to imitate forms of bacterial life, right on the computer screen. While the patterns it produces can be quite complex, the C# .NET code is surprisingly easy. In fact, the Wolfram Alpha computation engine is based, in part, upon cellular automata.
In this article, we’ll create our very own artificial intelligence bacteria by implementing cellular automata with the rule set from Conway’s Game of Life. To keep things interesting, we’ll also use the Strategy design pattern to implement the rule-sets for our artificial intelligence world. Let’s get started, and create some life!
In order to create our artificial life forms, we’ll first need to devise a world for them to live in. Since cellular automata require very little with regard to life requirements, we’ll use a basic 2-dimensional array in C# .NET as their world.
Each cell within the world will occupy a single array space (also called a cell), and will have a value of 0 if no cell exists at this coordinate, or 1 if a cell is alive in this coordinate. For example, if field[5, 6] is equal to 1, a cell is alive at this point.
With the basics of the world defined, we now need to define the rules that each cell will follow during its lifetime.
Just as life on earth must follow specific rules of physics, so too must the cells in our digital world, although the rules will be much more simple. The standard definition of cellular automata rule sets include two simple rules - what is required for a cell to continue living, and what is required to birth a new cell. Just by defining these two rules, we create amazingly complex cellular artificial life.
With the rules defined, we can follow the standard notation for cellular automata rule sets, which looks as follows:
The digits before the slash are what is required for a cell to continue living. The digits after the slash are what is required for a cell to be born. The digits refer to the neighbors of a cell in question. So for example, if we’re looking at the cell at position 5,6, we check its neighbors. If the cell has 2 or 3 neighbors, it can continue living and will not die. If the cell has 3 neighbors and it was not already alive (it had a value of zero), it will now be born (have a value of 1). Another way to consider this would be, if a cell only has 1 neighbor, it will die of loneliness, but if it has 2 neighbors, it will continue living. If the cell has exactly 3 neighbors, it will be born if was not yet living. Likewise, if the cell has more than 3 neighbors, it will die of overcrowding. As you can imagine, the rule set 23/3 is only a subset of a very large number of different patterns. 23/3 happens to be the rule set for the famous cellular automata implementation, Conway’s Game of Life. However, there are many different rule sets, all the way up to 8 digits on each side of the slash (depending on the dimensions of your world).
With the rule set definitions complete, we can now move on to setting up our artificial intelligence world in C# .NET.
The full project source code can be downloaded here.
Since we’ll be creating a 2-dimensional world for our cellular automata, we’ll be using a 2-dimensional array. We’ll also define the max width and height of the array so we can fit the world on our screen. To keep things as simple as possible, we’ll display our cellular automata in a plain old C# .NET console window. We’ll draw each cell, which is represented by a 1 within the C# .NET multi-dimensional array, and redraw the screen upon each tick. The initial program code is shown below.
The first part to note in the code is our DrawField() method. This method draws the pixels from our C# two-dimensional array in the console window. This method is called inside a loop and is ran each tick. It’s interesting to note that a delay could be inserted within the loop to slow down the ticks, by adding System.Threading.Thread.Sleep(10); However, for our case, the faster the speed of the cellular automata, the quicker our evolutions will occur.
In the main portion of code, we set the size and position of the console window and draw a series of random cells throughout the 2-dimensional array. This will be our initial position before we begin applying the rules for our cellular automata. You can create a vast number of different initial positions, which in turn, can create vastly different patterns of artificial life.
The most important part of the above code is where we instantiate an instance of our cellular automata rule set. The RuleSet class holds the job of manipulating the cells and applying the rules for life, death, and birth. Notice we use a RuleSet variable, which will be an abstract base class (or even an interface) and implement it with the concrete class ConwaysGameOfLife(). As you can tell, we could create many different implementations of the rule set to define different versions of rules for our artificial intelligence cellular life.
Let’s move on to creating the base RuleSet class, from which all rule sets will inherit from.
Our base RuleSet class will take care of handling the common code, used by all the different versions of rule sets. For example, each rule set will need to be able to calculate its neighbors. We’ll define a function GetNumberOfNeighbors(x, y) which will return the count of neighbors for a particular cell at position x,y. This function itself, is the heart of any cellular automata rule set.
Notice in the above code, GetNumberOfNeighbors() is fairly basic in structure. We simply check each side across, up and down, and diagonals for a particular cell to count its neighbors. If any neighboring cell holds a value of 1, then we increment the count.
Since we’re implementing the Strategy design pattern by creating an abstract base class, we’re going to be defining concrete implementations for each cellular automata rule set. We can also take advantage of the Template Pattern to make coding the concrete rule sets even easier. Notice in the above code, our public method Tick() calls a protected method TickAlgorithm(). The user who implements the RuleSet() class will have access to call the Tick() method, but not the TickAlgorithm() class. TickAlgorithm will be defined by the concrete class and will contain the code which actually modifies the world array, according to the rule set. The public method Tick() then copies the results in the main world, thus advancing our artificial life one generation forward.
With the base RuleSet class defined and a template method created, it’s quite easy to design a concrete rule set class. We simply inherit from the RuleSet class and implement the template method, TickAlgorithm(), as follows:
Note in the TickAlgorithm() method, we execute the rules for our cellular automata artificial life and returns a new world array with the changes made. Since our rule set is 23/3 (which is also called Conway’s Game of Life), we’ll leave a cell alive (with a value of 1) if it has exactly 2 or 3 neighboring cells with a value of 1. If cell is currently a zero (meaning the cell is not alive), and it finds itself having 3 neighbors, the cell will become alive and get a value of 1. In all other cases, the cell will die and reset its value back to zero.
Naturally, we can create many different rule sets, based upon our RuleSet class, to implement different versions of cellular automata artificial life. For example:
The above code defines a different rule set for cellular automata, based upon 125/36. If a cell has 1, 2, or 5 neighbors, it will continue living (if it was already alive). If a cell has 3 or 6 neighbors it will be born (if it was currently a zero). Each different ruleset can create drastically different patterns of virtual life.
Similar to the above concrete ruleset examples, we can actually create a generic ruleset implementation that you can pass the notation form of the rule to implement all of the different behaviors, without having to implement individual ruleset classes for each one. This class makes it much easier to try out different cellular automata rule sets. For example, if you wanted to create the rule set 123/45, you could simply call RuleSet = new RuleGeneric(field, maxX, maxY, 123, 45). Likewise, to create the rule set 876/5432, you could simply call RuleSet = new RuleGeneric(field, maxX, maxY, 876, 5432). The code is as follows:
With our RuleSet design created and our main loop defined, we can run the example program to view our cellular automata artificial life forms. An example output from the above code produces the following:
Notice that clearly defined patterns begin to emerge from the initial random pixels we created. Each time the program is ran, the initial random pixels differ, yet similar patterns and movement emerge. It can be quite amazing how complex the patterns can evolve to be, using such simple rules for life. Since we are using the ruleset from Conway’s Game of Life, eventually the evolutions will stabilize and a final pattern will emerge.
The pattern below is a final stable pattern from an initial random configuration.
While cellular automata artificial life in C# .NET is interesting to look at, perhaps even art, the functional use of cellular automata could go much further. Certain rule sets for cellular automata have been proven to implement universal computation, also called Turing machines. A universal machine can be programmed to solve any mathematical problem, given enough space, time, and memory (such as, with a PC computer). By knowing that cellular automata can implement a universal machine, it’s actually possible to provide input to a cellular automata artificial life pattern and receive coherent output in return, virtually programming the cellular life.
For example, the initial configuration of a cellular automata (such as the random configuration we used above) can be considered the input. The final stabilized pattern of the cellular automata can be considered the output. Both the input and output would be considered encoded data, which could be translated to known values. A more concrete example would be attempting to solve the basic math function AND. One could theoretically devise a method to encode the data of 0 and 1 in an initial configuration of cellular automata, then run the program (ie. allow the cellular automata to fully run until stabilization occurs), and then count the output cells to decode the final value. Thus, passing in the initial values for 1 AND 0, the expected output would decode to 0. Likewise, passing in the initial values for 1 AND 1, the expected output would decode to 1.
Since an initial configuration for cellular automata consists of a very large number of possibilities, one could speed up the process of solving a mathematical problem with a cellular automata network, by using a genetic algorithm to discover the proper initial configuration and stable configuration for output.
The key behind using a genetic algorithm would be to create a precise fitness test which moves each cycle of the cellular automata closer to the expected answer. For example, we could draw an invisible line down the center of the world grid. The left side could represent 0 and the right side 1. If only cells on the left side are alive (or the majority), the output could be considered a 0. If only cells on the right side are alive (or the majority), the output could be considered a 1. Using this method, we can effectively encode and decode cellular automata data. This would allow us to theoretically use artificial life to solve a mathematical problem. The generations of life evolving would be considered the program executing and the configuration of cells at start and end would be the input and output, respectively.
Cellular automata is a form of artificial life involving single-celled virtual life forms, within a C# .NET computer program multi-dimensional array. While the rule sets behind the life, death, and birth of each cell is simple, the patterns of life that emerge from each single cell and group of cells can be quite complex. Cellular automata was initially created in the hopes of discovering self-replicating machines, but has been mostly held as an interesting visual to display. While certainly interesting to look at, it’s possible for cellular automata to produce real-world solutions and computations, and be capable of solving complex mathematical functions, similar to any computer. Perhaps, the real power behind cellular automata is yet to be discovered.
This article was written by Kory Becker, software developer and architect, skilled in a range of technologies, including web application development, machine learning, artificial intelligence, and data science.