apgsearch: a high-performance soup searcher

For general discussion about Conway's Game of Life.
wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: apgsearch: a high-performance soup searcher

Post by wildmyron » October 24th, 2014, 12:49 am

dvgrn wrote:
codeholic wrote:I've just realized, that the following variants are probably treated as separate still-lifes by apgsearch. It's a pity.
There seem to be quite a few more variants that might be worth adding to that last list -- various permutations of the two-sided eater2, many of which remove one of the two eater sites but are still fully functional from one side:

Code: Select all

x = 75, y = 16, rule = B3/S23
15bo29b2o$15bobo9b2o16b2o$15b2o10bo45b2o$6b2o20bo16b4o3b2o12b2o5bo$6bo
2bob2o16bob2o12bo3bobobo12bo2bobobo$8b2ob2o15b2ob2o15b2ob2o15b2ob2o2$
8b2ob2o15b2ob2o15b2ob2o15b2ob2o$8b2obo2bo13b2obobo14b2obobo14b2obo$13b
2o18bo19bo19bo$33b2o18b2o17b2o3$b2o20b2o18b2o16b2o$obo19bobo17bobo15bo
bo$2bo21bo19bo17bo!
It would probably work to add a list of specific objects to apgsearch -- if the pseudo_bangbang() function sees an eater2 variant that's on the list, it can send it back to be catalogued without breaking it into its component pieces. I haven't checked to see if this would actually work, but it seems as if it should.
[snip]
I'd been thinking about this for a while and it just occurred to me that you don't need any additional special object detection code - it's already built in to the pseudo object caching. Any pseudo-object which you don't want broken up into constituent parts can simply be added to the decompositions dict. E.g. this adds the tri-block to the list:

Code: Select all

    decompositions = {"xs18_3pq3qp3": ["xs14_3123qp3", "xs4_33"],
                      "xs12_rrz66": ["xs12_rrz66"]}
You can also add it to the common names list if you want the name to show up in the census or give it a score higher than 10.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: apgsearch: a high-performance soup searcher

Post by dvgrn » October 28th, 2014, 9:18 pm

Just noticed an odd feature that has probably been around for a few versions of apgsearch.

I was running the seed 18Mh for 18 million soups, and got the following reported soup numbers for xp2_7 (blinker):

Code: Select all

791154 791154 954923 954923 1206181 1206181 1653857 3114980 3114980 3784824
First, this is a little bit strange because the soup numbers for other very common ash objects are two digits long.

-- Except beehives are three digits, no doubt as an artifact of the way they're cleaned up by custom rules; they seem to not get counted until they show up in a not-trivially-cleaned-up combination -- and beehive combos are just that much less common than bi-blocks.

Second, the soups come in identical pairs, which is unusual.

Third, the pairs are all soups that generate glider-producing switch engines. (Those do indeed produce pairs of blinkers with every cycle, but they also produce gliders, for which I have yet to see a soup link.) (?)

Fourth and most interesting (at least to me), one of the numbers in the above list is not part of a pair. I'm assuming that 3784824 would have been paired if it hadn't hit the ten-soup cutoff. You have three guesses, and the first two don't count, as to which of the following soups correspond to the (other) singleton soup number:

Code: Select all

