Shrinking Gemini: Four Ideas

[igblan]

Here is a summary of four ideas for shrinking Andrew Wade's constructor-based knightship Gemini.

(1a) Move the BLACK and WHITE constructor-elbow output gliders closer together

[This idea was originated by Dave Greene and calcyman.]

The diagonal spacing between the BLACK and WHITE elbow output gliders is currently 9hd (half-diagonals). When a dense sequence of alternating BLACK and WHITE gliders is constructing at a highly localised site, it is often necessary to insert sequences of around 9 INCs or 9 DECs to get the elbow back to where it was. Reducing this spacing would, in general, reduce the number of such restorative sequences.

I have found an alternative set of four shoulder shotgun output salvos which reduces the spacing to the minimum 1hd. The cost is an extra tape-channel glider for the WHITE instruction, but that doesn't increase the length of the tape.

It's hard to estimate the tape-length saving, but it's probably around 3%-5%.

(1b) Reduce the number of tape channels per constructor from 4 to 3

The idea here is to be able to encode the minimum 4 instructions (DEC, INC, BLACK, WHITE) in 3 tape channels without adding decoding circuitry to the constructor. This could be accomplished by finding a set of 3 shoulder shotguns which produce 3 different 1G or 2G salvos (probably including the existing 2G DEC salvo), which in various (synchronised or slow) combinations perform the four instructions.

The search space is pretty large, so there's a good chance for this one, although again one would want to try to minimise the spacing between BLACK and WHITE outputs, as in (1a) above.

The tape-length saving would be around 25%.

(2) Eliminate two of the six reflector arrays

Napkin sketches suggest that it might be possible to alter of the morphology of the constructor to eliminate two of the six reflector arrays, at the cost of more crossing streams.

The tape-length saving would be around 18%, the approximate reduction in constructor population.

(3) Eliminate the destruction arm by adding a self-destruct mechanism to the constructor

[This idea was originated by Dave Greene.]

This is an old idea, but little to no research has been done so far. The idea is to seed the Herschel components with small still lifes so that a single glider (or perhaps a small number of gliders) can trigger the complete destruction of the constructor. Obviously one wants to keep the additional construction cost for these seeds to a minimum, otherwise diminishing returns set in.

Eliminating the destruction arm saves about 33%. The additional seed cost might be around 25%, depending more heavily on finding a good destruct mechanism for the reflector, since reflectors make up about 2/3 of the (current) constructor population. So overall the net saving might be around 10%.

Putting it together

(1), (2) and (3) are broadly orthogonal. So implementing all best cases could reduce the overal tape length by about 45%.

Cheers, Paul

[HartmutHolzwart]

Are there any concrete plans to implement one of these ideas?

Are there any concrete plans for examples showing a different velocity?

Is there any possibility to optimize the construction by changing the sequence of construction or using intermediate results multiple times? I'm thinking along the lines of peephole optimizing for the compiler.

Cheers,
Hartmut

[calcyman]

Are there any concrete plans for examples showing a different velocity?

Dave Greene has already accelerated Gemini by eight generations per period, and therefore attained a different velocity. The direction can also be modified easily, but not quite as easily as Dave's modification.

Is there any possibility to optimize the construction by changing the sequence of construction or using intermediate results multiple times?

Theoretically, altering the construction sequence may have some small benefit, similar to the Travelling Salesman Problem. Similarly, it's probably also NP-hard.

Intermediate results can't be used multiple times, if you're thinking of iterative/recursive loops. Gemini is a very passive configuration, and gliders on the tape do not interact with each other. Basically, there is no compression whatsoever; Gemini's format is as flat as possible. That has the advantage of minimising the configuration size. Locating the optimum between configuration simplicity and tape compression is an ongoing project of myself and William R. Buckley. We have almost solved the case for Nobili cellular automata.

[dvgrn]

Theoretically, altering the construction sequence may have some small benefit, similar to the Travelling Salesman Problem. Similarly, it's probably also NP-hard.

I hope to hear from Andrew himself at some point, about what he's already tried in the way of rearranging the construction. It looks as if the design has already been optimized quite carefully. The build order looks about as good as it's going to get, and it seems as if there's been a special effort to make the Herschel circuitry as cheap as possible to construct.

Notice in the blueprint below that the recipe glider channels are not in any kind of simple order, as far as which channel is routed to which constructor arm -- the channels on opposite edges of the stream are both routed to adjacent shotguns on the east constructor arm, for example. This makes perfect sense if you're connecting up the channels to the shotgun inputs with the smallest possible number of reflectors, and maybe keeping the reflectors close to the shotguns as much as possible to minimize the distances the constructor elbows have to travel.

Possibly there's some glider-stream-crossing optimization implied by the channel order, as well? At p576+ there's a lot of empty space in the stream, so for any given crossing, collisions would generally be the exception rather than the rule... but there are a lot of crossings!


(you may want to open this image in a new tab -- the "0" on the right edge gets cut off, at least in my browser.)

