apgsearch v1.0

[gameoflifeboy]

I tried B345678/S678, a Day & Night rule.

Did you get the rule number right? Apgsearch running slowly would be expected behavior on this rule, as almost every soup becomes a unique pattern with almost every cell dying in the next generation, and almost every dead cell inside of the pattern coming alive.

(If by "Day & Night rule" you mean that it is self-inverse however, you're right.)

Moral of the story: Try running soups manually before apgsearching a rule so you know what to expect.

[calcyman]

According to Mark Niemiec's life webpage (which I don't believe is in the public domain yet, but I have a local copy), the only objects with 12 cells are:

• 121 still-lifes;
• 6 period-2 oscillators (hexapole, cis-beacon-on-table, trans-beacon-on-table, phoenix, fox, and xp2_s0i0j0ezw1);
• 1 period-3 oscillator (the caterer);
• 2 period-4 oscillators (mazing and mold);
• 1 period-8 oscillator (figure-8);
• 1 period-15 oscillator (pentadecathlon).

So far, 130 of these 132 objects have appeared in b3s23/C1; we are still waiting for the period-2 phoenix and the period-1 very^5 long snake. Any speculation as to which will appear first, and when?

(All objects of 11 or fewer cells have already been seen in the census, the rarest being the pentapole.)

Anyway, I was wondering how large the Catagolue could grow before reaching internal limitations (the limiting factor probably being the 1MB maximum entity size imposed by the Google App Engine). I think that we can safely reach an object count of 50 * 10^12 before this is likely to become an issue (coinciding with reaching about 40000 distinct still lifes of the same bit count), so Catagolue should be able to withstand the current load for at least another three years or so.

I'm excited to see what rare objects emerge over the coming months. We've already seen various flotillae, a couple of bi-pentadecathlons, Elkies' p5, a buckaroo and a twin-bees shuttle. I wouldn't be surprised if the following small oscillators show up reasonably soon:

• Achim's p5 (pseudo-barberpole)
• Silver's p5
• Smiley
• Achim's p8

Larger oscillators seem plausible, such as the trans-twin-bees-shuttle and several variant stabilisations of the queen bee shuttle. I imagine that the Gosper glider gun has a frequency of less than 10^-15, so it's incredibly unlikely that we'll see one in this census.

Spaceships have the additional challenge of having to be produced on the boundary of a reaction, but the following small spaceships seem like reasonable contenders:

• Boring flotillae
• Coe ship
• Loafer

The popularity of spontaneous bilaterally symmetric explosions may also lead to larger moving objects:

• Pufferfish
• x66
• Schick ship

Does anyone else have a similar 'wish list'?

[praosylen]

Does anyone else have a similar 'wish list'?

I'm waiting to see the first double switch engine puffer that shows up. According to a calculation that I made a while ago, two separate switch engines in one soup has a frequency of around 1 in 7 billion. This has probably happened already. However, the probability of them going in the same direction at the same time and both stabilize is probably much lower (but I don't know how much lower). It's possible, however, that the probability is high enough that Catagolue has a reasonable probability of finding one. In any case, I'm still watching for one to show up.

[biggiemac]

We now have over half the 15-bitters. Also I have now passed half the objects contributed. Regarding wish lists, I'm hoping for a loafer or a non-switch-engine puffer. Small oscillators would also be excellent. Overall, I'm just happy about how much data this search is capable of generating.

[dvgrn]

Regarding wish lists, I'm hoping for a loafer or a non-switch-engine puffer.

Same here. The loafer is so slow that it seems likely to show up hundreds or thousands of times in soups for every one that actually escapes -- so if we could only check every tick of every soup for a loafer signature, it seems quite possible that several would have been found already. Unless we run a special search to check every generation of a lot of soups, I guess we won't know for sure.

Even more than the loafer, it does seem as if there ought to be other types of puffers, based on Herschels or R-pentominos or LOMs or who knows what, interacting with a small amount of junk to accidentally make translated copies of itself and the same junk. I can't see why regular B3/S23 should be so incredibly resistant to this kind of thing...

Code: Select all

#C Could Be B3/S23 --
#C p589 puffer
#C http://catagolue.appspot.com/hashsoup/D4_x1/LyQ88fwWEmd3110253/b38s23
x = 26, y = 26, rule = B38/S23
25bo$24bo$23b2o$24b2o$25bo19$2bo$b3o$o2b2o!
[[ AUTOSTART ZOOM 3 X 30 Y 30 STEP 4 ]]

[codeholic]

It seems that apgsearch does not separate these spaceships correctly: http://catagolue.appspot.com/object/ov_q8/b36s125

[wildmyron]

It seems that apgsearch does not separate these spaceships correctly: http://catagolue.appspot.com/object/ov_q8/b36s125

This is almost certainly due to the parallel soup processing of the census. Not this soup, but some other soup in the 100 being censused has an infinite growth pattern or isn't readily stabilised in some other way, and triggers the extended duration of APG_CoalesceObjects (i.e. stabilise3() returns step = 12). The second glider then overruns the history trail of the first and they are processed as a single object. Due to the size of the combined object, no attempt is made to separate the components.

