Synthesising Oscillators

mniemiec · Post by **mniemiec** » April 1st, 2019, 7:11 am

Freywa wrote:Obvious synthesis of 6 bits: ...

I have a similar synthesis of that from 1998-07-04 or earlier: http://www.conwaylife.com/ref/mniemiec/period.htm#p75

Freywa · Post by **Freywa** » April 1st, 2019, 7:11 am

mniemiec wrote:
Freywa wrote:Obvious synthesis of 6 bits: ...
I have a similar synthesis of that from 1998-07-04 or earlier: http://www.conwaylife.com/ref/mniemiec/period.htm#p75

I know. It's just not on the LifeWiki yet.

Post by **dvgrn** » April 1st, 2019, 10:33 am

Freywa wrote:
mniemiec wrote:
Freywa wrote:Obvious synthesis of 6 bits: ...
I have a similar synthesis of that from 1998-07-04 or earlier: http://www.conwaylife.com/ref/mniemiec/period.htm#p75
I know. It's just not on the LifeWiki yet.

Unfortunately it's an enormous job to get the LifeWiki's synthesis files caught up with current reality, all across the board. Due to the LifeWiki's rather conservative file management system, every time a synthesis is updated it's currently necessary to go in and manually locate the old synthesis file in an alphabetical list of thousands of files, type "DEAD" into a text box and click a button to delete it... and then go to another page and upload the new version... and then edit the LifeWiki article to mention the new cost in gliders.

I'd very much like to make a radical change to the way synthesis files are delivered on the LifeWiki, and stop uploading _synth files at all. They go out of date too easily. All we really need is for the LifeWiki to link to a URL anywhere on the web that contains the latest synthesis (and synthesis cost). But for that to work, we'd need some single source-of-truth database, with some reasonably efficient crowdsourced method of keeping it up to date.

So far the most likely idea I've had is to continue to put RLE:{pname}_synth articles on the LifeWiki. Unfortunately the best we can do to serve up the resulting RLE in a form that can be easily copied and pasted out is an "action=edit" link like this. That can be pretty confusing (and makes accidental edits more likely). We really just want the page to be a read-only view of the RLE and nothing else, like this.

So we need some other reliably available website -- Catagolue, maybe -- to parse that RLE-namespace _synth article and return only the contents of the wpTextbox1 textbox. (?) Maybe for security purposes it should also check that that text looks like valid RLE and doesn't look like, say, viral Javascript code.

This would do an end-run around Nathaniel's original system of requiring moderator/admin intervention to maintain _synth files. Those rules were put in place to avoid problems with user-uploaded junk taking over the LifeWiki pattern collection -- which is still a good goal, but it seems like the side effects are getting too awkward these days. There are probably better ways of keeping the pattern collection safe, and maybe we should be keeping all the _synth files in a separate downloadable collection anyway.

-- Comments, ideas, suggestions?

Freywa · Post by **Freywa** » April 1st, 2019, 12:29 pm

dvgrn wrote:-- Comments, ideas, suggestions?

@chris_c: are you still maintaining ceebo/glider_synth? Because that is the starting point for a possible long-term solution.

As of this post I am studying CS2040 Data Structures and Algorithms in NUS. Graphs are the last topic covered in that module, and I see that syntheses form a directed graph with constellations as vertices and glider sets as weighted edges where weight is the number of gliders. Given a database of syntheses in this representation, an object's cheapest synthesis is the shortest path from the vertex representing nothing to the vertex representing said object, which can be found using Dijkstra's algorithm.