The diagonal green lines are glider lanes -- I've added red arrows to show the direction the gliders are traveling. The jagged shapes are the Herschel conduits, which usually "split" a glider into two signals, eventually producing two output gliders for the construction arm with exactly the right relative locations in spacetime.

[dvgrn]

Speaking of Herschel conduits, the ones shown in the blueprint (greenprint?) in the previous post are a very good target for optimization. This didn't make it onto Paul's list, but the component shotguns in the construction arms are copied from the original prototype programmable constructor, without many changes. Because the timing can now be changed just by moving the gliders in the recipe streams, a lot of useless timing-related circuitry that used to connect to the shotguns has been mercilessly deleted ... but the shotguns themselves haven't changed much.

The original shotguns were definitely prototypes: they all terminate in the same Fx119 inserter, for example, which probably means that Hersrch was never really asked to look for the most efficient set of conduits. (You can always get the right synchronized gliders from a Hersrch search if you allow enough space and time, but it's much trickier to find the most compact possible solution.)

I'm looking at the four U-shaped sections of conduit in particular, where the signal goes the wrong way for a while and then turns and comes back. If you spend enough time on the problem, this kind of thing can usually be replaced by something shorter.

Also, there's a new and very easy-to-construct Herschel conduit now, Brice Due's F171, that wasn't known when that prototype circuitry was designed -- and the F171 allows for a constructible "Spartan Herschel transceiver", which may end up simplifying a lot of these routing problems:

Code: Select all

#C Four variants of a constructible Spartan Herschel transceiver
#C (The LifeHistory rule is built into Golly 2.1,
#C or can be downloaded from the rule repository.
#C The same rule produced the blueprint from the last post.)
x = 258, y = 345, rule = LifeHistory
232.A$230.3A$229.A$229.2A$209.2A6.2B5.7B$210.A6.3B2.7B$210.A.AB2.14B$
178.2A31.2AB.17B$179.A33.19B$179.A.AB30.20B$180.2AB30.20B$182.3B28.
20B$182.4B7.A18.22B2.B$183.4B6.3A15.23B.B2A$184.4B8.A13.4B2.20B2A$
185.4B6.2A12.4B2.19B.2B$186.4B5.6B7.4B3.19B$187.4B6.5B5.4B5.17B$188.
4B4.7B3.4B5.17B$189.4B2.8B2.4B4.18B$190.18B2.20B$191.39B$187.2A3.28B.
9B$188.A4.27B2.7B$188.A.AB.27B3.5B$189.2A28B5.3B$190.17B.4B10.7B$192.
19B11.2A.B.2A$183.A10.16B13.A3.A$183.3A8.15B11.3A5.3A$186.A7.14B12.A
9.A$185.2A3.B2.14B$185.21B$187.18B$187.17B$186.17B$184.18B$182.19B$
182.2BA15B$181.3BABA4B.9B$182.2B3A4B2.7B$181.5BA4B4.5B$180.10B3.5B$
179.6B8.2A$178.6B10.A$177.6B8.3A$176.6B9.A$175.6B$174.6B$173.6B$172.
6B$171.6B$170.6B$169.6B$31.A136.6B$31.3A133.6B$34.A131.6B$33.2A130.6B
$33.7B5.2B6.2A109.6B$35.7B2.3B6.A109.6B$34.14B2.BA.A108.6B$32.17B.B2A
31.2A75.6B$32.19B33.A75.6B$31.20B30.BA.A74.6B$31.20B30.B2A74.6B$31.
20B28.3B75.6B$27.B2.22B18.A7.4B74.6B$26.2AB.23B15.3A6.4B74.6B$26.2A
20B2.4B13.A8.4B74.6B$27.2B.19B2.4B12.2A6.4B74.6B$30.19B3.4B7.6B5.4B
74.6B$31.17B5.4B5.5B6.4B74.6B$32.17B5.4B3.7B4.4B74.6B$33.18B4.4B2.8B
2.4B74.6B$34.20B2.18B74.6B$34.39B74.6B$34.9B.28B3.2A69.6B$35.7B2.27B
4.A69.6B$36.5B3.27B.BA.A68.6B$37.3B5.28B2A68.6B$35.7B10.4B.17B68.6B$
35.2A.B.2A11.19B61.2A6.6B$36.A3.A13.16B10.A51.B2AB4.6B$33.3A5.3A11.
15B8.3A17.2A33.3B3.6B$33.A9.A12.14B7.A20.A33.B.B3.6B$57.14B2.B3.2A20.
A31.12B$58.21B19.2A29.13B$59.18B21.B8.2A19.13B$60.17B19.3B7.A.A17.14B
$61.17B16.6B6.BA17.14B$62.18B11.10B2.B3.2B15.14B$63.20B2.2B3.19B2.B
10.17B2.B$64.31B2A16B8.23B$63.9B.22B2A17B6.6B2A17B$64.7B2.41B4.8B2A
16B$64.5B4.41B2.29B$66.5B3.71B$69.2A8.6B.13B5.4B.34B$69.A10.6B4.B.7B
5.39B$70.3A8.6B19.31B2.B.B$72.A9.6B20.28B2.3B$83.6B20.27B2.B2AB$84.6B
21.24B4.2A$85.6B23.17B.B.B2A$86.6B24.9B.6B2.BA.A$87.6B25.6B5.2B6.A$
88.6B24.8B11.2A$89.6B24.5B2A$90.6B25.3B2A$91.6B25.2B$92.6B23.4B$93.6B
22.B2AB$94.6B22.2A$95.6B$96.6B$97.6B$98.6B$99.6B$100.6B$101.6B$102.6B
$103.6B$104.6B$105.6B$106.6B$107.6B$108.6B$109.6B$110.6B$111.6B$112.
6B134.A$113.6B131.3A$114.6B129.A$115.6B128.2A$116.6B107.2A6.2B5.7B$
117.6B107.A6.3B2.7B$118.6B106.A.AB2.14B$119.6B73.2A31.2AB.17B$120.6B
73.A33.19B$121.6B72.A.AB30.20B$122.6B72.2AB30.20B$123.6B73.3B28.20B$
124.6B72.4B7.A18.22B2.B$125.6B72.4B6.3A15.23B.B2A$126.6B72.4B8.A13.4B
2.20B2A$127.6B72.4B6.2A12.4B2.19B.2B$128.6B72.4B5.6B7.4B3.19B$129.6B
72.4B6.5B5.4B5.17B$130.6B72.4B4.7B3.4B5.17B$131.6B72.4B2.8B2.4B4.18B$
132.6B72.18B2.20B$133.6B72.39B$134.6B67.2A3.28B.9B$135.6B67.A4.27B2.
7B$136.6B66.A.AB.27B3.5B$137.6B66.2A28B5.3B$138.6B66.17B.4B10.7B$139.
6B4.2A61.19B11.2A.B.2A$140.6B.2B2AB51.A10.16B13.A3.A$141.10B33.2A17.
3A8.15B11.3A5.3A$142.10B33.A20.A7.14B12.A9.A$143.10B31.A20.2A3.B2.14B
$144.11B29.2A19.21B$145.11B19.2A8.B21.18B$146.12B17.A.A7.3B19.17B$
146.13B17.AB6.6B16.17B$146.3B2A9B15.2B3.B2.10B11.18B$142.B2.3BA2BA10B
10.B2.19B3.2B2.20B$140.9B2A12B8.16B2A31B$139.17B2A6B6.17B2A22B.9B$
140.16B2A8B4.41B2.7B$139.29B2.41B4.5B$139.71B3.5B$141.34B.4B5.13B.6B
8.2A$141.39B5.7B.B4.6B10.A$142.B.B2.31B19.6B8.3A$143.3B2.28B20.6B9.A$
142.B2AB2.27B20.6B$143.2A4.24B21.6B$147.2AB.B.17B23.6B$146.A.AB2.6B.
9B24.6B$146.A6.2B5.6B25.6B$145.2A11.8B24.6B$158.2A5B24.6B$158.2A3B25.
6B$160.2B25.6B$159.4B23.6B$159.B2AB22.6B$160.2A22.6B$183.6B$182.6B$
181.6B$180.6B$179.6B$178.6B$177.6B$176.6B$175.6B$174.6B$50.2A121.6B$
49.B2AB119.6B$49.4B118.6B$50.2B118.6B$49.3B2A115.6B$47.5B2A114.6B$46.
8B11.2A100.6B$46.6B5.2B6.A100.6B$44.9B.6B2.BA.A99.6B$42.17B.B.B2A99.
6B$39.24B4.2A94.6B$37.27B2.B2AB92.6B$36.28B2.3B92.6B$34.31B2.B.B90.6B
$18.B.7B5.39B88.6B$12.B.13B5.4B.34B87.6B$4.69B84.6B$.2B.38B2.29B83.6B
$2A40B4.8B2A16B83.6B$2AB.19B2A17B6.6B2A17B81.6B$.B2.19B2A16B8.12B2A9B
81.6B$5.6B2.2B3.19B2.B10.10BA2BA3B2.B82.6B$19.10B2.B3.2B15.9B2A3B85.
6B$22.6B6.BA17.14B83.6B$24.3B7.A.A17.14B81.6B$26.B8.2A19.13B79.6B$26.
2A29.13B77.6B$27.A31.12B60.2B.B11.6B$26.A33.B.B3.6B59.5B9.6B$26.2A33.
3B3.6B56.7B8.6B$60.B2AB4.6B52.B.9B6.6B$61.2A6.6B50.2AB.7B6.6B$70.6B
49.2A9B5.6B$71.6B44.A4.2B.8B3.6B$72.6B43.3A5.16B$73.6B45.A3.18B$74.6B
43.2A.20B$75.6B42.22B2A$76.6B43.20B2A$77.6B41.20B.B$78.6B39.B.18B$79.
6B37.20B$80.6B36.20B$81.6B36.18B$82.6B35.10B2A5B$83.6B34.10B2A5B$84.
6B29.2AB2.15B$85.6B25.2B.2AB.15B$86.6B23.2A20B$87.6B22.2A20B$88.6B22.
2B.17B$89.6B25.15B$90.6B24.14B$91.6B24.13B$92.6B25.10B$93.6B24.10B$
94.6B24.8B$95.6B23.8B$96.6B23.10B$97.6B22.11B$98.6B21.12B$99.6B21.10B
$100.6B20.10B$101.6B20.3B.7B.2A$102.6B20.10BA.A$103.6B19.9B.BA$104.6B
19.8B$105.6B18.8B$106.6B19.7B$107.6B18.6B$108.6B17.6B$109.6B16.7B$
110.6B15.8B2.2A.A$111.6B12.12BA.2A$112.6B11.11B$113.6B10.5B2A4B$114.
6B9.5B2A3B$115.6B8.10B$116.6B7.9B$117.6B6.9B$118.6B6.8B$119.6B4.8B$
120.6B4.6B$121.6B3.6B$122.6B2.6B$123.6B.7B$124.6B.6B29.A$125.11B28.3A
$126.10B27.A$127.10B26.2A$128.9B24.4B$129.8B7.2A14.3B$130.8B6.A14.4B$
131.7B3.BA.A13.4B$131.8B2.B2A13.4B$131.11B9.A4.4B$131.11B7.3A3.4B$
131.11B6.A5.4B$132.11B4.B2A3.4B$127.2A6.7B5.3B2.4B$128.A5.8B4.3B2.4B$
128.A.AB.10B3.8B6.2A$129.2AB.21B6.A$131.24B2.BA.A$131.25B.B2A$131.27B
$132.26B$132.26B$134.B.22B$137.20B$138.18B$139.15B$140.14B$141.14B$
142.14B$143.4B.9B$144.9B.4B$145.8B2.4B10.A$146.8B2.4B7.3A$147.7B3.4B
5.A$148.6B4.4B4.2A$148.7B4.9B$148.7B5.6B$148.8B.2B.7B$148.20B$148.22B
$148.22B$149.20B$143.2A7.16B$144.A6.17B$144.A.AB2.19B$145.2AB.20B$
147.23B$146.24B$147.23B$145.2AB.21B$144.A.AB2.20B$144.A6.17B.B2A$143.
2A9.13B2.BA.A$155.12B5.A$156.9B7.2A$157.5B$159.B$158.3B$158.B2AB$159.
2A!

These conduits all recover within 576 ticks, though half of them would have trouble at p497, which is the recovery time of the quickest 90-degree reflector, and therefore the ultimate limiting factor in this circuitry. Paul has noted on another thread that there are just a few spots in the current circuitry that need 575 ticks to recover, and these would be easy to remove. It's not clear yet whether it might make sense to build new circuitry that recovers in, say, 512 ticks instead of 576 -- or whether that would just make it that much harder to avoid collisions at glider crossings.

Hersrch isn't designed to handle adjustable conduits like these four transceiver variants, so it's hard to say how much they might reduce the synchronization circuits in the Gemini. However, it's fairly straightforward to include in Hersrch's Spartan library, say, the 25 shortest variants of each conduit. I'll try to get that done over this next weekend, and find out how much more effective Hersrch is (or how much slower!) with a hundred extra conduits to choose from.

Offhand I'd guess that optimizing the current constructor-arm shotguns would shave at least a few percentage points off the Gemini's total size. But the (1a) or (1b) options in Paul's list would probably reduce the length of the recipe stream even more significantly -- and these would require building all new circuitry anyway.

Keep the cheer,


DaveG

[igblan]

Hartmut: I see you found this topic anyway.

I am mostly pursuing (1b) for now.

To this end, I have already written a Python wrapper for RLife7.dll, the "agile" (it's the new buzzword) Life engine I used for Glue, which is very good for running small patterns and has built-in code for guessing when a pattern has settled down (eg has reached a P1/P2 core with departing gliders). I am in the process of transliterating a few more Glue classes from Smalltalk to Python, including those for handling affine transformations and analyzing the results of a collision. I will then write some gencolsy code to search for sets of three salvos which in combination can perform the four elbow instructions (and with luck maybe some others, like larger elbow moves).

The gencolsy code might also be pressed into service to help with (3).

Further work I did on on (2) yielded mixed results. At the moment, the components of Gemini are laid out on a 128x128 grid. (2) can be achieved, but at the expense of having to increase this to 168x168 (although there may be another, better solution). This in turn increases the amount of time spent simply moving the elbows between components during the construction. It isn't clear at the moment whether this would increase or decrease the length of the tape.

Has anyone succeeded in running Andrew's code? I know Dave has been pouring over its details.

I am a relative noob in Python, and a sleepy old man with a less agile brain, so don't expect anything right away. Even so, this has now become my only current research.

Cheers, Paul

[calcyman]

though half of them would have trouble at p497, which is the recovery time of the quickest 90-degree reflector,

That's the recovery time of the smallest 90-degree reflector. I have made a p466 non-Spartan and a p487 Spartan reflector.

[dvgrn]

That's the recovery time of the smallest 90-degree reflector. I have made a p466 non-Spartan and a p487 Spartan reflector.

Drat. It's getting so difficult to qualify everything properly these days -- should have said "the quickest 90-degree reflector [and/or glider-to-Herschel converter] that it might make sense to use in a Gemini 2". Wouldn't be a good tradeoff to cut ten ticks off the recovery time at the expense of having to build about twice as many still lifes.

Has anyone succeeded in running Andrew's code?

Yup, it works like a charm -- with a couple of caveats:

1) You have to install Python 3.1 -- I used the current Python 3.1.2 -- _not_ 3.0.

The destroy.py utility works in Python 3.0, but the asm.py utility returns a "zero length field name in format" error after a minute or two. Line 101 of lifelib.py, among other places -- something to do with "explicitly numbered format specifiers"... search for the above error message in http://diveintopython3.org/files.html if you want the details. Looks like a minor incompatibility, probably easy to fix.

I installed Python 3.1 on my Windows system, concurrently with the Python 2.x (mine is Python 2.6.2) that Golly expects to have available for running scripts. No apparent problems there, though I imagine there might be trouble if you wanted to do something like run generic non-Golly .py scripts from the command line; the 3.1 python.exe might end up trying to run your Python 2.x scripts by default.

2) In Windows, you have to call the Python executable explicitly... I think. I seem to remember having had Python associated with .py files at some point, but maybe two concurrent Python installations confused the system somehow.