I haven't verified that this is actually happening in this case, but if APG_CoaelesceOjects is run for 2^12 gen with this glider pair, their history trails do indeed merge.

[Scorbie]

Can a pattern with valid apgcode exceed 40x40 bounding box? If some of the phases have valid apgcodes and some don't?

Edit: Thanks, flipper77!

[flipper77]

Can a pattern with valid apgcode exceed 40x40 bounding box? If some of the phases have valid apgcodes and some don't?

When apgsearch attempts to canonize a pattern, it will pick out a representation that fits within the 40x40 bounding box. Only when all phases of the pattern can't fit within that restriction does apgsearch give it a prefix of "ov" for being oversized.

[flipper77]

Finally, all 12-bitters have been reported in the b3s23/C1 census, with the very^5 long snake as the last hold-out. This is very exciting considering Okrasinki's search never reached this mark, yet Catagolue (and many other contributors, especially biggiemac) has managed this task in just 2 months! Is it too much to hope for all 13-bitters by the end of the year?

[calcyman]

Is it too much to hope for all 13-bitters by the end of the year?

If we look at the number of occurrences of each length of snake (the rarest still-life for 6, 7, 9, 10, 11 and 12 bits, and a close second for 8 bits), there appears to be a rough geometric progression:

xs8: 203912
xs9: 11069
xs10: 220
xs11: 23
xs12: 1