x = 1766, y = 16, rule = B3/S23
2bo2bobo2b2ob2o235b3o3b2ob5obo237bob3o3b3o486bo2b7o3b2o485b4ob3o2b5o
235bob3obo4bob3o$2bo2b6o2b2o240bob3ob3o237b2o2b2obobo2bobo486b2o6b4o
486b2o2bo4bo2b2obo235b2o2b2ob3o2b2o$bo5b2o3b2obo237b2obobo2b2ob2o234bo
4b2ob2obobo488b5o2bobobobo484b2o2b4o3b2ob2o235bob7obobo$2ob2obo3b2o
242bo2bobob2ob2o234b2o4bo2bo2bob2o486bo2b2ob2o2bob2o485b4o4b2obo2bo
235bob4o2b4obo$4obob3o4b2o236b4obobobo2bo235bobo2b3o2bob2o486bobo2bo2b
ob4o487bo2bobob3obo2bo234bo3b2o2b2obob2o$2b2obobobo2bobo235b5o10bo235b
obo4bob2ob3o484bo2bo2b4o2bobo485bo4bob2obobob2o234bob2obo4bobo2bo$2o2b
o3bo4b2o236bobo4bobobobo236b2o2bob2o5b2o485bob2obob4obobo484b5obo3bo3b
o236b4o3b2obobo$2ob2obo2bob2ob2o235b3o2bo4b2ob2o235bobob3o3b2ob2o485bo
7b3o2bo485bo4b2o2bo2b2o238b2ob2ob5ob2o$2o2bobo2bo3b2o237b2o4b2ob2obo
238b3o3bob5o487bob4ob3o487b2ob2o2b4o3bo235bob3o3bo4bobo$3ob2ob5ob3o
234b3o3bo3bobobo236bo4bo2bo3b3o484b2ob2o2bob5obo484b3o2b3obobobo236b2o
bo2bo2b2obo$b3o5bob3o239bo3bo3b3o236b2obobob2ob2o2b2o486b2ob11o484bo2b
2o3bo3b2obo234bobob3o2bob5o$2obob2o3b2obobo238b2obob2obo240bobob2o3b3o
485bo4bobobo2bo487bo2b2o2b3ob2o238b7o3bo2bo$2o2bobo2bo4bo237b8ob5o234b
o4bo3b2ob2o487b2obob6o488b3ob2obo2bo2bobo235bobob3o4bo2bo$3o6bob4o238b
3o3b3o3bo234bob4o2b2obobo487bob4o2b4obo485bobo4b2obob4o234bo4bobobobob
o$o2b4o5bo2bo234bo3bobobob4obo241bobo5bo484b2o2b2o2b4o3bo484b2obob3ob
4obo236bobo7bo$ob4obo3bobobo236bo3bob3o3bo235bob7obo2bobo488bo2bo2bo2b
obo484bo3b5ob4o237bob2o5bo2bo!
So... why did apgsearch pick out that soup to immortalize, after passing over about 1.5 million other soups whose ash also contained blinkers?

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: apgsearch: a high-performance soup searcher

Post by wildmyron » October 29th, 2014, 12:49 am

dvgrn wrote:Just noticed an odd feature that has probably been around for a few versions of apgsearch.

I was running the seed 18Mh for 18 million soups, and got the following reported soup numbers for xp2_7 (blinker):

Code: Select all

791154 791154 954923 954923 1206181 1206181 1653857 3114980 3114980 3784824
First, this is a little bit strange because the soup numbers for other very common ash objects are two digits long.

-- Except beehives are three digits, no doubt as an artifact of the way they're cleaned up by custom rules; they seem to not get counted until they show up in a not-trivially-cleaned-up combination -- and beehive combos are just that much less common than bi-blocks.

Second, the soups come in identical pairs, which is unusual.

Third, the pairs are all soups that generate glider-producing switch engines. (Those do indeed produce pairs of blinkers with every cycle, but they also produce gliders, for which I have yet to see a soup link.) (?)
I suspect that this is new behaviour with v0.5. In light of your comments I didn't update straight away, but I have since done so and there are several other bug fixes and new features. One bug fix is to the HandlePlumes rule (now called HandlePlumesCorrected) which previously was removing isolated dots and dominos which stabilised oscillators in other rules (only happens with S0 and S1). HandlePlumes was designed to clean up isolated, decaying patterns which leave behind still life or P2 objects in a region of dead cells by removing marked dead cells which are no longer associated with live cells. To do this successfully, dead cells between inducting components should not be removed and this was operating successfully for B3/S23. One fix would have been to have custom HandlePlumes rules depending on the base rule. Calcyman's approach was to make a more conservative version of HandlePlumes which doesn't remove any marked dead cells neighbouring a live cell (guaranteed not to remove a marked cell which is part of a P2 oscillator in any rule). The result is that two blinkers in an isolated region of marked dead cells, which is cleaned up by HandlePlumesCorrected, don't have a signature which matches the ExpungeObjects rule.

You can see the effect of this like so:

* generate the soup for soupid 18Mh791154

Code: Select all

