go back to play with the sim

Petri Cells BFF: A Simulation of "Artificial Life"

This is the first high-complexity replicator I got, in an early version of the program. It's the result that made me jump out of my chair, and say, “I am a god”:

What is Petri Cells BFF?

I heard about this Sabine Hossenfelder video discussing a a paper that was released in august, on how “artificial life” in the form of executable programs could emerge organically from noise.

This paper sits at the intersection of several different topics which are very interesting to me - languages and computation, clever visualizations, origins of life, virtual evolution, and more. So I created an interactive visualization of the concept.

I more or less reproduce the research paper, with only slight modifications, and a different UI. This writeup will describe how the simulation works, and some of the results.

You’ve probably heard of the the prime example of cellular automata, Conway’s Game of Life. Example here, a program delivers emergent complexity out of simple interaction rules.

There are many cellular automata variants with hard-coded rules for cell interaction. But before you start getting bored, and saying "sure, we can do some fun things with cellular automata. But isn't that old news?" Know that this particular instantiation is completely unlike anything Conway dreampt of.

So let’s take things a step further: what if we allow variation in how the different cells on the grid behave?

In this project, every cell is is a self-contained computer program. These programs are composed of 10 principle executable “instructions”, which I will discuss in more detail later. For the purpose of visualization, we can assign each instruction a unique color. As the default setting, each program will be 64 instructions long. Then, each program can be represented as an 8x8 square “cell”, like this.

Okay. If the cells are each literally self-contained programs, what is the programming language? For that, the authors repurpose a language which, though esoteric, you may have heard of: Brainfuck. A super-minimalist language, it was made with the goal of creating the smallest possible interpreter for a Turing-complete language.

Supposedly, Brainfuck (BF) wasn’t meant for practical uses, but rather as a theoretical exercise in language design. That doesn’t apply here, though, because the language is actually chosen for it’s practicality. Because the syntax is so minimalist, any randomly created program will be executable.

Actually, we are not going to be using vanilla BF, but rather, a variant designed for programs to modify themselves, “BFF”. Whereas standard BF takes in an input and returns an output, BFF will write to the same tape that it reads from, modifying itself in real-time.

The instruction set for BFF is below.

There are a few other rules to cover. The program terminates if it reaches a limit on the number of reads (2^10 for me, 2^13 in the paper). If a value appears in the program which is not in the instruction set, it will not be executed - in theory, this can be used to store memory.

Picture each program/cell as an array of integers (in the original paper, they’re arrays of bytes). 9 of those values map to the instructions listed above - your "<"s, your "]"s, etc. The value of 0 is read to determine whether to enter/exit loops. Everything else is a no-op.

To play with and test the BFF interpreter, I built a visual version.

On the backend, I store programs as arrays of integers, but I also can print a program as a human-readable-string that read as Brainfuck code. If you click on a cell, it will give you both formats. You can think of the human-readable-string format as the “lossy” format, and the integer-array format as the “lossless” format.

From what I can tell, the original research paper just stores all of the programs as strings. This has a few advantages (and probably some disadvantages), and is one of the biggest ways that our implementations differ. I’ll discuss the language mapping more close to the end of this post.

Either way, we now have an interpreter for executing these programs. We can use it in really cool ways to recursively recombine programs with each other.

To combine programs with each other and make something new, there are 3 steps:

1. The programs are concatenated, literally like concatenating arrays or strings, into one program.
2. The program is executed, using the interpreter for BFF (self-modifying Brainfuck). Since the program makes changes to itself, the result will be a modified program.
3. The program is split in half, resulting in 2 new programs.

And the two new programs take the place of the original programs. This process can be expressed as one line of code: a, b = split(execBff(a + b)).

Grid Interactions

Now that you know the chemistry behind transforming 2 programs into 2 programs, we can introduce: THE GRID.

The rules for the grid are quite simple. Each epoch, iterate through all of the cells in the grid. The cell randomly chooses another cell with in its “radius” of adjacency (by default, no more than 2 away on each axis). skip a cell if it the cell it’s trying to pair with has already been reacted with in the same epoch (this probably helps with parallel processing in the original, but doesn’t make a big difference in my version). The cells react. Rinse and repeat.

At risk of burying the interesting bit, if you run this simulation, then some of the programs will spontaneously acquire the ability to self-replicate and dominate the grid.