Anyway, I unpacked the "gemini_with_programs" archive to a subdirectory of C:\Python31\, then adjusted the readme.txt instructions accordingly: from a command prompt in the C:\Python31\gemini\ folder, I tried things like

Code: Select all

   ../python destroy.py < sacrificial-object.rle > total-annihilation.yaml

   ../python asm.py < total-annihilation.yaml > total-annihilation.rle

Even for a pattern the size of the full Gemini replicator unit, compiling a recipe glider stream only takes a few minutes. No progress indicator or anything, so you just have to be patient, or go get a cup of coffee.

So then you just have to combine the output RLE with gemini-replicator.rle, to get the replicator unit to build or destroy something. I haven't figured out the *right* way to do this yet: there's a nice reference domino spark that obviously has to be put someplace, I just haven't looked for where it's supposed to go. To make sure I had the right idea, I did feed a sample destruction salvo into the replicator unit manually, with great success:

Code: Select all

x = 1094, y = 1068, rule = B3/S23
2bo$obo$b2o117$149bo$147bobo$148b2o128$296bo$294bobo$295b2o80$372bo$
370bobo$371b2o142$514bo$512bobo$513b2o182$676bo$674bobo$675b2o138$836b
o$834bobo$835b2o68$914bo$912bobo$913b2o180$1056b2obo6bob2o$1056bob2o6b
2obo15b2ob2obo$1060b2o2b2o20bobob2o$1060bo4bo20bobo$1061bo2bo22b2o$
1060b2o2b2o13b2o$1056b2obo6bob2o9bo2bob2o$1056bob2o6b2obo11b2obo$1054b
2o14b2o10bobo5b2obo$1054bo16bo9bo2b3o3bob2o$1055bo14bo11b2o3bo$1054b2o
14b2o12b4o$1056b2obo6bob2o14bo$1056bob2o6b2obo12bobob2o$1082b2o2bo$
1086bobo$1087b2o!

