Sifting ash for cool objects

[Kazyan]

Using QuFince, mvr did a high-powered glider collision search a while back, with a simple but sophisticated detection scheme for still lifes worth reporting: inflate still lifes along the Von Neumann neighborhood, then deflate twice along the Moore neighborhood, and whatever survives is probably worth looking at. Additionally, find all still lifes where there's a line of five in a row. This gets rid of all of the very common still lifes, with only the fourteener passing the second filter at an unwanted rate.

I got nerd-sniped by the problem of finding a more complete heuristic, and ideas for doing this better are welcome. The most complete way to census QuFince results is to do object separation, but that's too computationally expensive for the amount of junk that QuFince can pump out. The inflation and deflation method can be thought of as applying three INT rules in sequence:

Code: Select all

B1e2ei3e4e/S12345678
B/S8
B/S8

So how about finding a more fine-tuned set of rules? I set up a banlist of all objects with a frequency of at least that of the cis-mirrored bookend (so everything with a more than 1 in ~1 million rate of occurrence), minus the pentadecathlon, plus some constellations that tripped up earlier rules and a 200x200 or so patch of genuine life ash for completeness. There's also maximizelist of all 18-bit still lifes that cost at least 9 gliders to synthesize at the time that I grabbed the figures from catagolue. That's 13630 of them. The attached script, which contains a bunch of hardcoded garbage and misleading comments/variable names, randomly mutates from the three rules from a known starting point (an unreadable very large 280-bit integer) to achieve the following:

1. Applying them in sequence completely deletes the contents of the banlist.
2. Applying them in sequence preserves at least one cell in as many of the xs18s as possible.

The script is greedy and uses whatever improvement it finds as the next starting point during the run. It puts the details of the current best finding into the clipboard. I didn't make it user-friendly; it's being presented here for tinkering interest.

After some experimenting, I found that the following set of INT rules catches 12815/13630 of the expensive xs18s, roughly a 94.0% success rate:

Code: Select all

B3ckqry4-cei5ceijr6ek/S2n3eikq4cikz
B2ekn3-cenr4-ei5-ceiq6ci7/S2e3-aeik4-jnqty5aejqy6akn7c
B2ak3-jkq4aeijkw5ejknq6-ek8/S2cei3cenq4-aiqrt5-ajq6acn7e8

I'm not sure how computationally expensive it is to apply complicated INT rules like this, but it's definitely easier than full object separation. This is also overfitted to the xs18s, but it's a starting point for a broader maximizelist.

There's no particular reason to use only three rules, but when excluding b0, an INT rule has 101 possible bits to set. 303 bits is probably enough to design a good no-common-objects filter!

[apg]

I'm not sure how computationally expensive it is to apply complicated INT rules like this

Let's define a 3x3 napkin as 'normalised' if the 4 corner cells form one of the following 6 arrangements:

Code: Select all

x = 17, y = 10, rule = LifeHistory
CFC4.CFD4.DFD$3F4.3F4.3F$CFC4.CFD4.CFD5$CFC4.CFD4.DFD$3F4.3F4.3F$DFC
4.DFC4.DFD!

Note that any napkin can be rotated to form one that is normalised. As such, we can implement a circuit that normalises a napkin using 22 LOP3 operations:

• 6 LOP3s to implement the 4-input 2-output function that takes in the 4 corner cells and outputs the booleans "rotate by 90?" and "rotate by 180?";
• 8 LOP3s (multiplexers) to conditionally rotate by 180 degrees;
• 8 LOP3s (multiplexers) to conditionally rotate by 90 degrees.

The 6 normal arrangements were chosen so that the south-east cell is redundant -- which means we need not compute it, saving us 1 multiplexer, bringing that normalisation cost down to 21 LOP3s. Given a normalised napkin, there are 3 possibilities for the ordered pair of north-west and north-east cells, and 2 possibilities for each of the 6 remaining cells ignoring the redundant bottom-right cell; this gives 192 normalised napkins (as opposed to 512 original napkins). We proceed to compute the function f(nw, ne, sw, n, s, e, w, c) of the 8 non-redundant cells as follows:

• at most 24 LOP3s to compute the 24 partial functions where the first 5 variables are bound and the latter 3 are free;
• at most 23 multiplexers to tie these together into a BDD on the remaining 5 variables.

As such, we can evaluate an arbitrary INT rule using at most 21 + 24 + 23 = 68 LOP3s (plus 2 shuffles and 6 funnel-shifts).

[Kazyan]

With some new modifications, including simulated annealing and doing "sweeps" of single-point mutations, the script arrived at this set of rules that catches 13318/13630 of the expensive 18-bit still lifes, for a success rate of 97.7%:

Code: Select all

B3ckr4ajkqrty5aeij6a/S1e2en3-an4ajny
B3-ai4-iwy5-c6aek7e8/S2in3enqr4eikqtwy5-ir6-an7e8
B2aci3-qr4ijkqtwz5ejqy6ekn7c8/S2cei3aeinr4ciwz5cekqr6-in7

If you want to tinker with this set of rules, replace the "starterbits = 0" line in the script (line 153) with "starterbits = 12605041738456176285855580245900265389315400920100054038464125279919196153983074599232"

There are some overfitting issues with this one--I tried a different maximizelist of all natural 23-bit still lifes, and its success rate was only 92.4%, when a less-overfit ruleset (95% of on the xs18s) can get something like 94%.