Backtracking conduit search program -- ideas and estimates

[MathAndCode]

Do we have a program (likely some hybrid of Logic Life Search and Bellman) that can make a conduit with a particular output and clearance without being given a partial reaction?

[Kazyan]

Do we have a program (likely some hybrid of Logic Life Search and Bellman) that can make a conduit with a particular output and clearance without being given a partial reaction?

No. We don't.

One could probably be stitched together from existing catalyst search programs with something like this:

1) Do a 1-catalyst (or 2-catalyst) search on a desired input to generate an inital pool of results
2) Take all of the results from the pool as a new input, and then do a 1-catalyst (or 2-catalyst) search on those.
3) Combine all of the results from step 2) into a new pool. Weed out duplicates. Screen them to see if any have become clean conduits--if they do, report those and remove them from the pool.
4) Repeat steps 2) and 3) until the pool of results is empty.
5) Look through all of the reported conduits.

[MathAndCode]

Do we have a program (likely some hybrid of Logic Life Search and Bellman) that can make a conduit with a particular output and clearance without being given a partial reaction?

No. We don't.

One could probably be stitched together from existing catalyst search programs with something like this:

I was thinking of something that would work more directly by attempting to track evolution and catalyses backward in time. For example, let's suppose that we want to create a ∏-heptomino. (In reality, we would most likely enter a house into the program due to alternative evolution paths that are fairly common.)

Code: Select all

x = 3, y = 3, rule = B3/S23
3o$2bo$3o!

The program can track this back to see what could have evolved into it. Here are a couple of examples for going two generations back.

Code: Select all

x = 2, y = 4, rule = B3/S23
o$bo$bo$2o!

Code: Select all

x = 3, y = 4, rule = B3/S23
2o$2bo$2bo$b2o!

The program could be taught that sometimes, the interior of a pattern will fill up with a lot of on cells, causing most or all of the interior to die, leaving a detached front end and usually sparks. (Examples include generations 8–9, 18–19, and 26–27 of the R-pentomino.) However, instead of making the program specifically look for this, a better way might be to have the program focus on getting the front cells correct first and then killing a bunch of cells just behind with overpopulation from cells farther behind, killing those cells with overpopulation from cells even farther behind, etc…. It's possible that the program would also be taught to disregard sparks instead of viewing some object by itself and some object with a spark safely far behind as separate predecessors. With there in mind, here is one way to create the second grandparent.

Code: Select all

x = 7, y = 5, rule = B3/S23
4bo$4b2o$ob2ob2o$b5o$4o!

Suppose that the program tracks that path further back in time and arrives at this.

Code: Select all

x = 7, y = 5, rule = B3/S23
3b3o$3b4o$2b2o2bo$5bo$obo!

Those two dot sparks in the lower left don't seem very like to have happened naturally, so the program might guess that it should try a catalysis. After going through the effects of common catalysts, it should know to try a fishhook.

Code: Select all

x = 10, y = 9, rule = B3/S23
8bo$6b4o$5bo3bo$5b3o2$2b2o$bobo$bo$2o!

Another way to think about it is that if the dot sparks are viewed as part of a V triplet, that results in an object that could have evolved naturally more feasibly, so the program has to find a way to make something that ordinarily would have evolved into the version with the V triplet instead evolve into an object with one cell missing. The program can then continue to look for predecessors until it senses that another catalysis is necessary. Here is the pattern rewound a couple more generations.

Code: Select all

x = 10, y = 9, rule = B3/S23
9bo$6bo2bo$6bobo$6b2o2$2b2o$bobo$bo$2o!

Of course, the program would have also investigated other ways to make a ∏ through back-tracking.
Disclaimer: Obviously, I did not find that way of making a ∏ through the method that I have just detailed (or else there would be no need for the program), so the example above is no guarantee that the method is practical for a computer to carry out. It is possible that there will be too many paths for the computer to investigate (although there would be ways to narrow the paths down), that attempting to make the program recognize the aftermath of catalyses will fail, or that other problems will crop up.



Edit: Here is another example.
A while back, I wanted to make a Herschel from an alternative direction. I first found a promising parent.

Code: Select all

x = 5, y = 4, rule = B3/S23
2bo$2o$2b2o$4bo!

My first attempt to backtrack went to a grandparent similar to this:

Code: Select all

x = 7, y = 6, rule = B3/S23
o$ob2o$o$3b3o$4b3o$2bo!

