Sample Hersrch search script

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

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
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]
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
*** (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