x = 16, y = 16, rule = B3/S23
2bo2bobo2b2ob2o$2bo2b6o2b2o$bo5b2o3b2obo$2ob2obo3b2o$4obob3o4b2o$2b2ob
obobo2bobo$2o2bo3bo4b2o$2ob2obo2bob2ob2o$2o2bobo2bo3b2o$3ob2ob5ob3o$b
3o5bob3o$2obob2o3b2obobo$2o2bobo2bo4bo$3o6bob4o$o2b4o5bo2bo$ob4obo3bob
obo!
* Run for 24,600 generations (time taken by stabilise3())
* Change rule to APG_CoalesceObjects_B3S23, base to 2 and step to 12
* Step
* Change rule to APG_ClassifyObjects_B3S23
* Step
* Change rule to APG_HandlePlumesCorrected
* Run 1 gen
* Change rule to APG_ClassifyObjects_B3S23
* Step (overkill, but it's what census() does)

There will now be two isolated blinkers which have a different pattern of marked dead cells and which won't be cleaned up by ExpungeObjects.
dvgrn wrote:Fourth and most interesting (at least to me), one of the numbers in the above list is not part of a pair. I'm assuming that 3784824 would have been paired if it hadn't hit the ten-soup cutoff. You have three guesses, and the first two don't count, as to which of the following soups correspond to the (other) singleton soup number:

Code: Select all

<snip>
So... why did apgsearch pick out that soup to immortalize, after passing over about 1.5 million other soups whose ash also contained blinkers?
The one that doesn't generate a switch engine! In fact, stabilise3() fails on this soup, it returns success after 1860 gen. Then, while running APG_CoalesceObjects_B3S23 (step is 4 in this case) a glider hits a boat and leaves a blinker behind.

---

At this point I'd like to mention the significant new feature in apgsearch v0.5. In addition to linearlyse, there is now a powerlyse() function which can categorise growing patterns with growth rates other than linear. I guess it hasn't found anything in Life yet, but it will be interesting to see what else turns up in other rules.

Myself, I have less time to work on CA projects but Id like to update my non-totalistic version of apgsearch to v0.5 and post it to the hacking apgsearch thread, hopefully sometime next week.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

flipper77
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch: a high-performance soup searcher

Post by flipper77 » November 5th, 2014, 10:32 pm

dvgrn wrote: At some point I still might extend the common-names list to include Achim Flammenkamp's still-life and oscillator names, but that's not a very high priority for me at the moment.
On top of this, I'd like to see the common-names list get organized along the lines of (still lives, oscillators, spaceships, etc.), then by object frequency, so adding entries or modifying current ones follow a somewhat more consistent format.

flipper77
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch: a high-performance soup searcher

Post by flipper77 » November 7th, 2014, 11:20 pm

After some time, I've managed not only to add the common SL's and oscillators from the Lifewiki, but I've added all the objects from Achim's text dump web page into the commonnames list, including other objects I've found, as well as a few from a post. Any names with double pairs of brackets are additional SL's not from the Lifewiki's common still lives list or Achim's list, so some if not all those makeshift names I gave those objects don't make sense. Apart from that, I've also made a few modifications to some scores and a few names to existing objects, so you may have to change those to your prefered scores, as well as possibly re-add objects you've added yourself, so keep that in mind.
Attachments
common_names.txt
(100.49 KiB) Downloaded 489 times

User avatar
calcyman
Moderator
Posts: 2929
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch: a high-performance soup searcher

Post by calcyman » November 8th, 2014, 12:53 pm

After some time, I've managed not only to add the common SL's and oscillators from the Lifewiki, but I've added all the objects from Achim's text dump web page into the commonnames list, including other objects I've found, as well as a few from a post
Thank you!!!

The other resource I know is here: http://www.geocities.ws/conwaylife/lf020n.pdf

I've also added some more oscillators and spaceships to the commonnames list. The spaceships portion now includes all conceivable two-*WSS flotillae, since they're the ones most likely to emerge from random junk:

Code: Select all

                   "xq4_153": ("glider", 0),
                   "xq4_6frc": ("lightweight spaceship", 7),
                   "xq4_27dee6": ("middleweight spaceship", 9),
                   "xq4_27deee6": ("heavyweight spaceship", 12),
                   "xq4_27de6z4eb776": ("LWSS on MWSS 1", 40),
                   "xq4_0791h1az8smec": ("LWSS on MWSS 2", 40),
                   "xq4_27du6ze98885": ("LWSS on MWSS 3", 40),
                   "xq4_27de6z4eb7776": ("LWSS on HWSS 1", 40),
                   "xq4_6ed72z6777be4": ("LWSS on HWSS 2", 40),
                   "xq4_27de6zw8smeeec": ("LWSS on HWSS 3", 40),
                   "xq4_027deee6z8smec": ("LWSS on HWSS 4", 40),
                   "xq4_27de6z8smeeec": ("LWSS on HWSS 5", 40),
                   "xq4_06eeed72zcems8": ("LWSS on HWSS 6", 40),
                   "xq4_27dumze988885": ("LWSS on HWSS 7", 40),
                   "xq4_27dee6z4eb776": ("MWSS on MWSS 1", 40),
                   "xq4_27dee6zw4eb776": ("MWSS on MWSS 2", 40),
                   "xq4_677be4zx48889e": ("MWSS on MWSS 3", 40),
                   "xq4_06eed72zaghgis": ("MWSS on MWSS 4", 40),
                   "xq4_27due6ze98885": ("MWSS on MWSS 5", 40),
                   "xq4_27dee6zw4eb7776": ("MWSS on HWSS 1", 40),
                   "xq4_27dee6z4eb7776": ("MWSS on HWSS 2", 40),
                   "xq4_06eeed72z677be4": ("MWSS on HWSS 3", 40),
                   "xq4_27dee6zx8smeeec": ("MWSS on HWSS 4", 40),
                   "xq4_0sighhgazz791h1a": ("MWSS on HWSS 5", 40),
                   "xq4_sighhgazz791hh1a": ("MWSS on HWSS 6", 40),
                   "xq4_aghgiszza1hh197": ("MWSS on HWSS 7", 40),
                   "xq4_0aghhgiszza1h197": ("MWSS on HWSS 8", 40),
                   "xq4_02111197zcssqe4": ("MWSS on HWSS 9", 40),
                   "xq4_6eeed72zaghgis": ("MWSS on HWSS 10", 40),
                   "xq4_27duee6ze98885": ("MWSS on HWSS 11", 40),
                   "xq4_0791hh1az8smeec": ("MWSS on HWSS 12", 40),
                   "xq4_27duu6ze988885": ("MWSS on HWSS 13", 40),
                   "xq4_6eed72zaghhgis": ("MWSS on HWSS 14", 40),
                   "xq4_06eeed72zaghgis": ("MWSS on HWSS 15", 40),
                   "xq4_27deee6z4eb7776": ("HWSS on HWSS 1", 40),
                   "xq4_27deee6zw4eb7776": ("HWSS on HWSS 2", 40),
                   "xq4_0aghhgiszza1hh197": ("HWSS on HWSS 4", 40),
                   "xq4_aghhgiszzwa1hh197": ("HWSS on HWSS 5", 40),
                   "xq4_027deee6zsighhga": ("HWSS on HWSS 6", 40),
                   "xq4_27duue6ze988885": ("HWSS on HWSS 7", 40),
                   "xq4_06eeed72zaghhgis": ("HWSS on HWSS 8", 40),
                   "xq4_a1hh197zx6777be4": ("HWSS on HWSS 9", 40),
                   "xq4_27deee6zwsighhga": ("HWSS on HWSS 10", 40),
                   "xq4_027deee6z4eqscc6": ("sidecar", 45),
                   "xq16_gcbgzvgg826frc": ("Coe ship", 50),
                   "xq12_fh1i0i1hfzw8sms8zxfjf": ("lightweight schick engine", 50),
                   "xq12_xupuzw27d72zu10109ghuz3221": ("asymmetric schick engine", 50),
                   "xq12_v1120211vz01gpcpg1zxv7vzy01": ("middleweight schick engine", 50),
                   "xq12_v1120211vz120ioi021zw1vev1zx121": ("heavyweight schick engine", 50),
                   "xq4_a1hhpnzy03mvo2ms8zy211": ("MWSS on pushalong", 55),
                   "xq4_82gfxossz34d72w37d6": ("HWSS on semi-X66", 60),
                   "xq4_0oorxroozdjio404oijd": ("X66", 66),
                   "xq7_3nw17862z6952": ("loafer", 70),
                   "xq7_7dfxg88gxfd7zw123u2222u321": ("weekender", 70),
                   "xq3_mhqkzarahh0heezdhb5": ("dart", 75),
                   "xq3_3u0228mc53bgzof0882d6koq1": ("turtle", 75),
                   "xq3_16614e8o4aa82cc2": ("edge-repair spaceship 1", 75),
                   "xq3_km92z1d9czxor33zy11": ("edge-repair spaceship 2", 75),
I'm not sure that I agree that (practically) all still-lifes in the list should be set to 0.

Anyway, ideally the common names list will ultimately be a text file downloaded by apgsearch from catagolue at the beginning of each run.
What do you do with ill crystallographers? Take them to the mono-clinic!

flipper77
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch: a high-performance soup searcher

Post by flipper77 » November 8th, 2014, 5:35 pm

calcyman wrote: I'm not sure that I agree that (practically) all still-lifes in the list should be set to 0.
Absolutely, it's just that I left them that way for now, since I'm not too good at giving adequate scores for corresponding objects, hopefully this script takes off, and some sort of database can be organized to accumulate results from everyone running it.

EDIT: Thanks for the spaceship list, that's going to help, not that I'm holding my breath until one of these miraculously shows up, but as I mentioned before, it would be great if there was a good way to score some of these objects, I'm of the rough heuristic mentioned in the script, 15 + log2(n), but it seems like it won't be the best way to score SL's

User avatar
Extrementhusiast
Posts: 1966
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: apgsearch: a high-performance soup searcher

Post by Extrementhusiast » November 8th, 2014, 11:10 pm

A different idea: variable scoring based on time. (In other words, a rare object that appears after 10 generations is usually less valuable than the same object appearing after 1000 generations.) For that, one would multiply the preliminary score by a function (something like tanh(x)) that has an asymptote at y=1.
I Like My Heisenburps! (and others)

Bjorn
Posts: 19
Joined: October 23rd, 2014, 8:45 pm

Re: apgsearch: a high-performance soup searcher

Post by Bjorn » November 15th, 2014, 12:26 am

This might be a stupid question, but is there a way to turn the names of objects into the objects themselves?

flipper77
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch: a high-performance soup searcher

Post by flipper77 » November 15th, 2014, 8:18 am

Bjorn wrote:This might be a stupid question, but is there a way to turn the names of objects into the objects themselves?
Go here

That post not only has a script that turns canonised names into the objects, but there's a script to get previous soups from previous runs that generate objects you've encountered before.

Bjorn
Posts: 19
Joined: October 23rd, 2014, 8:45 pm

Re: apgsearch: a high-performance soup searcher

Post by Bjorn » November 15th, 2014, 1:32 pm

flipper77 wrote:
Bjorn wrote:This might be a stupid question, but is there a way to turn the names of objects into the objects themselves?
Go here

That post not only has a script that turns canonised names into the objects, but there's a script to get previous soups from previous runs that generate objects you've encountered before.
Thanks :)

