Simulating Rule 110 in Opus Magnum

In my previous posts about the 2022 Opus Magnum tournament, I mostly left out the final puzzle. It deserves a post of its own. The puzzle concept shares ideas with the “making a computer” puzzle, so many readers will benefit from starting there. This time, we simulated Rule 110, an abstract cellular automaton famous for images like the one below. This post will talk about how Rule 110 works, and what the Opus Magnum community did to simulate it in the game.

Cellular automata

I’ve talked about Conway’s Game of Life before, so the idea of cellular automata should be familiar. A universe on a grid, with rules for how a cell can update, depending on the cells around it. Where Conway’s Game of Life is arguably the most famous cellular automaton in two dimensions, Rule 110 takes place in only one dimension.

So how can Rule 110 generate the decidedly-two-dimensional image above? Well, this image is a “spacetime diagram” for Rule 110. A single row of pixels, from left to right, is the universe. Each slice corresponds to a different time. By reading top to bottom, you examine the evolution of the pattern over time. For the spacetime diagram here, the initial configuration has a single cell on (white), and everything else off (black). The rule is responsible for determining what happens next, and Rule 110 ends up evolving into a quite lively and chaotic collection of on cells, in the left half of the universe only.

Rule 110’s actual rules

Because the universe has only one dimension, each cell has two neighbors. The logic for what happens to any given cell, depends on 3 bits of information: Is the left neighbor on or off? Is the right neighbor on or off? Was the given cell initially on or off? For each of the 2³ = 8 ways these 3 bits can be assigned, the rule needs to provide an answer.

The diagram here outlines the 8 choices that comprise Rule 110. The choices may seem arbitrary, and that’s because they are! Rule 110 is named because it is one of 256 rules, which cover every possible way to assign the 8 outcomes. 2⁸ = 256 is not an enormous “rule space”, so when devising this system, Stephen Wolfram just made all of them and figured out afterward which ones were interesting.

Specifically, this is called Rule 110 because of what happens when you read the 8 result bits in binary. The 8 choices are organized from left to right according to the binary number encoded by the 3 bits (left, center right). The outcome of the choices, by this left-right ordering, is 01101110. If you turn that binary number into decimal, it is 64 + 32 + 8 + 4 + 2 = 110.

What makes Rule 110 interesting?

Let’s try to digest the rules above. On the far right, we see the rule that keeps “off” regions “off”. This is useful, because it helps all the activity stay nearby to where it started.

To its left, we see the rules for 010 and 001. Both of these lead to an on cell, which is how the single on cell grows both down and diagonally down-left. By contrast the 100 rule leads to an off cell, which prevents any activity from growing diagonally down-right.

The leftmost rule says that 111 turns the next generation off. This is exactly why there are big empty triangles in the spacetime diagram. Any time you have a bunch of cells on, all next to one another, every one in the middle dies. The void that is formed gets filled from the right using another diagonally-down-left-growing triangle, where its left edge cannot grow for the same reason.

Gliders and computation

When run on random initial conditions, this rule exhibits “class 4” behavior. Stephen Wolfram classified all 256 automata based on structure and complexity. Class 4 is the most advanced case, where there is some degree of structure, but also enough chaos to allow structures to interact with each other in diverse ways. One of the key features of a class 4 automaton is gliders.

In the image above, we can see a few different kinds of repeating structure. There are small regularly tiled triangles which make up a sort of “background”. Ripples in that background can propagate left or right, and at different slopes (equivalently, speeds). There are also static poles of triangles which can exist with background on both sides. All of these repeating, traveling structures are referred to collectively as gliders.

There are at least 13 fundamental gliders in Rule 110, and the interactions between them have been proven sufficient for Turing Completeness, equivalently, universal computation. I won’t try to go into the exact proof, it relies on an implementation known as a “cyclic tag system”, and an infinite starting condition. But, with the appropriate interpretation of what various signals mean, it’s possible to use Rule 110’s evolution to carry out arbitrarily complex computation.

So that’s neat.

Reducing Infinity

The post is about Simulating Rule 110 in Opus Magnum. But simulating an infinite number of cells becoming an different infinite set of cells, is infeasible. Of course, a theoretically pure version of Opus Magnum does have infinite space. But it doesn’t permit infinitely large inputs. Every solution only places finitely many instructions and parts. Accordingly, simulating a true Rule 110 generation is impossible.

One of the classic ways to pretend something is infinite, is to loop it back on itself.

Instead of simulating an infinite initial condition, we could simulate a loop of finitely many initial cells. Because it’s a loop, every cell does have a left and a right neighbor. But, the amount of complexity available on a loop is much smaller. If you shrink the loop all the way down to 6 cells, you lose basically all of the structures. It cannot be said that the finite loop version of Rule 110 is Turing Complete. What can be said, is that the finite loop version of Rule 110 is a nice computation puzzle.

2022 Opus Magnum tournament

After 8 weeks of ordinary puzzles, Bist wanted week 9 to be a computation puzzle. This would keep up the trend set by the 3 tournaments prior. Certain features also borrowed from prior tournaments:

• 2020: the scoring for the computation puzzle is one metric worth 10 possible points, with an extra 10 point bonus for completing it at all
• Spacechem 2020: the computation puzzle is Rule 110 in a loop
• 2021: the scored metric is cost/5 + cycles + area
• 2021: the computation puzzle uses fire and salt to represent 1 and 0

Scoring design

In 2019, there were 4 possible metrics for submissions, and people could submit to any two. This had pros and cons. It did separate the field into mains, which allowed the various mains to always demonstrate proficiency on every puzzle. But this separation also allowed people to not compete with each other. I was less contested as a cycles and sum main, while PentaPig, jinyou, and Shadowcluster competed for cost and area, leading to an easier path for me to win. Additionally, for the computation puzzle in particular, needing two submissions overworked people who wanted two top tier entries.

So in 2020 I changed it. The last puzzle gets just a single submission. Because the computation puzzle was so unusual, players would earn a chunk of points for completing it at all. A perfect week would still be 20 points, but it would be 10 from bonus and 10 from scoring the one submission. This did have the secondary effect of reducing the amount of gain/loss you could achieve on competitors. However, brookieoz kept this system when running the tournament in 2021, and the scoring didn’t stop me from making an epic comeback. So, Bist kept this system. We would be submitting just one scoring solution.

Spacechem Rule 110

Spacechem is a much older Zachtronics game from 2011. It has seen annual competitions similar to the Opus Magnum tournaments, and I’ve participated in two of them. In 2020, RP0 and 12345ieee designed the Spacechem task of implementing Rule 110 on loops of atoms. Neodymium ones and Zinc zeros, elements 60 and 30 to enable clean nuclear fission/fusion.

Spacechem does have some features in common with Opus Magnum, but it also has a lot more support for conditional behavior, and allows you to directly sense an atom. Recognizing this, Bist determined that a puzzle based on Rule 110 would still be new territory for the 2022 Opus Magnum tournament. I did feel like I had a slight advantage, as I was one of the couple dozen people to have completed a solution for Spacechem’s Rule 110. But I got 8th back then, so perhaps I wasn’t even the most advantaged of the group.

2021 features

Explosive Logic Unit, the famed subtraction computer where I won by a landslide, was brookieoz’s gift to the world in 2021. I think it had a lot of really good decisions in puzzle design, and I also benefitted from an understanding of state machines in making a good solution. Bist evidently agreed, because she modeled most of the detail of the Rule 110 puzzle directly from it.

Fire would be 1, salt would be 0. The puzzle would have as input, a ring of 6 fire-or-salt atoms around a central gold. The output would be the evolution of that ring by one generation in Rule 110. Fire makes the most sense for a 1, because the triplex bonder directly detects fire, a feature which led to the simplest algorithms for Explosive Logic Unit.

The single scored metric was also a copy of Explosive Logic Unit: cost/5 + cycles + area. Typically a sum metric is cost + cycles + area without any factors. But typical sum solutions end up sacrificing speed to be cheap. By weighting cost so much lower, the solutions should be fast, while still being conscious of the other metrics.

Transmutation CX

And so, Transmutation CX was born. Bist’s final puzzle for the 2022 Opus Magnum tournament went up onto the website on March 11th, with solutions due at the end of April 1st. We had 3 weeks to build a solution which would take any 6-atom ring, and advance it properly.

The name was chosen because CX is the Roman numeral expression for 110. Whether the in-game alchemy traces back to Roman origin, I don’t claim to know.

Included on the website was a breakdown of what the Rule meant, and extra requirements. The solution had to treat each input separately, meaning it couldn’t just store the info from the first output and copy it 6 times. It also couldn’t use output conditionals, meaning we could only drop something on the output if we knew it was correct. And finally, submissions would be checked against all 64 test cases using a validation tool built by panic. One solution file, many solutions, the computation puzzle paradigm we had come to know and love.

Let’s get started.

My Approach

Having succeeded in 2021 using a state-machine approach, I started by looking at Rule 110 as a state machine. The biggest way that a state machine can help here, is that it prevents needing to re-read as many bits. Naively, this puzzle wants you to read 3 bits, 6 times, for a total of 18 reads. I was immediately thinking of a concept where a machine reads only 8 times – twice to set state, and then 6 more times, each one updating state while writing.

Specifically, the last two bits you read, combined with the one bit you read next, total 3 bits. You can write whatever is appropriate for those 3 bits. Afterward, you still have enough information to know your new “last two bits” without re-reading them. You just have to encode that in the state.

This gives rise to a 4-state transition table that has absolutely nothing to do with Rule 110, and is just the diagram for “your state is the last 2 things you read.”

Each of the 8 arrows relates to a different combination of 3 bits within the input. Rule 110 comes into play when you make those arrows write something.

Writes

Just like in the other state machines, we need to have an associated write with some (or all) of our arrows. So to implement rule 110, we need every arrow to actually do two things. Write, and then continue without reading. Naively, this adds 8 states to our diagram. For completeness, I’ll draw the entire thing.

Now, we can combine any pair of states that write the same value and then continue to the same state. This includes several write states, but also more subtly, states 00 and 10. Both of them have the exact same destination for both 1 and 0 reads. After combining everything that can be combined, we have this:

As far as I could tell, this is the simplest state machine for Rule 110. 3 states that read, 5 states that write. My ideal algorithm would read 8 times, using the first two reads to get into the correct state, and the next 6 for their writes. The last 2 bits read would be the same as the first two bits, taking advantage of the loop. This would work regardless of the input order.

Implementation

In these state machines, I expect to always have some fixed object within the solution, that gets moved around by possible triplex bonds. Beyond that though, it’s really a matter of trial and error. I tried making the 1 reads the most important, but then I got thwarted by the 11 → x0 transition. I tried to make that transition important but had to add complexity for the other 1 reads. My initial goal of a 3 cycle repeat time per read, fell apart quickly.

I was confident that the stateful object would be stick-like, and that the first move could not be parallel to the stick. I tried a few different arrangements and targeted a 4 cycle loop per read. Eventually, I ended up with this:

The x0 state was the leftmost position of the stick. The 01 the center, and the 11 the right. One bit could be read every 4 cycles, for 32 cycles to process an entire input. The transition from 11 to x0 was done across two bond-shifts by arm 2, included in the video. Arms 2, 3 and 4 all had tasks to make sure that the stick made it to the right place within the cycle budget. It worked, well enough. I never found something better, at least.

Writing

This construction made sure the 3 read states mapped to each other correctly, but it left the writing as an unsolved problem. I found a way though, using the following logic statement:

“Write a 1 if and only if you started in the 01 state, ended in the 01 state, or took the 11 → x0 transition”. This seems like it might be a complicated condition to measure, but it actually depends on just a single position in the machine.

The duplication comes from the stick, onto a salt atom, so all of the “or”s in the statement above come naturally. On cycle 0 it can measure whether we start in the 01 state. On cycle 2 and 3, the 11 → x0 transition uniquely sits in that location. And on cycle 4, it measures whether we end in the 01 state.

