@dvgrn:
I'm reading your three last posts very caryfully to try to think straight about all this. I may have more comments later...
I think it will be meaningful to do all of these three things that we've already suggested:
- Have a list of the end results of small common reactions, that are likely to show up in fundamentally different ways. This is what I'm trying to adress with my soup search as discussed before.
On a side-note unrelated to elbow recipes: It would be interesting to find out what the most common predecessor is of each of the results of my soup search. Except for the most generic results, like two blocks close to each other, it seems likely that each result is connected to a small common predecessor.
I'm not very concerned about keeping this list small. We'll insert all orientations of them in a hash table before starting the search, so having a long list won't really hurt performance much.
I think it would be interesting to get to know about it, whenever such a result showed up, and then we can worry later about if it seems worth it to do a deep search with that as a starting point.
- Have a list of intermediate points in known useful recipes. Branching points are the most important, but it doesn't have to be limited to that. The only problem is that the list needs to be updated every time a new recipe is discovered -- I guess it could be automated some way. These would be inserted in the hash table too.
- Report any intemediate result that fit in a small bounding box. This of course is because shouting more gliders at it have a higher probability to reach all objects in the ashes than intermediate results with a bigger bounding box. We could then look at these and decide if it looks promising enough ta start a new search from that staring point.
dvgrn wrote:
I'm not quite sure about that. We could try to do deep searches from millions of potential elbows. Maybe we'll find that 99.9% of those searches end at depth 1, because no matter what glider you send second, the reaction always explodes or vanishes or makes a constellation that's bigger than our arbitrary threshold. Then we only have thousands of deep searches to run, and we can choose a meaning of "deep" to allow for a manageable total workload.
I might have not been very clear about what I meant. We will already try to deepen the search from millions of potential elbows as part of the regular search, at least as far as internal memory can hold (maybe a hundred million). For each additional glider at 90+ distance, the number of stable results seems to increase by something like a factor of 3. That means at least 10% of tested salvos create a new potiential elbow. Which is lucky, because if the number of results decreased with each new glider, we'd quickly run out of things to do...
What I meant was more like, can we use some good principles to pick out a few results that would be meaningful to start new deep searches from. And I guess the three ways I mentioned above are indeed possible ways to do that. Maybe we can think of more ways?
Thanks for the links, I took a look at this.
So far, as acknowledged by the author, this project uses a pretty straight-forward way to evolve patterns.
The code I had already written was a bit more efficient, and I already had most components I needed to put together the soup searcher, so I just did
So far, I use a byte grid for cells, and an additional smaller "tile map", where each byte corresponds to a 8-by-8 tile of the cell grid, and simply tells if that part of the grid is empty or not.
The evolve function processes 8 cells in parallel, by using 64-bit integers, and has no conditional statements in the inner loop (conditionals are very expensive if the condition depends on something that is essentially random, like cell states).
I could have used simsim314's LifeAPI, but I really don't see how a 64-by-64 tile would be enough for this search.
Maybe I'll start battling with bit fields and 64 cells parallel evolution eventually, it would probably be at least 3 times faster.
dvgrn wrote:
So what do you plan for a next step?
Now when the holidays are over, each step will take much more time...
My search program still doesn't know that the distance from the previous glider doesn't matter (except for the P2 phase), if the target is already stable when the next glider starts reacting with it. When that logic is in place, it will gain a lot of speed.
dvgrn wrote:
It just occurred to me that a block in the turns-to-honeyfarm position (instead of the pi-explosion position) might be a solution to the elbow-duplication problem. Just send even-parity gliders at p90 (or whatever) to make a crystal.
This is interesting, but it also gave me an idea for a fast adjustable elbow duplicator. It uses a recipe with a return glider that collides with the input stream. I found it with chris_c's script, and I assumed it's wouldn't be very useful.
For it to work, we need a way to get from a honeyfarm in the "crystal" position, to a block. I'm searching for one, and it looks possible, but not very easy.
To show this idea, I'm cheating and using a recipe with minimum distance 49 ticks to get from a honeyfarm to a block:
Code: Select all
x = 2097, y = 2101, rule = LifeHistory
2095.2E$2095.2E26$2071.2A$2072.2A$2071.A25$2044.2A$2043.A.A$2045.A51$
1991.2A$1992.2A$1991.A21$1968.A$1968.2A$1967.A.A55$1911.3A$1913.A$
1912.A20$1889.A$1889.2A$1888.A.A56$1831.3A$1833.A$1832.A20$1809.A$
1809.2A$1808.A.A56$1751.2A$1752.2A$1751.A21$1728.3A$1730.A$1729.A183$
1543.3E$1542.3BE$1542.2BE$1543.B102$1438.2C$1437.C.C$1439.C10$1426.C$
1426.2C$1425.C.C66$1358.2C$1357.C.C$1359.C10$1346.C$1346.2C$1345.C.C
66$1278.2C$1277.C.C$1279.C13$1263.C$1263.2C$1262.C.C63$1198.2C$1197.C
.C$1199.C13$1183.C$1183.2C$1182.C.C126$1055.2A$1056.2A$1055.A25$1028.
2A$1027.A.A$1029.A51$975.2A$976.2A$975.A21$952.A$952.2A$951.A.A55$
895.3A$897.A$896.A78$815.2A$816.2A$815.A29$784.2A$785.2A$784.A47$735.
3A$737.A$736.A24$709.2A$710.2A$709.A52$655.2A$656.2A$655.A24$629.A$
629.2A$628.A.A52$575.2A$576.2A$575.A25$548.2A$549.2A$548.A95$451.3E$
453.E$452.E25$424.2E$425.2E$424.E20$402.E$402.2E$401.E.E22$378.3E$
380.E$379.E20$356.E$356.2E$355.E.E21$333.2E$334.2E$333.E20$311.E$311.
2E$310.E.E21$288.2E$289.2E$288.E126$160.3C$162.C$161.C28$130.2C$131.
2C$130.C48$80.3C$82.C$81.C20$58.C$58.2C$57.C.C56$2C$.2C$C!