Self-destruct search program

[simsim314]

I saw the current destroy.exe has limitation of 248x248 grid. Can you change/remove/make possible to adjust/make additional version where the limitation is higher or non existent?

[simeks]

I saw the current destroy.exe has limitation of 248x248 grid. Can you change/remove/make possible to adjust/make additional version where the limitation is higher or non existent?

The reason for the limit is that intermediate results from one round are stored down into a byte stream, using one byte for each coordinate value. I could make a fix for that, but it would be helpful to know what is likely to be an acceptable limit, 504×504, 1016×1016, or more than that?

[simsim314]

I could make a fix for that, but it would be helpful to know what is likely to be an acceptable limit, 504×504, 1016×1016, or more than that?

Well for now I managed to fit exactly at the 248 boundary, but I think some of the posts for Orthogonid etc. could be much larger. I think the largest construction I can think of (say quadratic replicator) is even larger than 1016x1016.

The reason for the limit is that intermediate results from one round are stored down into a byte stream, using one byte for each coordinate value

If you need this not as a hash - maybe it's better to copy the whole result, calculating the bounding box at the beginning of the run. I'm afraid making assumptions like this is hurting the app, while the major performance issue is probably the iterator anyway.

If you only need this as a hash for "been there done that" you could easily create some hash function even of size 64 bits. You can take the bounding box divide into 64 bit streams, and then make some not trivial hash function. For example (taken from LifeAPI):

for(int i = state->min; i <= state->max; i++)
{
result += CirculateRight(state->state, i);
result += CirculateLeft(state->state, (i + 7) % 47);
}

[apg]

248-by-248 has always been fine for me (and the way that GoLGrid works, I think that increasing the grid area also increases the time it takes to compute a generation proportionally). For destroying larger mechanisms, it's more time-efficient to break it into pieces, run destroy256 on each piece in parallel, and add a few extra still-lifes to trigger the destruction of each piece from a single input glider.

[simeks]

If you only need this as a hash for "been there done that" you could easily create some hash function even of size 64 bits. You can take the bounding box divide into 64 bit streams, and then make some not trivial hash function.

The byte stream is not used as a hash. GoLGrid already has a nice vectorizable hash function that I've used in most projects so far. It's based on the public domain MurmurHash by Austin Appleby, but instead of multiplying the current hash with a constant for each word (which prevents vectorization) each word in the key is xor-ed with a random word which is specific for the position of that key word in the grid.

For example (taken from LifeAPI):

for(int i = state->min; i <= state->max; i++)
{
result += CirculateRight(state->state, i);
result += CirculateLeft(state->state, (i + 7) % 47);
}

The problem with such a simple hash function is that it's easy to find different patterns that hash to the same value, for example these two do (note that the position of the block differ):

Code: Select all

x = 144, y = 64, rule = LifeHistory
64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B
$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.
64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B
16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$
64B16.64B$64B16.64B$64B16.31B2A31B$64B16.30BA2BA30B$64B16.31B2A31B$
64B16.64B$64B16.64B$64B16.64B$64B16.37B2A25B$36B2A26B16.37B2A25B$36B
2A26B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.
64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B
16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$
64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B$64B16.64B
!

248-by-248 has always been fine for me (and the way that GoLGrid works, I think that increasing the grid area also increases the time it takes to compute a generation proportionally). For destroying larger mechanisms, it's more time-efficient to break it into pieces, run destroy256 on each piece in parallel, and add a few extra still-lifes to trigger the destruction of each piece from a single input glider.

I pretty much agree, and I think the program will have trouble producing useful results for larger patterns anyway. Still it would be an easy fix to increase the limit a bit, and it will not affect performance much, because the GoLGrid datatype keeps track of the bounding box of the pattern it contains at all times, and will only evolve those parts.

[Hippo.69]

I have to look at this topic (I have not looked at the code yet).
I would rather think about glider(s) invoked destructions than the *WSS(s) destructions, as it is much easier to got a glider.
As I understand from the comments the code is looking for the objects (from a limited set) to be added (to limited regions)
to affect the ongoing reaction, such that the reaction stabilises after each added object and the evaluation function somehow evaluates the remaining objects (to be destroyed).