This obviously doesn't look very feasible, so I tried another path and found something like this:

Code: Select all

x = 6, y = 5, rule = B3/S23
2bo$o$o2bobo$obo$3b2o!

This only looks marginally better, and attempts to backtrack further while maintaining a c/4 forward movement mechanism only got worse, with the back two-thirds becoming a jumbled mess of dot, domino, and banana sparks that I couldn't extend more than four (total) generations back.
Since that path was not working, I decided to go down a different path: Instead of assuming that the object had maintained a c/4 forward movement mechanism for a while, I decided to try assuming that it had recently transitioned from a c/3 forward movement mechanism. This yielded better results; I was able to go back six generations while still having the object look fairly plausible.

Code: Select all

x = 8, y = 8, rule = B3/S23
5bo$2bo$b4o$o$b2o$2b2o$4bo2bo$5bobo!

However, I could not figure out how to go back eight generations without making the object look unruly.

Code: Select all

x = 9, y = 13, rule = B3/S23
3bo$4bo$4bo$6bo$b2o$2o3bobo$bob2o$2bo2bobo$6bo$5bo$3bo$b3o2b2o$3b2o3bo!

Note: This is where I originally stopped trying to make a Herschel from an alternative direction. All later work on this in this post has been done just now.
Adding an additional cell to the six-generation predecessor makes it look even more plausible but prevents it from working as a Herschel predecessor.

Code: Select all

x = 8, y = 9, rule = B3/S23
5bo$2bo$b4o$o$b2o$2b2o$4bo2bo$5bobo$6bo!

This looks similar to the fishhook in the first example, so let's also treat this as the aftermath of a fishhook catalysis.

Code: Select all

x = 12, y = 13, rule = B3/S23
5bo$2bo$b4o$o$b2o$2b2o$4bo2bo$5bobo2$9bo$7b2obo$10bo$10b2o!

Nope, that doesn't work.

Code: Select all

x = 11, y = 14, rule = B3/S23
3b2o$5bo2$3o$o2b2o$2ob5o$2b4o2$5b2o$4b3o$2b3ob3o$3bo3bobo$3bo5bo$9b2o!

After seeing that, I looked back at some other fishhook catalyses, and I saw that the aftermath of fishhook catalyses varies a lot and typically does not include the presence of two dots separated by two cells orthogonally with the same relative position to the fishhook, so recognizing the aftermath of catalyses will likely be more difficult than I initially figured. It could at least be done by brute force, but that would take longer. This example is a good example of the process and also a good example that this will not be trivial.

[dvgrn]

It is possible that there will be too many paths for the computer to investigate (although there would be ways to narrow the paths down)...

You have good instincts for the likely difficulties. The above is exactly the problem that has stopped people from completing workable search programs, the last several times that this kind of backtracking idea has been proposed. Here's a thread describing a previous attempt.

I'd say that one of the basic problems is that the branching factor for backtracking searches is generally very much larger than people think it is. Of course, as you say, you can prune it down, but your pruning has to remove 10^99 out of every 10^100 options, so the odds are near 100% that you'll prune off the branches that actually work.

Here's an example to help this make more sense. Say you're backtracking a pi heptomino, same as in your post. What are the odds that the pruning algorithm will guess right about random sparks popping up in exactly the following places, as the backtracking proceeds from tick to tick through these eight ticks? Can you imagine writing some kind of measurement algorithm that can reliably decide that these specific choices are better than the billions of other options available?

Code: Select all

x = 84, y = 9, rule = B3/S23
32bo9bo19bo9bo9bo$22b2o9bo7bobo7b3o8bo8bobo7bobo$32bo10bo7b2o9bo18bobo
$50b2o9bo9bo$39bo2bo7b2o8b2obo7b3o7b2o$21bobo6bo2bo6bo2bo6b2o2bo6bo2bo
6bobo8b2o$2ob2o5b2ob2o6bobo7b3o7b3o8b2o8b2o8b2o9bo$2ob2o6bobo7b3o8bo$
2bo9bo!

Sparks could appear anywhere in a large area, on any of these ticks. But these precise locations are among the few that will allow us to complete the backtracking process in just a few more ticks, arriving at a minimum number of gliders:

Code: Select all

