apgsearch v1.0

[dvgrn]

In other Catagolue news, we now have a pie chart to display which contributors have submitted the most objects... I've heard rumours (or should that be 'rumors', since this is happening in the US?) that Dave Greene might be procuring large amounts of computing power reasonably soon, so it would be interesting to see how the b3s23/C1 pie chart changes over time.

That may remain a rumor for a while yet, unfortunately, since the "easy" pools of computers I can use at the University mostly don't have Python installed -- how silly is that? -- and I don't have admin access to install it.

I might be able to get access to the University's high-performance clusters temporarily, and they do have Python installed and would be able to skew those pie-chart stats very quickly indeed. But that may not work out either.

Meanwhile, what I've done so far has been a mere 8-CPU effort, spread across three computers in my office that are seriously overpowered for the work they generally do. Surely someone reading this has more multicore computers that within reach, that are similarly underused? If I set apgsearch running on three CPUs on a quad-core machine, there's generally not even a noticeable performance hit.

Surprisingly, after all this search activity, the the highest still-life bit count is still only 32. Statistically speaking, something bigger ought to be showing up any time now...!

[rowett]

Surely someone reading this has more multicore computers that within reach, that are similarly underused?

Perhaps BOINC could be a future goal?

Chris

[calcyman]

I'm currently running apgsearch on 18 CPUs, namely my dual-core laptop together with four quad-core computers surrounding me at the time of writing (but those are in a public location, so I'll need to terminate the search when I exit the room in about 15 minutes or so).

Surprisingly, after all this search activity, the the highest still-life bit count is still only 32.

Indeed, although Okrasinski's census only found 6 instances of still-lifes with more than 32 cells, and Catagolue is only 7% of the way to catching up with Okrasinski's census, so this isn't surprising at all.

Statistically speaking, something bigger ought to be showing up any time now...!

Markov property, Dave...

Perhaps BOINC could be a future goal?

Excellent idea. We're already putting a high load on Catagolue (frighteningly close to the free limits imposed by Google), so pretty soon I'll need to enable billing. Indeed, we're only 42% of the way through the day, but have already used 47% of the quota for Datastore write operations.

[calcyman]

Warning: there may be some server downtime in the next few hours due to Google-imposed daily quota limits. Don't be alarmed; apgsearch retains its progress if it can't contact Catagolue properly, and the information already in Catagolue will remain unaffected, so it shouldn't be the case that any progress is lost.

Screenshot of quota details

quota.png (42.6 KiB) Viewed 17284 times

Basically, Catagolue is already getting too popular for the free limits, so I'll need to enable billing. This only costs epsilon (i.e. a few pence per day on average), so I'm entirely willing to fund this, but due to annoying tax reasons they only allow companies or non-EU individuals to sign up for this.

[dvgrn]

Statistically speaking, something bigger ought to be showing up any time now...!

Markov property, Dave...

Bah. I mean, um... the number of soups being searched per hour has been continuing to increase lately, so statistically speaking, the per-hour probability of a 33-cell-plus still life appearing is higher now than it was a few days ago.

-- Also, we're up over 36 billion still lifes now. By the time I'd searched 22 billion soups on my own machine, a 40-cell still life had showed up, and A for awesome had run into the same one, derived from a very simple symmetrical pi-plus-two-blinkers reaction.

Seems as if spontaneous conversion to a symmetrical reaction will account for a larger and larger fraction of the high-bit-count still lifes, as the bit count gets higher. This is likely to mess up the nice power law somewhat, isn't it?

It's clear that it's far more likely that a reaction will "go symmetric", than that a soup will happen to start out exactly symmetrical... but I have no idea how to go about calculating the contribution of spontaneous symmetry to the high-bit-count census. Maybe the various tricksy ssssymmetric censuseses will turn out to have nice power laws themselves, which might give a clue about their contributions.

[HartmutHolzwart]

Just a few ideas on modifications:

1) How would the statistics change if we switch form an initial square to an initial diamond?