@@@@@@@@@@@
@@@@@@@@@@@
@@@@@@@@@@@
@@@@@@@@@@@
@@@@@@@@@@@
@@@@@@@@@@@
@@@@@@@@@@@
@@@@@@@@@@@

flipper77
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch: a high-performance soup searcher

Post by flipper77 » November 19th, 2014, 5:12 pm

I would like to see symmetry options added to apgsearch so that you're asked for symmetry options for the soups you search, which would be reflected by the temporary patterns generated by search's end, as well as the census results(i.e. @SYMMETRIES ...), so you'd know if a search has a certain set of symmetries just by looking at the file, but I'll probably add that stuff in myself if no one else here has done so already. Besides, I'd like to see if I can try this myself.

MikeP
Posts: 105
Joined: February 7th, 2010, 9:51 am
Location: Ely, Cambridgeshire, UK

Re: apgsearch: a high-performance soup searcher

Post by MikeP » November 20th, 2014, 12:06 pm

I just noticed that apgsearch knows about the loafer. Is it worth adding the snark catalyst too?

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: apgsearch: a high-performance soup searcher

Post by dvgrn » November 20th, 2014, 12:56 pm

MikeP wrote:I just noticed that apgsearch knows about the loafer. Is it worth adding the snark catalyst too?
Probably not, unfortunately. I've been test-running apgsearch for months now, enough to get a general sense of the power law governing the appearance of high-bit-count still lifes. The Snark catalyst is 31 or 34 bits for the common versions, I believe, and no doubt we could come up with hundreds of variants with slightly higher bit counts.