Speaking about “artificial life”, one little issue: scientists still can’t agree about what “life” means. But one thing they do agree on is that the ability to self-replicate is part of it. This is why most of the studies on the “origin of life” focus on reproduction. -Sabine

What I like about the “life” that emerges is how much of a stark phase transition it is. You don’t have to squint and imagine it. In many cases, a pattern will suddenly dominate the grid in an undeniable way.

Early Signs of Life

What we quickly noticed, with the default settings (a small grid, no noise), that there are basically 2 types of life which come to dominate.

Firstly, some life comes about almost immediately in the chaotic conditions under which the board is initialized, yielding some interesting patterns. For brevity, I will call this kind of life “complex life”.

No matter how many times I see this, I always get excited when it occurs. It never gets old.

These early-game replicators are some of the coolest, but they’re rare, only occurring maybe 1 out of every 10 runs. The strategy for finding them is to spam restart the simulation, letting it run no more than 200 epochs, until you get one. And when it comes to complex life, you’ll know it when you see it.

The second kind of life is very basic bi-color patterns which emerge later on. These are actually “sub-strings” (patterns within the cell) which propagate themselves outward eventually to neighboring cells, and eventually the whole grid. I’ll call these replicators “simple life”

Another thing you notice is the distinction between “surviving” and “replicating”. Most cells will eventually settle into a state that is relatively change-resistant. There is a surprising level of consistency within the board, as most can last a number of epochs with relatively few changes. Becoming a “persister” is in itself is a kind of adaptation, so to speak. But the replicators take things quite a step further than the pesisteres, by multiplying themselves across the grid.

When life emerges, it almost never goes away. So the board essentially becomes "locked" in one of a discrete number of "possibilities". For all of these observations, it feels like a coin toss whether the behavior implies something deeper about life and our world, or the behavior is just a pesky fluke of how the underlying language is implemented.

Noise

After a while, I got bored of this, so I introduced of noise options. The options are “kill cells” and “kill instructions”.

Kill cells will randomly pick a certain number of cells from the grid and replace them with entirely new random instruction sets.

Killing cells reliably creates complex life. If you run program long enough while killing cells at a 3% rate, it will virtually always result in an interesting pattern coming to dominate the board.

I attribute this to the power of RNG. The original paper seems to downplay the need for background random mutations, and emphasize that life can emerge merely from interactions between cells. Contrary to this, I found that if you’re after complex life, noise definitely helps.

How I would describe it is, after the early stage of the simulation, the game state becomes “ossified”. The cells have to become change-resistant, and there is not enough entropy in the system to support the amount of variance required to optimally seek out complex replicators.

This explains why, under default conditions, complex life tends to emerge early on. Since the grid is randomly initialized, there is a lot of variance in the system. Later, replicators do emerge eventually, but only as simple life, because there’s not enough bandwidth for anything more complex.

Kill instructions is another kind of noise. Instead of picking entire cells to kill, it will randomly replace individual instructions (codes) across the board.

The effects of this action are paradoxical and interesting. If life has not yet emerged, then it will make it harder for it to emerge in the first place. But if life has already emerged, and you subsequently turn on “kill instructions”, it will stimulate the changes and evolution of that life.

This is interesting to watch. In the absence of “kill cell” mutations, mutating and evolving life is actually quire rare. Complex life usually maintains a stagnant, unchanging phenotype. But if you introduce this kind of noise, then it will consistently and continually change.

It’s unsurprising that noise would have the effect of “shuffling” the genome, but it is quite surprising that the cells are resistant enough that they maintain the ability to self-replicate.

Other customizations

Cell Size

By default, a program is 64 instructions long - a square number, so it can fit into a cell. But there’s no reason it can’t be any other square number! I implemented the ability to create different-length programs: 49, 36, 25, 15, and so on. When you run the sim with smaller-sized programs, one thing you notice is that terminal states are more likely. Here, “terminal state” refers to a static, totally unchanging board.

To some extent, this is expected, because if programs are smaller, there are fewer permutations. It also makes me wonder if all programs will eventually resolve into either a terminal or looping state. In principle, the answer is yes, but how long will it take? Furthermore, “endgame” states are likely to have replicators, which makes the board look ordered - a fact which runs contrary to the intuitions based on entropy (or does it?). I should study this more.