But there’s a little catch here, because only one output atom can be the target of duplication. Cycle 0 and cycle 4 are the same cycle for different atoms. I found a way to keep going at this speed using an extra duplication glyph, now from one partly-finished output atom onto another. Cycles 0 and 2 read directly from the stick, and what would be cycle 4 actually reads from the neighboring atom (which has only read cycle 0). On the last atom of each output, it reads on cycle 4 directly.

My machine

With a few iterations between first solution (weighted sum 477) and final, I ended up making the following. It has weighted sum 387, coming from 435/5 + 208 + 92.

This looks remarkably similar to the ELU winning solve. Not in overall shape, where that one was very much “haha it is a gun”, but in method. It builds a thing, checks it against individual atoms 8 times, uses duplication to build the output, and repeats 6 times. Afterward it tears down the state register and starts over.

It’s slower and cheaper than the ELU solve, which leads to a higher weighted sum. I had achieved 365 in 2021. But I couldn’t see a way to implement my state machine in a tighter loop, so I figured I would just get as low as I could at this speed. Hopefully the story would be similar to 2021 when I had such a tremendous margin of victory, with top 3 scoring 365, 452, and 497. Even being under 400 felt like I must have a good solution. A possible winner?

I named this solution “Another nosedive :^)” in hopes that it would be in 1st, quite far ahead of 2nd.

Mod support

As an aside, the community has become better and better equipped to build mods for the game. During the 2022 tournament, mr_puzzel was working on a computation mod. This would load a random sequence of inputs for a given puzzle according to defined constraints, and update the output accordingly. He built a computation mod version of Transmutation CX within a few days of it releasing. Here is a video in-game of my solution running on the computation mod at high speed. Notice that this exercises far more of the different branches of execution than any individual instance of the puzzle.

In addition, player “notgreat” quickly built out an online tool that validated against changing inputs, with more accurate simulation than panic’s on-site validator. It was very barebones. The user needed to know exactly how to use it, and it reported in ascii. But this also helped as a resource for many of the players.

Art tool

At the final hour, panic released an “art tool” version of the on-site validator. This is something he did during the 2021 tournament as well. I think there is some worry that the artwork will say too much about implementation, hence leaving it to the final hour. But people could now use their solutions to generate artwork on an 8 by 8 grid.

Each pixel of the image comes from one possible input/output combination. The pixel is colored white, if every glyph and arm is necessary for that input/output combination. Any other color besides white, means that some part of your solution could be removed and still produce the correct output. The exact color depends on a random internal assignment of hues to parts.

There’s nothing really to say about efficiency based on amount of white. These are just a fantastic way of building hype before the reveal. Get everyone in the same chat to start guessing about implementations based on patterns and symmetry. Show off the prettiest images, before we can validly show off the solutions they come from. I really like this tradition.

Revealing everyone’s solutions

On the evening of April 1st, the tournament officially ended. All that remained was to livestream the results for Transmutation CX.

We had a little bit of a teaser – Bist teased that 500+ was a “bad” score, shortly before the deadline. We took it with a grain of salt given the date. It would be reasonable to ignore it completely, only 3 people got under 500 last year on Explosive Logic Unit.

Obviously “bad” is not the right word, everyone’s solutions are the culmination of significant effort by expert players. The tradition dates back to Spacechem tournament organizers, who love to make people squirm by revealing hints about the scores at the top. With the reveal underway, we got to understand what this teaser actually meant. Scores were definitely lower than last year. I wasn’t ready for how much more competitive the computation puzzle landscape would be!

We started in 38th place with a solution someone had thrown together in the last minute, and even that had a weighted sum under 1500. By the time we revealed 31st place, which was a new competitor who went by Joel, the weighted sum was down to 582. By contrast, 580 had gotten Rolamni 7th place in 2021.

I want to highlight a few very different designs. These gifs will show just one input going through to output, and avoid any setup/teardown work that the machine does outside of its work loop. If you want more detail about any of these or any other solution, the livestream is the best source of content.

Goodbye Galaxy + geco

