JHersrch

[Kasuha]

I'm trying to start developing new version of Hersrch and while I have many plans for improvements, things are going slow - what I've done so far does not involve any actual coding yet.

First idea I had was that with Golly now around, it could be possible to make the component/variant definition simpler. There would be just one pattern in a multistate rule which would contain both information about the beginning and ending group (with intent of supporting multiple groups, not just Herschel), their mutual position, contents of the initial patterns, usage area, and catalysts supporting evolution of the pattern which must not collide with other components.

Second thought here is that it might be useful also for the effort of extending the current Hersrch so maybe you could give it a try, too.

Hersrch.table:

Code: Select all

n_states:8
neighborhood:Moore
symmetries:permute

# 0 - dead cell which was dead since start and didn't change
# 1 - live cell which was alive since start and didn't change
# 2 - dead cell which was dead at the start, then became live, then died again (active)
# 3 - dead cell, manually marked (end group)
# 4 - dead cell, manually marked (end group + start group)
# 5 - dead cell which was alive at the start (start group)
# 6 - live cell which was alive at the start, then died, then became alive again (catalyst)
# 7 - live cell which was dead at the start

var livea={1,6,7}
var liveb={1,6,7}
var livec={1,6,7}
var lived={1,6,7}
var deada={0,2,3,4,5}
var deadb={0,2,3,4,5}
var deadc={0,2,3,4,5}
var deadd={0,2,3,4,5}
var deade={0,2,3,4,5}
var deadf={0,2,3,4,5}
var deadg={0,2,3,4,5}
var anya={0,1,2,3,4,5,6,7}
var anyb={0,1,2,3,4,5,6,7}
var anyc={0,1,2,3,4,5,6,7}
var anyd={0,1,2,3,4,5,6,7}

# birth on three neighbors
0,deada,deadb,deadc,deadd,deade,livea,liveb,livec,7
2,deada,deadb,deadc,deadd,deade,livea,liveb,livec,7
3,deada,deadb,deadc,deadd,deade,livea,liveb,livec,7
4,deada,deadb,deadc,deadd,deade,livea,liveb,livec,6
5,deada,deadb,deadc,deadd,deade,livea,liveb,livec,6

# death on underpopulation
1,deada,deadb,deadc,deadd,deade,deadf,deadg,anya,5
6,deada,deadb,deadc,deadd,deade,deadf,deadg,anya,5
7,deada,deadb,deadc,deadd,deade,deadf,deadg,anya,2

# death on overcrowding
1,anya,anyb,anyc,anyd,livea,liveb,livec,lived,5
6,anya,anyb,anyc,anyd,livea,liveb,livec,lived,5
7,anya,anyb,anyc,anyd,livea,liveb,livec,lived,2

# state change for catalyst cell when touched by active pattern
1,deada,deadb,deadc,deadd,deade,anya,livea,7,6
 

Hersrch.colors (I prefer dark cells on white background so feel free to adjust it according to your preferences):

Code: Select all

color=0  255  255  255
color=1    0    0    0
color=2  192  255  255
color=3  192   64   64 
color=4  128  128   64
color=5   64  192   64
color=6    0    0  255
color=7   96   96   96

Processing a component into the pattern would then go as follows:

1/ paste standard 2-state component including starting group into the rule

Code: Select all

x = 26, y = 23, rule = Hersrch
A$3A$3.A$2.2A18.A$21.2A2$19.3A2.A$21.A.A.A$22.A2.A$23.2A$.A$.A.A$.3A
12.2A$3.A11.A2.A2.2A$15.A.A4.A$16.A5.A.2A$19.2A.A.A$19.A2.A2.A$16.A4.
A2.2A$16.5A2$18.2A.A$18.A.2A!

2/ run the pattern, deleting any excess gliders (by state 2), until final group appears

3/ overwrite final group by state 3. If initial group overlaps with final group, mark overlapping cells using state 4.

Code: Select all

x = 28, y = 29, rule = Hersrch
16.B$15.3C$15.BCB$14.2B3C$14.5B$14.6B$2.A11.6B$2.3A9.5B$5.A7.6B$4.2F
3.B4.6B3.GF$4.8B.7B3.2EG$6.13B3.G.B$6.13B2.EFEB.A$5.16B.GE.F.A$3.17B
4.A2.A$.18B6.2A$.2BE13B$3BEBE4B.7B$.2B3E4B2.B.4B2F$.4BE4B7.F2BF2.2A$
2.7B8.FBFB3.A$18.F4B.A.2A$20.B2F.A.A$20.BFB.A2.A$18.A4.F2.2A$18.5A2$
20.2A.A$20.A.2A!

