Introduction to Life and Other Pasttimes

B3/S345678

 

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.

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.

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 3 neighbors, so it’s going to become alive, and the same goes for the cell directly below the middle. Now we can check our counts before making the necessary changes.

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.