apgsearch v1.0

[Alexey_Nigin]

...by an order of magnitude...

This was definitely an overestimate.

[apg]

After noticing that about half of the Catagolue's stored data (roughly one gigabyte at the time of writing) is just sample soup data for a shedload of random amorphous Day and Night objects, I've now implemented a change:

• New sample soups are only added to the database when the corresponding tabulation is less than 980K in size.

The reasoning is that if we've seen 40000 different period-2 oscillators in a rule, then we can safely say that period-2 oscillators are no longer interesting. (This new limit is ignored for B3/S23, because Catagolue is intended to be completely comprehensive for standard Life.)

This should save immensely on the datastore size and read/write operations, thereby increasing the cost efficiency. It appears to have resulted in a 20-fold reduction in the number of datastore entities written per haul for b3678s34678/D2_+1:

• 6873, 6877, 6707, 6731, 6848, 6816, 6987, 6840, 6806, 309, 314, 308, ...

In other news, the b3s23/C1 census is now five times larger than Okrasinski's five-year search (Nov 2003 -- Dec 2008) over at http://www.geocities.ws/conwaylife/lf020n.pdf. Thanks to biggiemac (for four of those multiples) and everyone else (for the remaining multiple) whose CPU time has been invaluable in the collection of these results.

[Extrementhusiast]

In other news, the b3s23/C1 census is now five times larger than Okrasinski's five-year search (Nov 2003 -- Dec 2008) over at http://www.geocities.ws/conwaylife/lf020n.pdf. Thanks to biggiemac (for four of those multiples) and everyone else (for the remaining multiple) whose CPU time has been invaluable in the collection of these results.

...and all this in less than five percent of the old time interval.

[biggiemac]

Now that I've graduated and moved out, I've left that lab unattended. We'll see how long into the summer they last before they are shut off, if at all.

[apg]

Now that I've graduated...

Congratulations on your graduation!

We'll see how long into the summer they last before they are shut off, if at all.

Probably until the next Windows Update operation causes a mass restart.

[gameoflifeboy]

On May 16 I apgsearched 2256859 soups on Day & Night, under symmetries D2_+2. The haul, being 13 megabytes, was too big to upload to Catagolue, but I will probably upload it as an attachment soon.

[wildmyron]

A few minor Catagolue website issues:

• http://catagolue.appspot.com/ is not very useful. Perhaps it could auto-redirect to http://catagolue.appspot.com/home instead of requiring the logo to be clicked upon.
• The handling of invalid characters in the apgcode seems inconsistent, e.g. entering "xp4_8eh5e0e5he8z178a707a871 " (apgcode for cloverleaf with an appended <space> character) loads the page http://catagolue.appspot.com/object?apg ... rule=b3s23 which shows an animated svg for the object and names it correctly, but lists 0 occurrences in the database.
• Object search doesn't check if the provided apgcode is given in canonical form, e.g. http://catagolue.appspot.com/object/xs1 ... y056/b3s23 shows an image of a flipped very^3 long snake, but lists no occurrences in the database, whereas http://catagolue.appspot.com/object/xs10_wg853z65/b3s23 has over 300 occurrences. I suppose this is an invalid apgcode, but in other instances where an invalid apgcode is provided (e.g. xp2_33 or xs5_33 - but not xp1_33), Catagolue gives an invalid apgcode error.

I think it's great to have some data integrity checking implemented. I don't have any further suggestions in that area but it's certainly more important than the above mentioned issues.

[apg]

It appears that someone is spamming /textcensus with GET requests to lots of rulestrings, many of which have not even been investigated (or worse, are nonsensical). I received about 40000 requests over a three-hour period:



Well, I decided to do some investigation. The requests originated from the IP address 97.119.146.54. Trawling the logs for the regex "97/.119/.146/.54" eventually finds legitimate activity generated by apgsearch:

Code: Select all

97.119.146.54 - - [21/May/2015:10:53:36 -0700] "POST /apgsearch HTTP/1.1" 200 131 - "Python-urllib/2.7" "catagolue.appspot.com" ms=141 cpu_ms=30 cpm_usd=0.000015 app_engine_release=1.9.21 instance=00c61b117c1a9f728fefc9dc27632484967ea9c9

So the haul was uploaded at 17:53:36 UTC, which means I can just check Catagolue's haul records for a haul uploaded at that precise time. This turned out to be easier than I expected:

http://catagolue.appspot.com/haul/b36s12/C1?committed=2

In conclusion, it appears that EricABQ has been spamming /textcensus for no apparent reason...?

Perhaps it could auto-redirect to http://catagolue.appspot.com/home instead of requiring the logo to be clicked upon.

Excellent idea. Implemented.

Object search doesn't check if the provided apgcode is given in canonical form

Oh, it gets much worse: http://catagolue.appspot.com/object/xq4_27deee6/b3s32

And even though it rejects invalid apgcodes such as xp5_33, it accepts other names without any difficulties (basically for expansion purposes) and allows you to comment on the resulting 'this pattern is a pattern' page:

http://catagolue.appspot.com/object/cabbage/b3s23

I think it's great to have some data integrity checking implemented.

You mean verifying that the hauls posted to /apgsearch are actually genuine? I agree; that's what I'm working on at the moment.

On May 16 I apgsearched 2256859 soups on Day & Night, under symmetries D2_+2. The haul, being 13 megabytes, was too big to upload to Catagolue, but I will probably upload it as an attachment soon.

Why?

[gameoflifeboy]

In conclusion, it appears that EricABQ has been spamming /textcensus for no apparent reason...?

That's me. I'm sorry if it caused any problem, I was trying out a script that accessed all possible rules to see if they were searched. I thought it was a good idea at the time.
I stopped the script now. I hope no lasting damage was done.

[apg]

Version 1.1 of apgsearch has now been released. This contains a bug-fix and a new feature:

Bug-fix: I think I know why apgsearch has been so inexplicably bug-ridden. I've only just discovered (the hard way!) that Python treats variables declared in the body of the class as static (meaning that they're shared across all instances of the class), which is not how I wanted it to behave. The updated version, apgsearch v1.1, now addresses this issue by using an explicit __init__ constructor.

New feature: Hauls uploaded to b3s23/C1 are now peer-reviewed by instances of apgsearch v1.1 (even those running different (rulestring, symmetry) combinations) to ensure the validity of the data.

Catagolue will still accept hauls uploaded by v1.0, of course -- but they need to be verified by an instance of apgsearch v1.1 before they are committed to the census.

So it's now basically impossible for a nefarious hacker to attempt to sabotage b3s23/C1 with spurious claims of 13-snakes, phoenixes and Simkin glider guns.

All other ordered pairs of the form (rulestring, symmetry) are still unprotected... but they're considerably less valuable in terms of total computational effort.

[biggiemac]

All my instances will still be running 1.0 until at least mid August if not September.

[biggiemac]

Does the verification process only happen for soups above a certain measure of rareness?

[apg]

Does the verification process only happen for soups above a certain measure of rareness?

Every haul undergoes the verification process. In order to pass, all of the following must be true:

• The chi-squared test statistic for the 300 most common objects (by the ranking in /textcensus/b3s23/C1) must be below a certain threshold (500.0);
• Sufficiently rare objects (those not in the 240 or so most common objects) must have the parent soups peer-reviewed to ensure that those objects all occur the claimed number of times;
• No invalid apgcodes appear in the haul.

Note the intentional overlap between the sets of objects in the first two bullet points: there are objects which are both common enough to be used for the chi-squared test, and rare enough that we peer-review to check that they actually occurred that many times. We'll refer to these as medium-rare objects.

If insufficiently many medium-rare objects are reported, the haul will fail on statistical grounds. But for each medium-rare object reported, it is necessary to provide an actual sample soup for the peer-reviewing. Now, finding sample soups with a given prefix whose hash generates a medium-rare object is computationally difficult (there is no shortcut over just running lots of random soups, a la apgsearch); hence, this is a legitimate proof-of-work that the submitter has actually scoured the claimed number of random soups:

https://en.wikipedia.org/wiki/Proof-of-work_system

Also, Catagolue doesn't allow duplicate uploads of the same haul prefix, so the proof-of-work is strictly non-reusable.

This is essentially the same proof-of-work I intend to use to implement a GoL-based cryptocurrency. Except for the cryptocurrency, extending the blockchain would require finding really rare objects (at least as uncommon as the tumbler, or possibly beyond if global gollypower increases).

[biggiemac]

So the number of CPU hours spent verifying a CPU hour of soup searching is minimal, I'm guessing like six orders of magnitude less? I'm mostly asking since my searches aren't participating in the verifying process yet, and I'm just hoping it isn't taking over all the other instances to keep up.

[apg]

So the number of CPU hours spent verifying a CPU hour of soup searching is minimal, I'm guessing like six orders of magnitude less? I'm mostly asking since my searches aren't participating in the verifying process yet, and I'm just hoping it isn't taking over all the other instances to keep up.

Each CPU-hour of computation takes about one CPU-second to verify (it took dsmiller 8 seconds to verify a 9-megasoup haul of yours, compared with an estimated 8 hours to actually produce the haul). So about 3.5 orders of magnitude rather than 6, but either way the verification takes a negligible amount of time.

And each instance of apgsearch v1.1 only attempts to verify up to 5 hauls between each submission, so it won't 'take over all the other instances to keep up'.

[Alexey_Nigin]

http://catagolue.appspot.com/census/b3s23

Where is 8x32?

[Extrementhusiast]

http://catagolue.appspot.com/census/b3s23

Where is 8x32?

25% and 75% are also missing, possibly due to the use of the % sign itself.

[biggiemac]

They're 25pct and 75pct now, although there were a couple hauls uploaded with percent signs that messed things up. The percent sign is only ever an escape character in urls.

[Alexey_Nigin]

It seems that I have noticed a bug.

For some reason, apgsearch separates the oscillator in the middle, finds out that halves do not work on their own, and marks the pattern as "PATHOLOGICAL".

[apg]

Then explain why the full oscillator occurs here in 29th position:

http://catagolue.appspot.com/census/b3s013/D4_+2/xp2

It seems that the frequency of bwbigmac hauls has decreased recently; could it be that several of the machines were interrupted?

[Alexey_Nigin]

Then explain why the full oscillator occurs here in 29th position:

I cannot explain it, but I am sure apgsearch separated "PATHOLOGICAL" oscillators. When I quitted the program, the list of unidentified objects was full of patterns like

Code: Select all

x = 6, y = 3, rule = B3/S013
2b2o2$6o!

[biggiemac]

It seems that the frequency of bwbigmac hauls has decreased recently; could it be that several of the machines were interrupted?

It would seem so I won't have access to that lab again for a couple months if ever. Maybe I could get a friend in the area excited about GoL and let them know that that lab is available.

[gameoflifeboy]

I don't know why, but for the past month or so, I've been unable to open many object lists, (like catagolue.appspot.com/census/b3s23/C1/xp2) on Firefox, on at least one computer, without it crashing. I'm still able to open them on Chrome, but does anyone else have this problem?

[gameoflifeboy]

"Beacon on something" from this soup can be called "Claw with long leg and cis-beacon down":

Code: Select all

x = 16, y = 16, rule = B3/S23
oobooboooobbbooo$
oooobobooobbbobo$
booobbbooboboooo$
oooooobbbooooobo$
obbobooboobbobob$
obobbobobooobboo$
ooobbooboboobooo$
bboboboooooobooo$
booooboobobooboo$
ooooboobbbobooob$
bobbbooboobooooo$
obobbboobobboboo$
bbobobobobbbbbbo$
bboobbboboboooob$
obbobbbobbbobbbb$
obobbobooooooboo!

[Extrementhusiast]

Found a slight bug: when trying out a new rule for the first time, it briefly samples some soups from regular Life before switching to the new rule.