Both Goodbye Galaxy and geco came up with an approach that built molecules of unknown shape. The prongs jutting out from the crystal help determine whether to move it over various calcifiers to do the computational logic. I’ve shown geco’s below, as it is a little easier to follow. At 519 weighted sum, it was a little too slow, but definitely beautiful.

Buttermilk Doughnut

This solution made a significant sized brick out of unknown atoms, processed the brick in parallel, and managed to use it to get nice throughput! This was the first solution under 200 cycles that we saw in the results stream. Unfortunately its expense left it at 505 weighted sum.

Guilty Bystander + jinyou

There’s something immensely satisfying about an endlessly circling ring of arms holding atoms. This was a feature of both Guilty Bystander’s and jinyou’s solutions. I’ve shown Guilty Bystander’s below, which scored 503 weighted sum.

Morraconda

This solution processed an output every 25 cycles It used 4 cycles for each trio of bit reads. It was expensive, since it was logic-gate-centric without a state machine. I thought this might be close to the fastest serious submission we would see in this results stream.

But then..

notgreat + Rolamni + Shadowcluster

On the final day, with 7 hours to go until the deadline, notgreat sent a powerful discord message.

This resembles something that I had said about my Explosive Logic Unit solve in 2021. However, I had never felt that kind of confidence during Transmutation CX. It remained to be seen whether this was truly a stroke of genius, or just a dud. But the reason this gets a spot in the blog, is because it genuinely was a good strategy.

notgreat did not win (5th), but their solve was better than mine (7th). The main thing holding them back, was that they discovered their strategy so late. The implementation was not so refined on cost and area. But wow was it fast, with one output per 16 cycles during the loop. Here is their 123 cycle, 380 weighted sum solution:

How does this work? To answer this, we need to talk about windowed counting.

Windowed counting

As before, we conceptually unwind the six atom loop into a string of 8 ones and zeros. The first two are repeated again at the end to allow all six 3-atom substrings. The windowed counting approach processes this string as shown in the diagram below:.

The windows in this diagram are the orange and blue brackets. Orange brackets contain 3 bits of input, blue brackets contain only 2. Each window has a yes/no question. Without caring about the order, we ask about the total number of ones in the window. We align the answers in pairs, and if either one of the paired answers is yes, that bit is a 1 in the output. Otherwise it is a 0.

You can check the 8 different rules comprising Rule 110, and see that yes this is a perfect match. Now let’s talk about why it is so efficient to implement this in Opus Magnum.

Speed

You need to measure 12 things per input, to pull off this algorithm. However, once you have established the first one, the next 11 measurements can happen one cycle apart. This is because the windows differ by exactly one atom. If you have a counting stick, whose position left to right represents the number of 1s in the current window, here is how you update it:

When moving from a blue window to an orange window, you try to triplex bond the new atom and shift right. If it was fire, the stick shifted right (one more 1 in the orange window than there was in the blue window). If it was salt, it didn’t shift (same number of 1s in the orange window as the blue window). Conversely, when moving from an orange window to a blue window, you try to triplex bond the atom being removed, and shift left. If it was fire, the stick shifted left (one fewer 1 in the blue window than was in the orange window). And salt once again means no change.

Every atom gets read twice (which is how I missed this), and the entire input can be processed in under 20 cycles. In notgreat’s implementation, it takes 16 for each input.

I did mention Rolamni and Shadowcluster as well. I’ll say that Rolamni got 3rd, with a weighted sum of 364. He beat my 365 from 2021 by the slimmest of margins. His solution is shown below, also using this windowed counting algorithm. I’ll leave Shadowcluster for later though.

Brookieoz + noeuchar + ebonnov

Officially, the winning algorithm was still a state machine like my own. There were very clean implementations of it, with smaller register structures and cheaper handling. Shown below are ebonnov’s 4th place solution (378), noeuchar’s 2nd place solution (362) and brookieoz’s winning solution (361).

The cycle counts of these solutions and my solution are all in the very low 200s, as they all have a 4 cycle loop per atom processed. ebonnov has a clever way of reading only 7 bits from the input instead of 8, so his is slightly faster. But between the two top finishers, the solutions scored nearly identically. 5 gold, one cycle, one area, one overall metric point separated them.

