Introduction to Life and Other Pasttimes
Originally published at http://thescinder.com on February 16, 2021, friends can read this article here: https://bit.ly/carle_2.
I’m running a contest based on open-ended exploration and machine creativity in Life-like cellular automata. It’s slated to be an official competition at the 2021 IEEE Conference on Games. If that sounds like something you could get into, check out the contest page, and look for the contest Beta release in March.
If you’ve never heard of John Conway’s game of life, then today you are in for a treat. In this post we’ll go through the recipe for building a tiny grid universe and applying the physics of Life to make a few simple machines. These machines can in turn be used as components in ever more capable and complex machines, and in fact there is a whole family of Life-like cellular automata, each with their own rules, to build in. But before we start bridging to other universes, we’ll begin with a recipe for the types of universes that can support Life and other interesting things.
Fiat Grid
Let this be a grate universe.
Let us start by building a simple grid universe. If you’d like to follow along and try your hand at universal creation at home, you can start with a chess/checkers or Go board if you’ve got one available. Otherwise, grab a piece of paper and draw some lines in a regular checkerboard pattern, or just enjoy the explanations and images.
Wow, look at that universe. Pretty nice, eh? Well, not yet. We’ve got a blank expanse of squares (we’ll call them cells), but there’s nothing going on. In short we’ve got space but no matter. To fill this limitless void (we’ll consider this universe to be wrapped on the surface of a donut-like toroid), we’ll use some coins that represent the state of each point in our grid universe. It’s helpful to have at least two different colors to keep track of updates, but you can make do with just a pencil in a pinch.
That’s better, now we’ve got one cell in state 1, colloquially known as “alive” in the Life-like cellular automata community. Now it’s time to define some physics. These will determine the maximum speed at which information can propagate through our universe, known as the speed of light, as well as universal dynamics. We’ll start by defining which cells can interact with each other in a given area, defining our universe’s locality. We define this by choosing a neighborhood, and our choice of neighborhood in turn determines the speed of light in our universe. For Life-like automata, we’ll use a Moore neighborhood. This means that each cell can be affected only by it’s immediately adjacent neighbors.
Now let’s choose our rule set. In this example we’ll start with John Conway’s Game of Life. The rules of Life state that any cell that is empty and has exactly three live neighbors will become alive, and any cell that is alive and has either 2 or 3 neighbors will stay alive. All other cells enter or remain in state 0, which is also colloquially called “dead.” In the notation used for Life-like cellular automata, this is written as B3/S23, and in case you’re skimming through this essay at extreme speed the rules are called out again in bullet points below.
At each update:
- Dead cells with exactly 3 live cells in their Moore neighborhood go from 0→1.
- Live cells with 2 or 3 live cells in their Moore neighborhood remain at state 1.
- All other cells die out or remain empty.
Now if we refer to our universe with a single live state, we notice that the lone live cell in our universe has exactly 0 neighbors. This doesn’t meet the criteria for survival, so we mark this cell for a transition from 1 to 0 with a dirty penny.
After the update, the grid is blank again, and since there’s no way for a cell to go from 0 to 1 with no neighbors, it stays that way.
Let’s consider a slightly more interesting pattern.
With 3 live cells we need to calculate more Moore neighborhoods (heh). We’ll start from left to right.
On the leftmost column and one cell further to the left, no neighborhoods contain exactly 3 cells, so there will be no births. The very leftmost live cell, however, has only 1 live neighbor, so we need to mark it for removal. Note that the rightmost live cell is still there, but it’s not a part of this neighborhood. We only change the cells later, after figuring all the changes we need to make in the next update.
We follow the same process on the right and mark that cell to transition to a dead state as well.
Now we can consider the center column.
The cell directly above the middle of the line has exactly 3 neighbors, so it’s going to become alive. We’ll mark cells with a shiny silver dime if they are set to become alive in the next step. The same goes for the cell directly below the middle, so we’ll mark it as well. Now we can check our planned updates to make sure we counted each neighborhood correctly before making the necessary changes. We haven’t changed any cell states yet, but we’ve marked the cells set to become alive with silver coins, and the cells set to be removed with black coins. Unmarked copper-colored pennies will stay the same.
When we update cell states, the pattern flips from a horizontal line of 3 live cells to a vertical one. If we continue making updates ad infinitum we’ll soon notice the dynamics are repetitive. This pattern is what’s known as an oscillator, and it has a period of 2 updates.
But the period 2 blinker is a far cry from the more interesting machines we can build in Life. Life rules facilitate stationary, mobile, and generative machines, and they can become quite complicated. Let’s have a look at the simplest mobile pattern, the 5-glider.
Removing the Moore neighborhood card and moving through the update process more quickly, we’ll start to see the pattern wiggle it’s way across the universe.
Now if we go through the same update process, but removing the update markers this time:
A wide variety of spaceships and other machines have been invented/discovered in Life. Another lightweight spaceship only slightly more complicated than the 5-glider looks like a tiny duck:
The remarkable thing about life is the complexity that can arise from a simple set of rules. With a definition of locality via cell neighborhoods and a short string (B3/S23) describing cell updates at each time step, a vast trove of machines are possible. In fact, you can even build a universal computer in Life, which you could in principle use to run simulations of John Conway’s Game of Life. Just follow the simple two step process for building Paul Rendell’s Turing machine and you’ll be computing in no time!
I used the cellular automata software Golly to make the figure above (click for a higher resolution version), and I’ll come clean and admit that the Turing machine actually is available in the software as an example. But for those looking for an extra challenge, there’s nothing stopping you from building the complete machine on a physical grid and updating it with coins or stones.
Now, Life is just one universe, and there are over 260,000 sets of rules just for the subset of cellular automata that are Life-like, i.e. that undergo B/S updates according to the number of neighbors in each cell’s Moore neighborhood. We’ll be looking at some of the other rulesets, and the machines that can be built therein, in future posts.
If you are interested in the creative and technical potential of Life-like cellular automata, and are perhaps interested in teaching machine agents to explore and create with them, check out the reinforcement learning environment CARLE that I am developing as a competition for the IEEE Conference on Games 2021.