To use it for big patterns (ECCA in my case) you need to split the pattern to smaller regions and compute SoD for each region separately and then create gliders to reach each of the regions in the predetermined way. It seems to me it could be advantagous to allow escaping gliders from the region (probably limited some way), so the regions could serve as splitters/reflectors as well.
Destroying an escaping glider could be easier then adding additional splitters. Reflecting the escaping gliders the required way to other regions is probably the cheapest solution... (especially when the regions are far apart).

OK, no I am reading the code. I will write my toughts (cs teacher habbit) ... mid_x mid_y ... doubles just to allow halves? Maintain twice the value. length_sq ... maintan four times the value.

You compute complete "geometrical graph" probbably just to compute the minimum spannng tree.
If you want to use it for bigger patterns, consider to filter some of the edges whose cannot be part of the MST. Slsparse/pslmake could be an inspiration. (Filter does not mean consder the edge and reject it, but rather not consider it at all).
You use Kruskal algorithm to find the minimum spanning tree. Using disjoint find union technique, rather to renaming an entire component would be better (for bigger graphs). Anyways if you use it on complete graph you will still be on quadratic complexity (times log for sorting).

Oh MAX_CENSUS_OBJECTS = 512, so the complexity of the MST computation could be already important.

I like the actual cost of the edge is computed only for minmum spaning tree egdes. (I am not sure how to write the expression most efficiently ... there is a Newton interpolation in each sqrt and one would probably suffice for the entire function ... but this would not be important).
... continue reading
It tests p2 stability? So should be changed for p8 based patterns? It would be nice to know the pre destruction pattern period and check corresponding stability.

I do not understand why you use different global positions (for patterns) for each function, when the functions newer call one other. But OK let it be a style. But would adding a pattern to a function cause global renumbering, I do not think the style is good for code maintainance.

do not like "s32 stable_gen = gens_until_stable (in_setup); run_for_gens (in_setup, stable_gen);"
You can copy the final pattern from gens_until_stable rather to running the simulation twice (mod 3 calculation required to find the global pointer ... if not fixed for the purpose).

(Hmm, looking at meaning ... implementation of bleed ... so for the golgrid ... and I am confused what the pop_?_on, pop_?_off represent ... set_empty_population_rect ... I am not fun of an overcommented code, but there some hint would help. Oh its the estimate of the minimal/maximal coordinate of a living cell (and the pattern is expected to be "around the region center"). It probably only expands, but does not shrink... hmm except the tighten_pop_*... oh OK, corresponding tightening is called whenever a somehow extreme cell dies.)

OK, back to the reading destroy.c. I like the forbidden_area, must_touch_area concept. But I would try to generate objects filtered by the must_touch _area (not thinking about other objects at all) rather to have a global object list ready what would be filtered.
OK make_pos_objects called with must_touch_area could be much more efficient then trying all possible postions. ... or with all shifts by object cells ... probably already fitered by forbidden_area.

Is it DFS on relevant inserted objects returning first found solution? I must read it wrongly ... the MST evaluation must be used somehow.
Oh OK, the run_setup inserts promissing sequences to the beam ...

OK I got the idea. The most important change request would be parametrized period (allowing at least 1,2, and 8 ) and incorporation of modfied stabilty test alowing an outgoing glider ... not crossing the forbidden area. I would probably incorporated the pslmake expected costs of added objects to the evaluation as well. It would be nice to prepend the search for the starting glider line/timing to start the destruction effcently.
After some optimization it would be nice to automate larger pattern splitting to parts where chain reaction is more promissing then long jumps by reflected emitted glider. ... may be automated from the edge lengths of the minimum spanning tree of the initial pattern.

[Hippo.69]

I have created unknown glider activated seed of destroyal.
https://github.com/Hippo-69/CGoL_gSoD.
It has to be tested ... it is based on simeks work and mainly on calcymans pslmake (parallel beam implementation).