2) What would be the outcome starting with a 8x32 rectangle? Or symmetric 8x64? The idea is that one dimension should be fixed, but buig enough to allow enough variety. So 4 is maybe too small, 16 too big.

3) What if we initialy "fence" the random initial pattern with a regular agar? The fence will be destroyed, but will give rise to different patterns (at least the pattern will arise with different likelihoods).

Btw.: Great work! And apgsearch should give related rules a headstart wrt. to CGOL, where we didn't have this sort of tool for 20+ years.

[dvgrn]

By the time I'd searched 22 billion soups on my own machine, a 40-cell still life had showed up, and A for awesome had run into the same one, derived from a very simple symmetrical pi-plus-two-blinkers reaction.

Well, this is strange. So much for my theory about convergence to simple "bottleneck" predecessors... I hadn't actually retrieved the soup for my copy of that symmetric 40-cell still life, out of my pre-Catagolue search results. It turns out that there's no commonality between the two construction methods whatsoever:

Code: Select all

#C Two construction methods for xs40_gj1u0u1jgzdlgf0fgld
#C No convergence at all -- different even after the penultimate tick (!)
#C [[ THUMBNAIL HEIGHT 300 AUTOSTART GPS 2 LOOP 30 ]]
x = 33, y = 25, rule = B3/S23
30b2o$30b2o2$28bo$29bo$27bo2bo$26b2obobo$27bo3b2o$3bo18bo3bo5bo$5bo16b
2o2bo4bo$bo4bo17bo$3bobo$2obob2o2b2o$4bob2obo$8b2o14bo$8bobo11b2o2bo4b
o$22bo3bo5bo$27bo3b2o$26b2obobo$27bo2bo$29bo$28bo2$30b2o$30b2o!

So... the only 40+-cell still life that nonsymmetric apgsearching has found so far, is eight cells heavier than its nearest competitor (is that really true, or has there been another find with 33+ cells?) making it very unlikely to appear according to the naive power law formula. And yet it has showed up twice, using two completely independent mechanisms.

Okay. If Catagolue turns up this same 40-bitter ahead of schedule again (before 34-, 36-, or 38-bit objects) and if it turns out to be a third independent synthesis reaction, then somebody is trying to tell us something. No idea what, though... maybe it's just "this is the most likely way to stabilize a very long induction coil."

Code: Select all

#C seed for 40-cell xs40_gj1u0u1jgzdlgf0fgld = 16Mc10089581
x = 16, y = 16, rule = B3/S23
7o4b2o$b6o5b3o$ob3ob2ob2o2bo$b3o2bob3ob2obo$2b7obob2obo$o2bobobob2ob3o
$bob5o4bo$2obo6b3obo$o2bob3o5bobo$5b3obobo$2b3obob2ob2ob2o$o2bobo5bo3b
o$bobob2o2bobo2bo$b3obobo6bo$o3bo3b3o3b2o$3b3o2bobo3bo!

By contrast, my pre-Catagolue searches also eventually turned up a 32-bit still life -- another long induction coil crystallized out of a small symmetric region in an asymmetric soup. This one is not the same as the 32-bitter that Catagolue has found, which is somehow vaguely reassuring. It's very reminiscent of the 40-bitter, though:

Code: Select all

#C seed for 32-cell xs32_039u0u93z6a87078a6 = 11Mj607782
x = 16, y = 16, rule = B3/S23
obo2bob4ob3o$bobob2o3bo2b3o$o2b2o4bo3bo$3bob3obobo$2obo3b3obo$b7ob2obo
b2o$o3b3obobob4o$ob4o2b2obob2o$2o2bob2ob7o$obobobob2ob2ob2o$bo2bo5bo3b
2o$4b2o5b2o$4o3b4ob4o$2b2ob2o2bobo$2bob6o$2obob3ob2obobo!
#C [[ THUMBNAIL AUTOSTART X 60 ZOOM 6 GRID GRIDMAJOR 10 ]]

[calcyman]

