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.

Evaluating Open-Ended Exploration and Creation

Challenges in evaluating open-ended exploration and creation

Cross-posted here and here.

I’ve been working on a reinforcement learning (RL) environment for machine exploration and creativity using Life-like cellular automata. Called CARLE (for Cellular Automata Reinforcement Learning Environment), the environment is the basis for an official competition at the third IEEE Conference on Games. But Carle’s Game is somewhat unusual in that it is a challenge in open-endedness. In fact, the RL environment doesn’t even have a native reward value, although there are several exploration reward wrappers available in the repository.

At the risk of pointing out the obvious, judging a contest with no clear goal is a challenge in and of itself. However, in my humble opinion, this is the type of approach that is most likely to yield the most interesting advances in artificial intelligence. Qualitative advances in a vast universe are what drives progress in humanity’s humanity*, even though judging these types of outputs are more difficult than recognizing an improvement in the existing state-of-the-art. The difficulty in recognizing qualitative advances contributes to the ambiguity of trying to evaluate works of art or art movements.

The first transistors did not improve on the performance of the mechanical and vacuum tube-based computers available at the time any more than the quantum computers in use today can unequivocally outperform electronic computers on useful tasks. Likewise, improvements in AI benchmarks like ImageNet or the Atari suite do not intrinsically bring us closer to general AI.

Life-like CA have generated a rich ecosystem and many exciting discoveries by hobbyists and professional researchers alike. Carle’s Game is intended to reward both artistic creativity and ingenuity in machine agents, and in this post I tinker with several rulesets to learn something about my own preferences and what determines whether CA outputs are interesting or boring from my own perspective.

* We’ll probably need a more inclusive term for what I’m trying to express when I use this word here, although it’s impossible to predict the timeline for machine agents claiming personhood and whether or not they might care about semantics.

Arts and crafting

Life-like CA can produce a wide variety of machines and pleasing forms. Some rulesets seem to produce pleasing patterns intrinsically, akin to the natural beauty we see in our own universe in planets and nebulas, rocks and waves, and other inanimate phenomena. This will be our starting point for determining contributes to an interesting output.

In the following comparison of a scene generated with random inputs for two different rulesets, which one is more interesting?

You may want to zoom in to get a good feel for each output, although aliasing of small features in a scaled down render can be interesting in their own right.

If you have similar aesthetic preferences as I do, you probably think the image on the right is more interesting. The output on the right (generated with the “Maze” ruleset) has repeating motifs, unusual tendril-like patterns, borders, and a ladder-like protrusion that looks interesting juxtaposed against the more natural-looking shapes prevalent in the rest of the pattern. The left image, on the other hand, looks more like a uniform and diffuse cloud centered on a bright orb (corresponding to the action space of the environment). One way to rationalize my own preference for the pattern on the right is that it contains more surprises, while simultaneously appearing more orderly and complex.

The “boring” ruleset, at least when displayed in the manner above by accumulating cell states over time, is known as 34-Life and has birth/survive rules that can be written as B34/S34 in the language of Life-like CA rules. The more interesting CA is unsurprisingly call Maze and has rules B3/S12345.

Here’s a pattern produced by another ruleset with some similarities to Maze:

That image was generated with a modified Coral ruleset, i.e. B3/S345678. In my opinion this ruleset demonstrates a substantial amount of natural beauty, but we can’t really judge a creative output by what essentially comes down to photogenic physics. That’s a little bit like if I were to carry a large frame with me on a hike and use it to frame a nice view of a snowy mountain, then sitting back to enjoy the natural scene while smugly muttering to myself “that’s a nice art.” To be honest now that I’ve written that last sentence it sounds really enjoyable.

There’s an interesting feature in the coralish ruleset image, one that contrasts nicely with the more biological looking patterns that dominate. A number of rigid straight features propagate throughout the piece, sometimes colliding with other features and changing behavior. It looks mechanical, and you might feel it evokes a feeling of an accidental machine, like finding a perfect staircase assembled out of basalt.

Giant’s Causeway in Northern Ireland. Image CC BY SA Wikipedia user Sebd

Regular formations like that are more common than one might naively expect (if you’ve never seen a nature before), and throughout history interesting structures like Giant’s Causeway have attracted mythological explanations. If you were previously unaware of the concept of stairs and stumbled across this rock formation, you might get a great idea for connecting the top floors to the lower levels of your house. Likewise, we can observe the ladder-like formations sometimes generated by the modified Coral ruleset and try to replicate it, and we might want to reward a creative machine agent for doing something similar. If we look at the root of the structure, we can get an idea of how it starts and with some trial and error we can find a seed for the structure.