Keep the cheer,


DaveG

[dvgrn]

Running asm.py with various modifications can give some fairly good rough estimates of the potential space savings for some of the items in Paul's list.

For example, for item (1a), if I change the "targetx|y|d -= 9" lines to -1 and rerun asm.py, I get a new Gemini recipe that's only 8.09 million (!) cells long instead of 8.44 million, saving about 4% of the length.

[The glider salvo created for the comparison isn't actually a working recipe, since we'd need new shotguns to get an offset of 1 instead of 9 between the two glider parities. This recipe would have to be interpreted by Gemini 2 hardware that doesn't exist yet, but it would still build a Gemini 1.]

In terms of the number of gliders, the new recipe is only 92.6% as big as the old one -- 145,976 gliders vs. 157,619. So the change saves a lot of gliders without having a proportional effect on the length. Looks like the big savings must be in the destruction recipe, which has relatively few long-distance elbow moves and can benefit the most from this particular optimization.

I ran asm.py on just the destruction-recipe YAML, with and without the above 9 -> 1 change. The new recipe was only 66.8% of the length of the old one, with 72% as many gliders. So the new recipe is a little denser, probably due to a higher proportion of glider outputs vs. DEC operations, since a DEC takes only one glider and everything else needs two.

In the full Gemini, a lot of the construction recipe is made up of strings of INCs and DECs. So to shorten those glider streams significantly, we might

1a) shrink the area of the Gemini replicator unit,
1b) move the various pieces closer to each other somehow (less arm-moving, more building),
2) use INCn or DECn in place of INC or DEC, and/or
3) use "disposable elbows" on the construction arms -- more about this later.