4/ continue running the pattern until all oscillators return to initial state and the leftover activity settles (or remove it using state 2)

Code: Select all

x = 28, y = 29, rule = Hersrch
16.B$15.3C$15.BCB$14.2B3C$14.5B$14.6B$2.A11.6B$2.3A9.5B$5.A7.6B$4.2F
3.B4.6B3.BF$4.8B.7B3.2FB$6.13B3.B.B$6.13B2.3FB.A$5.16B.BF.F.A$3.17B4.
A2.A$.18B6.2A$.2BE13B$3BEBE4B.7B$.2B3E4B2.B.4B2F$.4BE4B7.F2BF2.2A$2.
7B8.FBFB3.A$18.F4B.A.2A$20.B2F.A.A$20.BFB.A2.A$18.A4.F2.2A$18.5A2$20.
2A.A$20.A.2A!

5/ perform any additional edits you find suitable and you're done

You can always re-run the pattern by overwriting initial state (4, 5) by state 1. Of course you must also restore the final group in the end.

For another example, pattern defining a component changing "H-minus-6" group into Herschel is this:

Code: Select all

x = 8, y = 6, rule = Hersrch
.EB$2B2EC$3BEDBC$.2B.CDCB$5EBC$3BEB!

The resulting pattern will be then used as follows:
- position, orientation, and type of initial group (states 4 and 5)
- position, orientation, and type of final group (states 3 and 4)
- active area of the component (states 2, 3, 4, 5, 6, and 7)
- catalyst areas of the component (state 6 and its immediate neighborhood)
- structure of the component to be used when building the circuit (states 1 and 6)

When checking for collisions, Hersrch would not test active areas against each other, rather catalyst area of one component against active areas of other components. Therefore there's no need to shape the active area. You may want, however, to mark some catalysts by state 1 if they are not essential and may eventually overlap with something.

Regarding further development I intend to switch definitions from many files as they are now to using just a single definition file containing all components and their variants, probably encoded using slightly extended JSON with search parameters defined using another JSON-encoded file instead of extending already huge amount of command-line parameters. Hersrch would then run with just two parameters, one specifying the definition file and the other specifying the file with search parameters.

I understand that what was done so far does not really deserve a post yet because there's not much to use on it ... but I'd hate to miss something obvious and only realize it when it's too late. So any comments are welcome.

[Kasuha]

For those who prefer bright cells on dark background there's a color table similar to LifeHistory.

Hersrch.colors

Code: Select all

color=0   48   48   48
color=1    0  255    0
color=2    0    0  128
color=3  255   48   48 
color=4  255  128  160
color=5  255   48  255
color=6   48  255  255
color=7  192  192   48

[Sokwe]

pattern defining a component changing "H-minus-6" group into Herschel...

Do you intend to define the pre-Herschel+block type dependent conduits by using the "H-minus-6" starting group, like this?

Code: Select all

x = 35, y = 35, rule = Hersrch
19.3B$19.5B$18.6B$18.8B$18.8B$12.B4.9B$11.3B3.11B$9.6B2.13B$3.4B2.7B.
13B$.E27B$2B2E26B$3B2E25B$.4BE2B2F21B$5E3B2F22BC$3BE28B2C$5.28B2C$7.B
2.22B2C$9.24B$8.24B$8.24B$6.2AB2.20B$5.A.A3.18B$5.A6.18B.B$4.2A7.18B
2F$13.18B2F$13.3B3.13B$14.B2.3B.11B$17.2F2.9B$18.A3.7B$15.3A5.4B$15.A
8.5B$27.2F$27.A$28.3A$30.A!

If so, would you want the other conduits that normally end with a Herschel to end with the "H-minus-6" group instead?

Code: Select all

x = 30, y = 23, rule = Hersrch
2.A$2.3A12.B.3B.B$5.A10.10B.C$4.2F3.B5.2B2F5B5C$4.8B3.2B2F10BC$6.8B.
12B2C$6.20B2C$5.15B.2B2.C$3.17B$.18B$.2BE15B$3BEBE4B.7B$.2B3E13B$.4BE
14B$2.7B2.8B$13.6B$13.5B$14.4B$14.4B$15.B.BFA$17.BF.A$20.A$20.2A!

with intent of supporting multiple groups, not just Herschel

Do you also intend to include the Herschel transceivers?

[Kasuha]

Do you intend to define the pre-Herschel+block type dependent conduits by using the "H-minus-6" starting group, like this?
If so, would you want the other conduits that normally end with a Herschel to end with the "H-minus-6" group instead?