Still lifes above 30 bits are very rare, and most of the ones that show up are the relatively common symmetric ones. I guess there's no harm in adding a definition for the Snark catalyst, but I'd expect it to take thousands of years of distributed searches involving every computer on the planet, before any given arbitrarily-chosen 30+-cell still life would happen to show up in a soup search. Even then it might well appear only because it was present in the initial conditions.

Now, this is just a crackpot theory until we get some good statistics from 'catagolue' -- but I suspect that the number of gliders required to construct an object will turn out to be fairly strongly correlated with the object's frequency of appearance in random soups. The loafer needs 8 gliders, where the Snark catalyst needs 48. Both of these numbers are just the current-best recipes, but the best possible recipes might still have a cost ratio of about 1:6.

It seems vaguely possible that 8-glider-constructible objects might be within reach of a few years of distributed searching -- and so, in a fit of somewhat unreasonable optimism, loafers and other likely small spaceships were thrown in with the other common-object definitions. It's a little discouraging that a loafer will probably have to show up and be destroyed in hundreds or thousands of soups, before one manages to escape and get counted by apgsearch. But I guess we can live with that...

48-glider-constructible objects are going to be, let's say, X^40 times less common than loafers. The value of X is a very interesting question that I wish someone would look into properly. But even if X is as low as 2, it takes more optimism than I can come up with to even pretend that Snark catalysts might ever make an appearance.

(Anyway, if they do, someone will no doubt notice during an occasional survey of the high-bit-count objects in the catagolue database!)

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: apgsearch: a high-performance soup searcher

Post by dvgrn » November 21st, 2014, 6:51 pm

dvgrn wrote:48-glider-constructible objects are going to be, let's say, X^40 times less common than loafers. The value of X is a very interesting question that I wish someone would look into properly. But even if X is as low as 2, it takes more optimism than I can come up with to even pretend that Snark catalysts might ever make an appearance.
Taking my own advice about looking into the power law for high-bit-count objects... attached is some raw data for total object counts on my system. In all, my copy of apgsearch has seen about 22 billion still lifes coalesce out of random soup. If I add up the counts for all stable objects with N bits, N=4..40, I get a graph that looks like this:
Frequencies of N-bit still lifes
Frequencies of N-bit still lifes
Still-life-frequencies.png (20.35 KiB) Viewed 23418 times
This seems to imply that the chance that a still life appearing out of random soup will contain N bits should be, very roughly, 1 in 10^(N/3). There's a lot of up and down around the trend line, of course, due in part to a significant bias toward objects an even number of bits.

I haven't attempted any kind of correlation with glider-construction recipes yet. So for the Snark catalyst, maybe all we can say at the moment is that the odds of a 34-bit still life appearing from random soup might be about 1 in 200 billion. That is, one still life in 200 billion will be a 34-bitter. Divide that by the number of different 34-bit still lifes to get the odds of any particular 34-bit still life showing up...!

A 31-bit still life should show up every 20 billion still lifes or so, except that there's that awkward bias against odd-bit-count still lifes. Maybe not coincidentally, I haven't actually seen a 31-bitter yet. EDIT:... besides four copies of xs31_69b88bbgz69d11dd, as Lewis points out below, which has a simple predecessor and so is uncharacteristically common.

I suppose we could extrapolate from known lists of N-bit objects, and say that there are probably about 1.7 billion 31-bit objects, and 24 billion 34-bit objects. Which makes the odds of seeing a Snark catalyst... um... somewhere around where I thought it was.

(Someone should check my math. Other exponents near N/3 are equally plausible, of course. I've left out N-bit oscillators from these calculations, assuming that they wouldn't make much of any difference if I included them.)
Attachments
Appearances-per-still-life.txt
Number of appearances for each still life
(94.49 KiB) Downloaded 485 times

User avatar
Lewis
Posts: 337
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

Re: apgsearch: a high-performance soup searcher

Post by Lewis » November 22nd, 2014, 7:40 am

dvgrn wrote: A 31-bit still life should show up every 20 billion still lifes or so, except that there's that awkward bias against odd-bit-count still lifes. Maybe not coincidentally, I haven't actually seen a 31-bitter yet.
In the text file you posted, the still life "xs31_69b88bbgz69d11dd" has four occurrences.

Is there a known reason why the bias towards even-size still lifes in Life is so large compared to other similar rules? Rules like 2x2 have the same tendency towards symmetry in objects (i think), which is what I assume causes Life to favour even sizes, but from plotting a graph similar to yours with my census results for 2x2, it's much more linear. Am I just missing something obvious?

Also, just out of curiosity, if you've got a text file similar to the one above for still lifes, but with counts for ships/oscillators/switch engines etc. could you please post it?

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: apgsearch: a high-performance soup searcher

Post by dvgrn » November 22nd, 2014, 8:53 am

Lewis wrote:
dvgrn wrote: A 31-bit still life should show up every 20 billion still lifes or so, except that there's that awkward bias against odd-bit-count still lifes. Maybe not coincidentally, I haven't actually seen a 31-bitter yet.
In the text file you posted, the still life "xs31_69b88bbgz69d11dd" has four occurrences.
Oops. I must have meant:

"... besides that unusually common symmetrical b2o2b2o$obo2b2o$o$b6o$7bo$b6o$o$obo2b2o$b2o2b2o! one that keeps showing up."

I also saw the relatively common 40-bit still life that others have reported, and a couple of 29-bitters did eventually appear to fill the gap I was seeing earlier... but if frequency=10^(-N/3) is anything like accurate, it's going to take a long time to fill the big gap from 32 to 39. 10^13 is 10 trillion, or 450 times as much searching as I've done on my system so far.

That still ought to be within reach of a distributed 'catagolue' search, though! EDIT 2/22/2016: It was.
Lewis wrote:Is there a known reason why the bias towards even-size still lifes in Life is so large compared to other similar rules? Rules like 2x2 have the same tendency towards symmetry in objects (i think), which is what I assume causes Life to favour even sizes, but from plotting a graph similar to yours with my census results for 2x2, it's much more linear. Am I just missing something obvious?
Well... how does this sound? The 2x2 rule is B36/S125, which includes birth on an even neighbor count, as well as an odd neighbor count as in Conway's Life. This means that a bilaterally symmetric pattern in 2x2 can recover live cells along its (orthogonal or diagonal) spine.

In B3/S23, as soon as all spinal-column cells are turned off (which tends to happen pretty quick due to overcrowding) they can never turn back on again without some external non-symmetric influence. So any symmetric still life that forms will be even-sized. You'll only get odd-sized symmetric B3/S23 still lifes in those very rare cases where there's an odd number of surviving ON cells along the spine.

By contrast, in the 2x2 rule the ratio of odd:even spine cell count seems likely to be much closer to 1:1 (not that I've checked) -- because spine cells can easily turn back on again.

Does that look like a good enough theory to explain the bias toward even cell counts? Or are there also significantly more even-sized asymmetric still lifes in Conway's Life? I haven't dared to look, because that would leave me fresh out of crackpot theories.
Lewis wrote:Also, just out of curiosity, if you've got a text file similar to the one above for still lifes, but with counts for ships/oscillators/switch engines etc. could you please post it?
It may take a few days, but I'll adjust my script and post those results soon. Might also collect the soup seeds for all the objects seen only once or twice, in case any of them turn out to be particularly rare and interesting.

MikeP
Posts: 105
Joined: February 7th, 2010, 9:51 am
Location: Ely, Cambridgeshire, UK

Re: apgsearch: a high-performance soup searcher

Post by MikeP » November 22nd, 2014, 10:25 am

dvgrn wrote:The Snark catalyst is 31 or 34 bits for the common versions, I believe, and no doubt we could come up with hundreds of variants with slightly higher bit counts.
Far more than hundreds. The catalyst itself only consists of about half the live cells; the others are there to stabilise the edges. I was thinking of looking for any still life with the same catalytic region, not an exact match.

Of course this might complicate apgsearch a bit; I haven't looked at it that closely.

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: apgsearch: a high-performance soup searcher

Post by dvgrn » November 23rd, 2014, 10:47 am

MikeP wrote:
dvgrn wrote:The Snark catalyst is 31 or 34 bits for the common versions, I believe, and no doubt we could come up with hundreds of variants with slightly higher bit counts.
Far more than hundreds. The catalyst itself only consists of about half the live cells; the others are there to stabilise the edges. I was thinking of looking for any still life with the same catalytic region, not an exact match.
But none of them have fewer than 31 ON cells, right? Is there more than one 31-bit version? If not, I think the same probability estimate still applies.

Odds of a still life being the one 31-bitter:
1/20 billion/1.7 billion 31-bit objects = 1 / 34 quintillion = 3.4e-19

Odds of a still life being a particular 34-bitter:
1/200 billion/24 billion 34-bit objects = 5e-21

Let's say there aren't any 32- or 33-bit Snark catalysts, but then a couple of 34-bit versions, four with 35 bits, eight with 36 bits, and so on.

The number of B3/S23 still lifes with N bits seems to be around 2.4^N/360.

If we use an exponential frequency estimate for N-bit still lifes of 2^-N -- a little more optimistic than 10^(-N/3) --then for N>=34, that gives us a nice formula, very simple and very very approximate:

frequency = 2^(N-33) * 2^(-N) * 360 * 2.4^-N = 4e-8 * 2.4^-N

Add that up for all N>=34, and it still looks like you'd probably see a dozen or so of the 31-bit Snark catalysts before you see the first one with any higher number of bits. To see the first 31-bit Snark catalyst, according to the 3.4e-19 number above, I'd most likely have to search a few billion times longer than I have so far. [I've seen just ~10^10 still lifes go by, so that leaves a factor of 10^9, and unfortunately that does not mean I'm over halfway there...!]

-- Of course this is all based on the unlikely assumption that all N-bit still lifes are equally likely to appear. Really Snark catalysts in general seem significantly less likely than many other still lifes with the same bit count, so the next refinement would still seem to be an estimate based on relative glider construction recipe costs.

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: apgsearch: a high-performance soup searcher

Post by dvgrn » November 23rd, 2014, 10:10 pm

dvgrn wrote:...I'll adjust my script and post those results soon. Might also collect the soup seeds for all the objects seen only once or twice, in case any of them turn out to be particularly rare and interesting.
A first draft is attached. The total number of objects is 36443746853, just at the moment, with 2996 different apgcodes.

I'll have to look at the high-period items again -- hadn't noticed (or remembered) that there's a "y" and a "q" object for each switch engine type. But anyway it looks as if I'll be past the 3000-object mark fairly soon.

I had a quick look through the oscillator list again; the rarest and most interesting one is maybe the fumarole -- soup ID 17Mf3707357.
Attachments
Still-life-and-oscillator-all.txt
Census of 36 billion still lifes and oscillators
(62.05 KiB) Downloaded 434 times

flipper77
Posts: 197
Joined: October 24th, 2010, 3:25 am
Location: Spokane, WA

Re: apgsearch: a high-performance soup searcher

Post by flipper77 » November 26th, 2014, 8:13 pm

I'm almost ready to post an updated common names dictionary that involves the link Adam posted earlier(I added the oscillators manually, since there were < 200, although that was before I knew Python, the script is mainly for sl's). On the pdf, many objects contain cumulative counts, which will be used to give objects reasonable scores, and my script catches all associated object counts. At this point in time, all I literally need is a good way to score objects based on how many times the document has seen these objects, because I agree to the fact that sufficiently rare still lives require a decent score.