Now it’s time to look at Shadowcluster’s solution.

Global Optimum Strategy

It turns out, notgreat was correct. At least as far as we know today. The best solution for Transmutation CX was built by Shadowcluster, who was advising on puzzle design and therefore not a participating tournament member. According to Shadowcluster, he built this entirely without looking at any of the submissions. He too discovered the windowed counting approach, with more time than notgreat and with more investment in the outcome than Rolamni.

As a result, he was able to put together a solution with weighted sum 338. A total blowout.

It’s a bit slower than notgreat’s, taking 18 cycles for each output. But it uses circulating loops of atoms to carry the left-moving and right-moving information without needing to dispose anything except the input, which tightens up the layout a lot.

The windowed counting approach is amazing here. I missed it because I assumed I would only want to read once. But with two different unknown atoms moving the stick, it actually remains in better control than would be possible with only one. Shadowcluster’s solution doesn’t have any arms touching the stick after it has been built. The stick is always in the right place from the unknowns alone. I’m very glad Shadowcluster made this solution and reminded us all he is a brilliant player even outside of his area-optimizer domain.

For fun

Almost every solution above is 6T. From the instructions post, 6T is defined as a solution whose instructions complete 6 outputs. I used F10 to trim out a loop, but the actual programming of these solutions is extremely instructions-heavy. Each has over 1000 instructions, and in Morraconda’s case a whopping 3647.

Three of the submissions shown in this post are not 6T. Geco’s crystalline solution, Buttermilk Doughnut’s sticks, and ebonnov’s state machine are 1T – they loop after each output. The lowest instruction count is geco at 205.

Now it would definitely be possible to build a solution to this puzzle in less than 1T. After my wins in the two trackless-instructions metrics, I thought about making a fun solution to Transmutation CX that tried to optimize for TI. 1/6T makes some sense, each tape loop computing one atom of the output.

But no, I was hard set on an idea that needed to be 1/9T to work. And I did make it work! I present, a 57 instruction trackless solution to Transmutation CX:

You did what now?

I built this solution based on a second algorithm that seemed very useful (and in fact, was used by many competitors). The rule table for Rule 110 looks an awful lot like an OR gate between the rightmost pair of bits. The only difference is in the 111 transition where an OR would write a 1, but Rule 110 writes a 0.

So, the algorithm here takes the OR of adjacent bits, while keeping track of runs of three 1 reads in a row. Whenever it finds one, the piston at the top will shove a salt, replacing the bit that would otherwise go to the queue.

The queue is a hex arm (length 2, close to center) that could deliver atoms to either of two bonders. First three end up sticking back to the input. But after that, we finally reach the condition to extract gold, and so the next 6 stick to the gold. Eventually this makes an output.

It’s carefully balanced so that the inputs are read 8 times each. The 9th time coincides with when the 3rd atom gets stuck to it and it bonds to gold. On that time only, the gold atom actually blocks the input for a single cycle. When the arm goes to grab at the input, it gets nothing, which later steps treat the same as a salt. This allows the run-of-three-1s counter to reset.

The TI solution is not nearly as cursed or forward-first as prior weeks. It’s more of a proof of concept of a specific 1/9T idea, but I am glad I made it. With a 7th place finish in the puzzle’s true standings I didn’t have that exciting of a final showing otherwise.

Summary

In all, this year’s computation puzzle was a much closer battle, and close battles do a lot less to shake up the standings. As long as PentaPig, Rolamni and I all submitted and were near each other in score, nothing could change the top 3. Rolamni was the only one of the three of us to find the windowed counting idea, and finished the best among us for it, but the margin was still too large to overcome.

What could be the reason for such a change from last year? Perhaps the novelty of computation has worn off, or maybe prior art gave too many hints. People were more able to visualize an approach scoring in the 500 range, because of what did well in 2021. It may be time for a new computing paradigm, to bring back the wide spread. Perhaps it’s time to explore changing the computation metric to TI. A man can dream.

With the increasing mod support, I would not be surprised if 2023 tournament has a computation puzzle which involves a completely new way of playing the game. I look forward to what this community has in store!