x = 116, y = 10, rule = B3/S23
92bo8bo10bo$32bo9bo19bo9bo9bo10bo8b2o6bobo$22b2o9bo7bobo7b3o8bo8bobo7b
obo7bo9b2o8b2o$32bo10bo7b2o9bo18bobo7b3o8bo$50b2o9bo9bo20bo11bo8bo$39b
o2bo7b2o8b2obo7b3o7b2o9bo9b2o9bobo$21bobo6bo2bo6bo2bo6b2o2bo6bo2bo6bob
o8b2o8b3o8b2o8b2o$2ob2o5b2ob2o6bobo7b3o7b3o8b2o8b2o8b2o9bo$2ob2o6bobo
7b3o8bo$2bo9bo!

So... it seems like making this kind of thing work would require some kind of very clever hybrid of backtracking and forward-tracking -- maybe a large database of "edgy" reactions where a search program could look for matches with the edges of the current reaction. It's a bit hard to imagine that matches could be found often enough to make this work, though.

[wwei23]

What are the odds that the pruning algorithm will guess right about random sparks popping up in exactly the following places, as the backtracking proceeds from tick to tick through these eight ticks?

Ignore those areas, and find a predecessor that generates the main region. Then look at those areas and see if they have sparks in them, or something that isn't a spark and will interfere later.

[MathAndCode]

I'd say that one of the basic problems is that the branching factor for backtracking searches is generally very much larger than people think it is. Of course, as you say, you can prune it down, but your pruning has to remove 10^99 out of every 10^100 options, so the odds are near 100% that you'll prune off the branches that actually work.

Yes, that's even larger than I anticipated. However, we can narrow it down a lot by demanding that the object consistently exhibit a forward movement mechanism. This will remove most of the options, but the options without a consistent forward movement mechanism most likely will not allow us to insert the object from a distance off, so they will not be as useful. This could get rid of some useful options—the object in my first example faltered for three generations before resuming a forward movement mechanism—but the remaining options will be much more useful on average. In addition, this will ensure that the front section stays reasonable.
Another way to reduce the branching factor is to teach the problem to recognize how realistic certain groups of objects are. I'm sure that at least some predecessors will be relatively easy for the program to narrow out. Also, if only one part of the object is unrealistic, this could be a sign to try a catalysis.

Here's an example to help this make more sense. Say you're backtracking a pi heptomino, same as in your post. What are the odds that the pruning algorithm will guess right about random sparks popping up in exactly the following places, as the backtracking proceeds from tick to tick through these eight ticks? Can you imagine writing some kind of measurement algorithm that can reliably decide that these specific choices are better than the billions of other options available?

Sparks could appear anywhere in a large area, on any of these ticks. But these precise locations are among the few that will allow us to complete the backtracking process in just a few more ticks, arriving at a minimum number of gliders:

Yes, it will be difficult for the program to guess where the sparks should best go by going through the generations in backwards order. However, I suspect that if the program focuses on the front few rows, lets the back rows be anything, goes back a few more generations, sees what options result in those few front rows, then sees what back rows they created will be much more efficient.

[dvgrn]

... your pruning has to remove 10^99 out of every 10^100 options, so the odds are near 100% that you'll prune off the branches that actually work.

Yes, that's even larger than I anticipated.

To be clear, those are numbers I made up to give a sense of the size of the problem, not anything specific to any particular search. I think you'll easily end up with 10^100 possible branches of a search tree, if you're trying to track a pi-heptomino backwards for say twenty or thirty ticks, looking for a way to start it from a Herschel/B-heptomino/R-pentomino/whatever, adding helper catalysts in likely locations as you're suggesting, dealing with the possibility of dying sparks showing up magically as you backtrack, etc.

I don't really know if that's the right number for what you're visualizing, but it's in the right ballpark -- i.e., "so many branches that you'll absolutely have to figure out how to prune off most of them without ever actually looking at them". 10^100 will be too big for some bounding box search size, and too small for some other bounding box size that's only a little bit bigger.

Yes, it will be difficult for the program to guess where the sparks should best go by going through the generations in backwards order. However, I suspect that if the program focuses on the front few rows, lets the back rows be anything, goes back a few more generations, sees what options result in those few front rows, then sees what back rows they created will be much more efficient.

Good luck! Someday someone will write a backtracking program like this that's actually capable of finding something. Based on the number of failures so far, it doesn't seem to be an easy task.

