Goucher-Grankovskiy construction arm

Post by **calcyman** » June 21st, 2023, 11:40 am

Hippo.69 wrote: ↑
June 21st, 2023, 8:42 am

calcyman wrote: ↑
June 21st, 2023, 6:18 am

Hippo.69 wrote: ↑
June 21st, 2023, 3:53 am
I expert bigger X_i sets depending on current DBCA configuration including arm block position (agnosticised salvo is the input) and 3 semistates. But we can prune vertices not on optimal paths during the search.
The block arm position is determined by the last glider fired, as are the states of 3 of the semisnarks and all of the bistable switches. So it's only the fourth semisnark state and the particular choice of output glider (from the alternatives for that glider) that togerher fully determine the DBCA's complete state.
Yes an no. You forget that my agnosticise not only determines the periodicity, but also line options. I consider the original salvo only as source of p8 inbetween configurations and any gliders with the same sequence of inbetween configurations are possible alternatives.

Yes, I'm aware of that, but I don’t see how it changes what I've written? Let's consider the case where the 17th glider in the salvo deletes an excess block. Then your agnosticise script will find 12 alternatives (6 lanes and both phases), so X_17 contains 12 possible alternatives for that glider. For each of these, there are 2 possible final states of the DBCA (depending on that semisnark; everything else is determined), so we need only 12 * 2 = 24 vertices in the 17th level of the dynamic programming DAG, in complete agreement with what I wrote.

Hippo.69 · Post by **Hippo.69** » June 21st, 2023, 12:44 pm

calcyman wrote: ↑
June 21st, 2023, 11:40 am
Yes, I'm aware of that, but I don’t see how it changes what I've written? Let's consider the case where the 17th glider in the salvo deletes an excess block. Then your agnosticise script will find 12 alternatives (6 lanes and both phases), so X_17 contains 12 possible alternatives for that glider. For each of these, there are 2 possible final states of the DBCA (depending on that semisnark; everything else is determined), so we need only 12 * 2 = 24 vertices in the 17th level of the dynamic programming DAG, in complete agreement with what I wrote.

OK:), actually I am not sure only one semisnark could differ (the vertices represent finished level), phase of glider could differ, lines could allow different colors, number of cycles could differ (so semisnark for clocking phase...). The same arm block position could correspond to emissions of both colors. But we just have to create vertices for achieved emissons and their number does not matter ... just we have to encode them.
Of course we continue search only with "shortest" in each "state".

Post by **calcyman** » June 22nd, 2023, 7:52 am

calcyman wrote: ↑
June 12th, 2023, 6:37 pm
Defragmentation of the slow salvos. This is already done very well by vanilla slmake. (Yes, it's frustratingly slow, but that's only really a problem when you have > 10000 gliders. In any case, I have some preliminary ideas for parallelising this step, so I'll work on implementing this in pslmake.)

Even without parallelism, a small amount of precomputation should be able to make the defragmentation run much more quickly (specifically, by eliminating candidate reorderings without having to simulate them).

Specifically, we run the slow salvo one glider at a time, changing the pattern P to the pattern P'. We track the 'lifetimes' of individual cells, seeing which glider was responsible for creating them, and which glider was responsible for later deleting them (if any). This imposes a directed acyclic graph on the set of gliders in the salvo, and a reordering is valid only if it's consistent with the DAG. (The converse is not true: there could be reorderings that don't work despite being consistent with this DAG, e.g. because junk gets in the way, so we still need to simulate those.)

The directed acyclic graph obtained by this method can be replaced with its transitive reduction -- https://en.wikipedia.org/wiki/Transitive_reduction -- without changing the partial ordering constraints implied by the DAG.

The computation of this DAG and its transitive reduction only needs to be performed once at the very beginning of the defragmentation; it doesn't change at all when we perform the swaps (which simply correspond to changing the topological order with which we traverse this DAG).

For a candidate swap A,B;C,D --> A,C;B,D, we immediately reject the swap if there's a glider in B that's connected by an edge in the transitive reduction to a glider in C. Indeed, for each position of the semicolon, we can efficiently compute the space of DAG-compatible positions of the two commas, and then find the swap which gives the greatest reduction in L1 loss. For a lot of positions of the semicolon, namely those which occur between two gliders that are connected by an edge, no swaps whatsoever are possible.

Hippo.69 · Post by **Hippo.69** » June 23rd, 2023, 11:21 am

calcyman wrote: ↑
June 21st, 2023, 2:40 am

calcyman wrote: ↑
June 19th, 2023, 12:01 pm
It costs 905 monochromatic gliders to build the entire white section:
885 gliders by improving how pslmake handles spanning trees. This took about 2 hours to produce the salvo:

Nonwhite color agnosticised (except the initial part where perpendicullar gliders interfere) (glider lines have to be changed by some additive constant): .. "incompatible wih later levels is for debugging, I have another version where the coliding levels are commented as well"
So we have to choose which trash interfers with the DBCA and should be removed as well ...