Coral ladder seed. We’ll pay some homage to the story of John H. Conway coming up with the Game of Life on a breakroom Go board to illustrate machines in Life-like CA.

When subjected to updates according to the modified Coral ruleset, we see the ladder-like structure being built.

Although Coral and the modified ruleset shown here is very different from John Conway’s Game of Life, we can relate this ladder-like structure to a class of phenomena found in various Life-like CA: gliders and spaceships. A glider is a type of machine that can be built in Life-like CA that persists and appears to travel across the CA universe. These can be extremely simple, and make good building blocks for more complicated machines. In Life, a simple glider can be instantiated as in the figure below.

Spaceships are like gliders, and in general we can think of them as just another name for gliders that tend to be a bit larger. The space of known spaceships/gliders in Life is quite complex, and they vary substantially in size and even speed. Support for gliders in a given CA universe also tells us something about the class of a CA ruleset, which has implications for A CA’s capabilities for universal computation. Searching for gliders in CA has attracted significant effort over the years, and gives us some ideas for how we might evaluate curious machine agents interacting with Life-like CA. We can simply build an evaluation algorithm that computes the mean displacement of the center of mass of all live cells in a CA universe and how it changes over a given number of CA timesteps. Although this does give an advantage faster gliders, which are not necessarily more interesting, it provides a good starting point for developing creative machine agents that can learn to build motile machines in arbitrary CA universes. Clearly it wouldn’t make sense to compare the same quantitative value of that metric for a Coral ladder versus a Life glider, but we could evaluate a set suite of different CA universes to get an overall view of agents’ creative machinations.

What can a machine know about art, anyway?

Evaluating agent performance with an eye toward rewarding gliders is one way to evaluate Carle’s Game, but if that’s all we did we’d be constricting the challenge so severely it starts to look like a more standard benchmark, and it would no longer provide a good substrate for studying complexity and open-endedness. I would also like to encourage people from areas outside of a conventional machine learning background to contribute, and so in addition to rewarding agents that discover interesting machines, we should also try to reward interesting and beautiful artistic expression.

We can consider using automated means to evaluate agent-CA interactions based on quantitative preconceptions of art and beauty, for example by rewarding different types of symmetry. Or we could use novelty-based reward functions like random network distillation or autoencoder loss.

We can also try to reward machine creations for the impact they have on a human audience. In the final submission evaluation for the contest at IEEE CoG, I plan to incorporate a people’s choice score as well as to solicit curation from human judges that have expertise in certain areas. But soliciting human judgement from the crowd and experts while the contest was underway would not only require a prohibitive amount of human effort, it could change the final outcome. An online audience voting for the best creations might grow bored with interesting output prematurely, and competing teams might borrow inspiration from others or outright steal patterns as they are revealed in the voting interface.

Instead of online voting during competition, I am considering training an “ArtBot” value model that can provide stable feedback while the competition is still going. I’m still working out what this will entail, but I plan to open the competition beta round in March with the aim of eliciting feedback and pinning down competition processes. It might be as simple as training a large conv-net on image searches like “not art” or “good generative art”, but we can probably expect better results if we take some ideas from the picbreeder project. Picbreeder is a website and project led by Jimmy Secretan and Kenneth Stanley where users select the best image from a few options, which are then evolved using ideas like NEAT and compositional pattern producing networks (pdf). The results are quite impressive, and you can view the results on the website.

The culmination of the challenge will involve a final submission of creative agents, which will be presented with a secret suite of CA universes that will include but won’t be limited to Life-like CA based on Moore neighborhoods. The test suite may also include CA from the larger generalized space of possible CA known as “Larger than Life”, which I think should provide enough diversity to make it difficult to game or overfit the evaluation while still being tractable enough to yield interesting results.

If you’re thinking of entering Carle’s Game for IEEE CoG 2021 and/or have ideas about evaluating machine agents in open-ended environments, @ me on Twitter @RiveSunder or leave an issue on the GitHub repository for CARLE. I look forward to meeting the creative machines you develop and discover.

Update 2021-02-14: Coral ladders are not found in the Coral universe, but rather can occur in rulesets between “Coral” (B3/45678) and “Life Withour Death” (B3/S012345678). In an earlier version of this post I describe finding the phenomenon in the Coral ruleset, but due to an implementation error I was actually working with B3/S345678. The text is updated to reflect the proper rules.