how about a sir robin synthesis?
-
- Posts: 330
- Joined: January 24th, 2018, 4:36 pm
- Location: Minnesota, USA
how about a sir robin synthesis?
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!
Re: Synthesizing the elementary knightship
Maybe we should try for an eater before we look for a gun.
Re: Synthesizing the elementary knightship
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.Macbi wrote:Maybe we should try for an eater before we look for a gun.
Not today!googleplex wrote:Welp, you knew it was coming! can we synthesize it?
(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.
Re: Synthesizing the elementary knightship
I think, because this spaceship is very large and contains a lot of space dust, it would be very difficult to synthesise.
Re: Synthesizing the elementary knightship
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?dvgrn wrote: ↑March 7th, 2018, 12:35 pmThat'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.
Re: Synthesizing the elementary knightship
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.Roger wrote: ↑January 2nd, 2021, 1:49 amFinding 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?
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.
-
- Posts: 5166
- Joined: August 31st, 2020, 5:58 pm
Re: Synthesizing the elementary knightship
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!
I am tentatively considering myself back.
-
- Posts: 295
- Joined: July 26th, 2020, 10:39 pm
- Location: Texas, USA
Re: Synthesizing the elementary knightship
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.MathAndCode wrote: ↑January 2nd, 2021, 2:46 pmOn 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: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.Code: Select all
probably suboptimal synth
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!
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
Me on LifeWiki
-
- Posts: 5166
- Joined: August 31st, 2020, 5:58 pm
Re: Synthesizing the elementary knightship
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.goldenratio wrote: ↑January 2nd, 2021, 3:19 pmWe 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.)
I am tentatively considering myself back.
-
- Posts: 714
- Joined: May 27th, 2016, 1:01 am
Re: how about a sir robin synthesis?
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...
-
- Posts: 5166
- Joined: August 31st, 2020, 5:58 pm
Re: how about a sir robin synthesis?
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 pmAnother 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 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.Jormungant wrote: ↑January 4th, 2021, 4:07 pmIf 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 am tentatively considering myself back.
- Extrementhusiast
- Posts: 1966
- Joined: June 16th, 2009, 11:24 pm
- Location: USA
Re: how about a sir robin synthesis?
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:Jormungant wrote: ↑January 4th, 2021, 4:07 pmIf 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...
- 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.
- 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.)
- Run a time- or iteration-limited search on the current pattern.
- 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.
- 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.)
- If the search finishes without any partial solutions, backtrack to the most recent non-inverted supposition, invert it, and continue forward.
- If a complete or sufficiently-long partial solution is found, save it and backtrack similarly if more solutions are desired.
- Repeat steps 2 and 3 until no more backtracking is possible.
I Like My Heisenburps! (and others)
Re: Synthesizing the elementary knightship
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.
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.MathAndCode wrote: ↑January 2nd, 2021, 2:46 pmGoogle also has a history of donating computer resources to recreational pursuits along this line.
-
- Posts: 714
- Joined: May 27th, 2016, 1:01 am
Re: how about a sir robin synthesis?
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".Extrementhusiast wrote: ↑January 4th, 2021, 11:49 pmDepending on if I'm understanding you correctly, it might not take anything more complicated than JLS. I've developed the following procedure for searching:Jormungant wrote: ↑January 4th, 2021, 4:07 pmIf 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...While it does take more active involvement, I've found that this procedure saves time overall.
- 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.
- 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.)
- Run a time- or iteration-limited search on the current pattern.
- 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.
- 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.)
- If the search finishes without any partial solutions, backtrack to the most recent non-inverted supposition, invert it, and continue forward.
- If a complete or sufficiently-long partial solution is found, save it and backtrack similarly if more solutions are desired.
- Repeat steps 2 and 3 until no more backtracking is possible.