I'm still undecided about a lot of things including this but it's one of options. It may be e.g. used for components which are not dependent on following Herschel's glider (because implementing conditions which go further than to adjacent component would be uncomfortable). Original intent was to support R, B and Pi besides just Herschels and for the sake of the example I needed a component where starting group overlaps with ending group.

Do you also intend to include the Herschel transceivers?

That's also one of options, too. Actually the intent is to allow defining your own signal groups because I am not sure that we exhausted them yet. Of course it will come with increased memory demand proportional to number of these groups used and particularly gliders will be probably one of the more hungry ones as their basic "advance" component has step of just two or four generations, which will result in filling the search space with a huge amount of reachable states.

[dvgrn]

When checking for collisions, Hersrch would not test active areas against each other, rather catalyst area of one component against active areas of other components. Therefore there's no need to shape the active area. You may want, however, to mark some catalysts by state 1 if they are not essential and may eventually overlap with something.

That seems to address the only potential problem I've thought of so far, along the lines of my attempted distinction (in the Herschel update thread) between "primary" and "secondary" catalysts. Any catalysts that just suppress output gliders would obviously be secondary, state-1-only catalysts, for example. I'm not sure about the first block-suppressing eater in F117 and similar, or the blinker-suppressing eater in the Fx77. There are at least a couple of different placements for that Fx77 eater, so maybe marking it as nonessential would be the best bet.

Will there be a forbidden-tuples section in the new JSON data file? Seems like it would be nice to have fixes for specific conduit combinations, so that JHersrch could build really clean tracks that actually work with no editing needed, a bit more reliably. Maybe this would just be for pairs, or maybe the same trick could work for triples and larger combinations. If the fixes were given as XOR patches to the standard conduits, then they'd at least have a fair chance of working most of the time, even for A+B+C tracks where there's a patch for A+B and another one for B+C.

I'd love to have JHersrch be able to work with single-glider inputs and outputs. Standard stable G-to-Hs are certainly embarrassingly big and awkward, but p8 G-to-Hs are quite nice, and of course we have p4 as well as p5/6/7/8 glider reflectors now. I definitely see the problem with the search tree very quickly getting impossibly big, though...

Maybe there are reasonable constraints that could be set -- no more than N reflectors, no more than one H-to-G converter and one G-to-H... and this kind of search would be most useful in very small spaces, so the trick might be to start really small and search gradually larger areas, until the first solutions start to show up...?

I was also wondering about Herschel-to-junk converters -- Herschel-to-beehive, Herschel-to-block, and so on, with plenty of room around the output object(s). Seems like there are an enormous number of these out there, really, that have some potential for stable circuitry -- junk that can be used to reflect an incoming glider, or help with the construction of something more complicated (a *WSS, a switch engine, a 2c/3 signal, or whatever). There's never really been a good place to collect all of these converter conduits. But it could be very useful to be able to search for, say, a track with a Herschel input _here_ that places a block _there_ between 600 and 800 ticks later, without hitting the pattern that's intended to make use of that block.

-- And I guess that's a separate question: might it be possible to define a forbidden "active area" around the starting point, and another one around the ending point, so that candidate tracks for open-ended searches will fit into the space they need to fit into? This is slightly different from just making sure that the starting conduit releases a glider if it needs to, or the ending conduit doesn't require a dependent conduit to follow it if there won't actually be one there. Maybe this would be simpler to do with a post-search filter on the results?

[Kasuha]

Things are going embarrassingly slow now, I have started coding but have nothing that works yet. Discussing new features in this stage feels a bit premature. There definitely will be forbidden sequences just like in the old Hersrch because otherwise it would generate too many impossible circuits.
It should be possible to add glider as one of transport groups.
Constraints on resulting circuit can sure be added too, but they will not constrain how full the search space will get as they can be only applied in the final phase.
Regarding herschel-to-junk, it should be possible to add, too, if you define the junk particle as a transport group with no conduits that accept it. Or perhaps later it can be added in a form which would not even extend the search space but discussing that is premature now.
Forbidden areas at the start or at the end should be possible too ... but again, let's discuss that when something is working already.

[Kasuha]

Okay... I have to apologize to anyone whose hopes I might have put up, but I have to put this project on hold for indefinite time. I thought that maybe during Christmas holidays I'll be able to work on it and get something done but unfortunately Real Life (tm) made me reconsider my preferences and give up on some of my interests, this project being one of them. It'll stay on my hard drive and I may return to it sometime but at present I cannot promise it will be anytime soon.
Sorry.