The elephant in the room is the glider-crossing avoidance logic. It's easy enough to find the three places to change -9 to -1 to use more efficient salvos for the two glider parities. And it would even be relatively straightforward to rewrite program.yaml to build different shotguns in different locations. But the rest of asm.py is full of magic numbers that will have to be changed to other magic numbers if the constructor shotguns are replaced.

Some of these I could figure out, but a lot of the collision-related stuff may have to be re-invented from the ground up. Possibly Andrew would be able to find the necessary shortcuts -- but I wonder if he'll be interested in producing a Gemini 2. All these meddlesome suggestions for improvement might just look like a lot more late nights, to put together something that's almost as big and does the same thing as the Gemini...!

Keep the cheer,


DaveG

P.S. Ah, yes, the "disposable elbow" idea:

Andrew's construction already shows how to build blocks, which later become elbows, far away from the intersection point of the two arms -- and also how to destroy elbows using standard construction techniques to reflect a glider back to hit them. But suppose an elbow was removed in this way in mid-construction instead of at the end, and another elbow was waiting directly behind it, some distance away?

The construction arm could immediately start using the new elbow to build in a completely different location. That would save a long string of INC instructions, at the cost of having built that extra elbow at some previous time (hopefully when the arms were in more or less the right position anyway.)

I _think_ I can see a couple of places in the current construction where this trick might work. Probably won't try to implement anything until there are some new shotguns to build, though.