Do you mind if I split this discussion off into a new thread that says something about "Search program idea", or "Backtracking algorithm" or something? What should I call it? It's all pretty much hand-waving at this point, and doesn't really belong in this already oversized thread.

[MathAndCode]

Do you mind if I split this discussion off into a new thread that says something about "Search program idea", or "Backtracking algorithm" or something? What should I call it? It's all pretty much hand-waving at this point, and doesn't really belong in this already oversized thread.

I would say yes if not for the fact that I don't have anything to say in response to your post (besides the usual refrain about how this will probably be feasible after twenty or so years' worth of Moore's law, which seems unnecessary to point out again). If I'm interpreting your post correctly, all of the ideas that I have listed have already been thought of and tried, and it seems pointless debating by what margin this will fail.

[dvgrn]

If I'm interpreting your post correctly, all of the ideas that I have listed have already been thought of and tried, and it seems pointless debating by what margin this will fail.

I definitely don't want to claim that all of your ideas have already been thought of and tried. Some of them definitely haven't been tried. Some of them seem so impractical to me, based on my very vague intuition about the size of the search tree involved, that I can't even think of how they could be tried in practice. But I could very well be wrong.

So what I'm saying is more like this:

1) your ideas don't include any actual runnable code, so in my book they count as 'hand-waving'.

2) The person who posts a vague idea about a search program design is generally the best candidate for turning that vague idea into an actual search utility; if they can't figure out how to do it, the odds are that nobody else will understand the idea well enough to do it either.

3) Generally there isn't any shortage of ideas for search programs -- there's only a shortage of actual implementations of search programs... especially search programs that have been proven to be useful, by finding something that no other search program has found.

[MathAndCode]

I definitely don't want to claim that all of your ideas have already been thought of and tried. Some of them definitely haven't been tried. Some of them seem so impractical to me, based on my very vague intuition about the size of the search tree involved, that I can't even think of how they could be tried in practice. But I could very well be wrong.

So what I'm saying is more like this:

1) your ideas don't include any actual runnable code, so in my book they count as 'hand-waving'.

2) The person who posts a vague idea about a search program design is generally the best candidate for turning that vague idea into an actual search utility; if they can't figure out how to do it, the odds are that nobody else will understand the idea well enough to do it either.

3) Generally there isn't any shortage of ideas for search programs -- there's only a shortage of actual implementations of search programs... especially search programs that have been proven to be useful, by finding something that no other search program has found.

Alright; I shall start formulating ideas. Please keep in mind that I am also working on reducing the cost of universal construction, creating an outline/demonstration for introducing newcomers to how to discover patterns, and more, as well as real-life responsibilities, of course, so the amount of time that I will devote to this is limited.
First, I'd like to know of any other programs that have been developed that I could use as a starting point so I won't have to do unnecessary work. You gave me the link to one example, but there might be attempts that more closely match my idea.
For the idea of requiring the pattern to be consistently moving be realized, I just thought of a solution that is much simpler than my original idea of storing at least six forward movement mechanisms and matching each frame to the front of the region: Simply measure the x-coordinate of the cell farthest to the east (or the analog for some other direction) and require it to increase every so often. I'm somewhat tempted to allow 90° turns, but that would make the branching factor worse, and I don't want to do that.
One thing that might be more of a challenge than I originally anticipated is efficiently weeding out predecessors that are difficult to make. I figured that some of the unhelpful predecessors could be filtered out by counting the ratio of cells that survive from one generation to the next, but that could also disqualify perfectly legitimate patterns where a bunch of cells on the inside were just born, so in the next generation, many of them die, and they throw off quickly dying sparks. (Examples include generations 8–9, 18–19, and 26–27 of the R-pentomino.) Of course, we could just count the number of predecessors for each object, but I don't want to have to do that because that would likely be more computationally expensive. There might be some machine-learning algorithm that could do the task, but that would carry the same problem. Does anyone have any ideas?
Lastly, what are we going to do if one of the predecessors also drops an object behind it instead of just sparks? I think that the program should try to investigate it as a transparent catalyst because it could serve as a helpful reset point (since every object with less than a certain number of cells will only last so long before either ceasing to be active or getting larger than a certain size), but that could be a computational hassle.

[wwei23]

This seems like an interesting idea, though I have absolutely no idea how to implement it. Good luck.

[MathAndCode]

This seems like an interesting idea, though I have absolutely no idea how to implement it. Good luck.

I outlined a rough framework for getting started in my previous post.