To further improve the flexibility and reduce the size of this database we could make edges represent synthesis components (a polymorphism that reminds me of another module I'm taking as of this post, CS2030 Programming Methodology II), the same component usable between multiple pairs of constellations. Thus the component "add block on domino" would be a single object in the database rather than having to be encoded separately for each object. We just need to specify the spatial and temporal offset for this component relative to the constellation it is being applied on.

The format in min_paths.txt is, unfortunately, quite hard to understand – in the sense that manually converting an RLE of a synthesis into that format is hard. I'm looking for ways to lessen the pain.

(P.S. the 3- and 4-glider synthesis databases could all be folded inside as well… mwahahaha)

Post by **dvgrn** » April 1st, 2019, 1:08 pm

Freywa wrote:@chris_c: are you still maintaining ceebo/glider_synth? Because that is the starting point for a possible long-term solution.

Or part of a long-term solution, anyway. Any time we have a way of programmatically generating optimal glider syntheses for a large number of patterns, we should be able to avoid a lot of pointless manual update work. I.e., have the LifeWiki link to a URL somewhere that runs a script to generate the latest and greatest synthesis -- and/or programmatically check any such database against what's currently reported in the LifeWiki, and generate a report that at least allows for a very quick and easy manual update.

Freywa wrote:... the component "add block on domino" would be a single object in the database rather than having to be encoded separately for each object. We just need to specify the spatial and temporal offset for this component relative to the constellation it is being applied on.

This brings up an interesting point. In practice we often need to keep track of multiple "add block on domino" recipes, because the context is important: to add a block to a domino at the bottom of concave area in a larger object, for example, we might need a more expensive recipe. Or if we're building a spaceship to add to a larger fleet, we might need to use a few extra gliders, or a totally different recipe, because the cheapest construction results in huge sparks that would destroy the rest of the fleet.

So it would be nice if our synthesis collection system could store multiple components and multiple syntheses for the same object, rather than just throwing away the previous recipe as soon as a new cheaper one appears.

Mark Niemiec's database generally takes the approach of documenting all known synthesis mechanisms that might be useful -- whereas recent syntheses showing up on the LifeWiki are more likely to be Current-Cheapest-Synthesis-Only.

mniemiec · Post by **mniemiec** » April 1st, 2019, 5:53 pm

dvgrn wrote:Mark Niemiec's database generally takes the approach of documenting all known synthesis mechanisms that might be useful -- whereas recent syntheses showing up on the LifeWiki are more likely to be Current-Cheapest-Synthesis-Only.

I first got the idea from a comment Bill Gosper made - that he would like to see older, even obsolete syntheses, to see how things used to be made; sometimes, tools may be used in those that may still be useful elsewhere. I generally try to use the following principles:
1) Each synthesis is broken up into as many temporally-distinct pieces as possible, to aid in automated synthesis (i.e. it's easier to arrange several groups of gliders that arrive in small waves separated by arbitrary space than to require them all to arrive simultaneously)
2) I always include the cheapest synthesis, in terms of gliders.
3) If there were previous obsolete methods, I will try to include those, but only if they include something new (e.g. an old synthesis that used old less-efficient sub-steps to make a predecessor will include the most efficient modern way to make it), and if such obsolete mechanisms used to e used in multiple syntheses, they will only be listed in the first one.
4) If a pattern has multiple distinct pieces (e.g. pseudo-still-lifes, inductors, etc.) I try to also include syntheses that begin with one of the pieces and add the other(s); these can be used as templates to aid in syntheses of larger patterns.
5) Similarly, with inducting objects, I try to include syntheses that begin with each of the pieces (e.g. beacon on cap from beacon + add cap, and block-on-cap + block-to-beacon).

chris_c · Post by **chris_c** » April 2nd, 2019, 7:00 am

Freywa wrote: @chris_c: are you still maintaining ceebo/glider_synth? Because that is the starting point for a possible long-term solution.

I've not done any work with it for about two years. The current state of play was summarised here. Recently I have documented the format better and released the code that analyses glider syntheses.

What is missing:

Here is the point in the code where the object representing a synthesis is produced. But here you see that nothing actually gets done with the result. We need to write code that takes the result and prints it out in the synth-string format.
Code that takes a list of synth-strings and outputs only those synth-strings that belong to a shortest-path tree. This is basically just Dijkstra's algorithm.

Just writing these pieces of code should be pretty easy. Going further it would be nice if the 2nd piece of code would only include apgcodes that were interesting. For example, constellations should be excluded unless they are on a shortest-path between the empty universe and an interesting object. In the past my list of interesting objects was hard-coded as the list of all 16-bit or smaller still lifes. This had the advantage that this piece of code was completely independent of Life. Hard-coding is not sufficient if you want to catalogue all glider syntheses.

Freywa wrote: The format in min_paths.txt is, unfortunately, quite hard to understand – in the sense that manually converting an RLE of a synthesis into that format is hard. I'm looking for ways to lessen the pain.

Best to avoid working with these thing manually I think. I already have Javascript code that takes an apgcode and outputs the full synthesis RLE. Of course this only works if the apgcode is in min_paths.txt but there is no reason that min_paths cannot be extended to included oscillators and other still lifes.

Freywa · Post by **Freywa** » April 10th, 2019, 11:50 am

chris_c wrote:What is missing:

Here is the point in the code where the object representing a synthesis is produced. But here you see that nothing actually gets done with the result. We need to write code that takes the result and prints it out in the synth-string format.

Code that takes a list of synth-strings and outputs only those synth-strings that belong to a shortest-path tree. This is basically just Dijkstra's algorithm.
Just writing these pieces of code should be pretty easy. Going further it would be nice if the 2nd piece of code would only include apgcodes that were interesting. For example, constellations should be excluded unless they are on a shortest-path between the empty universe and an interesting object. In the past my list of interesting objects was hard-coded as the list of all 16-bit or smaller still lifes. This had the advantage that this piece of code was completely independent of Life. Hard-coding is not sufficient if you want to catalogue all glider syntheses.

Well, forget about all of that. I've designed a brand-new glider synthesis database called Shinjuku. The announcement is here.

Freywa · Post by **Freywa** » April 12th, 2019, 7:37 pm

While adding component lines to Shinjuku I noticed that the LifeWiki counts for candlefrobra and its cis-boat version are outdated, as Martin had found 11- and 9-glider syntheses respectively in 2015: