ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Technological Challenges

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

Technological Challenges

Postby simsim314 » April 24th, 2014, 4:09 am

All "big" life patterns are built from small "technologies". Gemini for example is based on stable reflector, G->H converter, and Herschel duplicators and conduits. Gemini also uses some special H -> G converter that can pack gliders nicely together. It's also uses 2-3-4 Glider packs for arm moving and reflection operations, and syntheses of Spartan parts with two 90 degree glider collisions. All those technologies were "small discoveries" that accumulated into something like Gemini.

So to improve designs in Life we need some small "technological solutions". So I suggest we post here what we need (preferably for what purpose). And hopefully with time also solve at least partially some of the challenges.

Here is my "request list":

1. A cross signal adjuster (needed for multiple channels replicators): given two signals (say two gliders at any phase and on some known lanes), that would "collide" or intervene each with others "functionality", the adjuster will get those two signal as an input, and will ALWAYS give an output of the same signal on some other output lanes, regardless of the input phase and the location on the lanes. The adjuster can have constant delay (which is always applied).

2. A better G->H converter. The current spartan G->H converter is of about 500 ticks, this slows down all current replicators designs.

3. A simple gate mechanism (or a flip-flop - needed for computational designs). Given a stream of gliders (on some input lane), and another input glider (a key) that could "open and close a gate". If the gate state is "open" the input glider will "close" the gate and the stream will be blocked. If the gate was closed the input glider will "open the gate" and the stream will pass freely. This open-close gate mechanism should be reusable of course and as small as possible.

4. A fast and small stable duplicator. Like the Snark but instead one output glider this one will have two (or more). As with Snark small, stable, and fast are qualities that are needed.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby dvgrn » April 25th, 2014, 2:12 pm

simsim314 wrote:... to improve designs in Life we need some small "technological solutions". So I suggest we post here what we need (preferably for what purpose). And hopefully with time also solve at least partially some of the challenges.

1. A cross signal adjuster (needed for multiple channels replicators): ...

This is a somewhat trickier project than the old p30/p46/p60 signal crossers (if I'm understanding it correctly). If there are no constraints at all on the timing of Glider 1 and Glider 2, and the signals have to cross each other and end up at known spacetime locations relative to their inputs... well, I think this would take some creative use of multiple regulators, which would have to be redesigned to be constructible.

Even minimal constraints would make this problem much easier. If you can guarantee that Glider 1 and Glider 2 will both show up within some number of ticks, for example, and that you don't need the outputs to appear until after both input gliders have been processed, then I think you can get away with just the reaction at the heart of the regulator, plus some signal splitters and miscellaneous wiring. If you can guarantee that Glider 1 will appear before Glider 2, that also makes the problem relatively trivial.

A similar problem that I've had on the back burner for a while is an exact-timing merge circuit (ETM). If you want to combine two signal gliders that may be either present or absent, G1@(X1, Y1, T1) and G2@(X2, Y2, T2), how do you get G1 OR G2 = G3@(X3, Y3, T3)? I've been slowly working out various non-Spartan solutions for this -- they do exist, and they're gradually getting more compact. But really it seems as if there should be a small transparent glider-emitting Herschel converter that can do this -- inside a 20x30 box, let's say -- by producing a spark that suppresses an incoming glider, and then replacing it a little later with an exactly-timed equivalent glider. No luck there so far.

simsim314 wrote:2. A better G->H converter. The current spartan G->H converter is of about 500 ticks, this slows down all current replicators designs.

Hear, hear! The Silver reflector/converter was a wonderful discovery in its time, but there must be something smaller that can be found with modern computational power. Distributed search, anyone?

simsim314 wrote:3. A simple gate mechanism (or a flip-flop - needed for computational designs).

Here's a first effort in that direction. The inputs are Herschels instead of gliders, but we can just add on the improved G->H converter from #2 above, and we'll be all set...!

#C permanent Herschel-circuit switch from the "Demonoid",
#C guarded with semi-Snarks to produce a safe toggle
x = 191, y = 128, rule = LifeHistory
70.A$70.3A$73.A$72.2A6.2A$79.A.A$80.A2$74.2D$67.2A5.2D$67.2A6.2C$75.
2C2$84.2A$84.2A2$69.2A$68.A.A$68.A$67.2A2$114.A$114.3A$117.A$32.A83.
2A$30.3A$17.A11.A67.A$17.3A9.2A50.A15.3A$20.A58.3A18.A$7.2A10.2A57.A
20.2A11.2A11.E$8.A69.2A32.2A9.3E$8.A.A112.E.E$9.2A112.E$32.2A100.A$
32.2A99.A.A$53.2A78.A.A$53.2A26.2A51.A$81.2A2$9.E$9.E.E$9.3E$11.E11.
2A$23.A27.2A$24.3A23.A.A38.2A$26.A23.A41.A20.2A$49.2A25.2A11.3A21.A.A
$2.2A72.2A11.A25.A$3.A111.2A$3A$A61.2A$63.A$60.3A$13.2A8.A36.A$13.2A
6.3A48.2A$20.A51.A$5.2A13.2A51.3A$6.A68.A$6.A.A$7.2A$12.2C$12.2C2D$
14.2D3$9.A$8.A.A$8.2A3$17.2A$17.2A26$82.2A$82.A$80.A.A$80.2A2$113.2A
14.A$88.2A24.A14.3A$89.A13.2A6.3A18.A$89.A.A11.2A6.A19.2A$67.E22.2A$
65.3E87.A$65.E.E85.3A$65.E86.A$152.2A2$121.2A$121.2A2$79.2A$66.2A11.
2A99.E$67.A110.3E$64.3A94.2A15.E.D$64.A53.2A41.2A15.E$118.A19.2A49.A$
83.2A14.2A3.2A13.3A15.A.A48.A.A$84.A15.A3.A16.A15.A50.A.A$81.3A13.3A
5.3A28.2A10.2A39.A$81.A15.A9.A41.A$146.3A9.2A$146.A11.A$159.3A$161.A!

I'm sure someone could come up with a modern variation on the old Herschel Latch pattern, too, with a little effort. The key would be to find a Herschel-to-block converter that cleanly destroys the block if another Herschel was sent in... and then figure out how to get both the input and output Herschels and the "key" signal to their respective locations with nothing but Spartan salvos.
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Technological Challenges

Postby towerator » April 26th, 2014, 11:34 am

Hmm...
For me, it would be very useful, for massive structures like the "DNA-like spiral replicator" to have a synthesis for the spark catalyst.
This is game of life, this is game of life!
Loafin' ships eaten with a knife!
towerator
 
Posts: 328
Joined: September 2nd, 2013, 3:03 pm

Re: Technological Challenges

Postby simsim314 » April 27th, 2014, 2:08 am

dvgrn wrote: G1@(X1, Y1, T1) and G2@(X2, Y2, T2), how do you get G1 AND G2 = G3@(X3, Y3, T3)?


Hmm isn't this one from calcyman is a nice AND gate?

x = 25, y = 20, rule = LifeHistory
3.2A19.A$4.A17.3A$4.A.A14.A$5.2A13.A.A$21.A3$4.2A13.2A$4.2A13.2A5$17.
2A$17.A.A$17.A2$.2A$A.A$2.A!


Here is also an asynchronous AND gate:

x = 95, y = 67, rule = S23/B3
55boo$55bo$53bobo$53boo20$81bo$79b3o$28boo48bo$27b3oboo45boo$28boob3ob
oo$27b3oboobboo$27boo3$88bo$59boo25b3o$59boo24bo$33boo50boo$32bobo28b
oo$32bo30boo$31boo26boo$59boo$45boo$44bobo$44bo$43boo8boo20boo$53bo21b
oo$54b3o$56bo5$93bo$92bobo$boo90bo$obo$bbo$$83boo3boo$83boo3boo3$75bob
oo$73b3oboo$72bo11boo$73b3oboo5bo$75bobobbo4b3o$79boo6bo!


dvgrn wrote:I think this would take some creative use of multiple regulators...


Well this is an approach, but I was kinda hoping to have something based on stable technology. Anyway using 8 unit each one in its own phase it's kinda "ugly' solution. Although I must admit I don't have any better idea and this approach will probably work.

dvgrn wrote:Even minimal constraints would make this problem much easier...


Well it's probably true but you can't have any small piece of your technological solutions to have constrains, this limits your flexibility and bigger design. If you have such unit that works without constrains you simply place it and forget about it, if you don't you all the time need to think does this unit will work or not. Though "acceptable" constrain, would be time delay.

dvgrn wrote:Distributed search, anyone?


Well the problem is not the search, but the search space. How or with what "parameters" do you suggest to make this search? Just bouncing glider into random SLs hoping for H without destroying the SLs is kinda lost cause. We need a better and more "limited space", which will yield result with much bigger probability.

dvgrn wrote:Here's a first effort in that direction.


WOW! This is really great gate mechanism...I really want to use it for some designs I'm thinking about.
Last edited by simsim314 on April 27th, 2014, 5:01 am, edited 2 times in total.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby simsim314 » April 27th, 2014, 4:58 am

towerator wrote:DNA-like spiral replicator


Hmm what do you think missing for this replicator? For example what stops you from designing spiral replicator yourself? Assuming you have time and motivation, what is the technological details that you think missing for it?
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby simsim314 » April 27th, 2014, 8:17 am

Junk-less sensor (needed for quadratic growth replicators): given two units X and Y at some distance D, have an indication there is a unit at this distance or not. i.e. X and Y should "know" of each other existence, but without sending "junk" gliders (i.e. if Y or X doesn't exist the glider can't just go without returning). For example X could send a glider at time T if there is a unit Y, and not to send anything otherwise. They should not leave a mess.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby dvgrn » April 27th, 2014, 10:11 am

simsim314 wrote:
dvgrn wrote: G1@(X1, Y1, T1) and G2@(X2, Y2, T2), how do you get G1 AND G2 = G3@(X3, Y3, T3)?


Hmm isn't this one from calcyman is a nice AND gate?

It is indeed. I described the problem fairly clearly, but then ruined it with a typo -- I meant "OR" but wrote "AND". Have corrected that now. Here's a sample of the kind of thing I've been building:

#C Sample ETMs  (Exact-Timing Merges, i.e., OR gates)
x = 476, y = 202, rule = LifeHistory
76.2D8.2D3.2D3.2D252.2D8.2D3.2D3.2D$76.D.D6.D2.D.D2.D.D2.D251.D.D6.D
2.D.D2.D.D2.D$76.D8.D2.D.D2.D.D2.D251.D8.D2.D.D2.D.D2.D$86.2D2.D2.D.D
2.D261.2D2.D2.D.D2.D$85.D2.D.D2.D.D2.D260.D2.D.D2.D.D2.D$85.D2.D.D2.D
.D2.D260.D2.D.D2.D.D2.D$86.2D3.2D3.2D262.2D3.2D3.2D$398.A$398.3A$401.
A$400.2A5$422.A20.A$364.2D2.D2.D.3D44.3A11.A7.A.A$363.D2.D.D2.D2.D44.
A14.3A6.A$135.A227.D2.D.D2.D2.D44.2A16.A16.2A$135.3A225.D2.D.D2.D2.D
20.2A39.2A16.A$138.A224.D2.D.D2.D2.D20.2A55.A.A$137.2A225.2D3.2D3.D
77.2A$385.A$385.3A$388.A$387.2A40.2A25.2A$159.A269.2A25.A$101.2D2.D2.
D.3D44.3A11.A282.A.A$100.D2.D.D2.D2.D44.A14.3A280.2A$100.D2.D.D2.D2.D
44.2A16.A14.A$100.D2.D.D2.D2.D20.2A39.2A12.3A$100.D2.D.D2.D2.D20.2A
52.A254.2A$101.2D3.2D3.D74.2A244.2A6.A.A$122.A289.2A19.A6.A$122.3A
287.A.A15.3A6.2A$125.A59.2A227.A15.A$124.2A40.2A17.2A227.2A$166.2A$
408.2A$408.2A$443.2A$442.A.A$442.A$169.2A270.2A$149.2A19.A$149.A.A15.
3A$151.A15.A234.2A$151.2A19.2A228.A$173.A200.D.D3.D22.3A53.2A$145.2A
23.3A201.D.2D2.D24.A53.A.A$145.2A23.A203.D.D.D.D80.A$374.D.D2.2D2.C
27.A49.2A$374.D.D3.D3.C8.2A14.5A$374.D.D3.D.3C9.A13.A5.A$103.D.D3.D
78.2A204.A.A12.3A2.A$103.D.2D2.D78.A.A204.2A15.A.2A$103.D.D.D.D35.2A
43.A218.4A2.A$103.D.D2.2D2.C32.A44.2A212.2A3.A3.2A$103.D.D3.D3.C26.2A
4.A257.2A4.3A38.2A$103.D.D3.D.3C26.A4.2A265.A29.2A7.2A$141.3A268.A.2A
27.A$128.2A14.5A262.2A.2A27.A.A$129.A13.A5.A294.2A$129.A.A12.3A2.A
310.2A$130.2A15.A.2A29.2A221.2A55.A$144.4A2.A20.2A7.2A221.A54.A.A$
139.2A3.A3.2A22.A231.3A51.2A$139.2A4.3A24.A.A231.A$147.A25.2A268.A$
147.A.2A38.2A252.3A$146.2A.2A38.A244.A11.A$187.A.A218.A9.A15.3A8.2A
14.A$187.2A219.3A5.3A18.A22.A.A$138.2A271.A3.A20.2A23.A$138.A33.A237.
2A3.2A$139.3A30.3A291.A$141.A21.A11.A196.D.D3.D85.3A$137.A9.A15.3A8.
2A14.A174.A6.D.2D2.D84.A$137.3A5.3A18.A22.A.A173.3A4.D.D.D.D84.2A$
140.A3.A20.2A23.A177.A3.D.D2.2D$139.2A3.2A221.2A3.D.D3.D$195.A176.D.D
3.D92.2A.2A$101.D.D3.D85.3A228.2A46.A.2A$101.D.2D2.D84.A231.2A23.2A
21.A$101.D.D.D.D84.2A218.2A35.A14.2A4.3A$101.D.D2.2D303.A2.A35.3A11.
2A3.A3.2A$101.D.D3.D256.2A40.2A4.2A38.A16.4A2.A$101.D.D3.D92.2A.2A
159.2A39.A.A47.2A15.A.2A$153.2A46.A.2A200.A48.A.A12.3A2.A$153.2A23.2A
21.A202.2A48.A13.A5.A$141.2A35.A14.2A4.3A212.2A37.2A14.5A$140.A2.A35.
3A11.2A3.A3.2A210.A56.A$135.2A4.2A38.A16.4A2.A210.3A$134.A.A47.2A15.A
.2A212.A$134.A48.A.A12.3A2.A$133.2A48.A13.A5.A$143.2A37.2A14.5A$143.A
56.A$144.3A294.A$146.A294.3A$444.A$443.2A3$170.A229.A$170.3A227.3A$
133.A39.A229.A$133.3A36.2A228.2A$136.A316.2A$135.2A309.2A5.A.A$446.2A
7.A$455.2A2$442.A$182.2A228.2A27.A.A.2A$175.2A5.A.A220.2A5.A.A26.A.A.
A.A$145.2A28.2A7.A220.2A7.A25.2A.A.A.A2.A$138.2A5.A.A36.2A228.2A25.A
2.2A.4A$138.2A7.A293.A4.A$147.2A22.A229.A40.3A.A2.2A$170.A.A.2A224.A.
A.2A38.2A3.2A$134.A35.A.A.A.A223.A.A.A.A$133.A.A.2A30.2A.A.A.A2.A219.
2A.A.A.A2.A$133.A.A.A.A30.A2.2A.4A220.A2.2A.4A$132.2A.A.A.A2.A27.A4.A
224.A4.A$133.A2.2A.4A28.3A.A2.2A221.3A.A2.2A$133.A4.A34.2A3.2A223.2A
3.2A$134.3A.A2.2A$136.2A3.2A71$.2C254.2C$C.C253.C.C$2.C255.C!

These are 0 mod 8 and 4 mod 8, so I just need six more of these to make a complete set, to be able to merge any two same-color glider signals... and eight more to merge different-color signals, I suppose.

simsim314 wrote:
dvgrn wrote:Distributed search, anyone?

Well the problem is not the search, but the search space. How or with what "parameters" do you suggest to make this search? Just bouncing glider into random SLs hoping for H without destroying the SLs is kinda lost cause. We need a better and more "limited space", which will yield result with much bigger probability.

Existing tools are mostly command-line C++ code -- Paul Callahan's 'ptbsearch', Gabriel Nivasch's 'catalyst', Guam's search utility that found the semi-Snark (haven't been able to get hold of the source code for that one yet) (2015 EDIT Yes, I have!)... Brice Due also wrote his own code at one point, which found the F171 Herschel conduit, and Paul Chapman has written an optimized Spartan searcher that might turn up something one of these days. But most of these tools use small pre-defined catalysts, and so they can all produce at least potentially Spartan circuitry.

