Sample Hersrch search script

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
dvgrn
Moderator
Posts: 6697
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Sample Hersrch search script

Post by dvgrn » June 30th, 2009, 12:20 am

A few weeks ago I set up Karel Suhajda's Hersrch utility to hunt for an LWSS-fleet gun as described in the superstring gun discussion. I planned to post the resulting batch-file script, in case anyone wanted a real-life example of a Hersrch search -- and today I finally got around to finishing the writeup.

With Hersrch it's often easiest to start with a "template" pattern that shows the Herschel conduits that need to be connected:

Code: Select all

#CXRLE Pos=-31,-178
x = 383, y = 361, rule = B3/S23
54b2o$53bo2bo$54b2o7$92b2o$59b2o31b2o$59bo$57b3o$90b2o40b2o$90b2o40b2o
5b2o$77b2o60b2o$78bo38bo$78bobo36b3o$79b2o39bo16b2o$75b2o42b2o16b2o$
40b2o33b2o66b2o162bo$41bo101b2o160b3o$41bobo15b2o243bo$42b2o15b2o243b
2o$318b2o$289b2o27b2o$289bo$88b2o200b3o$88b2o202bo31b2o$81b2o241b2o$
80bo2bo15b2o219b2o$81b2o15bo2bo218b2o$98bobo23b2o$99bo20bo3b2o165b2ob
2o$119bobo24b2o143bo3bo$60b2o56bobo14b3o8bo109b2o34b3o30b2o$60bobo55bo
16bo8bobo44bo39bo24b2o32bobo32b2o$62bo54b2o15b2o8b2o45b3o35b3o58b2o$
62b2o130bo33bo$81b2o110b2o33b2o24b2o$81b2o171b2o$174bo42bo23b2o$155b2o
17b3o38b3o24bo$44b2o102b2o6bo20bo36bo27bobo$43bobo102bo6bo20b2o11b2o
23b2o27b2o46bo$43bo102bobo6b2o32b2o48b2o50b3o$42b2o102b2o91b2o53bo$41b
o251b2o$41b3o$44bo88b2o$43b2o87bobo$132bo25b2o66b2o$131b2o25b2o65bo2bo
$226b2o24b2o$201b2o49b2o29b2o$202bo42b2o36b2o$41b2o92b2o62b3o8b2o17b2o
13bo2bo$41b2o91bobo62bo11bo17bo15b2o$65b2o67bo4b2o67b3o19b3o39bo$65bob
o65b2o5bo27b2o38bo23bo38bobo46b2o$67bo69b3o5bo23bo101b2o24b2o21b2o24b
2o$67b2o68bo6bobo19b3o20b2o89b2o16bo15b2o31bo$145bo20bo22bo90bo14b3o
16b2o31bobo$190b3o88bo13bo52bobo$192bo87b2o67bo3b2o$207bob2o34b2o69b2o
35b2o$207b2obo34b2o62b2o5b2o$51b2o256b2o$52bo163b2o$52b3o161b2o9$184bo
$182b3o$181bo26b2o$181b2o26bo$166b2o41bobo$167bo42b2o$167bobo$168b2o
10bo$179bobo$179bobo$11bo168bo4b2o$11b3o154b2o15bobo$14bo152bobo17bo$
13b2o152bo19b2o$166b2o25b2o88bo$193bo49bo37b3o$191bobo10b2o35b3o36bo$
191b2o11b2o34bo39b2o$240b2o$4bo351b2o$4b3o23b2o145b2o135b2o14bo25bo$7b
o21bo2bo144b2o30b2o78b2o24bo14b3o21bobo$6b2o22b2o177b2o79bo13b2o6b3o
18bo20b2o$205b2o83bobo11b2o6bo19b2o$205b2o84b2o$362b2o$249b2o112bo$
211b2o36b2o112bobo$211b2o13b2o136b2o$225bobo$16b2o147b2o58bo96b2o$16b
2o148bo57b2o10b2o84b2o$166bobo68bo$167b2o65b3o9b2o32b2o$234bo11bo20b2o
11b2o$247bo20bo$246b2o17b3o$265bo53b2o32b2o$319bo20b2o11b2o$284b2o14b
2o3b2o13bo20bo$8b2o275bo15bo3bo13b2o17b3o$3b2o2bo2bo271b3o13b3o5b3o29b
o$3bo4bobo271bo15bo9bo$2obo5bo347b2o$bobob2o351bo$o2bo2bo161b2o15b2o
118bo49b3o$2o2bo4bo158b2o15bobo105bo11b3o47bo$5b5o150b2o25bo103b3o14bo
$161bo25b2o86bo14bo16b2o52bo$4bob2o153bobo111b3o12b2o69b3o$4b2obo154b
2o114bo52bo32bo$277b2o50b3o13bo17b2o$262b2o64bo16b3o$262b2o5b2o57b2o
18bo$181bo51bo35b2o7b2o67b2o$179b3o51b3o7b2o33b2o17b2o$178bo57bo6bo3b
2o48b2o$178b2o20bo34b2o4bobo4bo18b2o$184bo15b3o38b2o5bobo16b2o$182b3o
18bo45b2o22b2o$181bo20b2o11b2o56b2o$181b2o32b2o120b2o$294b2o41b2o$294b
o19b2o$296bo16bobo59b2o$295b2o16bo61b2o$291b2o19b2o10b2o$184b2o105bo
33bo$165b2o17b2o106b3o27b3o9b2o$165b2o127bo27bo11bo19b2o$335bo17bobo$
334b2o17bo$164b2o186b2o$165bo$162b3o12b2o50b2o$162bo14bo16b2o34bo$178b
3o14bo31b3o3bob2o$180bo11b3o20b2o10bo2b4ob2o44b2o$192bo22bo14bo50b2o$
216b3o13b2ob2o2b2o6b2o$218bo14bobo4bo6bobo$233bo2b4o9bo$234bobo2bobo7b
2o113b2o$235bo4b2o123bo$362b3o$362bo3$261b2o$260bobo$260bo18b2obo$259b
2o18b2ob3o$285bo$279b2ob3o$280bobo$280bobo$281bo5$269b2o$269b2o9$98b2o
$65b2o31b2o$65bo$63b3o$96b2o40b2o$96b2o40b2o5b2o$83b2o60b2o$84bo38bo$
84bobo36b3o$85b2o39bo16b2o$81b2o42b2o16b2o$46b2o33b2o66b2o162bo$47bo
101b2o160b3o$47bobo15b2o243bo$48b2o15b2o243b2o$324b2o$295b2o27b2o$295b
o$94b2o200b3o$94b2o202bo31b2o$87b2o241b2o$86bo2bo15b2o219b2o$87b2o15bo
2bo218b2o$104bobo23b2o$105bo20bo3b2o165b2ob2o$125bobo24b2o143bo3bo$66b
2o56bobo14b3o8bo109b2o34b3o30b2o$66bobo55bo16bo8bobo44bo39bo24b2o32bob
o32b2o$68bo54b2o15b2o8b2o45b3o35b3o58b2o$68b2o130bo33bo$87b2o110b2o33b
2o24b2o$87b2o171b2o$180bo42bo23b2o$161b2o17b3o38b3o24bo$50b2o102b2o6bo
20bo36bo27bobo$49bobo102bo6bo20b2o11b2o23b2o27b2o46bo$49bo102bobo6b2o
32b2o48b2o50b3o$48b2o102b2o91b2o53bo$47bo251b2o$47b3o$50bo88b2o$49b2o
87bobo$138bo25b2o66b2o$137b2o25b2o65bo2bo$232b2o24b2o$207b2o49b2o29b2o
$208bo42b2o36b2o$47b2o92b2o62b3o8b2o17b2o13bo2bo$47b2o91bobo62bo11bo
17bo15b2o$71b2o67bo4b2o67b3o19b3o39bo$71bobo65b2o5bo27b2o38bo23bo38bob
o46b2o$73bo69b3o5bo23bo101b2o24b2o21b2o24b2o$73b2o68bo6bobo19b3o20b2o
89b2o16bo15b2o31bo$151bo20bo22bo90bo14b3o16b2o31bobo$196b3o88bo13bo52b
obo$198bo87b2o67bo3b2o$213bob2o34b2o69b2o35b2o$213b2obo34b2o62b2o5b2o$
57b3o255b2o$58bo163b2o$58b3o161b2o9$190bo$188b3o$187bo26b2o$187b2o26bo
$172b2o41bobo$173bo42b2o$173bobo$174b2o10bo$185bobo$185bobo$17bo168bo
4b2o$17b3o154b2o15bobo$20bo152bobo17bo$19b2o152bo19b2o$172b2o25b2o88bo
$199bo49bo37b3o$197bobo10b2o35b3o36bo$197b2o11b2o34bo39b2o$246b2o$10bo
351b2o$10b3o23b2o145b2o135b2o14bo25bo$13bo21bo2bo144b2o30b2o78b2o24bo
14b3o21bobo$12b2o22b2o177b2o79bo13b2o6b3o18bo20b2o$211b2o83bobo11b2o6b
o19b2o$211b2o84b2o$368b2o$255b2o112bo$217b2o36b2o112bobo$217b2o13b2o
136b2o$231bobo$22b2o147b2o58bo96b2o$22b2o148bo57b2o10b2o84b2o$172bobo
68bo$173b2o65b3o9b2o32b2o$240bo11bo20b2o11b2o$253bo20bo$252b2o17b3o$
271bo53b2o32b2o$325bo20b2o11b2o$290b2o14b2o3b2o13bo20bo$14b2o275bo15bo
3bo13b2o17b3o$9b2o2bo2bo271b3o13b3o5b3o29bo$9bo4bobo271bo15bo9bo$6b2ob
o5bo347b2o$7bobob2o351bo$6bo2bo2bo161b2o15b2o118bo49b3o$6b2o2bo4bo158b
2o15bobo105bo11b3o47bo$11b5o150b2o25bo103b3o14bo$167bo25b2o86bo14bo16b
2o52bo$10bob2o153bobo111b3o12b2o69b3o$10b2obo154b2o114bo52bo32bo$283b
2o50b3o13bo17b2o$268b2o64bo16b3o$268b2o5b2o57b2o18bo$187bo51bo35b2o7b
2o67b2o$185b3o51b3o7b2o33b2o17b2o$184bo57bo6bo3b2o48b2o$184b2o20bo34b
2o4bobo4bo18b2o$190bo15b3o38b2o5bobo16b2o$188b3o18bo45b2o22b2o$187bo
20b2o11b2o56b2o$187b2o32b2o120b2o$300b2o41b2o$300bo19b2o$302bo16bobo
59b2o$301b2o16bo61b2o$297b2o19b2o10b2o$190b2o105bo33bo$171b2o17b2o106b
3o27b3o9b2o$171b2o127bo27bo11bo19b2o$341bo17bobo$340b2o17bo$170b2o186b
2o$171bo$168b3o12b2o50b2o$168bo14bo16b2o34bo$184b3o14bo31b3o3bob2o$
186bo11b3o20b2o10bo2b4ob2o44b2o$198bo22bo14bo50b2o$222b3o13b2ob2o2b2o
6b2o$224bo14bobo4bo6bobo$239bo2b4o9bo$240bobo2bobo7b2o113b2o$241bo4b2o
123bo$368b3o$368bo3$267b2o$266bobo$266bo18b2obo$265b2o18b2ob3o$291bo$
285b2ob3o$286bobo$286bobo$287bo5$275b2o$275b2o!
In the above pattern, there's an Lx input Herschel at (27, 70, t=0) -- 'Lx' meaning a left-rotated mirror image Herschel, starting from the standard o$obo$3o$2bo! orientation. More important, there's an L output Herschel at (34, 13, t=193) for the lower spaceship gun. 193 is the sum of 116 and 77, the timings of the two conduits used in the Herschel signal splitter. The output location is marked by a 'ghost' Herschel in the pattern above -- i.e., a Herschel with one cell removed that dies harmlessly after a few ticks.