[igblan]

My very next request was going to be adding a little code to Andrew's constructions programs to gather some stats.

... saving about 4% of the length.

I am oddly pleased that my 3%-5% estimate for (1a) was not inaccurate, although of course changes and/or improvements to the shotguns might yet dwarf that figure for good or ill.

1a) shrink the area of the Gemini replicator unit,
1b) move the various pieces closer to each other somehow (less arm-moving, more building)

I expect a few cells can be shaved from the 128x128 grid, and maybe it can be distorted a little in places as well. I imagine Andrew picked this round number partly to aid hashlife - although this only affects memory usage in the long run, producing only marginal improvements in speed owing to fewer garbage collections.

But the rest of asm.py is full of magic numbers that will have to be changed to other magic numbers if the constructor shotguns are replaced.

Ah, this is disappointing. Avoiding cross-stream collisions still looks to me where most of the perspiration went in, and looks time-consuming and tedious to redo. And I expect Andrew won't be madly keen to revisit the problem, since I found it hard to do the same with the MRM, both P30 and stable versions (which is why Adam is still nagging me occasionally about the broken P30 MRM currently out there ).

I have not yet taken the plunge and installed Python 3 alongside Python 2.

Cheers, Paul

[dvgrn]

I have not yet taken the plunge and installed Python 3 alongside Python 2.

Well, the only hard part is getting started -- accept the defaults and the installation will be done in just a couple of minutes. Here's the link for a Python 3.1 Windows install to make it a little easier.

-- You also need the YAML library for Python 3.1. How negligent of me not to have mentioned that before.

After running those two installers (which both have very nice uninstallers, by the way, in case you don't like the results) just put the script files and some RLE in the right places, as described in the previous post, and you're ready to go. Make a new subprogram.yaml with just one subpattern definition from the original program, run asm.py on that, and figure out how to feed the resulting streams of gliders into gemini-replicator.rle.

Keep the cheer,


DaveG

[mscibing]

I hope to hear from Andrew himself at some point, about what he's already tried in the way of rearranging the construction. It looks as if the design has already been optimized quite carefully. The build order looks about as good as it's going to get, and it seems as if there's been a special effort to make the Herschel circuitry as cheap as possible to construct.

I chose the build order with an eye to efficiency. I tested the build out a piece at a time, but once I had a component built successfully I did not revisit its construction. There are undoubtedly some gains to be made in build order, but probably not much. I can't take credit for the Herschel circuitry. it comes almost entirely from constructor-memory-tape in Golly. I did notice that the Hershel components used fishhooks in place of snakes, I assume for ease of construction.

Notice in the blueprint below that the recipe glider channels are not in any kind of simple order, as far as which channel is routed to which constructor arm -- the channels on opposite edges of the stream are both routed to adjacent shotguns on the east constructor arm, for example. This makes perfect sense if you're connecting up the channels to the shotgun inputs with the smallest possible number of reflectors, and maybe keeping the reflectors close to the shotguns as much as possible to minimize the distances the constructor elbows have to travel.

This was done to minimize the number of reflectors, and to minimize the northwest - southeast ("y") size of the pattern. Minimizing the size of the pattern was also why I re-ordered the components of the arms, though I did keep the glider streams on a 128 cell diagonal grid.

Possibly there's some glider-stream-crossing optimization implied by the channel order, as well?

Nope. Some of the glider stream crossings are "shadowed" by crossings elsewhere in the pattern, but this is more happy accident than design.

[mscibing]

The destroy.py utility works in Python 3.0, but the asm.py utility returns a "zero length field name in format" error after a minute or two. Line 101 of lifelib.py, among other places -- something to do with "explicitly numbered format specifiers"... search for the above error message in http://diveintopython3.org/files.html if you want the details. Looks like a minor incompatibility, probably easy to fix.

Replace {} with {0} on lines 83, 96, and 101. If you got that far there probably aren't any additional incompatibilities.

I haven't figured out the *right* way to do this yet: there's a nice reference domino spark that obviously has to be put someplace, I just haven't looked for where it's supposed to go.

(1024, 5120). Same with the origin of whatever you're destroying. Anything being build has the origin at (0,0).

... 2) use INCn or DECn in place of INC or DEC, and/or ...

