Extending apgcodes to larger patterns

For general discussion about Conway's Game of Life.
User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Extending apgcodes to larger patterns

Post by praosylen » January 22nd, 2017, 6:05 pm

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.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Extending apgcodes to larger patterns

Post by Apple Bottom » January 22nd, 2017, 8:24 pm

Image
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Extending apgcodes to larger patterns

Post by praosylen » January 22nd, 2017, 9:34 pm

Apple Bottom wrote:[xkcd]
I definitely agree. Sorry if I shouldn't have posted.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Extending apgcodes to larger patterns

Post by Apple Bottom » January 23rd, 2017, 6:28 am

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.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

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

Re: Extending apgcodes to larger patterns

Post by calcyman » August 12th, 2017, 9:35 pm

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.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Extending apgcodes to larger patterns

Post by Saka » August 12th, 2017, 9:41 pm

Generatioms is being added too??? Calcyman, is Catagolue EVER in say, 7+ years, going to support custom rules?

User avatar
muzik
Posts: 5614
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Extending apgcodes to larger patterns

Post by muzik » August 13th, 2017, 7:42 am

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?

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Extending apgcodes to larger patterns

Post by Apple Bottom » August 13th, 2017, 8:49 am

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.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

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

Re: Extending apgcodes to larger patterns

Post by calcyman » August 13th, 2017, 8:57 am

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.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Extending apgcodes to larger patterns

Post by Saka » August 13th, 2017, 9:16 am

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)

drc
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm

Re: Extending apgcodes to larger patterns

Post by drc » August 13th, 2017, 10:51 am

@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)

User avatar
muzik
Posts: 5614
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Extending apgcodes to larger patterns

Post by muzik » August 13th, 2017, 10:57 am

apgsearching one of those custom speeds/directions rules would be quite interesting.

User avatar
muzik
Posts: 5614
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Extending apgcodes to larger patterns

Post by muzik » August 13th, 2017, 1:13 pm

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.

Post Reply