The ratio of successive terms tends to be between about 10 and 50, so we can expect the 13-bit snake (which should be the last xs13 to go, if it's anything like the situation with 10-, 11- and 12-bit objects) somewhere between 10T and 50T objects. If it's the former, then the end of the year is a reasonable target. If the latter, then not (unless we acquire some more biggiemacs).

[Kazyan]

More biggiemacs? My university has hundreds and hundreds of computers, but almost all are in regular use except maybe one of the small liberal arts labs. I'll look into that lab this weekend.

[biggiemac]

The "farm" I have set up is all background processes, even when the computers are otherwise in use. On Windows at least, the "switch user" option keeps processes running (I believe on macs the "login window" does the same). So you can log in as yourself, download apgsearch and golly, set up 4 instances with a reasonable time between hauls, switch user, and move on to the next. It's invisible to other users what your account has running. Since golly is submissive (as I was told), the computers aren't too affected by the search, but rather the search is slowed when other users are present. The only thing that would stop the program is someone rebooting or a power bauble.

[praosylen]

We've just hit 1 trillion objects!

[dvgrn]

A trillion -- that's getting to be a fairly impressive number! Objects, objects everywhere, nor anything p7 I think.

On Windows at least, the "switch user" option keeps processes running (I believe on macs the "login window" does the same).

On my campus, the IT department is clever -- the "switch user" option is disabled, so you can't keep background processes running without leaving yourself logged in and vulnerable.

Of course, even with "switch user", a competent admin might notice any time that a single user has a lot of background processes running on a lot of computers. They might well get worried that someone is running a botnet or some such. Be prepared for sudden unexpected shutdowns...!

I have a copy of Golly set up on my university share drive, with a customized version of the apgsearch script in the Golly root directory renamed to "golly-start.py". Rulestring, symmstring, and payoshakey are hard-coded so they don't need to be retyped each time -- just have to start Golly several times and that's it.

In my tests a while ago, there wasn't actually much advantage to running four instances instead of three, on a four-core system (at least the ones I have access to). Three instances run significantly faster, so that they process just about the same number of soups as four instances would -- and possibly they leave the computer a little bit more responsive, with one dedicated core left to quickly handle whatever else comes up.

Also, I've found on my systems that sqrtspp =14 reliably processes a few more soups per second than either sqrtspp = 13 or sqrtspp = 15. 14x14=196 soups seems to be the top of the curve. I'd be curious to know if other people see a similar pattern. If you run three or four instances on the same multi-CPU computer, presumably any other differences should average out.

[calcyman]

Also, I've found on my systems that sqrtspp =14 reliably processes a few more soups per second than either sqrtspp = 13 or sqrtspp = 15. 14x14=196 soups seems to be the top of the curve.

Wouldn't the optimal sqrtspp depend on the symmetry and rule combination (and possibly even on the hardware)? It appears that you've been running different values of sqrtspp in b3s23/D4_+2 rather than b3s23/C1:

http://catagolue.appspot.com/haul/b3s23 ... ommitted=2

This has given me the idea of adapting apgsearch to allow different 'pages' of soups to have different values of sqrtspp, determined by some probability distribution. Naturally, that probability distribution will be updated based on the average* number of soups processed per unit time as a function of sqrtspp. That way, apgsearch will locate the optimum by itself, instead of relying on a human experimenter such as Dave Greene to determine the optimum. Machine learning seems to be in vogue** at the moment, so I might as well try it...

* by which I mean exponentially-weighted moving average, so it will be able to respond reasonably quickly to changes in the environment. A Kalman filter would theoretically be even better, but in practice there's usually no discernible difference.

** by which I mean popular, rather than featured in the fashion magazine of that name.

At the moment the set of feature requests seems to be:

• Machine-learning to optimise sqrtspp;
• Interactive system where apgsearch scores soups based on Catagolue frequency data;
• Verify incoming b3s23/C1 hauls.
• Sort soups by symmetry on Catagolue /object pages.

[codeholic]

Other feature requests were:

• Natural sorting viewtopic.php?p=17173#p17173
• Parallel census for pseudo still-lifes, pseudo-oscillators and pseudo-spaceships viewtopic.php?p=18681#p18681
• Tracking feature requests in Uservoice viewtopic.php?p=18703#p18703

[Sphenocorona]

Suggestion: Allow the user an option to disable showing animated SVGs on Catagolue, instead showing static images which when clicked will take the user to the animated image. They make my browser slow to a crawl once they appear on screen, and so I'm unable to navigate pages with more than one or two posted on them

[biggiemac]

Restarted my army of instances. Of the 25 computers, only 12 were left, so now we're back at 100 known instances churning out in excess of 30K soups/sec. The deluge of hauls should begin at around 4 AM PST, which is 11 AM UTC. Hope for more excitement!

[Alexey_Nigin]

Now that I have finally installed apgsearch, I have got a few questions:

• Why does the script silently accept the value of 200000 soups per haul, but upload results only after 500000 soups?
• How many soups should I upload in order to get a place in a pie chart?
• What will happen if anyone decides to draw some cells while the script is running?

I also have one feature request: add 1x256 as a possible symmetry (much like 8x32).

P. S. Adam, please accept my belated congratulations on your birthday!

[biggiemac]

apgsearch has hardcoded a minimum of 500k between uploads in the source code. (Most of my searches run at 9 million, which takes about 7 and a half hours between).

The pie chart has a place for every contributor, but my own contributions have made the requirements a bit large to be above 0.1%. With 78B soups in, it would take about 78 million soups to make 0.1%. (Edit: specifically in C1. Other symmetries have far fewer objects found so far.)

I don't think that 1x256 would be too interesting..

[calcyman]

Why does the script silently accept the value of 200000 soups per haul, but upload results only after 500000 soups?

I imposed a lower limit of 500k to prevent people from DDoS-ing Catagolue with lots of small hauls. Catagolue itself rejects any haul with fewer than 80k soups for this reason.

How many soups should I upload in order to get a place in a pie chart?

For niche combinations of rule/symmetry, you won't need many at all. For b3s23/C1, it looks like you would need to beat Neil Bickford, which equates to contributing roughly 250 million soups (so about 10 CPU-days, given the reasonably accurate approximation of 1 CPU-hour = 1 million soups).

What will happen if anyone decides to draw some cells while the script is running?

I believe Golly disallows that.

[Alexey_Nigin]

Will you punish me if I decide to seriously investigate Day & Night?

http://catagolue.appspot.com/census/b3678s34678/C1

Edit: Oops... I had decided to launch two instances and see what would happen. It was running at 900 sps and the amount of large low-period objects was growing enormously fast. I have probably answered my own question.

[calcyman]

By the way, apgsearch v1.04 has been released. It now runs precisely the number of soups specified (subject to the 500k minimum) instead of rounding it up to the nearest multiple of 100. Moreover, the number of soups per page is optimised during runtime, so there should be a slight performance boost.

Edit: Oops... I had decided to launch two instances and see what would happen. It was running at 900 sps and the amount of large low-period objects was growing enormously fast. I have probably answered my own question.

That's okay. The xp2 tabulation (which is by far the largest) is only 140K in size, which means it can grow to about 7 times its current size (or 40K distinct objects) before Catagolue breaks.

Similarly, the xs20 tabulation in b3s23/C1 can probably grow to about 25 times its current size (giving 60 * 10^12 total objects as a conservative estimate* for when this happens). So we're about 3% of the way to saturation.

* which may well be as inaccurately low as the Conservative estimates produced by the pollsters in the run-up to the election.

P. S. Adam, please accept my belated congratulations on your birthday!

Thank you very much!

[gameoflifeboy]

Suggestion: Allow the user an option to disable showing animated SVGs on Catagolue, instead showing static images which when clicked will take the user to the animated image. They make my browser slow to a crawl once they appear on screen, and so I'm unable to navigate pages with more than one or two posted on them

Seconded. Hopefully this is easy enough to do with the giffer.py script. I also wish the census page would give the most popular rules (combining the soups searched in all symmetries) instead of the most popular rule/symmetry combinations, as most of those are just symmetries of b3/s23. If possible, a list on multiple pages or otherwise of every rule that has been censused would also be nice.

By the way, I just added LifeWiki links to my Catagolue backup for the objects that have them.
Edit: Maybe you could also give LifeWiki links on object pages, as well as links to the pentadecathlon.com page of the object and Mark Niemiec's sythesis file, if these exist?