Some notes on how it works:
Brute Force and Just-in-time
To search for conduits, an obvious method is to 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 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 catalyst placements is still pointless). One spectacular example is this Herschel-to-MWSS partial found by Tanner Jacobi.
Code:
Select all
x = 32, y = 32, rule = LifeHistory
20.B3D2B$19.BD2BDB$20.3BD2B$19.D3BDB$20.3BD2B$19.BDBD2B$20.6B$19.6B$
20.6B$19.6B$20.6B$12.B6.6B$11.3B6.6B$9.6B4.7B$3.4B2.7B3.8B$.27B$B2A
26B$3AB2A21BD2B$B2AB3AB2E16BDBD2B$3AB2A2B2E16BDBD2B$2A25BD4B$5.26B$7.
B2.20B$10.19B$10.17B$10.18B$11.5B.11B$11.4B2.12B$18.4B.2BE3B$23.BEBE
2B$24.2E2B$26.B!
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 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.
Code:
Select all
x = 62, y = 46, rule = LifeHistory
50.B$45.7B$45.8B$45.9B$45.10B$45.9B$46.8B$43.11B$43.12B3D$42.13BDBD$
41.14BDBDB$40.2B3D11BD2B$40.10B2D7B$39.BD5BDB2D2BD7B$38.2BD5B2DBDBD8B
$38.2BD5BD3BD10B$38.24B$39.2B.3D16B$43.B.3BD10B$46.2BD9B$46.2BD8B$38.
C7.11B$38.3C5.11B$41.C4.12B$12.4B24.2C3.B.11B$11.2D5B22.18B$11.2D5B2D
22.17B$12.6B2D22.13BD4B$11.9B21.14BD5B$9.5BD5B19.16BD4B$7.7BD5B17.23B
$7.2BA4BD3B.B2C15.2BA19B$6.3BABA4B3.BC.C13.3BABA7BD8B$7.2B3A4B6.C14.
2B3A7BD7B$6.5BA4B6.2C12.5BA7BD7B$5.10B20.10B2.8B$4.4B26.4B10.7B$3.4B
26.4B12.6B$2.4B26.4B12.7B$.4B26.4B14.6B$4B26.4B14.6B$3B26.4B15.7B$2B
26.4B16.6B$B26.4B18.4B$26.4B19.4B$25.4B21.2B!
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. Let us consider the ordinary eater.
Code:
Select all
x = 39, y = 7, rule = LifeHistory
5.A9.2A8.A10.A$5.A.A7.2A8.A9.A.A$4.D2A7.D2A7.DA8.DA2.A$2.2CD7.2CD7.2C
D7.2CD.2A$.C.C7.C.C7.C.C7.C.C$.C9.C9.C9.C$2C8.2C8.2C8.2C!
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, and so knowing the contact points let 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.
Beyond just checking the contact point, we can look at more of the active pattern. The following (contrived) situation has the correct neighbour counts, but is also overwhelmingly likely to not work because the active pattern has the wrong shape.
Code:
Select all
x = 6, y = 6, rule = LifeHistory
3A.A$4.DA$2.2CD$.C.C$.C$2C!
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:
Code:
Select all
x = 6, y = 6, rule = LifeHistory
2.3DA$2.3DA$2.2C2D$.CDC2D$.C4D$2C!
The cells to the right of those two active ones are unrestricted: there are many possibilities that work. Other catalysts are much more particular about the approach they will interact with.
Code:
Select all
x = 14, y = 11, rule = LifeHistory
3.2A$3.A5.DC2D$2A.A5.2D3C$A.2A.2A2.5D$5.A.A.DA3D$5.A.4A3D$6.A6.A$7.A
2.4A$6.2A2.A$11.A$10.2A!
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 is not likely to work, 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:
Code:
Select all
x = 5, y = 6, rule = LifeHistory
2.2D$.2DCA$.DCDC$2DC2D$D2CD$4D!
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:
- Required cells failing, as above.
- A filter for a particular state failing. For example, you may want to make sure that a glider escapes from a reaction.
- A catalyst failing to recover within a specified time.
- An overall time limit being reached without all catalysts recovered.
- An overall time limit being reached without any catalysts interacting at all
- A catalyst marked "transparent" not actually acting transparently. This is most common with blocks, and is intended to avoid "boring" results.
- A piece of junk surviving for too long.
Any time one of these problems occurs, we can safely drop that branch of the search: there is no way for a problem of one of these kinds to be solvable at any point further into the future.
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 can 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 points within the past lightcone of the problem, and so we can save time by trying to find 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.
Code:
Select all
x = 46, y = 13, rule = LifeHistory
33.4B$32.A6B$32.2A6B$33.7B$32.10B$30.12B$28.12B2A$A27.12BA2B$A.A8.ACD
13.10B4.A2D$3A7.DC4D12.9B3.DC4D$2.A7.2D3CD11.BA8B3.2D3CD$11.3DCD10.2A
8B5.3DCD$13.3D11.2A14.3D!
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.
Code:
Select all
x = 23, y = 15, rule = LifeHistory
8.D2C12D$6.2AD3C11D$6.2A3D2C10D$5.3BCDC2DC9D$3.5B3C2D2C8D$.7BCDCD2C9D
$.7B4D3C8D$2BA5B6D2C7D$.A6B6DC8D$.3A4B7D3C5D$2.6B9DC5D$8.15D$8.15D$8.
15D$8.15D!
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.
Code:
Select all
x = 21, y = 13, rule = LifeHistory
7.4AB$6.2AB4A$6.AB2AD2C8D$5.3BABDCD2C6D$3.4B2AB2CD2C6D$.6B2ABC10D$.9B
DC9D$10B4D2C5D$.A8B4DC6D$.ABA6B5D3C3D$.2A6B.7DC3D$10.11D$10.11D!
In fact, this is the generation than contains the unique solution to this problem that uses another eater. The following placement is just 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.
Code:
Select all
x = 21, y = 14, rule = LifeHistory
18.2A$7.4AB6.A$6.2AB4A3.A.A$6.AB2AD2C2D3C3D$5.3BABDCD3C5D$3.4B2AB2CD
2C6D$.6B2ABC10D$.9BDC9D$10B4D2C5D$.A8B4DC6D$.ABA6B5D3C3D$.2A6B.7DC3D$
10.11D$10.11D!
In general, after solving the one problem there is a good chance we expose a new problem that needs solving. In the following situation, the second eater saves the first one, and in turn in saved by the third one.
Code:
Select all
x = 24, y = 22, rule = LifeHistory
7.2A$8.A$8.A.A11.2A$9.2A11.A$20.A.A$20.2A9$A$A.A$3A$2.A$14.2A$14.A$
15.3A$17.A!
This search strategy can cause placements to be tested
non-chronologically, because after solving a problem that occurs 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.
Code:
Select all
x = 21, y = 21, rule = LifeHistory
12.4D$12.D2CD$13.2A8$A$A.A$3A$2.A2$12.2A3.2D$11.D2CD.AC2D$11.4D.CDCD$
16.2DC2D$17.D2CD$17.4D!
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 that we can use lightspeed considerations to our advantage. As it stands, after we place a catalyst, we begin anew and test all locations in 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
For some perturbations, there are often multiple catalysts that can cause the same perturbation. The eater 1 and eater 2 are notorious examples.
Code:
Select all
x = 37, y = 10, rule = LifeHistory
5.A9.2A8.A9.2A$5.A.A7.2A8.A.A7.2A$5.2A8.2A8.2A8.2A$2.2C8.2C6.C.2C6.C.
2C$.C.C7.C.C4.3C.2C4.3C.2C$.C9.C5.C9.C$2C8.2C6.3C.2C4.3C.2C$20.C.C7.C
.C$20.C.C7.C.C$21.C9.C!
Unless this duplication is somehow dealt with, it can cause a combinatorial explosion in the search tree where all combinations of eater 1s and eater 2s are tried even if they lead to the same perturbation.
Code:
Select all
x = 83, y = 39, rule = LifeHistory
46.C19.C$45.C.C17.C.C$45.C.C17.C.C$C19.C22.3C.2C14.3C.2C$3C9.C7.3C9.C
9.C14.C4.C14.C$3.C6.3C10.C6.3C10.3C.2C6.3C5.3C.2C6.3C$2.2C5.C12.2C5.C
15.C.2C5.C10.C.2C5.C$9.2C18.2C23.2C18.2C5$.A8.2C9.A8.2C.C12.A8.2C9.A
8.2C.C$.A.A6.C.C8.A.A6.2C.3C10.A.A6.C.C8.A.A6.2C.3C$.3A8.C8.3A12.C9.
3A8.C8.3A12.C$3.A8.2C9.A6.2C.3C12.A8.2C9.A6.2C.3C$31.C.C42.C.C$31.C.C
42.C.C$32.C44.C2$46.C20.C$11.C20.C12.C.C8.C9.C.C8.C$10.C.C18.C.C11.C.
C7.C.C8.C.C7.C.C$C9.C.C8.C9.C.C9.3C.2C6.C.C6.3C.2C6.C.C$3C6.2C.3C6.3C
6.2C.3C6.C11.2C.3C3.C11.2C.3C$3.C11.C8.C11.C6.3C.2C11.C3.3C.2C11.C$2.
2C5.2C.3C8.2C5.2C.3C9.C.2C5.2C.3C6.C.2C5.2C.3C$9.2C.C17.2C.C20.2C.C
17.2C.C5$.A8.2C10.A8.2C.C11.A8.2C10.A8.2C.C$.A.A6.C.C9.A.A6.2C.3C9.A.
A6.C.C9.A.A6.2C.3C$.3A8.C9.3A12.C8.3A8.C9.3A12.C$3.A8.2C10.A6.2C.3C
11.A8.2C10.A6.2C.3C$32.C.C42.C.C$32.C.C42.C.C$33.C44.C!
Here I follow Adam P. Goucher's idea for Silk (unimplemented at time of writing) to use a Bloom filter to quickly test whether the reaction has been seen previously. A Bloom filter lets us store the hash 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
- all non-transparent catalysts are present,
- at least two generations have passed since the most recent catalyst was placed, and
- the population of the active pattern is at least 12.
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 coming from identical 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 will inevitably miss 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:
Code:
Select all
x = 12, y = 10, rule = LifeHistory
3.2A.3A$5.A$2D8.2D$DCA2.2A2.ACD$DCA.D2CD.ACD$2D2.4D2.2D2$.2A6.2A$D2CD
4.D2CD$4D4.4D!
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.
Code:
Select all
x = 10, y = 11, rule = LifeHistory
2.2A$A.2A$3A$.A2$.2A3.2D$D2CD.AC2D$4D.CDCD$5.2DC2D$6.D2CD$6.4D!
Currently, 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 fairly separated pieces.
Code:
Select all
x = 31, y = 31, rule = LifeHistory
22.2A$17.2A3.A.A2.2A$17.A6.A3.A$9.2A3.2A.A2.4A.3A$9.A4.A.A3.A2.A.A$
10.3A.A8.ABAB3A$12.A.2A2.B3.2B2ABA2.A$13.7B.6B2.2A$15.10B$6.A8.9B$6.
3A6.10B$9.A6.8B$8.2A3.B3.9B$8.8B.9B$10.18B2D$10.18BDBD$9.21BD$7.20BDB
2D$5.22B2D$5.2BC19B$4.3BCBC16B$5.2B3C15B$4.5BC12B.2B$3.10B2.8B$2.4B
10.9B$.4B12.6B.2A$4B12.8B2A$3B14.6B.B$2B15.BDBD$B17.DBD$18.3D!
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 might be easy to show that problems on the right are 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.
beaucoup. 