If we can find a conduit that moves the lower gun's output Herschel to the upper gun's input Herschel with exactly the right timing, the LWSSes will come out in a horizontal line -- and we'll be able to string together as many guns as we want and get a longer line.

The upper gun has an input Lx Herschel at (21.-110); the spot is marked by another ghost Herschel. So we need a short string of Herschel conduits that moves a Herschel (-6, -180) between these two locations, and mirror-reflects it. The timing will have to be exactly right, too -- more about that later.

The spaceship guns in the upper half and lower half of the pattern can be separated by any even vertical distance -- odd distances don't work because the spaceship phases couldn't be synchronized (try it if you don't see why). The horizontal offset is a fixed 6 cells.

Everything else being equal, the distance between the two guns will also determine how long the connecting conduit needs to take to deliver the signal. That is, if the guns are moved two steps farther apart, the first LWSS will take four ticks longer to traverse the distance to the second LWSS's construction site... so the connecting conduit also has to take four ticks longer to deliver its output Herschel.

The -e command-line parameter gives Hersrch an equation describing which lengths and timings of Herschel conduits will work. You can use as many variables as you need. In the problem we've described above, there's really just one independent variable, the distance between the guns. Unfortunately Hersrch is very unlikely to find a compact solution without a larger search space.

In any case, a Herschel can't travel nearly as fast as an LWSS, so without a delay mechanism of some kind, the signal will never get to the upper LWSS gun in time to line the output up with the lower LWSS. We'll need to delay the lower LWSS gun for a while to give the upper gun time to trigger.

That's what the rectifiers are for. Moving a 180-degree glider reflector one diagonal step will change the reflected glider's return time by 8 ticks -- the path length changes by four ticks for both the input and the reflected gliders. We can adjust the lower gun's rectifier to make the glider path longer, giving the upper LWSS gun time to catch up.

----------------------------------

Hersrch is currently compiled as a Windows command-line utility. To my knowledge, no one has done a Linux or Mac build. The usual way of communicating the search parameters is with a Windows batch file, like this:

Code: Select all

set x=10000
set u=1000
set t=100
set n=25
set name=connect
hersrch -p 997 -o %name%.rle -f %name%.log -n %n% -s -x %x% -u %u% -t %t% -e (t=20..45,y=-18..0)L(0)[34,13]..Lx(167+8*t-4*y)[21,-110-2*y]
pause
Just make a text file with the above contents and a .bat extension, in the same folder as the Hersrch executable, and double-click on the .bat file. Hersrch's output looks like this:

Code: Select all

Accepted 546 targets
Loaded 31 components, 92 variants
Prepared 17 components, 30 variants
Building Aho/Corasick tree...
Tree built: 693 nodes, 438 sequences, complete to depth 3
Counting component sets...
Found 3107 component sets
Searching...
*** (5050 @ 224) VFX77 VFX176 VFX158 (l=1,p=997,t=24,u=1000,y=-13)
*** (4500 @ 224) VFX158 VFX176 VFX77 (l=1,p=997,t=24,u=1000,y=-13)
*** (7371 @ 2497) VL112 VFX119G VL112 VL156 VR64X (l=1,p=997,t=40,u=1000,y=-19)
... Sorting ...
*** (4500) VFX158 VFX176 VFX77 (l=1,p=997,t=24,u=1000,y=-13)
*** (5050) VFX77 VFX176 VFX158 (l=1,p=997,t=24,u=1000,y=-13)
*** (7371) VL112 VFX119G VL112 VL156 VR64X (l=1,p=997,t=40,u=1000,y=-19)
Search complete
Here's a walkthrough of what the various parameters mean -- much of this can also be found in Hersrch's readme.txt, but this explanation is specific to the example batch file above:

-p 997: the Herschel circuits used have to be compatible with signals arriving 997 ticks apart. 997 is an arbitrary large prime number, so this just means that conduits with oscillators won't be used in the search.

This batch file doesn't include a -c parameter (compression setting), so conduits can be used even if they're very slow to recover. If input Herschels will be entering the track quickly, say every 200 ticks, you should add a "-c 200" to the parameter string to exclude slow conduits like the standard Fx119.

-o %name%.rle: output will be written to connect.rle. Change the "set name=connect" line to write the output pattern to a different location.

-f %name%.log: the search details written to the screen will also be written to a log file, connect.log.

-n %n%: The number of conduits in the output pattern will be limited to the 25 most compact solutions (as measured by bounding box). You can change the "set n=25" line to get as many solutions as you want.

-s: forces Hersrch to run through a complete search, sort the result in order of size, and write only the smallest candidates to the output file. The RLE won't contain more than 25 results (but there are only two solutions in this case, so this setting has no effect.) Without -s the search would stop as soon as it found the first 25 solutions -- no sorting.

-x %x%: maximum allowable size of candidate patterns is 10,000 cells (100x100 or equivalent). Watch out for this parameter -- especially if you're doing searches for very long-distance connections, too small a value here will mysteriously cause Hersrch to find no solutions. Change the "set x=10000" line at the top if necessary. However, keeping this at a reasonably low value is a quick way to weed out unnecessarily long conduits.

-u %u%: maximum amount of time a conduit is allowed to take to send a Herschel to its destination. This parameter is primarily used for searching for closed circuits (usually Herschel-based guns). If you're searching for a loop with period 999, for example, you might want to limit solutions to just single-Herschel loops (in which case "set u=1000" is a good setting).

Or you might want to allow length-1998 loops with two Herschels in them, so you'd change the line to something like "set u=2000". For closed loops, the loop length will be a multiple of the -p parameter. For open-conduit searches I usually use an arbitrary large prime for the -p parameter (e.g., 997) to make sure that periodic conduits will be disallowed -- and the -u setting just needs to be bigger than the largest possible total time delay between input and output Herschels.

This can get tricky if time is one of your variables, and/or if you have a non-zero starting time -- so double-check this along with the -x setting if you're mysteriously seeing no solutions where you know there should be some.

-t %t%: this specifies the size of the Aho-Corasick tree, in kilobytes. Depending on how much memory you have and what kind of searches you're running, it may improve search time to increase this number. The default value of 1000 is a good choice, but in quick searches like this one a smaller value seems to work fine as well.

-e (t=20..45,y=-20..0)L(0)[34,13]..Lx(167+8*t-4*y)[21,-110-2*y]: This specifies the the heart of the search, the equation describing valid spacetime locations for candidate conduits' output Herschels. English translation:

"Try all combinations of variables t and y, where t is between 20 and 45 and y is between -20 and 0. Start with a Herschel rotated 90 degrees left (L) from the standard orientation, at time (0), with the center cell placed at [34, 13]. Find a series of conduits that mirror-reflects that input Herschel (Lx) and moves it to [21, -110] -- or any location directly above that point that will allow the output spaceships to line up.

"The Herschel has to arrive at the target in exactly 167+8*t-4*y ticks. For the two guns in the position shown in the template, 167 ticks would be ideal -- then the reflectors at the lower left wouldn't have to be moved, or could even be left out. The -2*y says that if the guns are moved one cell farther apart, the candidate Herschel conduit has to take two ticks longer to deliver its Herschel (to allow the lower gun's LWSS to catch up to the upper gun's new output location.) Remember that in the Hersrch universe, y increases downward, not upward...

"In practice, the distance between the guns is too far for a Herschel to travel in just 167 ticks. The reflectors can be adjusted to account for any extra time needed by the Herschel: moving a reflector out one space slows down the gun by 8 ticks. The 8*t provides the second degree of freedom needed to make the search likely to be successful."

Post Reply