Lately, I’ve been obsessed with cellular automata. A subset of computability theory, it’s a fascinating subject that keeps me awake at night, from reading “A New Kind of Science” by Stephen Wolfram, or mulling over different JavaScript implementations of Conway’s famous “Game of Life”. If you’re not familiar, it’s not terribly complex. In fact, the simplicity of this subject, at least in terms of understanding the big picture, is quite simple: you simulate some kind of model, with it’s own set of constraints, using a computer. In fact, it’s so simple, you don’t even need a computer for most simulations, but it’s a bit masochistic to do it without one.
Watch this video to get an idea of Conway’s game of life, and the amazing complexity it produces.
Think of it like a game, any other simple game: you have a few rules, or “moves” in some cases, and the game is constrained to some fixed space – in some cases a grid of tiles, in others a 3-dimensional space – but regardless, you let these rules express themselves over time. Usually when the outcomes are studied, it’s important to watch the game unfold in discrete time – that is, simple “units” of time, like for example, every second, or every hour.
Importance of variety in CA simulations
After creating several of my own implementations in my daily scripting project Etude, I was frustrated when a few versions came out pretty lame. At first I assumed I didn’t quite understand the problem and that my code was buggy. I mulled over it, and rewrote different versions for clarity, but ultimately I realized that a lot of times, the results just plain suck. What is fascinating to me, is that a few changes in the “truth table” – the set of rules that determine the outcome – turn the dull, lifeless output into this dazzling, animating set of blocks. These rule sets are simple, but they still produce interesting outcomes.
In the above example, I relied on a very simple rule set: each “unit”, in this case a 10px (or N pixel) block, is drawn on the “board”. Going through, row by row, column by column, the pixels are drawn as either black or white – denoting the traditional binary states of 1 or 0, on or off. When starting off, I “seed” the board with random states, by choosing a random number and then toggling it on or off if that number is equal to a fixed number. This random seeding kicks things off, and allows the “deterministic” generations that come after to have something to work with.
As time unfolds, more and more behavior is seen. Sometimes it goes very fast, and then slows down, other times it’s sluggish at the beginning, only to ramp up and even out of control, “dying” off shortly thereafter. Sometimes it can even maintain an equilibrium, in the sense that the animation continues at a reasonable pace, establishing a rhythm and pattern.
Wolfram’s book mentioned above covers these automata in more detail than I think will ever be covered by anyone else, so if you’re interested, I suggest grabbing that hefty tome, because it’s reasonably priced for the kind of insight it contains.
This simple, grid based automata has produced so many odd results, they have even been classified as different “species” because of their apparent self-referential, survival nature. Even a wiki exists to catalogue all these new types! Make no mistake, we’re simply talking about cells in a grid, but introducing this dimension of time has revealed a startling truth about reality – that life could very well be a much more complex version of this game.
Going beyond the grid
After exploring a bit, I’ve found implementations of Game of Life in 3d and on Minecraft. I also found a YouTuber who has been playing around with more complex versions of his own, giving them more parameters and rules, which have resulted in even cooler outcomes. There are countless other types of implementations of rule-based evolution simulations. One that has an interesting divergence from the typical automata is the Evolving virtual creatures project. Start clicking around YouTube and you’ll soon be immersed in videos of all types, simulating many different variations on this theme. Truly fascinating stuff.
Perceptrons: the building block of Neural Networks
Coined by Marvin Minksy, the father of modern AI, the perceptron is a singular unit of “perception” that when combined with other perceptrons, creates what I might call “a field of understanding”. Each Perceptron is another “black box”, where inputs are given, and encoded as a simple binary state. Once encoded, they are weighted and measured against a given threshold, and if they meet the criteria, they cause the Perceptron to fire output (or out its backside, if you’d like). This is really just the input for another Perceptron, and when you wire many (say, trillions, for example), you start to get an idea of how a human brain might actually work, and even be able to simulate something approximating it. This video gives a nice example for the basics. If you’d like to get more into it, I suggest reading Perceptrons and “Society of Mind”, both by Marvin Minsky.
The next step: Machine Learning & Neural Networks
Now that we’ve established some simple rules, we realize that emergent properties can come from these constraints. The next step is to actually teach a computer, using some new types of constraints. A different domain for this, though similar in nature, categorized squarely as AI, is the study of Neural Networks. This is a field I have read about but have yet to write implementations for – though that will change in the future. Regardless, it’s kind of a big brother to the traditional finite automata I talked about earlier. It is a domain specific solution to the concept of learning, done in a very simplistic model of how neurons and synapses in the brain work. This video has a good explanation, though there are many more if you’re interested. The concept relies on the traditional concept of computability, and the ability to give an input to some “black box” and assume an output will come out of the other side. In this case, the black boxes are nodes, and they are connected to other nodes like a graph.
The gist of this procedure is to start with a random weighting for each node, and then using the graph to represent “connections”, we can give inputs to one node and expect a weight to come out the other end, which will determine the direction to go. This procedure (I have intentionally simplified it) results in a consistent technique for training a model to behave or learn, in very, very elementary ways. The usefulness of neural networks is determined by the weighting they are deterministically designed to have, the amount of data they are given as inputs, the amount of nodes they have, and of course, the amount of generations that can lapse. The more data and time steps, the better the results. This has a lot of drawbacks, but it is a powerful step in the right direction. I haven’t gone into the minutiae because this is more of a “high-level” post. If you’d like to learn more, Udacity has an AI program for it, and there are thousands of resources online. I recommend Python for practicing in real code, should you choose to jump into it full speed. SciPy is great for science related computing, and PyBrain is a designed specifically for machine learning.
Evolutionary algorithms and “Fitness Functions”
Well, now that we’ve got our finite automata and our neural networks, it’s time to take this party to the next level, by simulating evolution. You could argue that our first example of cellular automata are actually perfect examples of evolution, and you’d be right in your argument. But this evolution is more of a side effect than intended design choice. What I mean is, the evolutionary model of design wasn’t “baked” in, but rather emerged as a property of truth tables. The field of evolutionary algorithms aims to solve that because it is a problem domain solution – it was designed with a problem in mind, and the solution to that problem is its domain.
Fitness functions, once again, are simple in principle, though more complex in implementation: the components of a fitness function are its rules, the number of generations it is allowed, the individual units in the simulation, and the actual fitness function which determines the “best genes” that should be passed on to the next generation. With a fitness function in mind, we let the simulation run, and then for each discrete time step, we measure the “fitness” of every unit in the simulation – and using a threshold for survival, we ruthlessly weed out those units who do not meet the fitness or even the threshold, if we want finer-grained control. This is once again, a simplistic simulation of what we see in real life.
However, we are faced with the deterministic problem once more: the fitness functions are determined by the creator, so the arbitrary choice will always result in a winner for that fitness function. The insight gained from using this simulation is not in the final result – that should already be known, given that it was chosen by its creator – but rather the emergent properties that evolve within this constraint that allow a unit to solve the challenge. These “offshoots” of the simulation are really where the interesting stuff happens. In the Evolving virtual creatures project noted above, the emergent properties are the types of kinetic motions each block creature developed to complete the pre-determined goal formed by the creator – in that case, capturing a block first. This resulted in fascinating growths, deformations and odd physical traits that helped or hindered the unit in finding its way to the goal.
Learning from the micro to extend the macro
A common theme here is the simulation of observable states within the context of computability. Now that we’ve got this sweet computing power, we can simulate and model behavior from the real world, by recreating it in the soft-world. One overarching problem that I see is that while we hope to gain some insight beyond what we already can observe by simulating these miniature versions of our worlds – whether it’s a mini society of a mini-mind – we can’t necessarily gain something bigger and greater than ourselves. We are working with existing data, deterministic data – and so that proves a constraint. But who knows, there is a great chance that we will slowly learn using these tools, then incrementally evolve to create greater tools – what Daniel Dennett answers as “both” to the chicken and egg question of “which came first – evolution of tools or evolution of humans?”.
There is a great deal of observation to be done still, and I am excited to see it explode in the future, as it will likely signal a boon for civilization, since we can model our own behavior around it. Just imagine the kind of power we can wield if we learn to simulate everything before making major decisions. Combined with the prospect of Quantum Computing, and I think we’re in for a wild ride in the next decades and centuries. I think the idea of slow, solid growth and finally explosions of innovation are likely to be the theme of humanity as a result of all this.
This brave new science
I think Stephen Wolfram is justified in coining the phrase “A New Kind of Science”, because we are steadily paving a whole new type of science – that of simulation and computability – and it has profound results that clearly supersede the traditional capabilities of math. With this powerful tool in hand, we no longer need to be victims of some mysterious force, a god, a mathematical constant or otherwise; we have tools to simulate this behavior and it’s up to us to cultivate this newfound knowledge to further understand reality and eventually shape it for ourselves. These are powerful concepts, some that may seem idealistic, megalomaniacal or even outrageous, but we are actually at a point where it’s real!