how about a sir robin synthesis?

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Post Reply
googleplex
Posts: 330
Joined: January 24th, 2018, 4:36 pm
Location: Minnesota, USA

how about a sir robin synthesis?

Post by googleplex » March 7th, 2018, 11:07 am

Welp, you knew it was coming! can we synthesize it?
Last edited by googleplex on March 8th, 2018, 9:29 am, edited 1 time in total.
Look at me! I make patterns in golly and go on the forums! I wanna be Famous!

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Synthesizing the elementary knightship

Post by Macbi » March 7th, 2018, 12:25 pm

Maybe we should try for an eater before we look for a gun.

User avatar
dvgrn
Moderator
Posts: 10875
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Synthesizing the elementary knightship

Post by dvgrn » March 7th, 2018, 12:35 pm

Macbi wrote:Maybe we should try for an eater before we look for a gun.
An eater won't be a problem -- I could build one in a few hours. A compact or elegant eater, on the other hand, might be a bit tricky... Luckily we probably don't need to worry about an eater with the fastest possible recovery time, until and unless a knightship gun actually does show up.
googleplex wrote:Welp, you knew it was coming! can we synthesize it?
Not today!

(I have a mixed record on Life-related prognostication, but I'm pretty confident on this one.)

There are many thousands of known spaceships that we don't know how to synthesize, that would be orders of magnitude easier to synthesize than this huge fast-moving high-period object. You almost might as well try to synthesize a spaghetti monster.

That's not to say that someday we might not have a backtracking search algorithm that generates predecessors, and recursively chooses predecessors that are more amenable to being constructed by gliders -- maybe they contain large simple stable regions, or maybe the search will prefer predecessors that effectively break the construction problem into several widely-separated smaller islands.

The problem is to define a metric -- an algorithm that can somehow give each predecessor an accurate score, to tell us reliably that one predecessor is somehow "closer" than another to being a glider synthesis. People have done a lot of hand-waving about what might work as a metric, but so far it's all vaporware.

Once we have actual code that assigns a helpful score to an arbitrary pattern, the rest of the search becomes relatively easy -- assuming that it will usually be possible to find predecessors for a given pattern that have a lower score than the pattern itself. That might be a big assumption.

Without a reliable metric, the glider synthesis problem for this particular knightship is -- I would guess -- billions of times harder (at least) than the problem of finding the knightship in the first place... and that only happened after Tom and Adam ran multiple-core searches over a period of several weeks.

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Synthesizing the elementary knightship

Post by 77topaz » March 7th, 2018, 3:32 pm

I think, because this spaceship is very large and contains a lot of space dust, it would be very difficult to synthesise.

Roger
Posts: 8
Joined: January 1st, 2021, 9:54 pm

Re: Synthesizing the elementary knightship

Post by Roger » January 2nd, 2021, 1:49 am

dvgrn wrote:
March 7th, 2018, 12:35 pm
That's not to say that someday we might not have a backtracking search algorithm that generates predecessors, and recursively chooses predecessors that are more amenable to being constructed by gliders -- maybe they contain large simple stable regions, or maybe the search will prefer predecessors that effectively break the construction problem into several widely-separated smaller islands.

The problem is to define a metric -- an algorithm that can somehow give each predecessor an accurate score, to tell us reliably that one predecessor is somehow "closer" than another to being a glider synthesis. People have done a lot of hand-waving about what might work as a metric, but so far it's all vaporware.

Once we have actual code that assigns a helpful score to an arbitrary pattern, the rest of the search becomes relatively easy -- assuming that it will usually be possible to find predecessors for a given pattern that have a lower score than the pattern itself. That might be a big assumption.

Without a reliable metric, the glider synthesis problem for this particular knightship is -- I would guess -- billions of times harder (at least) than the problem of finding the knightship in the first place... and that only happened after Tom and Adam ran multiple-core searches over a period of several weeks.
Finding a good approximation to that search metric sounds almost exactly like a good problem for a deep-learning neural net -- it's an exercise in pattern recognition very comparable to, say, learning to play Go. Any Life enthusiasts have contacts in DeepMind, or want to try reproducing their methods?

User avatar
dvgrn
Moderator
Posts: 10875
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Synthesizing the elementary knightship

Post by dvgrn » January 2nd, 2021, 10:29 am

Roger wrote:
January 2nd, 2021, 1:49 am
Finding a good approximation to that search metric sounds almost exactly like a good problem for a deep-learning neural net -- it's an exercise in pattern recognition very comparable to, say, learning to play Go. Any Life enthusiasts have contacts in DeepMind, or want to try reproducing their methods?
Somebody in the conwaylife community is probably only a couple of handshakes away from somebody on the AlphaZero team. I'd love to see what a few weeks of DeepMind focus on glider synthesis or spaceship search problems might come up with.

On the other hand, it's possible that someone has already spent some time on the problem, without coming up with any promising results. I wouldn't be terribly surprised if targeted glider syntheses turned out to be a problem that's many orders of magnitude more intractable than Go -- i.e., on a large scale, more like finding the factors of pseudoprimes than like taking incremental steps toward winning a game.

I was just thinking about this again this morning, since now we have 3c/7 spaceships that are a lot more amenable to glider synthesis than the old flying spaghetti monster -- or Sir Robin, probably, because at least the 257P7H3V0 is symmetrical, so you can kinda sorta cut the number of bits in half. Still it seems very far out of reach of current methods, so any kind of new approach would be very interesting.

MathAndCode
Posts: 5162
Joined: August 31st, 2020, 5:58 pm

Re: Synthesizing the elementary knightship

Post by MathAndCode » January 2nd, 2021, 2:46 pm

dvgrn wrote:
January 2nd, 2021, 10:29 am
Somebody in the conwaylife community is probably only a couple of handshakes away from somebody on the AlphaZero team. I'd love to see what a few weeks of DeepMind focus on glider synthesis or spaceship search problems might come up with.
Google also has a history of donating computer resources to recreational pursuits along this line. If I remember correctly, one example is the proof that any Rubik's Cube position can be solved with at most twenty moves. However, I don't think that it's very worthwhile to use a bunch of computing resources just to be able to give a better estimate of how many more decades we'll have to wait until we can make progress. On the other hand, one thing that we definitely can do is synthesize part of Sir Robin. For example, here's a way to make the six-cell region at the back of generation 1 (and also the six-cell region at the back of generation 2) of Sir Robin that I found in less than five minutes:

Code: Select all

x = 22, y = 21, rule = B3/S23
3bo15bo$bobo15bobo$2b2o15b2o3$2bo$3b2o$2b2o3$15b2o$15bobo$15bo6$b2o$obo$2bo!
It looks like someone with more experience who is willing to put in more effort could probably synthesize the back 8–10 rows of Sir Robin before the space junk gets bad. This might be useful in a few more years, when constructing the smaller tagalongs is more feasible, but for now, trying to construct part of Sir Robin is a novelty at best (unless one makes it through an entire region of space junk, at which point synthesizing Sir Robin will look much more promising, and other people will join the effort).
I am tentatively considering myself back.

goldenratio
Posts: 295
Joined: July 26th, 2020, 10:39 pm
Location: Texas, USA

Re: Synthesizing the elementary knightship

Post by goldenratio » January 2nd, 2021, 3:19 pm

MathAndCode wrote:
January 2nd, 2021, 2:46 pm
On the other hand, one thing that we definitely can do is synthesize part of Sir Robin. For example, here's a way to make the six-cell region at the back of generation 1 (and also the six-cell region at the back of generation 2) of Sir Robin that I found in less than five minutes:

Code: Select all

probably suboptimal synth
It looks like someone with more experience who is willing to put in more effort could probably synthesize the back 8–10 rows of Sir Robin before the space junk gets bad.
Have you seen synth-patt? It allows you to look for 3-glider syntheses of common/small active regions. Unfortunately I can't check for you right now since I don't have access to Golly at this moment, but given how small that junk is it's very likely to have multiple 3-glider syntheses.
EDIT: Here's one of many 3Gs synth-patt found:

Code: Select all

x = 12, y = 8, rule = B3/S23
3bo$4bo4bobo$2b3o4b2o$10bo2$bo$b2o$obo!
We could synthesize a small part of Sir Robin, but what would be the purpose for that? You can't build a gun with a synthesis for only part of the spaceship (and synthesizing a spaceship incrementally is infeasible due to how fast partial spaceships decay.)
Last edited by goldenratio on January 2nd, 2021, 3:35 pm, edited 1 time in total.
Oscillator discussion is boring me out. I'll return when the cgol community switches to something else.

Me on LifeWiki

MathAndCode
Posts: 5162
Joined: August 31st, 2020, 5:58 pm

Re: Synthesizing the elementary knightship

Post by MathAndCode » January 2nd, 2021, 3:25 pm

goldenratio wrote:
January 2nd, 2021, 3:19 pm
We could synthesize a small part of Sir Robin, but what would be the purpose for that? You can't build a gun with a synthesis for only part of the spaceship (and synthesizing a spaceship incrementally is infeasible due to how fast partial spaceships decay.)
Yes, I made that point at the end, where I called it a novelty at best. A more synthesis for a larger part of Sir Robin might be useful as a partial for constructing the entire spaceship, but it will probably be at least a decade before that becomes practical, so there's no point in trying to synthesize part of Sir Robin for that purpose beforehand. While I should have made that obvious, I consider the parenthetical statement at the end of my previous post in this topic to be extremely unlikely.
I am tentatively considering myself back.

Jormungant
Posts: 677
Joined: May 27th, 2016, 1:01 am

Re: how about a sir robin synthesis?

Post by Jormungant » January 4th, 2021, 4:07 pm

If there is one thing I believe deep-learning could help, it would be to supplement search procedures for spaceship and low period oscillators by providing the position of the most constrained positions in a partial solution so that dead-ends are detected faster (without listing an extensive list of partial that are doomed to fail because of a given position). This task is somehow done indirectly by limiting widths and enforcing an order, guarantying that such positions to be hit a some point, but that bounding task would be learned too. Still, evaluating a state by a neural network net is expensive, so it should only done in the early stages for the search exclusively. Another thing that would be nice is if it would attempt to guess a mean to split the search grid in two, so that independent search spaces can be investigated in parallel somehow (to fight combinatorial complexity somehow); but that is not something I would assume would be a game-changer. Well, I like to mess around with this game of life to give me a break from coding, so that sounds like a severe headache in both cases as far as implementation goes...

MathAndCode
Posts: 5162
Joined: August 31st, 2020, 5:58 pm

Re: how about a sir robin synthesis?

Post by MathAndCode » January 4th, 2021, 5:18 pm

Jormungant wrote:
January 4th, 2021, 4:07 pm
Another thing that would be nice is if it would attempt to guess a mean to split the search grid in two, so that independent search spaces can be investigated in parallel somehow (to fight combinatorial complexity somehow); but that is not something I would assume would be a game-changer.
I mentioned the idea of the search program splitting the spaceship into multiple overlapping sections, and I think that it would indeed make the search effort go a lot faster. I doubt that it would close all of the current technological gap (although we won't know for sure unless we try it, which would be worthwhile even if it doesn't close all of the current technological gap because it could be used for synthesizing other spaceships), but I suspect that it would make finding a Sir Robin synthesis using this method possible at least several years, possibly a decade, sooner than otherwise.
Jormungant wrote:
January 4th, 2021, 4:07 pm
If there is one thing I believe deep-learning could help, it would be to supplement search procedures for spaceship and low period oscillators by providing the position of the most constrained positions in a partial solution so that dead-ends are detected faster (without listing an extensive list of partial that are doomed to fail because of a given position).
I agree that having the program look for solutions for more difficult regions would be helpful. However, I'm considering the possibility that before the program looks for solutions for the most difficult regions, it should set solutions for "obvious" regions that have one solution that makes much more sense than anything else, e.g. a fairly large section of two or more lines resembling zebra stripes traveling with the grain.
I am tentatively considering myself back.

User avatar
Extrementhusiast
Posts: 1966
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: how about a sir robin synthesis?

Post by Extrementhusiast » January 4th, 2021, 11:49 pm

Jormungant wrote:
January 4th, 2021, 4:07 pm
If there is one thing I believe deep-learning could help, it would be to supplement search procedures for spaceship and low period oscillators by providing the position of the most constrained positions in a partial solution so that dead-ends are detected faster (without listing an extensive list of partial that are doomed to fail because of a given position). This task is somehow done indirectly by limiting widths and enforcing an order, guarantying that such positions to be hit a some point, but that bounding task would be learned too. Still, evaluating a state by a neural network net is expensive, so it should only done in the early stages for the search exclusively. Another thing that would be nice is if it would attempt to guess a mean to split the search grid in two, so that independent search spaces can be investigated in parallel somehow (to fight combinatorial complexity somehow); but that is not something I would assume would be a game-changer. Well, I like to mess around with this game of life to give me a break from coding, so that sounds like a severe headache in both cases as far as implementation goes...
Depending on if I'm understanding you correctly, it might not take anything more complicated than JLS. I've developed the following procedure for searching:
  1. Start with a small search space in the original search pattern. If the search pattern is empty, a bit of forcing (e.g. a cell being off in one generation and on in the next) may be needed to get the search started.
  2. Find the (cell, time, state) trio that implies the states of as many other (cell, time) pairs as possible. Suppose that that (cell, time) pair has that state. (If there's a tie, pick the (cell, time) pair that occurs first in the search order. If there's still a tie between both states for the first (cell, time) pair, pick either one.)
  3. Run a time- or iteration-limited search on the current pattern.
    1. If the search passes the time/iteration limit before finishing, stop the search and either shorten the search space, if it wasn't just lengthened, or make another supposition.
    2. If the search finishes with one or more partial solutions, accept the implications with caution and lengthen the search space. "Useless" cells (e.g. the casing in an oscillator search) can also be excluded from the search space here. (Because of a bug in JLS's pruning of combinations, finding a partial solution occasionally causes some branches of the search tree to be pruned erroneously, which can occasionally result in more implications than the same search without pruning would produce. Thus, it is a good idea to verify that the inverse of each implication is false, especially if there are relatively few implications overall, when the bug most frequently occurs.)
    3. If the search finishes without any partial solutions, backtrack to the most recent non-inverted supposition, invert it, and continue forward.
    4. If a complete or sufficiently-long partial solution is found, save it and backtrack similarly if more solutions are desired.
  4. Repeat steps 2 and 3 until no more backtracking is possible.
While it does take more active involvement, I've found that this procedure saves time overall.
I Like My Heisenburps! (and others)

Roger
Posts: 8
Joined: January 1st, 2021, 9:54 pm

Re: Synthesizing the elementary knightship

Post by Roger » January 6th, 2021, 6:13 am

dvgrn wrote:
January 2nd, 2021, 10:29 am
Somebody in the conwaylife community is probably only a couple of handshakes away from somebody on the AlphaZero team. I'd love to see what a few weeks of DeepMind focus on glider synthesis or spaceship search problems might come up with.
I'm probably only 2-3 handshakes away from someone on the AlphaZero team -- but I'm not sure how to search for the first of those handshakes, and that's not an automatable problem. :D
MathAndCode wrote:
January 2nd, 2021, 2:46 pm
Google also has a history of donating computer resources to recreational pursuits along this line.
Also of allowing some of their developers to spend ~20% of their time on apparently-useless projects. I suspect what might be more practical to find is not someone on the DeepMind team directly, but someone at Google who would be interested as treating this as a 20% project, with the nominal excuse for their manager that they're learning how to apply DeepMind reinforcement learning technology by applying it to a well-known toy problem. Fortunately the actual GoL search-evaluation part is eminently parallelizable: it mostly involves running bits of open-source C code and passing messages between them containing RLE (or a binary equivalent) -- it wouldn't be that hard to build a framework around that out of basic Google tech like Flume jobs and protocol buffers.

Jormungant
Posts: 677
Joined: May 27th, 2016, 1:01 am

Re: how about a sir robin synthesis?

Post by Jormungant » January 6th, 2021, 2:03 pm

Extrementhusiast wrote:
January 4th, 2021, 11:49 pm
Jormungant wrote:
January 4th, 2021, 4:07 pm
If there is one thing I believe deep-learning could help, it would be to supplement search procedures for spaceship and low period oscillators by providing the position of the most constrained positions in a partial solution so that dead-ends are detected faster (without listing an extensive list of partial that are doomed to fail because of a given position). This task is somehow done indirectly by limiting widths and enforcing an order, guarantying that such positions to be hit a some point, but that bounding task would be learned too. Still, evaluating a state by a neural network net is expensive, so it should only done in the early stages for the search exclusively. Another thing that would be nice is if it would attempt to guess a mean to split the search grid in two, so that independent search spaces can be investigated in parallel somehow (to fight combinatorial complexity somehow); but that is not something I would assume would be a game-changer. Well, I like to mess around with this game of life to give me a break from coding, so that sounds like a severe headache in both cases as far as implementation goes...
Depending on if I'm understanding you correctly, it might not take anything more complicated than JLS. I've developed the following procedure for searching:
  1. Start with a small search space in the original search pattern. If the search pattern is empty, a bit of forcing (e.g. a cell being off in one generation and on in the next) may be needed to get the search started.
  2. Find the (cell, time, state) trio that implies the states of as many other (cell, time) pairs as possible. Suppose that that (cell, time) pair has that state. (If there's a tie, pick the (cell, time) pair that occurs first in the search order. If there's still a tie between both states for the first (cell, time) pair, pick either one.)
  3. Run a time- or iteration-limited search on the current pattern.
    1. If the search passes the time/iteration limit before finishing, stop the search and either shorten the search space, if it wasn't just lengthened, or make another supposition.
    2. If the search finishes with one or more partial solutions, accept the implications with caution and lengthen the search space. "Useless" cells (e.g. the casing in an oscillator search) can also be excluded from the search space here. (Because of a bug in JLS's pruning of combinations, finding a partial solution occasionally causes some branches of the search tree to be pruned erroneously, which can occasionally result in more implications than the same search without pruning would produce. Thus, it is a good idea to verify that the inverse of each implication is false, especially if there are relatively few implications overall, when the bug most frequently occurs.)
    3. If the search finishes without any partial solutions, backtrack to the most recent non-inverted supposition, invert it, and continue forward.
    4. If a complete or sufficiently-long partial solution is found, save it and backtrack similarly if more solutions are desired.
  4. Repeat steps 2 and 3 until no more backtracking is possible.
While it does take more active involvement, I've found that this procedure saves time overall.
Deep learning could do that "active involvement" better (or at least automate it in some ways...), if trained to find the most promising cells to investigate first; however, if one wants to fully investigate a well-defined bounded searchspace to arrive to a negative/positive results, that will be of no use. I think it would be fair to say that the rectangle-like bounding design works in conjunction with the "search order" for position of cells to guaranty that search stays local, and does not fork to search in two locations in alternance, which would slow down the search from the re-computing partials previously searched (that pruning of combination is fighting this, but it is buggy if I understand); however, as the bounding rectangle size increase, I would assume that the probability of this costly forking increases, making the search in this higher magnitude searchspace even worse than it should be. We now have an amoeba looking p28 gun, which is nice to know is possible; but one would assume a more compact alternative should exist, so a guided deeplearning priority/parallelization planed search could allow to think outside the "box".

Post Reply