Warning: there may be some server downtime in the next few hours due to Google-imposed daily quota limits. Don't be alarmed; apgsearch retains its progress if it can't contact Catagolue properly, and the information already in Catagolue will remain unaffected, so it shouldn't be the case that any progress is lost.

As expected, it went over quota at 05:10 UTC, and back online at 08:00 UTC. This doesn't seem to have caused any damage: there were 20 failed attempts to upload hauls this morning, but it's clear that the progress wasn't lost since a few 4000000-soup hauls have appeared (since apgsearch failed to upload the first 2000000, it continued for another 2000000 before successfully reattempting to upload).

So I guess for the moment the quota is more of an annoyance than anything else, but it could be crippling if search power increases much beyond the current state. In particular, if the Datastore 'read' operations run out (as opposed to the 'write' operations), the webpages won't work correctly.

And yet it has showed up twice, using two completely independent mechanisms.

The common 40-bitter appeared thrice in Okrasinski's census, along with another 40-bit still-life:

Code: Select all

.##.....##.
#.#.....#.#
#....#....#
.#########.
...........
.#########.
#....#....#
#.#.....#.#
.##.....##.

-- Also, we're up over 36 billion still lifes now.

What? We're at 41 billion objects, but a third of those should be oscillators (mostly blinkers).

2) What would be the outcome starting with a 8x32 rectangle? Or symmetric 8x64? The idea is that one dimension should be fixed, but buig enough to allow enough variety. So 4 is maybe too small, 16 too big.

I could introduce 8x32 as a new 'symmetry', I suppose.

[dvgrn]

-- Also, we're up over 36 billion still lifes now.

What? We're at 41 billion objects, but a third of those should be oscillators (mostly blinkers).

Oops. Well, I just have to survive being wrong for a short embarrassing stretch of time here -- I'll be right by next week.

8x32 might be interesting to experiment with. I'd expect a slight increase in big symmetrical still-life counts, but not too much difference otherwise.

There are lots of other possible lines of research along the same lines. For example, what about initial densities other than 50%? It would be a little fiddly to get a guaranteed-random attenuation or thickening of the SHA-256 bit pattern to hit an arbitrary density, but percentages like 25% or 75% should be easy enough -- superimpose a rotated copy of the soup on itself, maybe?

[Kazyan]

The 40-cell still life just showed up, and it's the Pi + 2 blinker reaction again. No need to panic about the island of stability yet.

[rowett]

I've been running this now for a few days. Excellent work I must say putting this all together. A couple of questions:

1. How do I make it so my name appears on the results rather than my email address?
2. Would it be possible to see in the results when you are the first to discover a certain object? It would be motivating (sad, but true) to know that your CPU was the first to add a certain object to the Catagolue.

Best regards,
Chris

[wildmyron]

1. How do I make it so my name appears on the results rather than my email address?

When you create your payosha256 key at http://catagolue.appspot.com/payosha256 you have the opportunity to enter a display name. There doesn't seem to be a way to update that (overwriting your key sounds ominous if you want to retain history of contributions) but seeing as payosha256 seems to be calcyman's creation, I think you'll need to wait for a response from him.

@calcyman: Fantastic job with Catagolue and apgsearch. Thank you for putting in the effort to polish this project. Do you still envision creating a CAsh cryptocurrency based on the soup search or has the project morphed into something entirely different?

[dvgrn]

There doesn't seem to be a way to update that (overwriting your key sounds ominous if you want to retain history of contributions)...

Hmm, you're right. I just tried changing my display name by overwriting with the same key, and now I have two slices of pie instead of one. No other bad effects that I can see, though -- new contributions show up in the haul list just fine under the new name.

[gameoflifeboy]

This is listed as a sample soup that produces a cis-queen bee shuttle, but it doesn't.

Code: Select all