User avatar
calcyman
Moderator
Posts: 2929
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch: a high-performance soup searcher

Post by calcyman » November 27th, 2014, 9:01 am

What about this heuristic?

If there are at most 2^(20 - n) occurrences of a particular still-life in Okrasinski's census, award it n points (and obviously choose the largest n for which this is true).
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Extrementhusiast
Posts: 1966
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: apgsearch: a high-performance soup searcher

Post by Extrementhusiast » November 27th, 2014, 2:00 pm

calcyman wrote:What about this heuristic?

If there are at most 2^(20 - n) occurrences of a particular still-life in Okrasinski's census, award it n points (and obviously choose the largest n for which this is true).
Obviously, if an object is not in said census, a different scheme will have to be used, as you can't just go around giving those objects an infinite number of points. What about relating it back to apgsearch, where the value is determined by the frequency in the next n soups?

Or, perhaps a simpler fix: change it to "if there are at most 2^(20 - n) - 1 occurrences of an object in that census, award it n points", so as to get rid of the singularity at zero, by moving the infinity point to where an object has a negative number of occurrences (which cannot happen).

EDIT: Just found a pretty major bug, where an MWSS fails to be identified, and so ContagiousLife et al runs for over 2^32 generations, while leaving an ever-growing trail (in the shape of the history of an MWSS) of state 4 cells behind the front end. What's more, typing 's' or 'q' doesn't do anything. (Unfortunately, I didn't save the seed number, but I think I started the search at around 6 PM last night (definitely between 11 AM and 7 PM (although given the last visit time to the forums as being 3:25 PM, that might be closer to the actual cutoff)), definitely didn't change the seed number from the default (of the form 2014-11-28T??:??:??.???000_), and it got stuck in this loop after it had processed 5642300 soups.) Perhaps instituting a suitably large cutoff time (2^24 generations?) would be a good patch for this until the error can be figured out.
I Like My Heisenburps! (and others)

User avatar
calcyman
Moderator
Posts: 2929
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch: a high-performance soup searcher

Post by calcyman » November 29th, 2014, 11:46 pm

That's bizarre. It's supposed to give up long before 2^20 generations, identifying any remaining chaos based on its population growth. I have no idea why the script would run Golly for more than 2^32 generations.

You should be able to determine the seed as progress is saved every 250 000 generations. So just look for the most recent file in your apgsearch progress directory.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Extrementhusiast
Posts: 1966
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: apgsearch: a high-performance soup searcher

Post by Extrementhusiast » November 30th, 2014, 2:52 pm

Found the seed: it's 2014-11-28T14:08:58.074000_. (Without the final period, of course.) I shall test it to see if the problem recurs.

EDIT: Can't seem to jump to the middle, so I'd have to start it from the beginning. Considering that I've already got a search running, I'll hold off on it for now.
I Like My Heisenburps! (and others)

Post Reply