If the increment size is relatively prime to the decrement size, it's not necessary to keep the original INC or DEC.

Some of these I could figure out, but a lot of the collision-related stuff may have to be re-invented from the ground up. Possibly Andrew would be able to find the necessary shortcuts -- but I wonder if he'll be interested in producing a Gemini 2.

The collision-related stuff was not a lot of work compared to creating the construction recipe. I would not mind re-doing it. It was mostly a matter of firing gliders into the pattern and adjusting their relative delays until they collided "head on".

The construction arm could immediately start using the new elbow to build in a completely different location. That would save a long string of INC instructions, at the cost of having built that extra elbow at some previous time (hopefully when the arms were in more or less the right position anyway.)

I like this idea. The construction syntax would have to be extended to let the assembler know the new position whenever the active elbow was switched, and how soon it could start using it.

-- You also need the YAML library for Python 3.1. How negligent of me not to have mentioned that before.

YAML was a mistake; when it came time to write the construction recipe I found the syntax slightly awkward. I should have spent the time to roll my own parser. If it weren't for the sheer size of the recipe it wouldn't have mattered.

Cheers,
Andrew

[HartmutHolzwart]

Mostly to Andrew:

Is there a specific reason that you chose exactly that slope 5? Why exactly this translation?

Could you build a gemini II with slope 4 for example? Would that one be more complicated with longer period?

[mscibing]

Mostly to Andrew:

Is there a specific reason that you chose exactly that slope 5? Why exactly this translation?

I built Gemini with a slope of 3/2 in a 45 degree coordinate system. In the usual coordinate system that works out to a slope of 5. A slope 4 Gemini would have a longer period, but the slope of 5 is by no means optimal. I tried to align Gemini with powers of 2 grids to help hashlife out, but I suspect that doesn't actually make much difference.

[calcyman]

I tried to align Gemini with powers of 2 grids to help hashlife out, but I suspect that doesn't actually make much difference.

If you base your pattern on a power of two grid, and you give it a power-of-two period, then the HashLife speed-up is phenomenal. My Phi calculator, for example, has a special component designed to make it run fast in HashLife. And it does: 10^12 generations in one hour on my machine.

A way to do this would be to use p512 instead of p576 base period. That should be possible using present technology.

[igblan]

Mostly to calcyman.

My understanding is that the Gemini tape is not really p576. Additional delays have to be introduced occasionally in order to avoid collisions in crossing streams. Reducing the minimum separation of tape gliders to 512 would not address that: the tape would remain globally asynchronous. It's possible that where delays have to be introduced they could be reasonably large powers of 2, eg 32 or 64. That might help hashlife some, although of course it would increase Gemini's bounding box.

I think hashlife is mostly struggling where the tape passes itself. There is probably an enormous amount of novelty in the local combinations of NW and SE tape patterns, certainly enough to cause at least one GC per complete Gemini cycle.

The other source of novelty is of course where the current construction and destruction are taking place. Little can be done about that AOTBE.

Cheers, Paul

[HartmutHolzwart]

Would a slope of 3 be any different (this would be (2,1) diagonally)? Would the tape get easier or more complicated?

What would be the minimum distance for the constructur to be built? In terms of speed, is it more efficient to build the next constructor relatively near and replicate more often or to build the next constructor far away?

Also I understand that the two constructor approach does not give apure diagonal ship. This could be solved by building the second constructor glide symmetric, implying a program to build the constructor in a different orientation. The deletion part could stay the same. Does this sound reasonable?

Also there is a case for building a purely orthogonal spaceship as the other extreme.

[calcyman]

My understanding is that the Gemini tape is not really p576. Additional delays have to be introduced occasionally in order to avoid collisions in crossing streams.

Correct. It should, however, be possible to redesign Gemini to avoid crossing streams, increasing the bounding box of each semi-Gemini (but not the cell count), and therefore only slightly increasing the length of the tape.