x = 31, y = 31, rule = B3/S23
ooobbboobboobbbobobbbooooboobbo$
oooooooboobbobbboboobbbobbbobob$
oooboobbboobobbooooobbobboboobb$
bobbbbobobbbobobooobboobbbbbooo$
boobbobboobooboobobbbboooobbbbo$
boobooobbobbbbbobobobbooboobobb$
oobobobbboobbobobbobbbbbbbobbbo$
obbbbbbobbooobooobboooooboobboo$
boboobbbbbbobbobooobooboboooobo$
boobooobbooobbobbbbboooobbbobbo$
obobbboobooobbbobbbooooobbbbbbb$
obbbobbooooooooobbooobbobobboob$
boooobbobbbobboobobobbobobbooob$
bbbbbbobbbbobbbobbobbbobboooobo$
bbboobboooboobooobbbbboobbbooob$
oboboooobbooooooooooobboooobobo$
booobbboobbbbboooboobooobboobbb$
oboooobbobbbobbobbbobbbbobbbbbb$
booobbobobboboboobbobbbobboooob$
boobbobobbooobbooooooooobbobbbo$
bbbbbbbooooobbbobbboooboobbbobo$
obbobbboooobbbbbobbooobboooboob$
obooooboboobooobobbobbbbbboobob$
oobboobooooobbooobooobbobbbbbbo$
obbbobbbbbbbobbobobboobbboboboo$
bbobooboobbobobobbbbbobboooboob$
obbbboooobbbboboobooboobbobboob$
ooobbbbboobbooobobobbbobobbbbob$
bboobobbobbooooobboboobbboobooo$
bobobbbobbboobobbbobboobooooooo$
obbooboooobbbobobbboobboobbbooo!

[dvgrn]

This is listed as a sample soup that produces a cis-queen bee shuttle, but it doesn't.

Uh-oh -- might have to start the whole census over now... all right, probably not. Wonder if this is the same problem that caused the missing rockets in Day and Night?

Would it be possible to see in the results when you are the first to discover a certain object? It would be motivating (sad, but true) to know that your CPU was the first to add a certain object to the Catagolue.

I don't care so much about getting my name in the spotlight for particular discoveries -- or that's what I tell myself, anyway -- but I would definitely like to have an easy way to tell when new things are discovered.

It would be nice to have each object page credit the first person who sent in a soup containing that object, as per Chris' suggestion. A summary page of the latest new objects would also be interesting: anything that has come in recently that Catagolue has never seen before, let's say. There should be at least a few new objects cropping up every day, for quite a while yet.

I kind of miss the scoring system on the old apgsearch. I had hacked my copy of the script so that it included a link to the highest-scoring soup in a haul, right at the top of the census HTML page. Usually it turned out to be something with a score in the low to mid 30's, and that was generally just the rare soup that produced several pulsars and/or a pentadecathlon and/or multiple *WSSes going their separate ways and/or a big still life or two. It was fun when a higher-scoring soup cropped up, even a trivial combination one.

Certainly it'd be good to give top billing in B3/S23 (C1) to any new "y" or "xq" discoveries, or at this point any new "xp" periods. Did any previous soup searches turn up periods not yet on the current list, besides the high-period glider-block cycle that was presumably an artifact of running on a torus?

[Kazyan]

The last holdout for the 11-bit objects is the hook-with-tail-except-there-are-two-hooks-this-time. I notice that hooks are a very uncommon motif for Life; this one might take a while.

[calcyman]

Here are a few updates:

• apgsearch v1.03 includes a new symmetry type, 8x32, as suggested by Hartmut Holzwart.
• High-scoring soups are collected by Catagolue for B3/S23 (since the scoring system does not work particularly well for other rules yet). The highest 1000 are displayed on the census page.
• The /census endpoint now includes a list of recently-updated censuses in addition to the most popular censuses.

Also, I would like to announce that after less than a fortnight of operation, Catagolue is almost halfway to catching up with TOLLCASS.

[gameoflifeboy]

What's TOLLCASS?

EDIT: Oh wait, I just figured it out. Never mind.

I didn't even know TOLLCASS got farther than the Catagolue, or even Achim's search for that matter!

[Scorbie]

So... the only 40+-cell still life that nonsymmetric apgsearching has found so far, is eight cells heavier than its nearest competitor (is that really true, or has there been another find with 33+ cells?)

