Page 2 of 2

Re: Extending apgcodes to larger patterns

Posted: January 22nd, 2017, 6:05 pm
by praosylen
Here's yet another suggestion: For long strings of spaces, use 0y followed by two base-36 digits. If the number of spaces is over 36^2, use 00y followed by 3 base-36 digits; over 36^3 --> 000y followed by 4 digits; etc. For long strings of newlines, use 0z followed by a base-36 digit, and extend as needed with more leading zeroes as above.

Re: Extending apgcodes to larger patterns

Posted: January 22nd, 2017, 8:24 pm
by Apple Bottom
Image

Re: Extending apgcodes to larger patterns

Posted: January 22nd, 2017, 9:34 pm
by praosylen
Apple Bottom wrote:[xkcd]
I definitely agree. Sorry if I shouldn't have posted.

Re: Extending apgcodes to larger patterns

Posted: January 23rd, 2017, 6:28 am
by Apple Bottom
A for awesome wrote:I definitely agree. Sorry if I shouldn't have posted.
She's apples. :) It wasn't intended as criticism - and I do apologize if it came across as such -, just as an observation on how different, mutually-incompatible standards can arise.

As they say, perfect is the enemy of good -- and the road to hell is paved with good intentions.

Let's not overengineer apgcodes. They're good enough for what they do, the "greedy" extension is well-accepted and has desirable properties, and for extremely large patterns apgcodes are a poor fit anyway.

Re: Extending apgcodes to larger patterns

Posted: August 12th, 2017, 9:35 pm
by calcyman
I've implemented greedy apgcodes for larger patterns (including multistate patterns) in the upcoming v4.0 release, increasing the bounding box limit for oversized patterns from 40-by-40 to the following pair of constraints:
  • (width + 2) * (height + 2) <= 10000;
  • The resulting apgcode, without the prefix, cannot exceed 1280 bytes.
Apparently, Google App Engine increased their key length limit from 500 bytes to 1500 bytes; hence, these 1280-character apgcodes are fully compatible with Catagolue:

https://stackoverflow.com/a/33061526/5130486

I've tested the new apgcode generation on the spaghetti monster, and it agrees with the canonical form on the LifeWiki. I have yet to test multistate (e.g. Generations) patterns.

Re: Extending apgcodes to larger patterns

Posted: August 12th, 2017, 9:41 pm
by Saka
Generatioms is being added too??? Calcyman, is Catagolue EVER in say, 7+ years, going to support custom rules?

Re: Extending apgcodes to larger patterns

Posted: August 13th, 2017, 7:42 am
by muzik
Saka wrote:Generatioms is being added too???
Yep, seems like Generatioms is getting added. Time to screan with joy.

BTW, would this allow for multistate Larger than Life rules? How about snoitareneG rules?

Re: Extending apgcodes to larger patterns

Posted: August 13th, 2017, 8:49 am
by Apple Bottom
calcyman wrote:I've implemented greedy apgcodes for larger patterns (including multistate patterns) in the upcoming v4.0 release [...]

I've tested the new apgcode generation on the spaghetti monster, and it agrees with the canonical form on the LifeWiki. I have yet to test multistate (e.g. Generations) patterns.
Excellent! Great news. :)

What about existing ov_* patterns, at least those in B3/S23? We have a couple of these -- about 22.5k ov_p46's, 20k ov_p177's, 8.8k ov_p24's, 2.6k ov_p30's, as well as about a dozen rare ov_p's and ov_s's.[1] Provided we still know what soups all these came from, we could re-identify them and re-file them using their proper extended apgcodes.

