Conduits are a central piece of technology in Conway’s Game of Life, especially when engineering new pieces of stable circuitry. A conduit moves an active pattern (like a Herschel or B-heptomino) from one location to another by allowing it to react with a collection of stable catalysts. Along the way, it may release some gliders, produce additional active patterns or perform some other useful interaction, and so new pieces of machinery can be constructed by chaining conduits together.

As one very famous example we have the Fx77 conduit discovered by Dave Buckingham, which moves a Herschel forwards in 77 generations, also flipping it.

Many software tools have been written to search for new conduits: ptbsearch by Paul Callahan, Catalyst by Gabriel Nivasch, catgl by Dave Greene, CatForce by Michael Simkin and LocalForce by Nico Brown, to name a few. Typically these tools are handed an active pattern and a collection of catalysts, and spit out all placements of catalysts that interact with the active pattern and recover. At this point, hundreds of conduits are known, converting to and from various active patterns. But the more the merrier!

I’ve been working on yet another search tool, called Lightcone. Lightcone is pretty speedy: it can find apg’s Spartan G-to-W on this input file in just a couple of seconds. In this post I’ll explain some of the tricks it uses to cut down the search time.

Clicking on the patterns in this post will copy them to the clipboard so you can paste them into Golly. I’m using Chris Rowett’s LifeViewer to display the patterns.

Brute Force and Just-in-time

To search for conduits, an obvious method is brute force: simply test each possible arrangement of catalysts and check whether all the catalysts recover. This is the approach taken by the original version of CatForce by Michael Simkin, hence the name.

Original CatForce does cut down on the search space slightly by first calculating the reaction envelope of the input pattern and making sure that at least one catalyst lies in that envelope. After that, though, all possible placements for the other catalysts are tried (within user-specified bounds). This is the case even if the other catalysts do not interact with the pattern at all! Original CatForce applies most of its filtering after a candidate configuration has already been run all the way through.

For a small number of catalysts, say 1 to 3, this strategy can run to completion in a reasonable amount of time. And if many of the catalysts are expected to be transparent then the brute force approach is not too wasteful, because the configurations have to be run to completion to determine whether these transparent catalysts recover (although testing non-interacting placements is still pointless). One spectacular example is this Herschel-to-MWSS reaction found by Tanner Jacobi.

For searches involving non-transparent catalysts we can do much better. CatForce treats the first catalyst specially to ensure that it will interact with the active region. But we can generalise that idea to every subsequent catalyst placement too. Rather than trying every possible placement, just in case, throughout the search we watch the active pattern evolve and only try catalyst placements that will interact with it in the next generation. It is also easy to track the history of the pattern, and avoid any placement that would have interacted on some earlier generation. This just-in-time placement is used by all the other search tools I am aware of, including my “Symmetric” fork of CatForce.

On its own this is a huge improvement, because the reaction envelope can vary a lot after just a single catalyst placement.

The overall structure of the search is then a depth-first search over catalyst positions. At each node of the search tree, we either place a catalyst which interacts on the current generation, or advance to the next generation.

Contacts and Approaches

The first new idea, which functions independently of the others, is to only try placements where the active pattern is in the right shape for the catalysis to succeed. Consider the ordinary eater:

The vast majority of successful interactions with the head of the eater begin with the birth of exactly those two marked cells, cells that wouldn’t otherwise be born if not for the eater. I have been calling such perturbed cells the contact point of the catalyst. These contact points are easy to calculate in a pre-processing step.

If the initial interaction does not match, it is overwhelmingly likely that the catalyst is going to explode rather than recovering, so knowing the contact points lets us cut down the number of placements to check. Looking at the upper contact cell for the eater, a birth is caused when it gains exactly two active neighbours. When iterating through the reaction envelope, we only need to consider offsets for the eater that put that contact cell next to exactly two active cells.

In addition to checking the contact point, we can look at more of the active pattern. The following (contrived) situation causes the correct births, but is also overwhelmingly likely to not work because the active pattern has the wrong shape.

The required shape of active cells I have been calling the approach. In Lightcone, I check that the approach is correct by extracting a 5x5 “signature” around each possible contact point in the active pattern, and comparing it to the precomputed 5x5 signature around the contact point in the catalyst. (This is a bit faster than dealing with the entire state.) For the eater, the approach looks like:

The cells to the right of the two active ones are unrestricted, there are many possibilities that work. Other catalysts are much more particular about the approach they will successfully interact with.

There is a trade-off to this strategy, of course. We are deliberately excluding unusual interactions that begin in some other way. Each individual unusual interaction has a very small chance of working, but collectively we might be cutting out a lot of interesting results. Checking approaches really does make a huge difference to performance, so the reader will have to decide whether losing out on these serendipitous results is worth it.

Problems and their Lightcones

If a non-transparent catalyst is destroyed, it is unlikely to reform by chance. For this reason, most search tools allow the user to specify required cells of the catalyst, which are not allowed to have their state flipped at any point. For the eater, this might be all the marked cells in the following pattern:

This includes most of the cells in a halo around the catalyst; if a neighbouring cell on the left side is flipped on, the eater is probably in the process of exploding.

If after advancing the overall state we find that one of these required cells has its state flipped, we can drop that branch of the search: it is safe to assume that the catalyst will never recover.

A required cell failing is an example of what I call a problem that may occur with a given configuration. There are a handful of other problems that Lightcone can currently test for, depending on the input parameters:

Any time one of these problems occurs, we can safely drop that branch of the search. A key property of these problems is that they are “monotonic”, in the sense that no placement that interacts on a later generation can possibly cause the problem to be avoided.

Here is the next key idea. Rather than waiting until a problem occurs to react to it, at each node of the search tree we run a lookahead (with no further catalyst placements) to find the next problem that will occur. Once its time and location is known, this is a strong constraint on any possible solution. There must be at least one additional catalyst placement at a time and location that has a chance of averting the problem. That is, there must be at least one catalyst placement that has its contact point within the past lightcone of the problem, and so we can save time by restricting our attention to finding this catalyst placement first.

For example, consider the following interaction, with the required cells of the eater marked. After 36 generations we encounter a problem: one of the required cells of the eater has flipped.

Now we rewind back to generation 29, the moment we interacted with the first eater. To have a chance at solving the problem, the next placement must be in the following box.

This doesn’t help much right now, but as we advance in time this box gets more and more restrictive. After 2 more generations, we are down to the following region and no longer have to test any placements that interact with the left part of the active pattern; they are too far away to solve the problem.

In fact, this is the generation that contains the unique solution to the problem. The following placement is barely close enough to have an impact: the difference in the evolution of the pattern travels at near lightspeed to reach the problem in time.

In general, after solving one problem there is a good chance we create or expose a new problem that needs solving. In the following situation the second eater saves the first one, and is in turn saved by the third one.

This search strategy can cause placements to be tested non-chronologically, because after solving a problem that occurs in one part of the state, we may free ourselves to go back and interact with some other part of the state. This non-chronological placement appears to be fairly rare in practice.

The eater is placed in order to save the lower block, but once that is done, Lightcone is able to rewind and place the upper block.

So much for the past lightcone of a problem. There is another place where we can use lightspeed considerations to our advantage. As it stands, after we place a catalyst, we begin anew and test all locations within the envelope of the active pattern for whether they are suitable for a catalyst placement. But we don’t need to throw away all the work we’ve already done: the new active reaction can only be different from the previous one within the future lightcone of the placement we just made. Outside that lightcone, the determinations we made for whether a placement is valid can be reused.

Bloom Filter

Some catalysts interact in similar ways and can cause the same perturbation of an active pattern. The eater 1 and eater 2 are notorious examples.

Unless this duplication is somehow dealt with, it can cause a combinatorial explosion in the search where all combinations of eater 1s and eater 2s are tried, even if they lead to the same perturbation.

Here I follow Adam P. Goucher’s (unimplemented) idea for Silk to use a Bloom filter to quickly test whether the reaction has been seen previously. A Bloom filter lets us store the hashes of many millions of states using relatively little memory. The trade-off is a small risk of false positives, once too many hashes have been added to the filter. Again following a suggestion by apg, the filter is reset to empty once the chance of false positives reaches an intolerable level.

The criteria for when the active pattern is tested against the Bloom filter were arrived at through trial and error. Right now, the pattern is tested and added to the filter when

Of course, there is another balance to be struck here. We want to catch as many repeated reactions as possible, but not accidentally consider some dying sparks as a repeated reaction if they were actually arrived at by different means.

Future Ideas

Lightcone is certainly not the last word in conduit searching. It’s much smarter than a brute force search, but still makes choices that are obviously silly to the human eye. I’d love to hear ideas on any of the following topics:

Catalyst Welding

Lightcone only tries placing complete catalysts, and excludes any placement that will cause two catalysts to interact. This inevitably misses some solutions that involve non-trivial welds to pack catalysts slightly closer together than otherwise possible. One unsatisfying solution is for the user to provide pre-welded catalyst pairs as input, but in an ideal world Lightcone would do this systematically and automatically.

This will likely mean testing all interacting offsets of one catalyst against another, and testing whether a weld is possible. Presumably a SAT solver could make short work of this.

In a branch, I’ve had a go at implementing this, but the performance hit is unreasonably high (at least with the method I’m using currently).

Avoiding Hopeless Placements

Currently, some time is spent on placements where the recovery sequence of one catalyst leads to a cascade of interactions with additional catalysts. For example, the following completely hopeless chain of block reactions which takes 8 generations to finally fail:

It would be nice if these could be avoided without hardcoding those nearby block placements to be forbidden. It’s unclear to me what the correct heuristic is here. We have to be careful: not all tightly packed catalysts are useless. The similarly close eater in the following example is necessary for the block to survive.

Lightcone always tackles the chronologically earliest problem that occurs with the current configuration. In some situations this leads to poor performance, especially when the active region splits into two separated pieces.

A problem in the left region may be solved, revealing a problem in the right region, and vice versa. This alternation causes a combinatorial blowup in the time it takes to make progress on either side. In theory it should be possible to choose which problem to focus on more intelligently, but doing so naively causes even bigger issues: Lightcone might go down a rabbithole solving problems on the left, when it’s easy to show that the problem on the right is unsolvable.

This may be an opportunity for some parallelism: if there are multiple problems that are lightcone separated, we could attempt to resolve them in different threads.

Results

Finally, the fruits of our labour.

Sep 13rd, 2024: Lx65 duplicator

Oct 10th, 2024: Many H-to-Gs, one chosen at random shown here:

Nov 5th, 2024: Many more H-to-Gs, one chosen at random shown here:

Feb 11th, 2025: HF78B

Feb 20th, 2025: HLx86B