But it's difficult to adapt these tools to a distributed search, along the lines of Nathaniel Johnston's Online Soup Search, which was a downloadable Golly script. It's certainly possible to divide up the search space and send part of the tree to many different nodes. The problem is that each search tends to return megabytes of potential results, which then have to be processed further to find the actual good results (if any). Need to be able to reliably boil down those megabytes into kilobytes on the client machines, to keep the data transmission problem somewhat manageable.
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Technological Challenges

Postby simsim314 » April 27th, 2014, 2:57 pm

dvgrn wrote:These are 0 mod 8 and 4 mod 8, so I just need six more of these to make a complete set, to be able to merge any two same-color glider signals...


OK now I get it (you don't want to depend on glider inner state). This sounds like another technological challenge. For what purpose would it be useful?

dvgrn wrote:Existing tools are mostly command-line C++ code...


Do you know the general algorithmic approach those search utils have used?
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby dvgrn » April 28th, 2014, 3:19 pm

simsim314 wrote:OK now I get it (you don't want to depend on glider inner state). This sounds like another technological challenge. For what purpose would it be useful?

Well... let's say for example you're building a Life metacell out of nothing but stable circuitry -- that is, that the resting state of the metacell is stable, nothing moving at all. With ETM circuits you can build circuitry to emulate any rule -- except for B0 rules, where there would be nowhere for a signal to come from to start up the circuitry.

Basically you'd merge the inputs from all eight neighbors plus the current state of the cell, using eight ETM OR-gates, to get the signal to run through your rule-table circuitry to count neighbors and decide if the cell is going to be ON or OFF in the next metatick. No matter where the signal comes from, the output always appears at exactly the same spacetime location.

The idea is to produce a metacell that fits exactly into a large Golly hashtile -- nothing but powers of two spatially and temporally. Golly might well be able to run a meta-metacell pattern (or even another level up from that?) since each new level is just a limited number of new hashtiles.

Anyway, you can't use normal OR gates, because signals from different neighbors would tend to show up at different times, and then neighboring metacells might end up in different phases, which would eventually be disastrous (and not very Hashlife-compatible). There might be some similar problems with keeping the children of a quadratic-growth replicator pattern synchronized with each other... it looks as if that will usually turn out okay, though, as it does in Langton's Loops for example.

simsim314 wrote:
dvgrn wrote:Existing tools are mostly command-line C++ code...


Do you know the general algorithmic approach those search utils have used?

Basically these programs are both "brute force with optimizations" -- drop every possible catalyst into every possible position and orientation near an active reaction, run the resulting patterns, and just save the few exceptional cases where the catalyst survives.

'ptbsearch' and 'catalyst' both allow you to define various small still lifes as catalysts. The definitions tend to include "cells that have to stay ON" and "cells that have to stay OFF"; 'ptbsearch' allows for transparent catalysts where 'catalyst' doesn't. But allowing multiple transparent catalysts really slows down the search of course.

Brice Due and Paul Chapman have done some work on cleverer optimizations that try to avoid testing catalyst positions that are very very unlikely to work... but I haven't gotten hold of any source code from those projects. And Guam's search utility is likewise still a mystery.

Here's another piece of Spartan circuitry that temporarily stops a Herschel circuit. This version is configured to act as a period doubler:

x = 69, y = 114, rule = LifeHistory
24.2A$23.A2.A$24.2A8$28.D2C$29.C$27.3C6$35.2A$35.A.A$10.2A25.A$11.A
25.2A$11.A.A15.2A$12.2A15.2A11$13.2A.2C$12.A.A.C.C11.2A$12.A4.C12.A.A
$11.2A19.A$32.2A5$14.2A$13.A.A$13.A25.2A$12.2A25.A$20.2A15.A.A$20.2A
15.2A12$19.2A7.3A19.A8.2A$18.A.A8.A20.3A6.2A$18.A8.3A23.A$17.2A33.2A
13.2A$67.A$65.A.A$65.2A$60.2A$35.2A21.2D2A$35.A.A20.2D$37.A$37.2A$64.
A$63.A.A$64.2A3$55.2A$27.2A14.A11.2A$27.2A14.2A$42.A.A$18.2A.A$18.A.
2A6$19.A$19.3A$10.A11.A$10.3A8.2A14.A$13.A22.A.A$12.2A23.A4$34.2A$34.
A.A$36.A$11.C24.2A$11.C.C18.2A$11.3C18.A$13.C11.2A6.3A$25.A9.A$26.3A$
28.A4$2.2A$3.A$3A$A!

The following is a toggleable switch that will let a single signal through, only if an odd number of gliders have come in:

#C Herschel signal blocked unless a glider comes in
x = 162, y = 114, rule = LifeHistory
140.A$140.A.A$140.2A$138.A4$123.2A$124.A$124.A.A$125.2A4$156.2A$156.A
$154.A.A$112.A37.2A2.2A$112.3A35.2A$115.A$114.2A11.2A11.D$127.2A9.3D$
138.D.D$138.D4$113.C$113.C.C$113.3C40.2A$115.C22.2A16.A.A$137.A.A18.A
$137.A20.2A$136.2A4.2A$141.A.A$141.A$140.2A7.2A$127.2A20.2A$127.A$
128.3A$130.A4$159.2A$159.A$157.A.A$157.2A5$139.2A$140.A$140.A.A$141.
2A12$142.2A$142.2A14.2A$134.2A22.A$135.A23.3A$135.A.A23.A$136.2A$152.
A$150.3A$149.A$149.2A4$117.2A$118.A$118.A.A$45.A73.2A$45.3A$21.A26.A
22.A14.2A$19.3A25.2A20.3A14.A24.2A$18.A49.A18.3A6.2A13.A44.2A$18.2A
48.2A19.A6.2A11.A.A44.2A$109.2A$38.A$36.3A$35.A115.2A$10.D11.2A11.2A
114.2A$10.3D9.2A131.2A$10.D.D65.2A75.2A$12.D65.2A$.A$A.A117.2A27.2A$A
.A117.2A11.2A14.2A$.A131.A$134.3A$47.2A32.2A53.A$47.2A11.2A20.A$60.A
18.3A13.2A3.2A14.2A$35.D25.3A15.A16.A3.A15.A$34.D.D26.A29.3A5.3A13.3A
$34.2D57.A9.A15.A$43.2A$34.2A7.A$22.2A10.A9.3A$23.A11.3A8.A$20.3A14.A
$20.A!

Lots of other variants are possible, of course. The boat-bit location is borrowed from an old design by Dean Hickerson for Fibonacci-number period-multipliers.

EDIT: Here's the converse of the above -- a glider signal is diverted to a new path if a Herschel comes in, but otherwise it continues right on through the circuit. Not bad for just three catalysts:

#C Brice Due's demultiplexer, 22 August 2006
x = 83, y = 40, rule = B3/S23
34bo47bo$32b2o46b2o$33b2o46b2o13$3bo47bo$3b3o45b3o$6bo47bo$5b2o46b2o$o
47bo$3o45b3o$3bo47bo$2b2o46b2o13$50b3o$12b2o37bo8b2o$12bo38b3o6bo$13b
3o45b3o$15bo47bo!
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Technological Challenges

Postby simsim314 » April 29th, 2014, 9:21 am

Here is a concept making a cross channeling using multiple regulators and gates:

First of all we use two regulators per glider to have a mod 15 output glider. Then we have two options: If the two gliders mod 15 collide, we open gates for "close cross channel" (let's say we pass the first, and then the second). If the the two mod 15 gliders don't collide, we open the gates for "distant channels", which simply allows the "natural" crossing. Then we use a delayed xor gate, to combine the two outputs.

Now it's pretty heavy but it's possible and it will work for "all inputs". It would be nice to get rid of oscillators, and make it much lighter, but as a concept it's possible and it's not "so heavy".

dvgrn wrote:- drop every possible catalyst into every possible position and orientation near an active reaction, run the resulting patterns, and just save the few exceptional cases where the catalyst survives


I was thinking in this direction, the interesting question would be how much catalysts would there be after 3-4 iterations of say glider+block->pi interaction? thousand? hundreds? millions? And how explored this topic is? I mean were there some massive search attempts, that run for thousands of hours?

-----

About static metacells: we can always shoot a glider, but the difference between 0 and 1 will be the time delay, and then use semi snarks as binary adders. The gate mechanism will allow to differentiate between the S and B rules. And we can use only 2 semi snarks, so the "other" late shoot will readjust the gate mechanism to it's initial state.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby dvgrn » April 29th, 2014, 9:06 pm

simsim314 wrote:
dvgrn wrote:- drop every possible catalyst into every possible position and orientation near an active reaction, run the resulting patterns, and just save the few exceptional cases where the catalyst survives

I was thinking in this direction, the interesting question would be how much catalysts would there be after 3-4 iterations of say glider+block->pi interaction? thousand? hundreds? millions?

Just three or four ticks from glider+block->pi, the number of catalyst combinations is probably in the hundreds. If you mean up to three or four catalysts affecting glider+block->pi within let's say a hundred ticks, the number of possibilities is easily in the millions, even if you include only Spartan catalysts. Add eater2s and eater3s and other recent custom catalysts and you're quickly up into the billions or trillions -- and in many cases there's plenty of room for more than four catalysts.

simsim314 wrote:And how explored this topic is? I mean were there some massive search attempts, that run for thousands of hours?

Not terribly massive, I suppose. There have certainly been thousands of hours of ptbsearch and catalyst runs in all, between maybe half a dozen or a dozen people -- but a lot of the biggest effort was on 1997-era computers, so that part might translate to just a few hours on today's computers. I think the speed increase since 1997 is closing in on three orders of magnitude now (!).

However, the biggest part of the effort was interpreting the megabytes of results, and running follow-up searches on the most promising reactions. A modern version of this should probably semi-automate the display and exploration of candidate results, and maybe make some use of human intelligence to pick which reactions "look promising" and should be explored more deeply.

Something like a Golly script front-end for 'catalyst' or 'ptbsearch' might get people finding new and interesting reactions fairly quickly. Brice Due certainly showed that there was uncharted territory out there that hadn't been checked, as of 2006 -- his incomplete custom search program found the F171 Herschel conduit and the demultiplexer (down at the bottom of the post) during test runs with just a single catalyst type -- eaters only.

Similarly, Paul Chapman wrote an optimized Spartan-only search program last year, using a slightly different method. For a while he was getting good results -- more catalyst placements processed per second than ptbsearch or catalyst, I think. He avoided the too-much-output problem by only reporting complete tested Spartan circuitry -- but once he turned off the likely false positives, he didn't get any results for days at a time (not surprisingly). I don't believe that that program has made it past the pre-alpha stage, where it has to be re-compiled to change the search parameters...!

As long as we're only interested in Spartan conduits, it might work to run a very constrained search like Paul's on some kind of distributed platform, reporting only perfect matches. But the odds of finding non-Spartan conduits may go up significantly if you spend enough time looking at almost-solutions -- sometimes they're repairable by welding customized eaters together, or other tricks that the search utility doesn't know about.
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Technological Challenges

Postby dvgrn » April 30th, 2014, 3:30 pm

This is a extension of ideas from the Spartan Herschel splitters posted on another thread. The technological challenge here is to find Herschel splitters that are smaller and faster to recover.

Here's some known technology put together in a maybe-slightly-new way -- not smaller or faster, but unusually adjustable:

#C maybe-Spartan Herschel splitter based on Guam's Herschel transceiver.
#C The three input gliders are fairly adjustable -- just need two on the
#C   same lane, and another one (of either color) a safe distance away.
#C Repeat time is 319 ticks, limited by the Herschel transmitter.
x = 160, y = 212, rule = LifeHistory
77.2A$76.A.A$76.2A3$71.A$70.A.A$70.A.A$71.A10$92.A$91.A.A$91.A.A$92.A
$81.D$57.2A22.D.D$57.2A22.3D$83.D7$62.2A$61.A.A$61.A$60.2A2$80.A$79.A
.A$80.2A8$145.2A$144.A2.A$145.2A4$56.2A$56.2A$60.2A$60.2A$74.2A73.3D$
74.2A74.D$148.3D4$77.A$76.A.A7.2A$76.A.A7.2A68.2A$64.2A11.A78.A.A$65.
A92.A$62.3A93.2A$62.A$66.2A$66.2A4$148.2A$139.2A7.2A$140.A$140.A.A$
141.2A$157.2A$157.A$155.A.A$155.2A5$158.A$157.A.A$158.A3$115.A8.2A$
115.3A6.2A$118.A$117.2A13.2A22.2A$132.A5.2A16.2A$130.A.A5.2A$130.2A2$
123.2A$123.2A24.2A$149.2A$107.A$105.3A21.A$104.A23.A.A21.2A$104.2A23.
2A22.A$76.A76.A.A$74.3A77.2A$29.A20.A22.A46.2A$21.A6.A.A19.3A20.2A45.
2A$21.3A5.A23.A$17.2A5.A27.2A38.A53.2A$18.A4.2A67.3A51.2A$18.A.A62.A
11.A$19.2A62.3A8.2A14.A$86.A22.A.A$85.2A23.A2$15.2A25.2A$16.A25.2A$
16.A.A88.2A$17.2A88.A.A$109.A$109.2A$30.2A73.2A$30.A.A6.2A32.2A30.A$
32.A6.A20.2A11.2A23.2A6.3A$32.2A6.3A18.A36.A9.A$42.A15.3A38.3A$58.A
42.A2$77.2A$78.A$28.2A45.3A$28.A.A44.A$30.A$30.2A5$12.2A$11.A.A$11.A
25.2A$10.2A25.A$18.2A15.A.A$18.2A15.2A12$17.2A$16.A.A$16.A$15.2A5$33.
2A$33.A.A$35.A$35.2A7$25.2A$16.2A7.2A$17.A$17.A.A$18.2A6$17.A$17.3A$
8.A11.A$8.3A8.2A14.A$11.A22.A.A$10.2A23.A4$32.2A$32.A.A$34.A$9.C24.2A
$9.C.C18.2A$9.3C18.A$11.C11.2A6.3A$23.A9.A$24.3A$26.A2$2.2A$3.A$3A$A!

The first output Herschel can be trivially adjusted to any [+j,-j] location, and the second one can be placed at any sufficiently distant same-color [+j+k,-j+k] location.

In a non-Spartan version you can use a Snark instead of a semi-Snark, of course, and then any pair of input gliders can be made to work:

#C Everything is easier with a Snark.
#C Fetch it home by all means --
#C   you may serve it with greens,
#C And it's handy for triggering a Herschel receiver.
#C Here a custom F117 extension is shown for the transmitter,
#C   to allow the output Herschel to escape.
x = 155, y = 140, rule = LifeHistory
72.2A$71.A.A$71.2A3$66.A$65.A.A$65.A.A31.A$66.A30.3A$75.2A7.A11.A$75.
2A7.3A9.2A$87.A$86.2A39.A$126.A.A$126.A.A$127.A$99.2A15.D$99.2A15.D.D
$116.3D$118.D3$76.D$52.2A22.D.D$52.2A22.3D30.2A$78.D11.2A18.A$90.A16.
3A$91.3A13.A$93.A4$57.2A$56.A.A$56.A$55.2A2$75.A$74.A.A$75.2A8$140.2A
$139.A2.A$140.2A4$51.2A$51.2A$55.2A$55.2A$69.2A73.3D$69.2A74.D$143.3D
4$72.D$71.D.D7.2A$71.D.D7.2A68.2A$59.2A11.D78.A.A$60.A92.A$57.3A93.2A
$57.A$61.2A$61.2A4$143.2A$134.2A7.2A$135.A$135.A.A$136.2A$99.A52.2A$
81.2A14.5A50.A$82.A13.A5.A47.A.A$82.A.A12.3A2.A47.2A$83.2A15.A.2A$97.
4A2.A$92.2A3.A3.2A$92.2A4.3A$100.A52.A$100.A.2A48.A.A$99.2A.2A49.A3$
91.2A$91.A$92.3A$94.A56.2A$133.2A16.2A$133.2A4$144.2A$144.2A3$147.2A$
148.A$148.A.A$149.2A4$141.2A$141.2A4$35.A$35.3A$38.A$37.2A11.C$50.3C$
50.C.C$52.C3$10.D$10.3D$10.D.D15.2A$12.D15.2A$.A49.2A$A.A48.A.A$A.A
50.A$.A39.2A10.2A$41.A$31.2A9.3A$32.A11.A$29.3A$29.A!

Unlike the old standard Herschel transceiver, Guam's transceiver is transparent, so it's good for merging signals. It's also reversible, so you have your choice of output directions, and can easily use the two-dimensional adjustability to close a loop without having to fire up Hersrch -- you only have to worry about the chessboard square color. You could shut down the circuit again with a single synchronized glider in various locations, or with a boat-bit stopper.

#C Sample switchable Herschel factory using Guam's transceiver.
x = 203, y = 200, rule = LifeHistory
.A$2.A$3A51$50.A$51.A$49.3A9$86.2A$85.A.A$85.2A3$80.A$79.A.A$79.A.A
31.A$80.A30.3A$89.2A7.A11.A$89.2A7.3A9.2A$101.A$100.2A39.A$140.A.A$
140.A.A$141.A$113.2A15.D$113.2A15.D.D$130.3D$132.D4$66.2A$66.2A55.2A$
104.2A18.A$104.A16.3A$105.3A13.A$107.A4$71.2A$70.A.A$70.A$69.2A2$89.A
$88.A.A$89.2A14$65.2A$65.2A$69.2A$69.2A$83.2A$83.2A5$86.D$85.D.D7.2A$
85.D.D7.2A$73.2A11.D$74.A$71.3A$71.A$75.2A$75.2A9$113.A$95.2A14.5A$
96.A13.A5.A$96.A.A12.3A2.A$97.2A15.A.2A$111.4A2.A$106.2A3.A3.2A$106.
2A4.3A$114.A$114.A.2A$113.2A.2A3$105.2A$105.A$106.3A$108.A8$201.2A$
105.A95.A$105.3A91.A.A$108.A22.A67.2A$107.2A20.3A$128.A$128.2A2$55.A
42.A49.A36.2A$55.3A38.3A47.3A15.A20.2A$58.A36.A49.A18.3A$57.2A23.2A
11.2A35.2A11.2A20.A$82.2A48.2A32.2A4$201.2A$30.D170.2A$30.3D130.2A$
30.D.D15.2A113.2A25.2A$32.D15.2A57.2A81.2A$21.A49.2A34.2A11.2A56.2A$
20.A.A48.A.A46.A57.2A2.2A10.A$20.A.A50.A47.3A58.2A10.3A$21.A39.2A10.
2A48.A73.A$61.A108.2A24.2A$51.2A9.3A38.2A48.2A16.A12.2A$52.A11.A38.A
49.A14.3A6.A6.2A$49.3A30.2A20.3A25.2A20.3A11.A7.A.A$49.A33.A22.A26.A
22.A20.A$80.3A47.3A$80.A49.A!
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Technological Challenges

Postby simsim314 » April 30th, 2014, 7:12 pm

I liked this adjustable H splitter, because as we all know it's much better to adjust, rather than redesign. The adjustable circuitry can be also placed as "prototype", before we are sure we have everything in place, it's just much more "pleasant" to work with.

----

I've started to look for G->H, wrote some preliminary scripts, and although it's not something "drastic", just wanted to share this:

x = 22, y = 11, rule = LifeHistory
20.2E$20.2E$7.2E$8.E$2E6.E.E$.E7.2E$.E.E$2.2E10.2C$14.2C2.3A$18.A$19.A!


EDIT Just for the record here is something else I've found (also pretty much useless):

x = 164, y = 146, rule = LifeHistory
13$153.A$152.A$152.3A86$38.E$38.3E12.2E$41.E11.2E$40.2E8$37.2E$37.2E
13$42.2E3.2E$43.E3.E$40.3E5.3E13.E$40.E9.E12.E.E$64.2E2$60.3A$60.A$
61.A!

------

I was also trying to "back engineer" all known G->H and I've found some "preliminary" algorithm:

1. First find all "catalysts" when catalyst is defined as something which has been influenced by interaction, and survived in it's original form for at least one generation.

2. Find all pairs and triples of "compatible" catalysts: which defined as catalyst that have at least one common generation, i.e. generation where they both were influenced but didn't die yet (and of course all of them have to be "activated")

3. If 1-2-3 catalyst is not "stable" try to stabilize it with new catalyst.

4. Search all stable catalysts that return the initial block/beehive to it's initial place.

5. Use the created spark to generate H.

Obviously those are magic numbers, so the search can be made much deeper.

Doing some "hand search" made me realize that human can actually "guess" much better where the potential is, or "what is the actual problem". Another point is, after using 4-5 catalysts there is usually no more room for anything new. So the tree of choices is VERY wide but not that deep, making it an algorithmic challenge (in deep trees one can use some statistical analysis, to guess where to go, based on some random walking).

This algorithm also misses some depth when one of the catalyst is drastically changing the interaction, and all other catalyst stop to work. This adds some "new" options to the search, and I'm not sure either the current search engines didn't look in those directions, or this is a bad idea for some reason.

Anyway it's just a depth search, so "no magic".

I started to think about conduits. They have their own nuances, due to the fact that conduits are "moving" so unlike G->H components that can search for catalyst in some limited area, the conduits has to "localize the search" in "more active areas" making it a bit more complex, but also with much more potential results.

Anyway I think i should concentrate on G->H because it's what making everyone so miserable, when working with Spartan circuitry. Especially it's not so much about the size as it's about the recovery time. It would be great to find some G->H that works in ~100-200 generations. I think this with some compact "channel crosser", will allow the replicator to work 10-50 times faster.

EDIT |I've studied the semi snark, and it's a bit different depth search:

The first stage is just an eater catalyst:

x = 11, y = 14, rule = LifeHistory
.E$.3E$4.E$3.2E5$9.2E$9.2E2$.A$.2A$A.A!


Both of the blocks are second stage catalysts:

x = 38, y = 20, rule = LifeHistory
27.E8.2E$.E25.3E6.2E$.3E26.E$4.E24.2E$3.2E4$35.2E$9.2E24.2E$9.2E$27.A
$.A25.2A$.2A23.A.A$A.A4$6.2E$6.2E!


Next the boat (or tub) is the stabilizer:

x = 17, y = 19, rule = LifeHistory
.E8.2E$.3E6.2E$4.E$3.2E5$9.2E$9.2E2$.A$.2A12.E$A.A11.E.E$15.E3$6.2E$
6.2E!


And the last eater is one that creates the new block:

x = 20, y = 19, rule = LifeHistory
.E8.2E$.3E6.2E$4.E$3.2E13.2E$18.E$16.E.E$16.2E2$9.2E$9.2E2$.A$.2A12.E
$A.A11.E.E$15.E3$6.2E$6.2E!


So in semi snark the additional catalyst was needed not for creating the H but for recreating the initial block. So stage 4-5 in my initial algorithm are merged. Also it's interesting to notice that all the interaction stages are within 18 ticks. I would say the semi snark was generated by trying a deeper and more "tight" search.
Last edited by simsim314 on May 1st, 2014, 2:55 pm, edited 1 time in total.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby dvgrn » May 1st, 2014, 1:48 pm

simsim314 wrote:I liked this adjustable H splitter, because as we all know it's much better to adjust, rather than redesign. The adjustable circuitry can be also placed as "prototype", before we are sure we have everything in place, it's just much more "pleasant" to work with.

Just for the record, here's a sample completion of this prototype adjustable circuitry toolkit: the input glider lanes are different colors, and the output Herschels are centered on different colors as well. This last is a separate adjustment, by adding F116+F166:

x = 170, y = 155, rule = LifeHistory
33.2A$32.A.A$32.2A3$27.A$26.A.A116.2A$26.A.A115.A2.A$27.A117.2A8$149.
3D$150.D$48.A99.3D$47.A.A$47.A.A$48.A$37.D$13.2A22.D.D$13.2A22.3D116.
2A$39.D116.A.A$158.A$158.2A5$18.2A$17.A.A$17.A130.2A$16.2A121.2A7.2A$
140.A$36.A103.A.A$35.A.A103.2A$36.2A120.2A$158.2A$168.2A$168.A$166.A.
A$166.2A9$12.2A148.2A$12.2A148.A.A$16.2A146.A$16.2A146.2A$30.2A$30.2A
4$147.2A$33.A113.2A$32.A.A7.2A111.2A$32.A.A7.2A111.A$20.2A11.A122.3A$
21.A136.A$18.3A$18.A$22.2A$22.2A2$51.A8.2A$51.3A6.2A$54.A$53.2A13.2A$
68.A88.A$66.A.A86.3A$66.2A86.A$20.3A131.2A$22.A36.2A$21.A37.2A3$65.A$
64.A.A89.2A$65.A90.2A$132.2A$131.A.A$56.2A73.A$56.2A72.2A6$38.3A$40.A
$39.A6$152.2A$152.A.A$154.A$154.2A7$144.2A$135.2A7.2A$136.A$136.A.A$
137.2A$153.2A$153.A$151.A.A$151.2A5$154.A$153.A.A$154.A5$3A$2.A149.2A
$.A132.2A16.2A$134.2A4$145.2A$145.2A3$148.2A$149.A$149.A.A$150.2A4$
142.2A$142.2A!

Just adding F116 would be enough to change the Herschel's output color, but then the resulting circuit isn't Spartan... Herschel conduits are downright annoying sometimes -- too many subtle things that can go wrong. The Snark-assisted non-Spartan version would have input gliders on the same colors, since Snarks are color-preserving but semi-Snarks are color-changing.

simsim314 wrote:I've started to look for G->H, wrote some preliminary scripts, and although it's not something "drastic", just wanted to share this...

Argh! Another "near miss", that isn't really all that near. There's no particular reason why you shouldn't be able to catalyze the output pre-Herschel to re-create a block in the right location (after the block gets destroyed in the not-quite-right location). But then again, there's no particular reason why you should get the block back, either -- the odds are really pretty low, especially if you also want to get a new clean Herschel out, and suppress the other extra block somehow.

simsim314 wrote:I was also trying to "back engineer" all known G->H and I've found some "preliminary" algorithm:

1. First find all "catalysts" when catalyst is defined as something which has been influenced by interaction, and survived in it's original form for at least one generation.

2. Find all pairs and triples of "compatible" catalysts: which defined as catalyst that have at least one common generation, i.e. generation where they both were influenced but didn't die yet (and of course all of them have to be "activated")

I'm not sure if there's any practical advantage to thinking of catalysts as "compatible" in this way, but I suppose it might open up some new search space. For cases where catalysts are very close to each other, some combinations have occasionally been defined in ptbsearch as a single composite catalyst -- but I don't think that's what you're describing here.

As I recall, ptbsearch and catalyst both place catalysts one at a time, and each successful placement (where Catalyst #1 isn't immediately destroyed) creates a new branch of the tree, which is presumed to have a new, modified active area* that can in turn be catalyzed by more catalysts. If that branch is explored completely -- all possible combinations of Catalysts #2, #3, etc., have been tried -- then it's time to remove Catalyst #1 and try the next possible open location.

simsim314 wrote:4. Search all stable catalysts that return the initial block/beehive to it's initial place.

Computers are quite possibly fast enough now to make it worth looking also at glider+boat and glider+tub initial collisions, at least. Not sure about glider+pond or glider+ship, and glider+longboat seems like an awfully long shot (though ships are theoretically only twice as common as longboats).

There are also some glider+2block combinations where the two blocks fairly commonly reappear near each other -- the half-blockade is the example that springs to mind, but there might be others that would be statistically more likely to appear than, say, longboats. Less common still lifes still seem pretty hopeless -- I'd be really surprised, for example, if a glider+eater collision is found any time soon that restores the eater; you have to take into account not just the frequency of appearance, but the number of possible orientations.

[I'm curious about glider+blinker reactions, too, but P2 circuitry is just not as nice to work with as P1 stable stuff -- might be more annoying than useful to find a P2 G-to-H...! I believe Paul Callahan did quite a few searches using blinkers in various ways, but nothing really compelling turned up.]

simsim314 wrote:Doing some "hand search" made me realize that human can actually "guess" much better where the potential is, or "what is the actual problem". Another point is, after using 4-5 catalysts there is usually no more room for anything new. So the tree of choices is VERY wide but not that deep, making it an algorithmic challenge (in deep trees one can use some statistical analysis, to guess where to go, based on some random walking).

This algorithm also misses some depth when one of the catalyst is drastically changing the interaction, and all other catalyst stop to work. This adds some "new" options to the search, and I'm not sure either the current search engines didn't look in those directions, or this is a bad idea for some reason.

If I'm understanding you correctly, previous searches have used a method that avoids most of that problem -- see above -- and so have covered most of that search space.

simsim314 wrote:Next the boat (or tub) is the stabilizer...

Also it's interesting to notice that all the interaction stages are within 18 ticks. I would say the semi snark was generated by trying a deeper and more "tight" search.

That's funny that I never noticed that the semi-Snark only needs a tub to work, not a boat. The semi-Snark was found with Guam's mysterious search utility -- I haven't been able to get hold of him recently to get a copy of the source code.

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

* One of the big optimizations that could be done, without any other big changes to current search code, would be to figure out how to filter out the catalyst placements that don't actually make any difference -- they have the exact same effect as some other catalyst, or they interact trivially with a dying spark or output glider and have no interesting effect at all.

This filtering problem is complicated by the fact that different catalysts take up space in different ways, so even a trivial substitution might open up a key location for placing another catalyst. But it might be time to give up the idea of doing an exhaustive search, and instead concentrate on avoiding duplicated searches as much as possible, and covering as much new area as possible.

Current 'catalyst' search output, for example, very often has many hundreds of variations with the same exact final pattern but lots of different combinations of catalyst placement. It would certainly be worth boiling all those down to one output pattern, plus a parenthetical "(250 variants)" or whatever if you're still doing an exhaustive search. If that candidate actually looks interesting, then maybe it's time to unpack all the variants and try to find one that works.
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Technological Challenges

Postby simsim314 » May 1st, 2014, 6:29 pm

Here is an analysis of the current behive+glider -> H converter.

x = 201, y = 106, rule = LifeHistory
46.A39.A39.A$45.A39.A39.A$45.3A37.3A3.2E32.3A$91.E$89.E.E$38.E39.E10.
2E27.E$37.E.E37.E.E37.E.E$37.E.E37.E.E37.E.E$32.2E4.E39.E39.E$31.E.E
95.2E$31.E97.E.E$30.2E99.E$131.2E13$A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A
.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.
A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A
.A.A.A.A.A.A.A.A.A.A.A.A.A.A2$158.A2$158.A2$158.A2$158.A2$158.A2$158.
A2$158.A23.E$46.A49.A39.A45.3E$45.A49.A39.A22.A26.E8.A$45.3A47.3A3.2E
32.3A3.2E41.2E7.A$101.E39.E16.A34.3A$99.E.E37.E.E$38.E49.E10.2E27.E
10.2E17.A$37.E.E47.E.E37.E.E56.E$37.E.E47.E.E37.E.E28.A26.E.E$32.2E4.
E43.2E4.E39.E56.E.E$31.E.E15.2E30.E.E55.2E17.A21.2E4.E$31.E17.E.E29.E
57.E.E37.E.E$30.2E19.E28.2E59.E16.A20.E$51.2E88.2E35.2E$158.A2$158.A
2$158.A2$158.A2$158.A2$158.A$A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.
A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A
.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A3.A.A.A.A.A.A.A.A.A.A
.A.A.A.A.A.A.A.A.A.A2$158.A2$158.A2$158.A2$158.A2$158.A2$158.A2$158.A
2$158.A23.E$90.A91.3E$89.A68.A26.E8.A$89.3A3.2E87.2E7.A$95.E62.A34.3A
3.2E$93.E.E103.E$82.E10.2E63.A38.E.E$81.E.E102.E10.2E$81.E.E74.A26.E.
E$76.2E4.E102.E.E$75.E.E15.2E63.A21.2E4.E$75.E17.E.E83.E.E15.2E$74.2E
19.E62.A20.E17.E.E$95.2E81.2E19.E$158.A40.2E2$158.A2$158.A2$158.A2$
158.A2$158.A$160.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A!


If you go to generation 42 you can see that 3 out of the four stabilizing eaters are catalysts (that hold for one generation).

Another detail is that every two of the three eaters improves the "surviving" period of the "most short lived" of the two.

The key point I'm trying to say: you don't need to go into "depth" search from start. Most of the eaters are catalysts for the initial g+bh interaction. You need only to locate "all" the potential catalyst on stage 0, and check "compatibility". This will improve performance drastically (and probably will automatically remove many of the redundancy you're talking about). Taking into account that many of the catalyst don't influence the interaction drastically enough for the others catalyst to stop working. It's nice optimization to have fast "multi-catalyst system", on the first iteration alone.

Now the "fourth" eater is catalyst of "second order", which needs to be searched independently, either as a second iteration, or as "stabilizer" of the "unstable three eater system".

The other G->H even doesn't have additional stabilizer, it's simply three catalyst that work on pi, all of them compatible with each other (and I think improve the surviving time of the "worst" as well).

--------

Another problem I'm dealing with: the space for new catalysts is shrinking as the number of the catalysts grow. Because the catalyst is working due to previous N generations, so the "cell path" of those generations is actually "taken" by those catalysts and cannot be "altered". So placing the catalyst there is illogical, as it's illogical to place a catalyst in front of the first glider. This could be a nice optimization, not wasting time on places which are already "inside the path" of already present catalyst.

And finally some problem of distance I'm dealing with. Some catalyst just "throw the live cells" far away from the initial block. And due to the limitation I mentioned in previous section, the chances of "getting them back" are pretty slim, and get slimmer with every new catalyst.

--------

About the glider problem: I think this should be simply "hard coded" to avoid eaters that stop gliders as valid catalysts. This is too common problem, and too simple to handle it in any more "generic" way.

I was also thinking about something that called "evaluation function". In chess for example the tree has too many nodes, and this makes those kind of problem very common (also the problem with "same variation that get the same results in 250 ways). The solution in chess as I know it, is to "spread the search" over few branches in parallel, with most potential. When some branch is "dead end" (or when the evaluation of it dropped after searching all the leaves) the chess engine just search for new candidates, from the current "less explored" areas.

Small comment about the problem with "similar" results but different catalyst location. I don't have a very good answer to it, also I actually do think if some combination has a very good potential, maybe it does worth to search all the branches there. One of the solutions to this, is to have a "cache" to the evaluation function (or make it dynamic, so positions (and similar to them) that yield bad results are "reevaluated"), thus lowering the "evaluation" a little bit to give chance to other more potential branches to be searched deeper. So this and parallel search should give some answer to this.

Now the evaluation function could consist of various factors: the distance from the initial block, the potential points to place the catalyst, time the interaction works (we want to make it work faster than silver so above 500 ticks it's pointless). It's also can take some good "working" catalyst, and "learn" from them, giving bigger score to those that has been "proven" to work, and on the contrary "learn from the bad" giving lower score to those combination that was proved not to work.

-------

I was wondering, how bad is it to use golly with python for this kind of searches? I don't think I can write anything better than golly that will run Life simulation. On the other hand the python-golly interface is pretty heavy, python is slow, as i understand golly "data management" (all the get-put functions) is also not the best in the world. How crucial is it to write the search utility in C? Do you think it's possible to make some "golly oriented" script, that will use the golly speed, that could compensate of the other slow factors?

EDIT I was thinking on better definition of compatibility: Let's say we have two catalysts C1 and C2, and C1 started to influence the system at generation T1. So C2 at "distance" D should be influenced by C1 at T1 + D. So C2 should work as usual, for time less than T1 + D. And as for "transparent" catalyst go, the "rebirth" time of C2 should be less than T1+D.

Another point of "compatibility" should be that the radius of influence of C1 should reach C2 before the time C2 "suppose" to be dead, so C1 could influence this outcome. If we add this to definition, some incompatible catalysts can become compatible just because we've found some way to stabilize or prolong the leaving time of C2 (but yet again it wouldn't be C2 but C2+Delta). And this could save some precious search time.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby dvgrn » May 2nd, 2014, 10:13 am

simsim314 wrote:Another problem I'm dealing with: the space for new catalysts is shrinking as the number of the catalysts grow. Because the catalyst is working due to previous N generations, so the "cell path" of those generations is actually "taken" by those catalysts and cannot be "altered". So placing the catalyst there is illogical, as it's illogical to place a catalyst in front of the first glider. This could be a nice optimization, not wasting time on places which are already "inside the path" of already present catalyst.

This is taken care of in every catalyst search program I know about, by keeping a record of some variant of a LifeHistory-type "envelope" -- you can't place a new catalyst too close to any cell that is recorded as having already been ON at some point in the past.

A LifeHistory envelope is a little too crude, though. I think current search programs all use a neighbor count for each cell. If a cell's neighbor count is 1 -- that is, a single neighbor turned ON one or more times, but never two neighbors at once -- then it may still be okay to place a "pointy" catalyst next to that cell, like a tub, or the very tip of an eater's tail. But a block or other two-cell flat edge would cause a birth at that cell, so those are forbidden.

simsim314 wrote:I was also thinking about something that called "evaluation function". In chess for example the tree has too many nodes, and this makes those kind of problem very common (also the problem with "same variation that get the same results in 250 ways). The solution in chess as I know it, is to "spread the search" over few branches in parallel, with most potential. When some branch is "dead end" (or when the evaluation of it dropped after searching all the leaves) the chess engine just search for new candidates, from the current "less explored" areas.

Well, that's the hard part, isn't it? If you can come up with a really good evaluation function that keeps 99% of the promising reactions and throws away 99% of the "obviously useless" ones, you'll have no shortage of volunteers to write the rest of the search program for you.

simsim314 wrote:I was wondering, how bad is it to use golly with python for this kind of searches? I don't think I can write anything better than golly that will run Life simulation. On the other hand the python-golly interface is pretty heavy, python is slow, as i understand golly "data management" (all the get-put functions) is also not the best in the world.

I believe the consensus is that a Golly Python search utility would be slower than an optimized C/C++ version by at least an order of magnitude -- probably a lot more than that in most cases. Oddly enough, Golly isn't really all that fast at looking through lots of little chaotic patterns, which is what a search like this needs.

Golly's big advantage is its hashing tricks, but really the QuickLife algorithm is significantly faster than HashLife for chaotic patterns. Then you add in all the extra memory and time overhead of Python passing small patterns around in the form of horribly inefficient cell lists instead of simple one-bit-per-cell representations, and suddenly you're waiting around a hundred times longer for the same answers.

simsim314 wrote:How crucial is it to write the search utility in C? Do you think it's possible to make some "golly oriented" script, that will use the golly speed, that could compensate of the other slow factors?

Seems like it would take a pretty big cross-platform Golly-Python-based distributed search system to catch up with what you can do on one computer with C++. I think maybe what you want is C++ speed, but the cross-platform convenience of Golly. Paul Chapman's compromise was a compiled DLL called by a Python script. The links are to Paul's RLife8 DLL and the latest pre-alpha version of DOpSearch. These were used to find combinations of gliders on two or three lanes to manipulate a Geminoid construction-arm elbow.

So far I haven't even tried to figure out how to call RLife8 for my own search projects -- too many other things to do first (mostly in Real Life, unfortunately). So the documentation isn't too good at the moment. But at least we have working search code to figure things out from! RLife8 is about as fast as Paul could easily make it, and he certainly seemed to be worried about all the right things. [I'm not really a benchmarking/bit-twiddling/optimization expert myself, though I could probably play one on TV.]

In this case the Python script had nothing to do with Golly at all, but it shouldn't be too painful to use Golly for display and control purposes. There are a lot of GUI-control tricks possible with Golly 2.3+ using golly.getevent() -- select or click on a candidate pattern to move it to the top of the search queue, that kind of thing.
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Technological Challenges

Postby simsim314 » May 2nd, 2014, 10:20 am

I've written a rule that have "listener cell" in regular Life rule, and when the listener cell dies it triggers a "circle of influence" (which is actually a square in Life metric), centered in this cell. Two circles will "unite" into two "half circles", indicating the both of the triggers are "causally separated" and can't influence each other.

Here is the rule:

@RULE PropogatingLife

@TABLE
n_states:7
neighborhood:Moore
symmetries:rotate8

# 1 regular live cell
# 2 trigger cell
# 3 head live
# 4 head dead
# 5 tail live
# 6 tail dead

var la1 = {1, 2, 5}
var la2 = {1, 2, 5}
var la3 = {1, 2, 5}

var a1 = {0,1, 2, 5, 6}
var a2 = {0,1, 2, 5, 6}
var a3 = {0,1, 2, 5, 6}
var a4 = {0,1, 2, 5, 6}
var a5 = {0,1, 2, 5, 6}
var a6 = {0,1, 2, 5, 6}
var a7 = {0,1, 2, 5, 6}
var a8 = {0,1, 2, 5, 6}

var hla1 = {1, 2, 3}
var hla2 = {1, 2, 3}
var hla3 = {1, 2, 3}

var ha1 = {0,1, 2, 3, 4}
var ha2 = {0,1, 2, 3, 4}
var ha3 = {0,1, 2, 3, 4}
var ha4 = {0,1, 2, 3, 4}
var ha5 = {0,1, 2, 3, 4}
var ha6 = {0,1, 2, 3, 4}
var ha7 = {0,1, 2, 3, 4}
var ha8 = {0,1, 2, 3, 4}
var ha = {1, 2, 3, 4}

var z = {0,1}
var hz = {3,4}
var v = {1,2}

var hd1 = {0,4}
var hd2 = {0,4}
var hd3 = {0,4}
var hd4 = {0,4}
var hd5 = {0,4}
var hd6 = {0,4}

var tz = {5,6}

var ta1 = {0,1, 2, 3, 4, 5, 6}
var ta2 = {0,1, 2, 3, 4, 5, 6}
var ta3 = {0,1, 2, 3, 4, 5, 6}
var ta4 = {0,1, 2, 3, 4, 5, 6}
var ta5 = {0,1, 2, 3, 4, 5, 6}
var ta6 = {0,1, 2, 3, 4, 5, 6}
var ta7 = {0,1, 2, 3, 4, 5, 6}
var ta8 = {0,1, 2, 3, 4, 5, 6}
var ta = {1, 2, 3, 4, 5, 6}

var tla1 = {1, 2, 3, 5}
var tla2 = {1, 2, 3, 5}
var tla3 = {1, 2, 3, 5}

var td1 = {0,4,6}
var td2 = {0,4,6}
var td3 = {0,4,6}
var td4 = {0,4,6}
var td5 = {0,4,6}
var td6 = {0,4,6}

var d1 = {0,6}
var d2 = {0,6}
var d3 = {0,6}
var d4 = {0,6}
var d5 = {0,6}
var d6 = {0,6}


#regular case (with neighbour tails only) three neighbours

z,la1,la2,la3,d1,d2,d3,d4,d5,1
z,la1,la2,d1,la3,d2,d3,d4,d5,1
z,la1,la2,d1,d2,la3,d3,d4,d5,1
z,la1,la2,d1,d2,d3,la3,d4,d5,1
z,la1,la2,d1,d2,d3,d4,la3,d5,1
z,la1,la2,d1,d2,d3,d4,d5,la3,1
z,la1,d1,la2,d2,la3,d3,d4,d5,1
z,la1,d1,la2,d2,d3,la3,d4,d5,1

2,la1,la2,la3,d1,d2,d3,d4,d5,2
2,la1,la2,d1,la3,d2,d3,d4,d5,2
2,la1,la2,d1,d2,la3,d3,d4,d5,2
2,la1,la2,d1,d2,d3,la3,d4,d5,2
2,la1,la2,d1,d2,d3,d4,la3,d5,2
2,la1,la2,d1,d2,d3,d4,d5,la3,2
2,la1,d1,la2,d2,la3,d3,d4,d5,2
2,la1,d1,la2,d2,d3,la3,d4,d5,2

#regular case(with neighbour tails only)  two neighbors
v,la1,la3,d1,d2,d3,d4,d5,d6,v
v,la1,d1,la3,d2,d3,d4,d5,d6,v
v,la1,d1,d2,la3,d3,d4,d5,d6,v
v,la1,d1,d2,d3,la3,d4,d5,d6,v

#regular case (with neighbour tails only) death

1,a1,a2,a3,a4,a5,a6,a7,a8,0
0,a1,a2,a3,a4,a5,a6,a7,a8,0
2,a1,a2,a3,a4,a5,a6,a7,a8,4

#Neighbohr head no tails

z,hla1,hla2,hla3,hd1,hd2,hd3,hd4,hd5,3
z,hla1,hla2,hd1,hla3,hd2,hd3,hd4,hd5,3
z,hla1,hla2,hd1,hd2,hla3,hd3,hd4,hd5,3
z,hla1,hla2,hd1,hd2,hd3,hla3,hd4,hd5,3
z,hla1,hla2,hd1,hd2,hd3,hd4,hla3,hd5,3
z,hla1,hla2,hd1,hd2,hd3,hd4,hd5,hla3,3
z,hla1,hd1,hla2,hd2,hla3,hd3,hd4,hd5,3
z,hla1,hd1,hla2,hd2,hd3,hla3,hd4,hd5,3

1,hla1,hla3,hd1,hd2,hd3,hd4,hd5,hd6,3
1,hla1,hd1,hla3,hd2,hd3,hd4,hd5,hd6,3
1,hla1,hd1,hd2,hla3,hd3,hd4,hd5,hd6,3
1,hla1,hd1,hd2,hd3,hla3,hd4,hd5,hd6,3

2,hla1,hla2,hla3,hd1,hd2,hd3,hd4,hd5,2
2,hla1,hla2,hd1,hla3,hd2,hd3,hd4,hd5,2
2,hla1,hla2,hd1,hd2,hla3,hd3,hd4,hd5,2
2,hla1,hla2,hd1,hd2,hd3,hla3,hd4,hd5,2
2,hla1,hla2,hd1,hd2,hd3,hd4,hla3,hd5,2
2,hla1,hla2,hd1,hd2,hd3,hd4,hd5,hla3,2
2,hla1,hd1,hla2,hd2,hla3,hd3,hd4,hd5,2
2,hla1,hd1,hla2,hd2,hd3,hla3,hd4,hd5,2

2,hla1,hla3,hd1,hd2,hd3,hd4,hd5,hd6,2
2,hla1,hd1,hla3,hd2,hd3,hd4,hd5,hd6,2
2,hla1,hd1,hd2,hla3,hd3,hd4,hd5,hd6,2
2,hla1,hd1,hd2,hd3,hla3,hd4,hd5,hd6,2

z,ha,ha2,ha3,ha4,ha5,ha6,ha7,ha8,4
2,ha,ha2,ha3,ha4,ha5,ha6,ha7,ha8,4

hz,tla1,tla2,tla3,td1,td2,td3,td4,td5,5
hz,tla1,tla2,td1,tla3,td2,td3,td4,td5,5
hz,tla1,tla2,td1,td2,tla3,td3,td4,td5,5
hz,tla1,tla2,td1,td2,td3,tla3,td4,td5,5
hz,tla1,tla2,td1,td2,td3,td4,tla3,td5,5
hz,tla1,tla2,td1,td2,td3,td4,td5,tla3,5
hz,tla1,td1,tla2,td2,tla3,td3,td4,td5,5
hz,tla1,td1,tla2,td2,td3,tla3,td4,td5,5

3,tla1,tla3,td1,td2,td3,td4,td5,td6,5
3,tla1,td1,tla3,td2,td3,td4,td5,td6,5
3,tla1,td1,td2,tla3,td3,td4,td5,td6,5
3,tla1,td1,td2,td3,tla3,td4,td5,td6,5

2,tla1,tla2,tla3,td1,td2,td3,td4,td5,2
2,tla1,tla2,td1,tla3,td2,td3,td4,td5,2
2,tla1,tla2,td1,td2,tla3,td3,td4,td5,2
2,tla1,tla2,td1,td2,td3,tla3,td4,td5,2
2,tla1,tla2,td1,td2,td3,td4,tla3,td5,2
2,tla1,tla2,td1,td2,td3,td4,td5,tla3,2
2,tla1,td1,tla2,td2,tla3,td3,td4,td5,2
2,tla1,td1,tla2,td2,td3,tla3,td4,td5,2

2,tla1,tla3,td1,td2,td3,td4,td5,td6,2
2,tla1,td1,tla3,td2,td3,td4,td5,td6,2
2,tla1,td1,td2,tla3,td3,td4,td5,td6,2
2,tla1,td1,td2,td3,tla3,td4,td5,td6,2

hz,ta1,ta2,ta3,ta4,ta5,ta6,ta7,ta8,6
2,ta1,ta2,ta3,ta4,ta5,ta6,ta7,ta8,4

#tails

tz,tla1,tla2,tla3,td1,td2,td3,td4,td5,1
tz,tla1,tla2,td1,tla3,td2,td3,td4,td5,1
tz,tla1,tla2,td1,td2,tla3,td3,td4,td5,1
tz,tla1,tla2,td1,td2,td3,tla3,td4,td5,1
tz,tla1,tla2,td1,td2,td3,td4,tla3,td5,1
tz,tla1,tla2,td1,td2,td3,td4,td5,tla3,1
tz,tla1,td1,tla2,td2,tla3,td3,td4,td5,1
tz,tla1,td1,tla2,td2,td3,tla3,td4,td5,1

5,tla1,tla3,td1,td2,td3,td4,td5,td6,1
5,tla1,td1,tla3,td2,td3,td4,td5,td6,1
5,tla1,td1,td2,tla3,td3,td4,td5,td6,1
5,tla1,td1,td2,td3,tla3,td4,td5,td6,1

tz,ta1,ta2,ta3,ta4,ta5,ta6,ta7,ta8,0

@COLORS
0    0      0    0
1    255  255  255
2    255      0    0
3  255  255  255
4   0      0    255
5  255  255    255
6   0      0    0


And here is an example:

x = 97, y = 120, rule = PropogatingLife
60.A.A20.A$61.2A18.3A$61.A18.A$80.BA6$90.A$88.3A$87.A$87.BA$65.AB$65.
2A6$77.2A$77.2A$91.AB$91.2A$95.2A$95.BA14$71.2A$71.A.B$72.A7$67.A.2A$
67.2A.A2$76.AB$76.2A10$62.A$60.3A$59.A$59.2A2$66.2A$67.A$67.A.A$40.A
27.AB$31.A7.A.A$31.3A6.B$34.A$33.AB6$26.2A25.2A$26.2A25.A$51.A.A6.A8.
AB15.BA$2A49.BA7.3A6.2A15.A.A$AB61.A24.A$62.2A24.2A$38.AB$29.2A6.A.A$
30.A6.A41.A$29.A6.2A39.3A$4.BA23.2A45.A$4.2A70.2A4$40.AB$39.A.A$39.A$
38.2A4$83.2A$83.2A4$78.BA$78.2A$82.2A$82.2A$41.2A$41.2A$47.AB27.2A$
47.2A27.2A3$45.2A$45.2A5.2A$52.2A!


This made to "get feeling" on how "independent catalyst" (or compatible catalyst) are actually common. Two catalysts that are casually separated, can be safely "merged" without any further search prerequisites. Also it's kinda nice to notice that "almost compatible" catalyst are also pretty common, because the "influence" of single catalyst usually propagates slower than speed of light.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby simsim314 » May 3rd, 2014, 6:57 am

I was running some performance comparison between different languages, for Life-catalyst oriented implementations, and not surprisingly C was the fastest language (then c++ with around 30-50% slower), and a higher languages like C# or python (with golly) is not in the competition at all being 5-15 times slower.

I think the current approach, writing search utilities in C, and using golly as GUI is the best one. I don't see any real reason to use some sophisticated dll systems, all we need is command lines that read/write from files and python to manage external processes, and read/write into the same files as well.

There is also a remote but possible option, to add some code into golly source code itself. Not the best option, but getting familiar with golly code, can be beneficial in many ways, and many "tricks" from golly can come "out of the box", without too much effort.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby simsim314 » May 3rd, 2014, 5:01 pm

dvgrn wrote: If you can come up with a really good evaluation function that keeps 99% of the promising reactions and throws away 99% of the "obviously useless" ones


Well the point is not to "guess very well" if some reaction can come up with good results or not. This would be pretty difficult. The point is that any more or less "reasonable" evaluation function is simply so much better than brute force.

Think if it were chess: try to search for all possible moves from the starting position to mate. It would be simply inefficient, you will never get any results whatsoever with this approach, losing a lot of time searching in places where "no one" wouldn't even bother to look. So if you use even pretty "dumb" evaluation function, this will improve the performance of the engine by so many orders of magnitude. Just the fact that you look in "most promising" places first in much more depth, makes it so much more efficient, even if your concept of the most promising places is not so accurate.

And as I mentioned, there is an obvious evaluation function with catalyst searches (for G->H): like the minimal distance to the original block, and number of options to place the catalyst relatively "close" to the block. You're definitely right that it can for example have some "cache of patterns" and very similar pattern that showed to be a failure can also score lower. So we can come up with "more or less" reasonable evaluation function that will cut our "brute force search" in millions or billions of times, it doesn't has to be near perfection it's just needs to be "good enough" to work with, just not to waste a lot of time on totally useless cases or on the other hand use much more time on a obviously promising cases.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby dvgrn » May 5th, 2014, 10:58 pm

simsim314 wrote:And as I mentioned, there is an obvious evaluation function with catalyst searches (for G->H): like the minimal distance to the original block, and number of options to place the catalyst relatively "close" to the block. You're definitely right that it can for example have some "cache of patterns" and very similar pattern that showed to be a failure can also score lower. So we can come up with "more or less" reasonable evaluation function that will cut our "brute force search" in millions or billions of times...

Oh, I'm not arguing. The odds are good that a different approach will turn up new and interesting things.

Just seems like the devil's in the details, as they say. There are quite a few unfinished search utilities lying around out there for every functional one -- and not too surprisingly, the simpler programs seem to be the ones that get finished more often!

In 'ptbsearch' and 'catalyst' searches I'd say that the approach has been to set the search parameters in such a way that you're only searching a tiny fraction of the search space -- very similar to the factor of millions or billions you're talking about. For example, you might set a maximum of three catalysts, and only allow placement within the first fifty ticks of the pi explosion, so that pretty much all possible catalysts are bound to be within a reasonable distance.

Often this kind of limited brute-force search can be run to completion, and will come up with only maybe a few dozen hopeful candidates. Some manual inspection can determine which ones might benefit from searching further -- and then reasonable boundaries can be set up for new searches with those starting points, and so on.

Clearly it would be great if all this manual intervention could be avoided -- but on the other hand it's clearly doing a very good job of cutting many orders of magnitude off of the search space. It seems like a hard problem to write an evaluation function that can replace this expert-inspection stage. Here the difference between "promising" and "hopeless" seems fairly subtle, and very tricky to convert into an algorithm... I just know it when I see it!

At some point I'd like to set up a GUI for this kind of search, to allow more efficient use of human intuition. Let ptbsearch run for an hour, let's say, come up with a pile of possible branches to search... then display the candidates in as intuitive a way as possible, have the user click on them to re-order the good ones or delete the hopeless ones, and run for another hour (or whatever -- maybe every five minutes, or whevener the user feels like checking in.)
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Technological Challenges

Postby simsim314 » May 6th, 2014, 2:31 pm

dvgrn wrote: There are quite a few unfinished search utilities lying around out there for every functional one -- and not too surprisingly, the simpler programs seem to be the ones that get finished more often!


Oh I do agree on that... there are so many nice project to do in this area, and so little "infrastructural" support. Especially with C utilities. I recently took a look at WinLifeSearch source code. And although it's heavily documented, and a lot of effort went into support and simplicity (I actually managed to compile it for my x64 machine), it's still light year away, for me actually understand the code to be able to do some basic things, like dividing the search tree for multi-threading. It's just so much simpler for me to write the whole thing over. This would not happen with nice OO design and class structures. Unfortunately, c++ is 1.4 slower than c, which is a significant factor for out purposes.

EDIT I was looking into catalyst code, which I thought is c++. Fortunately (or not), it's c code. So I made it to compile with GCC compiler which generates by far the fastest executables. Now fortunately unlike the search.c in WLS project (lifesrc?), that has about 4K lines of code, Gabriel's catalyst has around 200-300 lines of "real" code. Manageable for me.

/* catalyst v1.0
   Released 3/21/2001
   Copyright (c) 2001, Gabriel Nivasch
*/
/*
   Modified By Michael Simkin
   GCC compatible C code.
*/

#include <stdio.h>
#include <stdlib.h>

#define Profilea 0
#define SZ 60
#define MAXGENS 100
#define MAXCATS 10
#define NCATS 7
#define CATSZ 15

typedef struct
{
    int x, y;
} cell;

typedef struct
{
    char c[CATSZ][CATSZ];
    int x, y, name;
} catalyst;

const catalyst cata[NCATS]=
{
    {   {   {' ', ' ', 'x', ':', '2', '1', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', '.', '*', 'o', ':', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', ':', '$', '%', '*', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {':', '*', '*', '*', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {':', '*', '$', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', '.', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
        },
        6, 6, 'eat1'
    },
    {   {   {' ', ' ', ' ', '.', '.', 'X', ':', '2', '1', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', '.', ':', '$', '*', '$', 'o', 'o', '2', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', ':', '*', '*', '*', '$', 'o', 'o', ':', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', '*', '%', '^', '$', '$', '$', '$', 'X', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', ':', '*', '*', '*', '$', '*', '*', '.', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', '.', ':', '%', '*', '^', '*', '$', '.', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ':', '*', '%', '*', ':', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', '.', ':', '*', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', '.', '.', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
        },
        9, 9, 'eat2'
    },
    {   {   {'x', '.', ':', ':', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'2', '*', '$', '*', '*', ':', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'X', '*', '*', '$', '*', ':', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'x', ':', ':', ':', '.', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
        },
        4, 6, 'snak'
    },
    {   {   {'.', 'X', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {':', '*', 'o', '2', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {':', '*', 'o', '2', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', 'X', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
        },
        4, 4, 'bloc'
    },
    {   {   {' ', ' ', ' ', ' ', '.', ':', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ':', '*', '*', ':', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ':', 'o', 'o', ':', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', '.', ':', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', 'x', '.', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', '.', ':', 'o', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', '.', '*', '$', 'o', '1', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', ':', '$', '$', '*', 'X', '1', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {':', '*', '*', '*', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {':', '*', '$', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', '.', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
        },
        11, 8, 'tubw'
    },
    {   {   {' ', '.', 'x', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', ':', '*', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'1', 'o', '$', '*', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'.', ':', '*', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', '.', 'x', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
        },
        5, 5, '_tub'
    },
    {   {   {' ', 'x', '.', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'x', ':', '*', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'1', 'o', '%', '*', ':', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {'1', 'X', '*', '*', ':', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', '.', ':', ':', '.', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
        },
        5, 5, 'boat'
    }
};
/* The following array contains the state of the pattern at each
generation from 0 to the current one. For each generation there are two
arrays: now[SZ][SZ] and history[SZ][SZ]. now[][] contains the state of
the pattern at that generation. The format is as follows:
If the cell is alive, then bit #9 (LiveBit) is set.
In addition, exactly one of the bits #0 to #8 is set, indicating the
number of live neighbors the cell has.

history[][] contains the superposition (inclusive "OR") of all the
states each cell has been in, in all the previous generations.

The purpose of history[][] is to know whether the cell has ever been alive,
and if it was never alive, to know all the different neighbor counts it
has had. If bit #9 is set, it means the cell has been alive at some
point, and each of the bits #0 to #8 that is set indicates a neighbor
count the cell has had at some point.

For each generation there are also four variables indicating the current
boundaries of the pattern, and the variable numcats, which indicates how
many catalysts have been placed this generation.
*/
struct board
{
    int now[SZ][SZ];
    int history[SZ][SZ];
    int xmin, xmax, ymin, ymax;
    int numcats;
} stack[MAXGENS];

//Bit values used in now[][] and history[][]:
#define LiveBit 512
#define CountBitMask 511

//This macro function is used in advance1gen():
#define WillLive(x) ((x)==8 || (x)==516 || (x)==520)

/* The following array is used to print out the patterns created.
At the beginning the initial pattern is set in it. In addition, each
time a catalyst is placed on the board at a certain generation, it is
also placed here. When the catalyst is removed from the board, it is
also removed from here.
*/
int boardgen0[SZ][SZ];
int g0minx=SZ, g0miny=SZ, g0maxx=0, g0maxy=0;

/* This array indicates which cells are fixed, i.e. if they are dead,
they are not allowed to live, and if they are alive, they are not
allowed to die. There are two sources from which fixed cells can come:
From the catalysts (cells marked 'x', 'X', and '*'), or from the input
pattern of the user. Note that cells that were set fixed dead by the
user or by a catalyst, might be set again as fixed dead by another catalyst.
Then, when the second catalyst is removed, the cell should still remain fixed
dead because of the first catalyst or the user's input. Therefore, the
procedure is as follows:
To set a cell as fixed, add 1. To unset it, substract 1. The cell is free
only if the value is 0. If the value is less than 0, it is an error.
*/
int fixed[SZ][SZ];

/* The following array contains info for each catalyst that has
been placed on the board: position, catalyst number, orientation,
generation placed, and the old values of the pattern boundaries, which
are restored when the catalyst is removed.
*/
struct catposition
{
    int x, y, n, orient, gen;
    int oldxmin, oldxmax, oldymin, oldymax; //Used to restore the values
    //after removing the catalyst.
    int g0oldminx, g0oldminy, g0oldmaxx, g0oldmaxy;
    //Used to restore g0minx, etc., after removing the catalyst.
} catplaced[MAXCATS];

int catisused[NCATS]; //The user can select which catalysts to use.

int startinggen, gens, catstoplace, catspergen, catsurvive;
int currgen, currx, curry, currcatn, currorient;
int nCatsTotal=0; //Used to index catplaced[]
int callcount=0;

int advance1gen(void);
int placecatalyst(void);
int removelastcat(void);
void printgen(int);
void printboard(FILE *);
void printinfo(FILE *);

int main()
{
    int initial[SZ][SZ];
    int x, y, g;
    int xmin=SZ, xmax=0, ymin=SZ, ymax=0;
    char ch;
    int tofile;
    FILE *fi;

#if Profilea
    if(ProfilerInit(collectDetailed, bestTimeBase, 50, 10))
    {
        printf("Error: ProfilerInit().\n");
        return 1;
    }
#endif

    //Use this commented-out code to print out a catalyst and check that
    //it is correct:
    /*for (y=0; y<cata[6].y; y++)
    {
       for (x=0; x<cata[6].x; x++)
          printf("%c", cata[6].c[x][y]);
       printf("\n");
    }
    if(1)return 0;*/

    for (x=0; x<SZ; x++)
        for (y=0; y<SZ; y++)
        {
            initial[x][y]=0;
            boardgen0[x][y]=0;
            fixed[x][y]=0;

            for (g=0; g<MAXGENS; g++)
            {
                stack[g].now[x][y]= 1<<0;
                stack[g].history[x][y]= 1<<0;
            }
        }

    for (x=0; x<NCATS; x++)
        catisused[x]=0;

    printf("Print output to file (y/n)? ");
    do
    {
        scanf("%c", &ch);
    }
    while (ch!='n' && ch!='N' && ch!='y' && ch!='Y');

    tofile=((ch=='Y') || (ch=='y'));
    if (tofile)
        fi=fopen("reactions.txt", "w");
    else
        fi=stdout;

    printf("\nPlease enter the pattern. Use ' ' or '.' for regular dead cells,\n"
           "',' for fixed dead cells, '*' for fixed live cells, and any other \n"
           "character for regular live cells. Finish the pattern with '!':\n");

    //Read the pattern entered by the user and store it in initial[][].
    //Set the fixed cells in fixed[][]:
    x=3;
    y=3;
    char c;
    while ((c=getchar())!='!')
    {
        if (c == '\n')
        {
            x=3;
            y++;
            continue;
        }

        if (c != ' ' && c != '.')
        {
            if (x>=SZ-3)
            {
                printf("Error: Pattern too wide.\n");
                return 1;
            }
            if (y>=SZ-3)
            {
                printf("Error: Pattern too tall.\n");
                return 1;
            }

            if (c == ',')
                initial[x][y]=1; //Fixed dead
            else if (c == '*')
                initial[x][y]=2; //Fixed live
            else
                initial[x][y]=3; //Live

            if (x<xmin) xmin=x;
            if (x>xmax) xmax=x;
            if (y<ymin) ymin=y;
            if (y>ymax) ymax=y;
        }

        x++;
    }

    //Initialize fixed[][], stack[0], and boardgen0[][],
    //centering the pattern in the middle of the board:
    int xoffset=(SZ-xmax-xmin-2)/2, yoffset=(SZ-ymax-ymin-2)/2;
    for (x=xmin-1; x<=xmax+1; x++)
        for (y=ymin-1; y<=ymax+1; y++)
        {
            stack[0].now[x+xoffset][y+yoffset]=0;

            if (initial[x][y]>1) //2 or 3, which is alive
            {
                stack[0].now[x+xoffset][y+yoffset]=LiveBit;
                //Little hack so that things work properly:
                stack[0].history[x+xoffset][y+yoffset] = 1<<3;

                boardgen0[x+xoffset][y+yoffset]=1;
            }

            if (initial[x][y]==1 || initial[x][y]==2) //Fixed
                fixed[x+xoffset][y+yoffset]=1;

            //Count the neighbors:
            int count=(initial[x-1][y-1]>1) + (initial[x][y-1]>1) + (initial[x+1][y-1]>1)
                      +(initial[x-1][y  ]>1)                       + (initial[x+1][y  ]>1)
                      +(initial[x-1][y+1]>1) + (initial[x][y+1]>1) + (initial[x+1][y+1]>1);

            if (count<0 || count>8)
            {
                printf("Error: count is out of range.\n");
                return 1;
            }

            //Check for inconsistency:
            if ((initial[x][y]==2 && count!=2 && count!=3) ||
                    (initial[x][y]==1 && count==3))
            {
                printf("Error: Inconsistency in the starting pattern.\n");
                return 1;
            }

            //Set the neighbor count bit:
            stack[0].now[x+xoffset][y+yoffset] |= 1<<count;
        } //for for

    //Set boundary variables:
    stack[0].xmin= g0minx= xmin-1 + xoffset;
    stack[0].xmax= g0maxx= xmax+1 + xoffset;
    stack[0].ymin= g0miny= ymin-1 + yoffset;
    stack[0].ymax= g0maxy= ymax+1 + yoffset;

    stack[0].numcats=0;

    //Repeat the initial pattern to the user:
    printf("\nYou entered:\n");
    if (tofile)
        fprintf(fi, "Initial pattern:\n");
    for (y=ymin; y<=ymax; y++)
    {
        for (x=xmin; x<=xmax; x++)
        {
            switch (initial[x][y])
            {
            case 0:
                ch='.';
                break;
            case 1:
                ch=',';
                break;
            case 2:
                ch='*';
                break;
            case 3:
                ch='o';
                break;
            }
            printf("%c", ch);
            if (tofile)
                fprintf(fi, "%c", ch);
        }
        printf("\n");
        if (tofile)
            fprintf(fi, "\n");
    }

    printf("\nCustomize which catalysts to use (y/n)? ");
    do
    {
        scanf("%c", &ch);
    }
    while (ch!='n' && ch!='N' && ch!='y' && ch!='Y');

    if ((ch=='Y') || (ch=='y'))
    {
        printf("These are the available catalysts:\n");
        for (x=0; x<NCATS; x++)
            printf("%2d: %c%c%c%c\n", x+1, cata[x].name>>24, cata[x].name>>16,
                   cata[x].name>>8, cata[x].name);
        do
        {
            printf("Enter a number from the above list, or 0 to finish: ");
            scanf("%d", &x);
            if (x==0)
                break;
            if (x>NCATS || x<0)
            {
                printf("Invalid number.\n");
                continue;
            }
            x--;
            catisused[x]=1;
            printf("%c%c%c%c selected.\n", cata[x].name>>24, cata[x].name>>16,
                   cata[x].name>>8, cata[x].name);
        }
        while(1);
    }
    else
        for (x=0; x<NCATS; x++)
            catisused[x]=1;

    if (tofile)
    {
        fprintf(fi, "\nCatalysts to use:\n");
        for (x=0; x<NCATS; x++)
            if (catisused[x])
                fprintf(fi, "%c%c%c%c\n", cata[x].name>>24, cata[x].name>>16,
                        cata[x].name>>8, cata[x].name);
    }

    printf("\nEarliest generation for placing catalysts? ");
    scanf("%d", &startinggen);

    printf("Latest generation for placing catalysts? ");
    scanf("%d", &gens);

    if (tofile)
        fprintf(fi, "\nGenerations for placing catalysts: %d through %d.\n",
                startinggen, gens);

    printf("How many generations must a catalyst survive? ");
    scanf("%d", &catsurvive);

    gens += catsurvive;
    if (gens>=MAXGENS)
    {
        printf("Error: %d exceeds the maximum number of generations, which is %d.\n",
               gens, MAXGENS-1);
        return 1;
    }

    printf("Maximum number of catalysts? ");
    scanf("%d", &catstoplace);
    if (catstoplace>MAXCATS)
    {
        printf("Error: %d exceeds the maximum number of catalysts, which is %d.\n",
               catstoplace, MAXCATS);
        return 1;
    }

    /* The purpose of this option was to allow the user to restrict the number of
    catalysts that can be placed in one generation, in order to reduce the
    huge number of possibilities that occur when catstoplace has a large value.
    However, searching with a large value of catstoplace is inconvenient in any
    case. Therefore, I deactivated this option but still left it in the code.
    To re-activate it, un-comment this code and remove the line
    "catspergen=catstoplace;":
    */
    /*printf("Maximum number of catalysts in one generation? ");
    scanf("%d", &catspergen);*/
    catspergen=catstoplace;


    printf("\n");

    if (tofile)
    {
        fprintf(fi, "Catalysts must survive %d generation%s.\n", catsurvive,
                catsurvive==1?"":"s");

        /*fprintf(fi, "%d catalysts maximum (%d maximum in one generation).\n\n",
           catstoplace, catspergen);*/
        fprintf(fi, "%d catalyst%s maximum.\n\n", catstoplace,
                catstoplace==1?"":"s");
    }

    currgen=0;
    currx=0;
    curry=0;
    currcatn=0;
    currorient=0;

    int numprinted=0;

    //Main loop:
    while(currgen>=0)
    {
        //Place another catalyst at this generation
        //until you can no more.
        if (currgen >= startinggen && currgen+catsurvive <= gens)
            while (nCatsTotal < catstoplace &&
                    stack[currgen].numcats < catspergen &&
                    placecatalyst())
            { }

        if (currgen==gens)
        {
            fprintf(fi, "Pattern # %d:\n", ++numprinted);
            printboard(fi);
            printinfo(fi);

            if (removelastcat())
                break; //Finished. Out of main loop.

            //Increment the current position:
            currx++;
            continue;
        }

        //Advance 1 generation.
        if (advance1gen())
        {
            if (nCatsTotal==0 ||
                    currgen-catplaced[nCatsTotal-1].gen>=catsurvive)
            {
                fprintf(fi, "Pattern # %d:\n", ++numprinted);
                printboard(fi);
                printinfo(fi);
            }

            if (removelastcat())
                break; //Finished. Out of main loop.

            //Increment the current position:
            currx++;
        }

        if (callcount%1000==0)
        {
            printf("%d calls to advance1gen().\n", callcount);
            printinfo(stdout);
            if (tofile)
            {
                fprintf(fi, "%d calls to advance1gen().\n", callcount);
                printinfo(fi);
            }
        }
    }

    printf("The end.\n%d call%s to advance1gen()\n"
           "%d pattern%s printed.\n", callcount, callcount==1?"":"s",
           numprinted, numprinted==1?"":"s");
    if (tofile)
        fprintf(fi, "The end.\n%d call%s to advance1gen()\n"
                "%d pattern%s printed.\n", callcount, callcount==1?"":"s",
                numprinted, numprinted==1?"":"s");

#if Profilea
    ProfilerDump("\pprofile");
    ProfilerTerm();
#endif

    return 0;
} //main()

/* This function advances the pattern 1 generation and checks that nothing
of this occurs:
- A 'fixed' cell changes
- The pattern reaches the edge of the board

If one of these occurs the function returns 1.
*/
int advance1gen(void)
{
    int x, y;

    callcount++;

    if (currgen==MAXGENS)
    {
        printf("Error in advance1gen(): Too many generations.\n");
        exit(1);
    }

    if (stack[currgen].xmin<=1 || stack[currgen].xmax>= SZ-2 ||
            stack[currgen].ymin<=1 || stack[currgen].ymax>= SZ-2)
        return 1; //Edge of the board reached.

    stack[currgen+1].xmin=SZ;
    stack[currgen+1].xmax=0;
    stack[currgen+1].ymin=SZ;
    stack[currgen+1].ymax=0;

    //We have to clear additional space around the pattern because it may
    //contain junk from before, and the function placecatalyst() sometimes
    //expands the boundaries without clearing.
    int xstart=stack[currgen].xmin-1-CATSZ,
        ystart=stack[currgen].ymin-1-CATSZ;
    if (xstart<1) xstart=1;
    if (ystart<1) ystart=1;
    for (x=xstart; x<=stack[currgen].xmax+1+CATSZ && x<SZ-1; x++)
        for (y=ystart; y<=stack[currgen].ymax+1+CATSZ && y<SZ-1; y++)
        {
            if (x<stack[currgen].xmin-1 || x>stack[currgen].xmax+1 ||
                    y<stack[currgen].ymin-1 || y>stack[currgen].ymax+1)
            {
                stack[currgen+1].now[x][y]= 1<<0;
                stack[currgen+1].history[x][y]= 1<<0;
                continue;
            }

            //Set the cell itself's next generation:
            if(WillLive(stack[currgen].now[x][y]))
                stack[currgen+1].now[x][y] = LiveBit;
            else
                stack[currgen+1].now[x][y] = 0;

            //Count number of the live neighbors the cell will have the next
            //generation:
            int count=0;
            if (WillLive(stack[currgen].now[x-1][y-1])) count++;
            if (WillLive(stack[currgen].now[x-1][y  ])) count++;
            if (WillLive(stack[currgen].now[x-1][y+1])) count++;
            if (WillLive(stack[currgen].now[x  ][y-1])) count++;
            if (WillLive(stack[currgen].now[x  ][y+1])) count++;
            if (WillLive(stack[currgen].now[x+1][y-1])) count++;
            if (WillLive(stack[currgen].now[x+1][y  ])) count++;
            if (WillLive(stack[currgen].now[x+1][y+1])) count++;

            //If it's a fixed cell, check that it will not change 2 generations
            //from now. We assume that it has already been checked that it will
            //not change next generation:
            if (fixed[x][y] &&
                    (((stack[currgen].now[x][y] & LiveBit) && count!=2 && count!=3) ||
                     ((stack[currgen].now[x][y] & LiveBit)==0 && count==3)))
                return 1;

            //Set the cell's count bit:
            stack[currgen+1].now[x][y] |= 1<<count;

            //Also set the next generation's history board:
            stack[currgen+1].history[x][y] = stack[currgen].history[x][y] |
                                             stack[currgen].now[x][y];

            //Adjust next gen's boundary variables if necessary.
            //Note that the pattern's boundaries will never become smaller than
            //in a previous generation, because of history[][]:
            if ((stack[currgen+1].now[x][y] & (~1)) ||
                    (stack[currgen+1].history[x][y] & (~1)))
            {
                if (x < stack[currgen+1].xmin) stack[currgen+1].xmin=x;
                if (x > stack[currgen+1].xmax) stack[currgen+1].xmax=x;
                if (y < stack[currgen+1].ymin) stack[currgen+1].ymin=y;
                if (y > stack[currgen+1].ymax) stack[currgen+1].ymax=y;
            }
        } //for for

    currgen++;
    currx=curry=currcatn=currorient=0;
    return 0;
} //advance1gen()

/* This function looks for a place to place a catalyst on this generation's
board, starting from the position specified by the globals currx, curry,
currorient, and currcatn, and going ahead. It makes sure that the
catalyst would not have reacted at any previous generation. It also makes
sure that the catalyst will react now, i.e. next generation.
*/
int placecatalyst()
{
    int catszx, catszy;
    char catcell;

    while (currcatn<NCATS)
    {
        //Skip this catalyst if it is deactivated:
        if (!catisused[currcatn])
        {
            currorient=0;
            currcatn++;
            continue;
        }

        while (currorient<8)
        {
            //Skip some orientations for symmetric patterns:
            if (cata[currcatn].name=='eat2')
                if (currorient>=4)
                    break;
            if (cata[currcatn].name=='bloc' || cata[currcatn].name=='_tub')
                if (currorient==1 || currorient==3 || currorient==5 || currorient==7)
                {
                    curry=0;
                    currorient++;
                    continue;
                }

            if (currorient<4)
            {
                catszy=cata[currcatn].y;
                catszx=cata[currcatn].x;
            }
            else
            {
                catszy=cata[currcatn].x;
                catszx=cata[currcatn].y;
            }
            if (curry<stack[currgen].ymin - catszy)
                curry=stack[currgen].ymin - catszy;

            while (curry<SZ-catszy && curry<=stack[currgen].ymax + catszy)
            {
                if (currx<stack[currgen].xmin - catszx)
                    currx=stack[currgen].xmin - catszx;

                while (currx<SZ-catszx && currx<=stack[currgen].xmax + catszx)
                {
                    int x, y, reacts=0, isgood=1;

                    //Check the catalyst in this position cell by cell:
                    for (x=0; x<catszx && isgood; x++)
                        for (y=0; y<catszy && isgood; y++)
                        {
                            //Select the cell according to the orientation:
                            if      (currorient==0) catcell=cata[currcatn].c[         x][         y];
                            else if (currorient==1) catcell=cata[currcatn].c[catszx-1-x][         y];
                            else if (currorient==2) catcell=cata[currcatn].c[         x][catszy-1-y];
                            else if (currorient==3) catcell=cata[currcatn].c[catszx-1-x][catszy-1-y];
                            else if (currorient==4) catcell=cata[currcatn].c[         y][         x];
                            else if (currorient==5) catcell=cata[currcatn].c[catszy-1-y][         x];
                            else if (currorient==6) catcell=cata[currcatn].c[         y][catszx-1-x];
                            else                    catcell=cata[currcatn].c[catszy-1-y][catszx-1-x];

                            if (catcell=='o' || catcell=='*')
                                if ((stack[currgen].history[currx+x][curry+y] != 1<<0) ||
                                        (fixed[currx+x][curry+y] > 0))
                                {
                                    isgood=0;
                                    continue;
                                }

                            if (catcell=='.' || catcell=='1' || catcell=='x')
                                if (stack[currgen].history[currx+x][curry+y] &
                                        (LiveBit | (1<<2) | (1<<3)))
                                {
                                    isgood=0;
                                    continue;
                                }

                            if (catcell=='$' || catcell=='%' || catcell=='^')
                                if (stack[currgen].history[currx+x][curry+y] & LiveBit)
                                {
                                    isgood=0;
                                    continue;
                                }

                            if (catcell==':' || catcell=='2' || catcell=='X')
                                if (stack[currgen].history[currx+x][curry+y] &
                                        (LiveBit | (1<<1) | (1<<3)))
                                {
                                    isgood=0;
                                    continue;
                                }

                            if (catcell=='1')
                                if ((stack[currgen].now[currx+x][curry+y] & CountBitMask) == (1<<2))
                                    reacts=1;

                            if (catcell=='2')
                                if ((stack[currgen].now[currx+x][curry+y] & CountBitMask) == (1<<1))
                                    reacts=1;

                            if (catcell=='x')
                                if ((stack[currgen].now[currx+x][curry+y] & CountBitMask) == (1<<2))
                                {
                                    isgood=0;
                                    continue;
                                }

                            if (catcell=='X')
                                if ((stack[currgen].now[currx+x][curry+y] & CountBitMask) == (1<<1))
                                {
                                    isgood=0;
                                    continue;
                                }

                            //Reject also if the catalyst will cause a birth in a fixed cell:
                            if (fixed[currx+x][curry+y] && (catcell=='.' || catcell=='1') &&
                                    (stack[currgen].now[currx+x][curry+y] & CountBitMask) == (1<<2))
                            {
                                isgood=0;
                                continue;
                            }

                            if (fixed[currx+x][curry+y] && (catcell==':' || catcell=='2') &&
                                    (stack[currgen].now[currx+x][curry+y] & CountBitMask) == (1<<1))
                            {
                                isgood=0;
                                continue;
                            }
                        } //for for

                    if (isgood && reacts)
                    {
                        //Save the current values of the boundary variables:
                        catplaced[nCatsTotal].oldxmin=stack[currgen].xmin;
                        catplaced[nCatsTotal].oldxmax=stack[currgen].xmax;
                        catplaced[nCatsTotal].oldymin=stack[currgen].ymin;
                        catplaced[nCatsTotal].oldymax=stack[currgen].ymax;
                        //Save the current boundaries of boardgen0[][]:
                        catplaced[nCatsTotal].g0oldminx=g0minx;
                        catplaced[nCatsTotal].g0oldminy=g0miny;
                        catplaced[nCatsTotal].g0oldmaxx=g0maxx;
                        catplaced[nCatsTotal].g0oldmaxy=g0maxy;

                        //Place the catalyst on the board.
                        //Also, modify the history board as if the
                        //catalyst was always there.
                        //Also place the catalyst on boardgen0[][]:
                        for (x=0; x<catszx; x++)
                            for (y=0; y<catszy; y++)
                            {
                                if      (currorient==0) catcell=cata[currcatn].c[         x][         y];
                                else if (currorient==1) catcell=cata[currcatn].c[catszx-1-x][         y];
                                else if (currorient==2) catcell=cata[currcatn].c[         x][catszy-1-y];
                                else if (currorient==3) catcell=cata[currcatn].c[catszx-1-x][catszy-1-y];
                                else if (currorient==4) catcell=cata[currcatn].c[         y][         x];
                                else if (currorient==5) catcell=cata[currcatn].c[catszy-1-y][         x];
                                else if (currorient==6) catcell=cata[currcatn].c[         y][catszx-1-x];
                                else                    catcell=cata[currcatn].c[catszy-1-y][catszx-1-x];

                                //Adjust now[][],  history[][], and boardgen0[][]:
                                if (catcell=='o')
                                {
                                    stack[currgen].now[currx+x][curry+y]=LiveBit+(1<<3);
                                    stack[currgen].history[currx+x][curry+y]=LiveBit+(1<<3);
                                    boardgen0[currx+x][curry+y]=2;
                                }
                                //It doesn't necessarily have 3 neighbors, but it doesn't matter.

                                if (catcell=='*')
                                {
                                    stack[currgen].now[currx+x][curry+y]=LiveBit+(1<<3);
                                    stack[currgen].history[currx+x][curry+y]=LiveBit+(1<<3);
                                    boardgen0[currx+x][curry+y]=2;
                                    fixed[currx+x][curry+y]++;
                                }

                                //Adjust the boundaries of boardgen0[][]:
                                if (catcell=='o' || catcell=='*' || catcell=='x' || catcell=='X')
                                {
                                    if (currx+x < g0minx) g0minx=currx+x;
                                    if (currx+x > g0maxx) g0maxx=currx+x;
                                    if (curry+y < g0miny) g0miny=curry+y;
                                    if (curry+y > g0maxy) g0maxy=curry+y;
                                }

                                if (catcell=='.' || catcell=='1' || catcell=='x')
                                {
                                    stack[currgen].now[currx+x][curry+y] <<= 1;
                                    stack[currgen].history[currx+x][curry+y] <<= 1;
                                }

                                if (catcell==':' || catcell=='2' || catcell=='X')
                                {
                                    stack[currgen].now[currx+x][curry+y] <<= 2;
                                    stack[currgen].history[currx+x][curry+y] <<= 2;
                                }

                                if (catcell=='$')
                                {
                                    stack[currgen].now[currx+x][curry+y] <<= 4;
                                    stack[currgen].history[currx+x][curry+y] <<= 4;
                                }

                                if (catcell=='%')
                                {
                                    stack[currgen].now[currx+x][curry+y] <<= 5;
                                    stack[currgen].history[currx+x][curry+y] <<= 5;
                                }

                                if (catcell=='^')
                                {
                                    stack[currgen].now[currx+x][curry+y] <<= 6;
                                    stack[currgen].history[currx+x][curry+y] <<= 6;
                                }

                                if (catcell=='x' || catcell=='X')
                                    fixed[currx+x][curry+y]++;

                                //Adjust the boundary variables if necessary:
                                if (catcell != ' ')
                                {
                                    if (currx+x < stack[currgen].xmin)
                                        stack[currgen].xmin=currx+x;
                                    if (currx+x > stack[currgen].xmax)
                                        stack[currgen].xmax=currx+x;
                                    if (curry+y < stack[currgen].ymin)
                                        stack[currgen].ymin=curry+y;
                                    if (curry+y > stack[currgen].ymax)
                                        stack[currgen].ymax=curry+y;
                                }
                            } //for for

                        //Record the placement:
                        catplaced[nCatsTotal].x=currx;
                        catplaced[nCatsTotal].y=curry;
                        catplaced[nCatsTotal].n=currcatn;
                        catplaced[nCatsTotal].orient=currorient;
                        catplaced[nCatsTotal].gen=currgen;
                        nCatsTotal++;
                        stack[currgen].numcats++;

                        return 1;
                    } //isgood && reacts
                    currx++;
                } //while currx
                currx=0;
                curry++;
            } //while curry
            curry=0;
            currorient++;
        } //while currorient
        currorient=0;
        currcatn++;
    } //while currcatn
    return 0; //No way to place a catalyst
} //placecatalyst()

/* This function removes the last catalyst that was placed, according to
the array catplaced[]. It backs up to the generation when that catalyst
was placed. It returns 1 if there are no catalysts to remove.
*/
int removelastcat()
{
    if (nCatsTotal==0)
        return 1;
    nCatsTotal--;

    currgen=catplaced[nCatsTotal].gen;
    currx=catplaced[nCatsTotal].x;
    curry=catplaced[nCatsTotal].y;
    currcatn=catplaced[nCatsTotal].n;
    currorient=catplaced[nCatsTotal].orient;

    stack[currgen].numcats--;

    int catszx, catszy, x, y;
    char catcell;

    if (currorient<4)
    {
        catszy=cata[currcatn].y;
        catszx=cata[currcatn].x;
    }
    else
    {
        catszy=cata[currcatn].x;
        catszx=cata[currcatn].y;
    }

    //Undo the placement of the catalyst, by restoring the values of
    //new[][] and history[][].
    //Also, remove the catalyst from boardgen0[][]:
    for (x=0; x<catszx; x++)
        for (y=0; y<catszy; y++)
        {
            int newhist=0;

            if      (currorient==0) catcell=cata[currcatn].c[         x][         y];
            else if (currorient==1) catcell=cata[currcatn].c[catszx-1-x][         y];
            else if (currorient==2) catcell=cata[currcatn].c[         x][catszy-1-y];
            else if (currorient==3) catcell=cata[currcatn].c[catszx-1-x][catszy-1-y];
            else if (currorient==4) catcell=cata[currcatn].c[         y][         x];
            else if (currorient==5) catcell=cata[currcatn].c[catszy-1-y][         x];
            else if (currorient==6) catcell=cata[currcatn].c[         y][catszx-1-x];
            else                    catcell=cata[currcatn].c[catszy-1-y][catszx-1-x];

            if (catcell=='o' || catcell=='*')
            {
                stack[currgen].now[currx+x][curry+y]= 1<<0;
                stack[currgen].history[currx+x][curry+y]= 1<<0;
                boardgen0[currx+x][curry+y]=0;
            }

            if (catcell=='*')
            {
                stack[currgen].now[currx+x][curry+y]= 1<<0;
                stack[currgen].history[currx+x][curry+y]= 1<<0;
                boardgen0[currx+x][curry+y]=0;
                fixed[currx+x][curry+y]--;
                if (fixed[currx+x][curry+y]<0)
                {
                    printf("Error 1 in removelastcat(): fixed[%d][%d] < 0.\n",
                           currx+x, curry+y);
                    exit(1);
                }
            }

            if (catcell=='x' || catcell=='X')
            {
                fixed[currx+x][curry+y]--;
                if (fixed[currx+x][curry+y]<0)
                {
                    printf("Error 2 in removelastcat(): fixed[%d][%d] < 0.\n",
                           currx+x, curry+y);
                    exit(1);
                }
            }

            if (catcell=='.' || catcell=='1' || catcell=='x')
            {
                stack[currgen].now[currx+x][curry+y] >>= 1;
                stack[currgen].history[currx+x][curry+y] >>= 1;
            }

            if (catcell==':' || catcell=='2' || catcell=='X')
            {
                stack[currgen].now[currx+x][curry+y] >>= 2;
                stack[currgen].history[currx+x][curry+y] >>= 2;
            }

            if (catcell=='$')
            {
                stack[currgen].now[currx+x][curry+y] >>= 4;
                stack[currgen].history[currx+x][curry+y] >>= 4;
            }

            if (catcell=='%')
            {
                stack[currgen].now[currx+x][curry+y] >>= 5;
                stack[currgen].history[currx+x][curry+y] >>= 5;
            }

            if (catcell=='^')
            {
                stack[currgen].now[currx+x][curry+y] >>= 6;
                stack[currgen].history[currx+x][curry+y] >>= 6;
            }
        } //for for

    //Restore the boundary variables:
    stack[currgen].xmin=catplaced[nCatsTotal].oldxmin;
    stack[currgen].xmax=catplaced[nCatsTotal].oldxmax;
    stack[currgen].ymin=catplaced[nCatsTotal].oldymin;
    stack[currgen].ymax=catplaced[nCatsTotal].oldymax;
    //Restore boardgen0[][]'s boundaries:
    g0minx=catplaced[nCatsTotal].g0oldminx;
    g0miny=catplaced[nCatsTotal].g0oldminy;
    g0maxx=catplaced[nCatsTotal].g0oldmaxx;
    g0maxy=catplaced[nCatsTotal].g0oldmaxy;

    return 0;
} //removelastcat()

void printgen(int mode)
{

    int x, y,n;

    for (y=stack[currgen].ymin; y<=stack[currgen].ymax; y++)
    {
        for (x=stack[currgen].xmin; x<=stack[currgen].xmax; x++)
            if (mode==0)
            {
                if (stack[currgen].now[x][y] & LiveBit)
                    if (fixed[x][y]) printf("*");
                    else printf("o");
                else if (fixed[x][y]) printf(",");
                else printf(".");
            }
            else
                printf("%4d", stack[currgen].history[x][y]);
        printf("\n");
    }
    printf("Catalysts placed at gens:");
    for (n=0; n<nCatsTotal; n++)
        printf(" %d", catplaced[n].gen);
    printf("\nGeneration %d\n   -----\n", currgen);
} //printgen()

void printboard(FILE *f)
{
    int x, y;

    for (y=g0miny; y<=g0maxy; y++)
    {
        for (x=g0minx; x<=g0maxx; x++)
            //Fix this:
            if (boardgen0[x][y])
                if (fixed[x][y]) fprintf(f, "*");
                else fprintf(f, "o");
            else if (fixed[x][y]) fprintf(f, ",");
            else fprintf(f, ".");

        fprintf(f, "\n");
    }
} //printboard()

void printinfo(FILE *f)
{
    int n;

    fprintf(f, "%d catalyst%s", nCatsTotal, nCatsTotal==1?"":"s");
    if (nCatsTotal>0)
    {
        fprintf(f, ", which react%s", nCatsTotal==1 ? "s at gen." : " at gens.:");
        for (n=0; n<nCatsTotal; n++)
            fprintf(f, " %d", catplaced[n].gen);
    }
    else
        fprintf(f, ".");
    fprintf(f, "\nGeneration reached: %d\n   -----\n", currgen);
} //printinfo()


So the next improvements would be:

1. Parameter for stability of the system as a whole (catalyst might survive 3 generations, but after adding another catalyst it might survive 10 - this improvement should be included).

2. The utility has a bug giving false positives. Like it never really works for tubs. It's also should not place catalyst on path of the input glider.

3. The patterns that return the initial block to it's place or somewhere near (like semi snark) should be recognized and placed in separate output file (or in the current file but in the beginning)

4. Evaluation function should be introduced placing the better patterns first.

5. Output should be in rle format

6. Multi-thread and x64 optimization should be included.

7. Python GUI should be added and deeper search using GUI support should be allowed.

8. There is still small optimizations left: take into account the amount of influence of the catalyst on the pattern. Include catalysts that don't change themselves but still influence the reaction (like the tub in semi snark).

EDIT2 By the way I'm a really big fun of human-computer cooperation. If we take a look at the best chess player today, it's not a computer and not human - it's human that knows how to use chess engine smarter than other humans. But in LIfe search utilities, we currently far away from even the weakest chess engines - so a lot of space to improve there. But yes certainly, the human factor is hard to replace, and even if engines perform better than any human, an engine + human will perform even better, no doubt. I just hope that engines will do the dumb work themselves, living to human to make a much more subtle decisions that engines are incapable to make.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby simsim314 » May 7th, 2014, 9:22 am

Here is a way to "slow salvo" 180 degree reflector 2G->G with 6 spartan components. This is by far the best 180 degree spartan reflector, for "high cost" 180 degree reflection purposes (i.e. where for some reason a minimalist 180 degree reflector is needed instead of heavy silver).

x = 152, y = 146, rule = LifeHistory
19.2A$19.A$17.A.A$17.2A$28.2A$28.A$26.A.A$26.2A4$37.2A$37.A$2.2A31.A.
A$.A.A31.2A$.A$2A15.2A2.2A$17.2A.2A$22.A10$24.2A$24.2A8$44.2A$43.2A$
45.A3$48.A$47.2A$47.A.A19$71.A$70.2A$70.A.A4$74.2A$73.2A$75.A19$97.2A
$96.2A$98.A3$101.A$100.2A$100.A.A19$124.A$123.2A$123.A.A4$127.2A$126.
2A$128.A19$150.2A$149.2A$151.A!


It's recovery is only 106 ticks.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby dvgrn » May 7th, 2014, 5:39 pm

simsim314 wrote:Here is a way to "slow salvo" 180 degree reflector 2G->G with 6 spartan components. This is by far the best 180 degree spartan reflector, for "high cost" 180 degree reflection purposes (i.e. where for some reason a minimalist 180 degree reflector is needed instead of heavy silver)... [Its] recovery is only 106 ticks.

That's an unusual variant of an early pattern that Paul Callahan eventually turned into a Herschel receiver. The classic version has the same 6sL count, but one of the eaters is just blocking a glider output:
#C "Glider stopper" used as a 2G->G 180-degree reflector
#C (the beehive can also stop a glider on two 90-degree lanes,
#C   and the rest of the circuitry is transparent to one of those lanes)
x = 42, y = 46, rule = LifeHistory
3.C$3.3C$6.C$5.CD7$28.2A$28.A$26.A.A$26.2A4$37.2A$2.2A33.A$.A.A31.A.A
$.A33.2A$2A$17.2A2.2A$17.2A.2A$22.A10$24.2A$24.2A8$40.2A$39.2A$41.A!

The only downside to these things is that the return glider is so close to the input stream that it's fairly expensive to build another circuit that can get hold of the return signal and do anything with it. You can start the input stream with an edge shooter, of course, but even then you have to put your next piece of circuitry way back before the input stream source.

The source circuitry tends to be overly complicated anyway because you have to merge two edge-shooters to get the required glider pairs. Somewhere in here, the extra 12sL for a full Silver reflector generally starts looking like a real bargain...!
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Technological Challenges

Postby simsim314 » May 8th, 2014, 6:46 am

dvgrn wrote:Somewhere in here, the extra 12sL for a full Silver reflector generally starts looking like a real bargain...!


Hmm.. I was thinking of dried salvo 180-degree reflector, where each SL is actually pretty expensive. We have currently three options:

1. 4G slow salvo + 2 dried Semi Snarks (12 SLs). That can return gliders at any distance.
2. 4G timed + 1G + 1 dried block.
3. 2G slow salvo + 6 SLs.
----

Now the two input gliders shouldn't be timed (except of some minimal delay), but they are not on the same lane.

I'm not sure what is the best approach there, but this 2G+6SL looks like an option between a heavy 4G synchronizer and heavy 12SLs dried salvo.

----

This construction can also be used in opposite glider collision designs.It's pretty light weighted, and we need 2G->G component anyway.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Technological Challenges

Postby dvgrn » May 10th, 2014, 1:22 pm

simsim314 wrote:I'm not sure what is the best approach there, but this 2G+6SL looks like an option between a heavy 4G synchronizer and heavy 12SLs dried salvo.

This construction can also be used in opposite glider collision designs.It's pretty light weighted, and we need 2G->G component anyway.

True enough -- I wasn't thinking of the "armless constructor" use.

I just remembered that there's almost a fairly decent way to produce those two gliders, separated by two lanes, using input gliders that are only semi-synchronized:

#C Spartan resettable version of boojum reflector,
#C   with a resettable Spartan rectifier at the right for comparison
#C The boojum reflector needs three asynchronous inputs
#C (or semi-synchronous, any timing within a fairly wide range).
x = 155, y = 78, rule = LifeHistory
2.A$A.A$.2A26$83.A$83.A.A$83.2A67.A$152.A.A$152.2A13$129.A$26.A30.2A
69.A.A$25.A.A29.2A69.A.A$26.A102.A3$31.2A$6.2A23.2A$7.A31.2A$7.A.A29.
A$8.2A27.A.A$4.2A25.2A4.2A$4.2A25.2A$50.2A$50.2A$32.2D85.2A$32.2D34.
2A49.2A$35.2C31.A.A$35.2C33.A66.2A$13.2A2.2A51.2A65.A.A$12.A.A2.2A
120.A$14.A21.2A101.2A$30.2A4.2A70.A$29.A.A27.2A46.A.A$29.A29.A.A45.A
2.A$28.2A31.A46.2A18.2A$36.2A23.2A65.A.A$36.2A92.A$103.2A25.2A$102.A.
A$42.A61.A$10.2A29.A.A$10.2A30.A!

I used the old unmodified 'catalyst' program to find the boojum reflector, but that was back in 2001 -- computers have gotten a lot faster since then, and I never attempted to add other transparent catalysts besides that second block. It's still quite possible that there's a Spartan version out there somewhere (that wouldn't need the third reset glider.)
User avatar
dvgrn
Moderator
 
Posts: 5814
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Next

Return to Patterns

Who is online

Users browsing this forum: No registered users and 5 guests