(That is, of course, IF we still have the soups. For the very common objects with thousands of appearances, where we only have 200 sample soup links and where hauls aren't available anymore, we might not.)

I'd be happy to help out, of course -- for both Life and other rules.

1. Including, apparently, an ov_s520 in C2_4, though looking at the soup I think that must've been a misclassification.

Re: Extending apgcodes to larger patterns

Posted: August 13th, 2017, 8:57 am
by calcyman
The apgcode detection seems to work with Generations rules. I tried identifying the period-4 Brian's Brain spaceship:

Code: Select all

x = 11, y = 5, rule = /2/3
AB2.AB$AB.AB$.AB.A4.B$2.AB4.A.B$4.AB2.B!
using the following code:

Code: Select all

    apg::lifetree<uint32_t, 6> lt4(500); // construct a 4-layer lifetree with 500MB of hashing memory
    apg::pattern bb(&lt4, "AB2.AB$AB.AB$.AB.A4.B$2.AB4.A.B$4.AB2.B!", "g3b2s"); // initialise a pattern inside lt4 with Generations rule g3b2s
    std::cerr << bb.apgcode() << std::endl; // compute and print the apgcode
which gives the apgcode xq4_3482h8a_03482lx8. (Yes, multistate apgcodes have multiple underscores, with each component giving a layer of the pattern. However, it's somewhat complicated as to how these layers map to Golly's state numbers, especially in the case of Generations rules.)
Saka wrote:Generatioms is being added too??? Calcyman, is Catagolue EVER in say, 7+ years, going to support custom rules?
It already does, inasmuch as it basically accepts anything that you choose to pass off as a rule name, symmetry type, and apgcode. If you make a search program which produces haul files for your favourite CA, then Catagolue will happily build a distributed census (as you discovered with Saka_Test).

The search program needn't even be a soup search: if you have a depth-first search program such as gfind or zfind, and you have a correspondence between positions in the search tree and alphanumeric strings (where prefixes correspond to ancestors), then you can conduct a distributed search for (say) width-20 c/6 spaceships using the existing Catagolue framework. If you incorporate all of zfind's command-line hyperparameters (period, offset, memory size, etc.) into the beginning of this string, then you can simply have a 'symmetry' called zfind whose tabulations will include things such as xq7, xq10, xq19 (potentially!), etc. And this will work without changing Catagolue in any way.

I'm surprised no-one has tried anything along these lines. The closest thing was my slow-salvo symmetry, but that was ugly in terms of implementation (indeed, I recall there was some non-deterministic element). Ideally every Catagolue-hosted search should be completely deterministic, with the 'randomness' only being present in the haul seed (as is the case for apgsearch).

As well as finding new spaceships in a systematic and distributed manner, it may help inform which combinations of hyperparameters are most effective for running zfind.

What you probably wanted to ask was:
is apgsearch EVER in say, 7+ years, going to support custom rules?
Maybe. The current progress on v4.0 has completely separated various levels of abstraction, so that you can write custom backends (as I've done for Generations, and will be doing for LtL). Any backend you write in this manner must take a 32-by-32 square of cells and return the 16-by-16 centre square after a number of generations (usually 1 for simplicity).

Once you've written that, it is automatically compatible with either of two containers (apg::pattern, which runs HashLife, and apg::upattern, which is based on vlife). So, provided you can write the C++ code to run a 32-by-32 square in your rule, the rest of the lifelib boilerplate code will be able to run unbounded universes efficiently in either a conventional or hashed manner. HashLife has the advantage that for regular patterns, it will eventually memoize all of the 32-by-32 tiles and never need to call your backend code again.

Re: Extending apgcodes to larger patterns

Posted: August 13th, 2017, 9:16 am
by Saka
Interesting. Here's a little proposal. A global "Pattern Share" network. People can select a pattern and then upload it into the "PatterNet" symmetry of the rule and make a huge collection of stuff people want to share. Maybe they can make custom descriptions, and the community can "Like" objects to get them higher on the list. To prevent unwanted content, people should have an account (Not anonymous) and have:
-Contributed at least 50K soups to CGoL
-Searched at least 3 different rules
-Searched at least 1 "official" higher symmetry

Is Patternbook the next big Social Media? A few possible names:
-PatterNet
-CAbook
-Patterngram
-CIPNet (Catagolue International Pattern Network)

Re: Extending apgcodes to larger patterns

Posted: August 13th, 2017, 10:51 am
by drc
@Saka
This may disadvantage linear growth patterns as you have to use a soup because thumbnails don't work with them. (if you understand what I'm saying, it's kind of hard to express in words)

Re: Extending apgcodes to larger patterns

Posted: August 13th, 2017, 10:57 am
by muzik
apgsearching one of those custom speeds/directions rules would be quite interesting.

Re: Extending apgcodes to larger patterns

Posted: August 13th, 2017, 1:13 pm
by muzik
Would it be possible for replicators and quadratic growth patterns to be recognised and encoded like still lifes, oscillators and spaceships?

xr for one-dimensional replicators, xt for two-dimensional replicators, and yq for quadratic growth patterns.