Unique Cell Counter and Compression Statistic

The original paper computes complexity precisely with special formulas. I tried to use the same formula they used, but found that the performance cost was too high. (Maybe they did it in a faster way).

Instead, I measure 2 relatively simple proxy metrics each epoch, both of which are surprisingly informative:

• The number of unique cells
• What I call "compression", which is just the ratio of the original length and the compressed length.

I compress with Pako, for no particular reason, except that it was the first library that worked.

An interesting result from these metrics is the heterogeneity of replicators.

Some replicators are homogeneous, allowing only a couple variations, where others are heterogeneous, allowing hundreds of different variants - especially at first. I’m not sure which kind are my favorite.

Despite the diversity of the the heterogeneous replicators, which allow for many subtle variants, there is rarely any confusion whether a group of cells is part of the same “species”.

History

To save time, you may want to run the simulations on high speeds, but that can make it easy to miss important events. Therefore, these simulations store their history, allowing you to rewind (even run the simulation in reverse).

To save on space, grid states are saved in 50-epoch increments when you run the animation. This is not a bug; I thought that storing every increment would be overkill on memory. If you’re still worried about space, you can turn it off (for the most part) by running this command from the console.

controller.miscSettings.storeStateWhenRunning = false;

Interpreter randomizer

For the purpose of this simulation, I arbitrarily map the underlying 32-bit value of 1 to “<”, I map 2 to “>”, I map 3 to “{“, and so on for the BFF language. Thus, if you have a “>” instruction, and you add 1 to it, you get a “{“. This impacts how the programs might mutate.

But there’s no reason, in principle, to privilege this particular mapping. We could, just as well, have 1 map to “{“, 2 map to “<“, or whatever.

Therefore, my simulation also supports the ability to reconfigure the language, by editing (or even randomizing) the mapping between the underlying data values and the BFF instructions. This impacts both the grid and the BFF interpreter. Changes to the language will come into effect as soon as you advance either of these visualizations. It will update the colors on the grid to reflect the update.

Cell Viewer

If you click on a cell, it will receive a black border, and the details of the cell will appear at the bottom of the grid. The details consist of its location, it’s integer-array representation, and its human-readable-string representation.

From there, you can edit the contents of the cell. Changes to the cell will take effect on the grid.

As that cell reacts with other cells, the cells that it reacts with will receive a thin green border.

Randomizing the pointer start position

When two cells are paired up, their programs are concatenated in sequence. This gives the first cell a big advantage over other cell, because the pointer starts at the beginning of the sequence, executing those instructions first, and it might not even reach the second half. To remedy this, I could introduce a variant which drops the pointer randomly somewhere, and ends when it makes a full rotation.

You can turn on this setting by running this command in the console.

controller.miscSettings.toRandomPivot = true;

I have noticed anecdotally that complex life does not emerge when this setting is switched on.

Super large grids

By using Three.js, I eventually got it working with large grids. Case in Point:

Grid Zooming

The site currently supports larger grids. To facilitate that, you can zoom and pan around. However, for super large grids, the zooming gets quite laggy.

Versions

This project has gone through a few iterations so far.

Version 0: Kivy

My initial mockup of the grid, along with the BFF interpreter visualization, was created in Kivy. Although I thought it was fun to experiment with a new framework, I quickly yearned for the convenience of JS - and the ability to easiliy run the simulation on the web.

Version 1: Vanilla HTML/JS

In the original JS implementation, each cell was made a separate canvas element. Every frame, the application would remove and re-creating all of the canvas objects.

Unspurprisingly, Version 1 was initially very slow.

The first obvious improvement was to not do that. Reuse existing canvas objects, rather than delete and re-create updated versions.

Optimization #2 involved batching of the updates. Previously, the program was drawing each tile every epoch using the fillRect() function. So the speedup was to precompute the updates, and sort them by color. Then, for each of those batches:

• Run ctx.fillStyle = color
• Run ctx.rect(), for each tile
• Run ctx.fill()

That way, the "fill" step happens once per cell (program), not once per tile (instruction).

I did get a really fascinating bug in this version. There was a bug that caused certain programs to become much (ie 10x) longer than they were supposed to be. But this did not break the UI, because the UI was flexible enough to allow for super long programs:

The buggy cells are pretty blurry, becuase there aren't enough pixels to show them fully in this version - still, it looks interesting.

This bug could never occur in later versions, because (due to optimizations), later versions don't allow different cells to be differently-lengthed in the UI.

Version 2: ThreeJS

The speedup in Version 2 wasn't good enough. To enable larger grids, and better usability, I wanted to support zooming and panning. I achieved this with ThreeJS.

The intuitive "first attempt" at using Three JS is:

• Each program / "cell" corresponds to a Three JS "Group". Together, they make up the grid.
• A program contains a list of instructions. Each "instruction" corresponds to an individual Three JS PlaneGeometry square. Together, they make up the sub-grids.

But that wasn't good enough. On a 20x20 grid, with programs 64-long, that's 400x64 individual objects to render, which makes the updates very slow.

The solution? Play with meshes. You can manually assign the vertices and indices in the mesh, and render each cell as a single mesh. It gets a little messy, but it certainly speeds things up. Now you have one object per cell, not one object per instruction.

But that still wasn't good enough. One object per cell is still too many objects, and Three JS can only handle so many objects. The basic mesh optimization worked for my standard 20x20 grids. But as soon as you tried to make super large, 200x200 grids, then zooming froze up significantly.

The solution? Render the entire board as one giant mesh, of course! This was pretty finicky, because now we need to manually calculate the positions and sub-positions of the cells and tiles, respectively.

But that still wasn't good enough. I now got this error: WebGL warning: drawElementsInstanced: Context's max indexCount is 30000000, but 34560000 requested So Three JS has a limit on how big meshes could be? Who knew!

The solution? Divide the number of vertices that you need by the max number of vertices per mesh, then generate that number of meshes. Make all the mesh objects basically the same, except that you "assign" different cells to different meshes, to even out the load. You then create all the cells the same as before, but belonging to different meshes.

That's the version that exists now. Is it good enough? I don't think so. You can make super large grids, but then zooming is super laggy (which annoyingly reverts back to page scrolling behavior). Feel free to test the limits yourself, and make suggestions.

The solution? IDK, but I think it's good enough for now.

Version 3?

A future version 3 could consist of a few things.

• The original paper experiments with several different minimalist programming languages My version only supports BFF, but it would be nice to extend it.
• The original paper creates graphs of complexity over time. I think this would be fun, but it's a tricky feature to shoehorn in.
• I think some sort of "full screen mode" would be cool.
• My performance was faster than I expected, given that the whole simulation, BFF and all, runs client-side with basic JS. But if I wanted to "next-level" my simulation, the next step would be to use GPUs - maybe with WebGPU?

Parting Ideas

Undoubtedly, the code used by the research paper has capabilities that exceed mine. Maybe. I haven't run it, because it was written mostly in Cuda, and I don't want to start up a cloud instance for it. As far as animations, the best display of the emerging life was a youtube video that, while cool, is really zoomed out and hard to understand what's going on.

So that's how I pitch my "petri cells" app. It does most things like 80% as well as the research, but in a much more accessible and Interactive way. Interactivity is something that I value very highly. In some minor way, playing with online Conway's Game of Life sims when I was 12 changed my life and approach to technology. If it was stuck between terminal commands, I would have missed out.

Going forward, I will advocate for something I would like to call Victor-completeness after Bret Victor. It dictates that: All aspects of a program's application state, "complete coverage" of it's memory, as it were, must be:

1. Included as part of the visualization
2. Live (eg: pausable, rewindable, user controls the time).
3. Editable

And Bret Victor might go farther, but I get the feeling he would never be truly satisfied.

Victor-completeness is not easy. Implementing BFF was the least time-intensive part of this entire project. (Now that I've brought that up, if you'd like to add additional languages to this visualization, feel free to contribute. Trust me, it's the easiest part!)

This may be a controversial statement, but I believe the people who currently have the best handle on UX are game designers. But the UX principles in game design need not be relegated to games (as fun as they are).

So my simulation isn't as good as the original, but that's why I like it. Everything is implemented in a way that (should be) simple and easy to understand. My measure of complexity is more basic, but it does a pretty good job. If I had to guess, my implementation of noise is also simpler. But it gets the job done.