The goal of the program is to compute for lifehistory patterns of parts of circuit a one time 2 glider splitter / glider turner / glider seed of destroyal.
The extended otsplitters/ turners/ sod's should be manualy connected by simple otsplitters / turners to create seed of destroyal of the entire circuit.

(It probably could be later (after a lot of experiments) automated to compute mst of the entire circuit and split the pattern to parts on mst tree edges longer than a given treshold (where it becomes more effective to send gliders than extending reaction by adding catalysts) ... and possibly automatied insertion of simple otsplitters / turners as well).

I have not experimented with using other then euklid lengths of edges. Progress evaluation uses only mst length, cost evaluation uses scaled current costs of the added objects.

Hmm, it seems to me deciding early generation as stable generation - 256 would be a bottleneck for bigger patterns, as the tail or the reaction is often far away from the remainder of the pattern so we actually want to continue reaction near the remainder of the pattern rather near the place where nothing remains.

So computing "remainder neighbourhood stable generation" could help.

Here is an example, where computation of early is definitely bad:

Code: Select all

x = 112, y = 208, rule = B3/S23
23b2o11bo$23b2o10bobo$35bobo31b2o$34b2ob3o2b2o25bo$40bo2bo23bobo$34b2o
b3o3bobo21b2o$34b2obo6b2o7$31b2o13b2o$31b2o13b2o$16b2o$15bo2bo$14bob2o
$14bo$13b2o$28b2o$28bo$29b3o23b2o$31bo24bo$53b3o4b2o$53bo6b2o5bo$65b3o
38b2o$49bo14bo41bo$49b3o12b2o38bobo$52bo47b2o2b2o$51b2o47b2o3$52b2o$
52b2o17b2o$71b2o6$68b2o$68bo19b2o$69b3o15bobo18b2o$71bo15bo20bobo$65b
2o19b2o22bo$65bo44b2o$66b3o$68bo4$103b2obo$103b2ob3o$109bo$103b2ob3o$
104bobo$104bobo$105bo5$64b2o$64bobo$35b2o29bo$34bobo29b2o$34bo$33b2o$
54b2o$54bo$55b3o$57bo$48b2o$48bobo$50bo$50b2o4$51b3o3$57b2o$57bo$38b2o
15bobo$38b2o15b2o12$4b2o31b2o$5bo30bobo$5bobo19b2o7bo$6b2o18bo2bo5b2o$
27b2o$21b2o$21b2o3$4b2o$4b2o5b2o15b2o$11b2o16bo$29bobo15b2o$17bo12b2o
15b2o$16bobo$9b2o6bo$10bo$7b3o$7bo3$8bo$7bobo$8bo2$48b2o$48bobo$13b2o
35bo$12bo2bo34b2o$13b2o6$57b2o$57bo$38b2o15bobo$38b2o15b2o2$bo$obo$obo
$bo5$6b2o$7bo$7bobo27b2o$8b2o26bobo$36bo$23b2o10b2o$3b3o17b2o$39bo$14b
2o22bobo$6b2o6b2o10bo11bo2bo$6b2o18bo12b2o$26bo2$19bo$18bobo26b2o$11b
2o6bo6b3o18b2o$12bo$9b3o47b2o$9bo49bo$60b3o$62bo$36b2o$37bo19b2o$37bob
o17bo$38b2o15bobo$50bo4b2o$49bobo$49bobo$38b2o10bo$37bobo22b2o$37bo24b
2o$36b2o$51b2o6bo$51bo6bobo$52b3o2bobo$54bo3bo24$14b2o$13bobo$15bo!

It's perfect that the faraway trash is removed, but it takes so long tht continuation near far trash liquidation is not what we want.
The remaing portion of the pattern stabilised at generation 1567, while the faraway trash at generation 1908. Early should be 1311 rather to 1652.
Or the search should be modified to try different early generations.

[Hippo.69]

There was a bug ... incorrect use of hashing (rather dependent on the thread then on the pattern), the git https://github.com/Hippo-69/CGoL_gSoD updated (with few other unimportant changes).