In terms of speed, is it more efficient to build the next constructor relatively near and replicate more often or to build the next constructor far away?

If, by 'speed', you mean 'replication frequency', then it is more efficient to build the next constructor as close as possible. If you mean 'the magnitude of the velocity', then building the constructor further away is more efficient, asymptotically approaching (1,1)c/580, as I mentioned earlier.

Also I understand that the two constructor approach does not give apure diagonal ship.

Technically, Gemini could do that, but only with a radically different tape. It could also translate itself by (0,0), and thus become an oscillator, using a similar principle.

[HartmutHolzwart]

So far it seems there are quite a few good ideas.

Is there a realistic chance to see an implementation of som of those ideas in the near future?

[igblan]

Is there a realistic chance to see an implementation of som of those ideas in the near future?

I am actively working on a Python program to search for a solution to (1b).

Cheers, Paul

[igblan]

Here is a sketch of a possible rearrangement of the reflector arrays described in idea (2), reducing them in number from six to four, at the cost of using slightly bigger reflectors to duplicate the signal at the top.



The diagram shows just the reflector arrays at both ends of Gemini. Only two tape channels are shown; more can be stacked up provided the distance between the incoming and outgoing tapes is increased.

Andrew's reflectors are 128 cells apart vertically. Mine are 149, which is the minimum.

The NE outputs at the top are on the same tracks at both ends of Gemini. They would go to the constructor arms.

Note that I have put the constructor arms at the top rather than the bottom. This reduces the number of crossing streams if the destruction arm can be done away with as in idea (3).

Cheers, Paul

[HartmutHolzwart]

Couldn't one do a version of gemini without destruction arm and tape? This would then be a puffer, but maybe smaller and less complicated.

I still didn't completely understand whether a slope 3 version of gemini would be harder or easier than the original.

Cheers,
Hartmut

[HartmutHolzwart]

What is the smallest period that one could reach with a Gemini type ship?

[dvgrn]

Couldn't one do a version of gemini without destruction arm and tape? This would then be a puffer, but maybe smaller and less complicated.

Here's a Gemini puffer pattern with all the gliders in the destructor-arm control channels suppressed [the suppressing eaters are still there, in a horizontal line starting around (3333,4444).] This reduces the starting population a good bit, since almost 27,000 gliders are gone, but it doesn't seem to affect the speed of execution very much. Also it doesn't make the Gemini-puffer any shorter than the original Gemini, since the destructor-arm recipe runs in parallel with the two sets of channels for the constructor arms, and it isn't the limiting factor in the length of the tape.

Removing the actual circuitry for the destructor arms, and the reflectors that feed gliders into the destructor shotguns, would definitely allow for a shorter pattern -- the length of the tape would go down by about a third. But what was left would definitely be just a ridiculously complicated puffer, until we get a good self-destruct mechanism working... and we already have plenty of puffers. Anyway, it would take some minor redesigning to avoid leaving ugly holes in the reflector arrays... and I'm going to wait until the weekend to attempt even a simple recompile to get a different velocity, let alone a significant circuitry change.

I still didn't completely understand whether a slope 3 version of gemini would be harder or easier than the original.

Meaning a slope of 3 in a 45-degree coordinate system? Can't we just call this a slope of 2? You should be able to produce a true (2x, x) Gemini knightship just by adding 3072 INC instructions to the westward construction arm, lengthening the distance between the two ends appropriately, and recompiling to avoid collisions in the glider-stream crossings in the upper part of the westward arm in the southeast replicator... I haven't looked at Andrew's code closely enough yet to find out if the (1024, 5120) offset is deeply buried in underlying assumptions in the collision-avoidance code, or if it's easy to change, or if anything will even need changing...!

Like Andrew, I have a sneaking suspicion that it won't make much of any difference to Golly's hashlife algorithm whether the construction offsets are powers of two, or small multiples of powers of two -- there are so many different permutations of the gliders in the channels that all the hash table entries for (e.g.) the old empty replicator units are bound to have been garbage collected before the new empty replicator units are completely constructed.

I'd really like to try this out and see if this crackpot theory holds up in practice, though, so I'll be trying to build a (4096,8192)/c33724632 knightship version this weekend.

What is the smallest period that one could reach with a Gemini type ship?

I did end up reworking the current Gemini down to its minimum length and shortest period, which was just what Calcyman said it was in another thread -- (5120,1024)/c33695514 . It could certainly be cut down much further in the various ways Paul Chapman has listed, or by silly little tricks like swapping the 0 channel with one of the channels 4, 6, 8, or 10, and then delaying all the destructor-arm gliders for as long as possible to give that channel-0 reflector a little more time to finish constructing. But that would take a full redesign and recompile, too. Guess I'll post an update once I find out how painful that really is --

[EDIT: basic math about the (2x,1x) knightship was wrong; the adjustment would be 3072 cells to the northwest, not 3132. Corrected the numbers above.]