At www.geocities.ws/conwaylife (this is TOLLCASS, right?) the biggest still lifes were two instances of the 40-bitter found here and a 34-bitter. Hope that tells us something.

[dvgrn]

At http://www.geocities.ws/conwaylife (this is TOLLCASS, right?) the biggest still lifes were two instances of the 40-bitter found here and a 34-bitter. Hope that tells us something.

TOLLCASS is The Online Life-Like Cellular Automata Soup Search (so you can see why it tends to get abbreviated.)

The geocities link is to the results of Andrzej Okrasinski's screen-saver soup search -- a census for ash from 12+ billion 20x20 soups, run between 2004 and 2008 or so. Catagolue isn't halfway to that 12-billion-soup goal yet, but it's quickly closing in on the 1/3 mark.

[calcyman]

Catagolue isn't halfway to that 12-billion-soup goal yet, but it's quickly closing in on the 1/3 mark.

Okrasinski's search examined 20 billion soups, so we're only 20% of the way to that goal. But since Catagolue has only been running for two weeks, we shouldn't be too disappointed.

In terms of objects (the only reasonable comparison since Achim's searches were toroidal and the other soups were 20-by-20 instead of 16-by-16), the order is as follows:

• Okrasinski (477 billion objects)
• TOLLCASS (176 billion objects)
• Catagolue (91 billion objects at the time of writing)
• Achim 2004 (50 billion objects)
• Achim 1994 (5 billion objects)

At the current rate, we can expect 2000 billion objects by the end of 2015.

[simsim314]

It seems the link to apgsearch is broken (I couldn't download it).

EDIT Woops sorry it was bug on my system.

[Andrew]

Catagolue (91 billion objects at the time of writing)

I'm more interested in the number of unique objects, and how often such objects are turning up, so I've written the following script:

Code: Select all

# Scan pages at http://catagolue.appspot.com to determine the number of
# unique objects found for a specified rule and symmetry.

# NB. Doesn't detect new zz_LINEAR objects.

import golly as g
import urllib2
import re

census_prefix = 'http://catagolue.appspot.com/census/'
object_prefix = 'http://catagolue.appspot.com/object?apgcode='

# prompt for rule and symmetry
inifile = g.getdir('data') + 'scan-catagolue.ini'
rule_sym = 'b3s23/C1'
try:
    f = open(inifile, 'r')
    rule_sym = f.readline()
    f.close()
except:
    # should only happen 1st time (inifile doesn't exist)
    pass

rule_sym = g.getstring('Enter the desired rule and symmetry\n' +
                       '(eg. b3s23/C1):', rule_sym, 'Enter rule/symmetry')
if len(rule_sym) == 0:
    g.exit()

# remember specified rule/symmetry for next time
try:
    f = open(inifile, 'w')
    f.write(rule_sym)
    f.close()
except:
    g.warn('Unable to save rule and symmetry in file:\n' + inifile)

objfile = g.getdir('data') + 'catagolue-' + rule_sym.replace('/','-') + '.txt'
old_objects = []
try:
    f = open(objfile, 'r')
    contents = f.readlines()
    f.close()
    for line in contents:
        old_objects.append(line.partition('\n')[0])
except:
    # should only happen 1st time
    pass

url = urllib2.urlopen(census_prefix + rule_sym)
census_data = url.read()

htmlfile = g.getdir('temp') + 'obj.html'
f = open(htmlfile, 'w')
f.write('<html>\n<title>' + rule_sym + '</title>\n<body>\n')
f.write('<p>Object prefixes and counts...<br>\n')

obj_names = []
new_objects = []
ocount = 0

# find all object prefixes
for oprefix in re.findall('<a href="/census/' + rule_sym + '/(.*?)"', census_data):
    pagename = census_prefix + rule_sym + '/' + oprefix
    g.show('scanning ' + pagename)
    url = urllib2.urlopen(pagename)
    obj_data = url.read()
    f.write(oprefix + ' : ')
    pcount = 0
    # find all object names on this page
    for obj_name in re.findall('<a href="/object/(.*?)/', obj_data):
        obj_names.append(obj_name)
        if len(old_objects) > 0 and not (obj_name in old_objects):
            new_objects.append(obj_name)
        pcount += 1
    f.write(str(pcount) + '<br>\n')
    ocount = ocount + pcount

g.show('done')

# save all object names in a text file
ofile = open(objfile, 'w')
for obj in obj_names:
    ofile.write(obj + '\n')
ofile.close()

f.write('</p><p>Total number of objects: ' + str(ocount))

if len(new_objects) > 0:
    f.write('</p><p>New objects have been found since last scan:<br>')
    rule = rule_sym.partition('/')[0]
    for obj in new_objects:
        # show link to object in Catagolue
        f.write('<a href="' + object_prefix + obj + '&rule=' + rule + '">' + obj + '</a><br>\n')
elif len(old_objects) > 0:
    f.write('</p><p>(No new objects found since last scan.)')

f.write('</p><p>All object names are saved in <a href="edit:' + objfile + '">' + objfile + '</a>')
f.write('</p></body>\n</html>\n')
f.close()

g.open(htmlfile)

The idea is you run it once a day or so to see if any new objects have been found. The script creates its output in Golly's help window, and looks something like this (if given "b3s23/C1"):

Code: Select all

Object prefixes and counts...
xs10 : 25
xs11 : 45
xs12 : 114
xs13 : 181
xs14 : 344
xs15 : 433
xs16 : 514
xs17 : 533
xs18 : 510
xs19 : 441
xs20 : 397
xs21 : 293
xs22 : 216
xs23 : 136
xs24 : 75
xs25 : 37
xs26 : 25
xs27 : 18
xs28 : 15
xs29 : 5
xs30 : 4
xs31 : 2
xs32 : 2
xs4 : 2
xs40 : 1
xs5 : 1
xs6 : 5
xs7 : 4
xs8 : 9
xs9 : 10
xp14 : 1
xp15 : 1
xp2 : 72
xp3 : 10
xp30 : 2
xp4 : 4
xp5 : 1
xp6 : 1
xp8 : 3
xq4 : 5
yl144 : 1
yl384 : 1

Total number of objects: 4499

(No new objects found since last scan.)

All object names are saved in /Users/akt/Library/Application Support/Golly/catagolue-b3s23-C1.txt 

If any new objects have been found then it will show links into the appropriate object pages.
Hopefully something like this capability will eventually get built into the Catagolue.

[calcyman]

How on Earth did Chris Rowett manage to submit a haul containing a number of soups not divisible by 100?!

http://catagolue.appspot.com/haul/b3s23 ... bbdeb94ada

Hopefully something like this capability will eventually get built into the Catagolue.

Yes, not least because that script puts an immense load on my server (generating animated SVGs of all objects). I'm going to change those pages so they only display a limited number of objects (say, 100 or so) but have buttons so you can navigate deeper down the list. I'll provide a text-only interface which gives you all objects from all tabulations in descending order of frequency.

In future, if you want to programmatically extract information from Catagolue, I'll give you a nice machine-readable endpoint. That's vastly better than scanning through HTML pages containing lots of animated SVGs.

[rowett]

How on Earth did Chris Rowett manage to submit a haul containing a number of soups not divisible by 100?!

Well after reading the comment in your code that said:

Code: Select all

# We have 100 soups per page, instead of one. This parallel approach
# was suggested by Tomas Rokicki, and results in approximately a
# fourfold increase in soup-searching speed!
sqrtspp = 10
spp = sqrtspp ** 2

I decided to see if it was any faster to try a larger number of soups per page.

Code: Select all

This haul was submitted by crowett@gmail.com on 2015-03-06 at 09:16:10 UTC. It contains 2340667 objects generated from 106496 soups.

106496 is not divisible by 100 but it is divisible by 256...

Sadly from my testing it made only a negligible performance improvement.

Best regards,
Chris