Moore's law, Schmoore's law

[pcallahan]

After briefly rejoicing that I can now run searches in real time that 20 years ago I used to wait for overnight like a kid watching for Santa Claus, I am now right back where I left off, trying to figure out if I ought to kill a running process to free up CPU for another idea that seems more promising or let it finish in the off chance of finding something really surprising.

Mind you, this is just on a laptop. I have not had a state-of-the-art desktop machine in years. Do I need to put one together? (It's not that much money, but hard to justify the expense in terms of the family budget...)

[Moosey]

After briefly rejoicing that I can now run searches in real time that 20 years ago I used to wait for overnight like a kid watching for Santa Claus, I am now right back where I left off, trying to figure out if I ought to kill a running process to free up CPU for another idea that seems more promising or let it finish in the off choice of finding something really surprising.

Mind you, this is just on a laptop. I have not had a state-of-the-art desktop machine in years. Do I need to put one together? (It's not that much money, but hard to justify the expense in terms of the family budget...)

So, to make sure I’m on the same page:
You’re running gfind or apgsearch or slmake or whatever, and you have another search program that is also running, and you’re wondering if you should terminate the search that you think is less valuable?

Christmas Eve is torture if you know there are gifts downstairs.

[Macbi]

If computing power doubles every 18 months and each additional cell doubles the search space then after 20 years we would expect to find patterns which are 14 cells larger.

[Moosey]

If computing power doubles every 18 months and each additional cell doubles the search space then after 20 years we would expect to find patterns which are 14 cells larger.

Let’s hope the elementary camelships are small. We’ll need to wait a while otherwise. (Of course, if computer power suddenly explodes because of quantum computers or whatever...)
Of course, we could also perhaps find a more efficient algorithm for finding ships or whatever. Depending on how much better the algorithms are, we could in theory find moderately large ships with much less time.

Oh, is there a unit for Ships/sec?

[testitemqlstudop]

If you are on Linux, you can send SIGSTOP / SIGCONT to stop / continue a process. This will save all progress and upon SIGCONT, the program will behave normally. However, this doesn't free up memory.

If computing power doubles every 18 months and each additional cell doubles the search space then after 20 years we would expect to find patterns which are 14 cells larger.

That only applies for brute-force searching.

[pcallahan]

You’re running gfind or apgsearch or slmake or whatever, and you have another search program that is also running, and you’re wondering if you should terminate the search that you think is less valuable?

Actually running some of my own (old) software. In this case, it is gencols doing a final pass to see if any of the stable constellations that don't emit gliders after collisions can do anything else remotely interesting. I have not found anything new and don't really expect to. Boat bit is winning, unsurprisingly, with eater-1 in distant second. I did find many trivial variations of this well-known eater, which I doubt I would have found using the same brute force method 20 years ago.

Code: Select all

x = 11, y = 10, rule = B3/S23
4b2o$4b2o2$2b4o$2bo3bo2b2o$5b2o2b2o2$b2o$obo$2bo!

Also a bunch of collisions (known mechanism) that just attach a beehive to a still life.

Code: Select all

x = 10, y = 11, rule = B3/S23
2bo$bobo$2bobo$3bo2b2o$4b2obo$b3o$o2bo$2o$7b3o$7bo$8bo!

...which gives me some optimism that I can go beyond what I explored earlier. This is kind of a mop-up search to see if I missed anything before cleaning up big files and moving on. I am really more interested in reactions like the glider/biloaf collision. I am not hopeful of finding one, but I don't think the space has been explored to the point where another small instance can be ruled out.

[Moosey]

... I am really more interested in reactions like the glider/biloaf collision. I am not hopeful of finding one, but I don't think the space has been explored to the point where another small instance can be ruled out.

What I’m about to say is going to be a wild tangent.

I once thought of a hypothetical SL with a fairly small (cells):(gliders necessary to synthesize object) ratio (such as a long^(unholy number) barge/boat/ship) that could be struck with a N gliders in order to be displaced (say, split up into gliders that synthesize it again) and to produce the same gliders again, in the same relative positions to the SL, which would make a very unusual engineered ship.

Also, would it be possible to make and engineered ship with a “Reader” that goes along a “snake” of information and moves it one step forward/turns R/L? It would be a concept similar to this rule:

Code: Select all

@RULE CopperHeads2
@TABLE
n_states:9
neighborhood:Moore
symmetries:rotate4reflect

0,0,1,2,1,0,0,0,0,5
0,1,2,2,2,0,0,0,0,1
0,1,7,2,2,0,0,0,0,1
0,1,2,7,2,0,0,0,0,1
0,1,7,7,2,0,0,0,0,1
0,1,2,2,7,0,0,0,0,1
0,1,7,2,7,0,0,0,0,1
0,1,2,7,7,0,0,0,0,1
0,1,7,7,7,0,0,0,0,1
0,1,2,2,0,0,0,0,0,1
0,1,7,2,0,0,0,0,0,1
0,1,2,7,0,0,0,0,0,1
0,1,7,7,0,0,0,0,0,1
0,1,2,2,4,0,0,0,0,1
0,1,7,2,4,0,0,0,0,1
0,1,2,7,4,0,0,0,0,1
0,1,7,7,4,0,0,0,0,1
1,0,2,2,2,3,0,0,0,3
1,0,7,2,2,3,0,0,0,3
1,0,2,7,2,3,0,0,0,3
1,0,7,7,2,3,0,0,0,3
1,0,2,2,7,3,0,0,0,3
1,0,7,2,7,3,0,0,0,3
1,0,2,7,7,3,0,0,0,3
1,0,7,7,7,3,0,0,0,3
3,1,2,2,2,0,0,0,0,0
3,1,7,2,2,0,0,0,0,0
3,1,2,7,2,0,0,0,0,0
3,1,7,7,2,0,0,0,0,0
3,1,2,2,7,0,0,0,0,0
3,1,7,2,7,0,0,0,0,0
3,1,2,7,7,0,0,0,0,0
3,1,7,7,7,0,0,0,0,0
1,0,5,2,2,0,0,0,0,3
1,0,5,7,2,0,0,0,0,3
1,0,5,2,7,0,0,0,0,3
1,0,5,7,7,0,0,0,0,3
5,0,1,2,1,0,0,0,0,2
5,0,1,7,1,0,0,0,0,2
4,0,1,2,1,0,0,0,0,0
4,0,1,7,1,0,0,0,0,0
2,4,0,1,3,2,3,1,0,4
7,4,0,1,3,2,3,1,0,4
7,4,0,6,3,2,3,1,0,4
2,4,0,1,3,7,3,1,0,4
2,4,0,6,3,7,3,1,0,4
7,4,0,1,3,7,3,1,0,4
7,4,0,6,3,7,3,1,0,4
0,2,4,1,0,0,0,0,2,1
0,7,4,1,0,0,0,0,2,1
0,2,4,1,0,0,0,0,7,1
0,7,4,1,0,0,0,0,7,1
1,3,4,2,2,0,0,0,0,3
1,3,4,7,2,0,0,0,0,3
1,3,4,2,7,0,0,0,0,3
1,3,4,7,7,0,0,0,0,3
3,1,2,4,0,0,0,0,0,0
3,1,7,4,0,0,0,0,0,0
1,4,2,0,0,0,0,0,0,3
1,4,7,0,0,0,0,0,0,3
3,1,2,2,4,0,0,0,0,0
3,1,7,2,4,0,0,0,0,0
3,1,2,7,4,0,0,0,0,0
3,1,7,7,4,0,0,0,0,0
6,3,2,2,2,0,0,0,0,3
6,3,7,2,2,0,0,0,0,3
6,3,2,7,2,0,0,0,0,3
6,3,7,7,2,0,0,0,0,3
6,3,2,2,7,0,0,0,0,3
6,3,7,2,7,0,0,0,0,3
6,3,2,7,7,0,0,0,0,3
6,3,7,7,7,0,0,0,0,3
0,6,2,2,2,0,0,0,0,6
0,6,7,2,2,0,0,0,0,6
0,6,2,7,2,0,0,0,0,6
0,6,7,7,2,0,0,0,0,6
0,6,2,2,7,0,0,0,0,6
0,6,7,2,7,0,0,0,0,6
0,6,2,7,7,0,0,0,0,6
0,6,7,7,7,0,0,0,0,6
0,6,2,2,0,0,0,0,0,6
0,6,7,2,0,0,0,0,0,6
0,6,2,7,0,0,0,0,0,6
0,6,7,7,0,0,0,0,0,6
3,3,2,2,2,0,0,0,0,0
3,3,7,2,2,0,0,0,0,0
3,3,2,7,2,0,0,0,0,0
3,3,7,7,2,0,0,0,0,0
3,3,2,2,7,0,0,0,0,0
3,3,7,2,7,0,0,0,0,0
3,3,2,7,7,0,0,0,0,0
3,3,7,7,7,0,0,0,0,0
3,3,2,2,2,3,0,0,0,0
3,3,7,2,2,3,0,0,0,0
3,3,2,7,2,3,0,0,0,0
3,3,7,7,2,3,0,0,0,0
3,3,2,2,7,3,0,0,0,0
3,3,7,2,7,3,0,0,0,0
3,3,2,7,7,3,0,0,0,0
3,3,7,7,7,3,0,0,0,0
3,6,2,2,4,0,0,0,0,0
3,6,7,2,4,0,0,0,0,0
3,6,2,7,4,0,0,0,0,0
3,6,7,7,4,0,0,0,0,0
3,6,2,2,2,0,0,0,0,0
3,6,7,2,2,0,0,0,0,0
3,6,2,7,2,0,0,0,0,0
3,6,7,7,2,0,0,0,0,0
3,6,2,2,7,0,0,0,0,0
3,6,7,2,7,0,0,0,0,0
3,6,2,7,7,0,0,0,0,0
3,6,7,7,7,0,0,0,0,0
3,6,2,2,0,0,0,0,0,0
3,6,7,2,0,0,0,0,0,0
3,6,2,7,0,0,0,0,0,0
3,6,7,7,0,0,0,0,0,0
0,0,6,2,6,0,0,0,0,8
0,0,6,7,6,0,0,0,0,8
6,0,8,7,2,0,0,0,0,3
6,0,8,2,7,0,0,0,0,3
6,0,8,7,7,0,0,0,0,3
6,0,8,2,2,0,0,0,0,3
8,0,6,2,6,0,0,0,0,7
8,0,6,7,6,0,0,0,0,7
3,0,7,2,2,6,0,0,0,0
3,0,7,7,2,6,0,0,0,0
3,0,7,2,7,6,0,0,0,0
3,0,7,7,7,6,0,0,0,0
0,6,2,2,4,0,0,0,0,6
0,6,7,2,4,0,0,0,0,6
0,6,2,7,4,0,0,0,0,6
0,6,7,7,4,0,0,0,0,6
4,0,6,2,6,0,0,0,0,0
4,0,6,7,6,0,0,0,0,0
2,4,0,6,3,2,3,6,0,4
7,4,0,6,3,2,3,6,0,4
6,4,2,0,0,0,0,0,0,3
6,4,7,0,0,0,0,0,0,3
0,6,4,2,2,0,0,0,0,6
0,6,4,7,2,0,0,0,0,6
0,6,4,2,7,0,0,0,0,6
0,6,4,7,7,0,0,0,0,6
6,3,4,2,2,0,0,0,0,3
6,3,4,7,2,0,0,0,0,3
6,3,4,2,7,0,0,0,0,3
6,3,4,7,2,0,0,0,0,3
3,6,2,4,0,0,0,0,0,0
3,6,7,4,0,0,0,0,0,0
6,0,4,2,2,3,0,0,0,1 #special case
6,0,4,2,7,3,0,0,0,1 #special case
1,0,4,7,2,3,0,0,0,6 #special case
1,0,4,7,7,3,0,0,0,6 # special case
0,0,1,7,1,0,0,0,0,5
6,3,4,7,7,0,0,0,0,3

@COLORS
0 48 48 48
1 255 0 0
2 0 255 0
3 255 255 0
4 255 255 255
5 0 0 255
6 255 0 255
7 0 255 255
8 0 100 255

Code: Select all

x = 14, y = 5, rule = CopperHeads2
ABA8.FBF$CBC8.CBC$.B10.B$.B10.B$.D10.D!

(the rule doesn't have turns implemented but I think you get the idea)

anyways, [/verywildtangent]

[pcallahan]

Well, I put in the sandbox for a reason, so wild tangents are fair game. What I'm looking for is something little and natural looking that I can hit repeatedly with gliders circulated by snarks. The problem with stable patterns is that if they block a diagonal, they always block it. I'm gambling that there might be something I could find that was uninteresting before stable reflectors that might seem interesting now. I can also explore larger sets of collisions. But so far, nothing even as promising as this which I reported in 1994.

Code: Select all

x = 81, y = 80
2bo$obo$b2o67$72b2o5b2o$72b2o5b2o5$79b2o$79b2o$67b2o$66bobo$68bo!

[Hdjensofjfnen]

Christmas Eve is torture if you know there are gifts downstairs.

Just sleep. It's like an 8-hour time machine into the future.

[pcallahan]

Christmas Eve is torture if you know there are gifts downstairs.

Just sleep. It's like an 8-hour time machine into the future.

And when you are running 8 hour life searches, every day is Christmas.

(Even if Santa puts coal in your stockings most of the time.)

[wildmyron]

Mind you, this is just on a laptop. I have not had a state-of-the-art desktop machine in years. Do I need to put one together? (It's not that much money, but hard to justify the expense in terms of the family budget...)

It probably depends a bit on the CPU in the laptop, but I think the major consideration here is that Moore's Law is really about transistor density rather than CPU clock speed. For the former it held up pretty well until about five years ago, whereas clock speed reached its limit near 2006. https://cs.stackexchange.com/questions/ ... lock-speed has a nice graph (out of date - only up until 2010) showing the difference. Transistor density is still going up but it's no longer doubling every 2 years. NOTE: I've just learnt that the analogue to Moore's Law for clock frequency is Dennard Scaling.

So for the kind of searching you are doing, newer CPU's don't help much. With modern compilers you might get a bit more performance out of a modern single core due to more complex instruction sets, but only if the compiler is able to translate the operations required into more efficient assembly (hand-waving a lot here). If you have a look at the progression of the performance of apgsearch over the years that Adam has been developing it you will observe that much of the improvement comes from clever algorithm design and judicious use of hand written assembly targeting the SSE and AVX instruction sets. Add in multi-threading and the software can then make use of the larger number of cores in modern processors without having to manually launch multiple jobs (pretty much equivalent in performance in this case because soup searching is embarrassingly parallel). I don't know if there's a nice history of the performance improvements available, but there are some numbers littered through the commit history of the apgsearch project.

I woudn't want to advise you on investing in a new desktop machine or not, but I think it is worthwhile investing time in looking at whether you can adapt your code to use lifelib as a backend for the CGoL pattern evolution. I can't talk much here as most of the code I write is in Golly Python scripts, and even just writing a naive C implementation would likely be much faster, but I can certainly see the potential there.

[pcallahan]

I woudn't want to advise you on investing in a new desktop machine or not, but I think it is worthwhile investing time in looking at whether you can adapt your code to use lifelib as a backend for the CGoL pattern evolution. I can't talk much here as most of the code I write is in Golly Python scripts, and even just writing a naive C implementation would likely be much faster, but I can certainly see the potential there.

Sounds like good advice, though my old C code (particularly in the ptbsearch distribution) is optimized for small, sparse patterns. I haven't benchmarked it against anything more recent so maybe I could do better with lifelib. The only thing is I still know how to use it (or have relearned). I'm also hoping it's just enough outside the mainstream that I will see things missed by more popular tools.

The point I might not have been clear on is that the searches are definitely much faster than they were on my circa 1998 Linux box or the Sun workstations at various universities. How much, I don't know, but the difference is that searches that used to run for a days and fill up my hard drive can be run while I get coffee and I don't worry much about output size.

The problem is that I'm not doing those searches. I am doing things I knew I would not get any resolution on back then. I never tried to dump out all 12x12 <=15 cell still life constellations and crash gliders into them like I'm doing now. But on a faster machine, I'm back to the same point where I am running as much as I can and I have to make decisions about whether to kill a process that I don't expect much from. Moore's law, meet combinatorial explosion. I know who wins this one. (Or Dennard Schmennard, same deal.)

I don't plan to get more powerful hardware, because I should probably drop my renewed Life obsession. But if I did have a dedicated server, I could keep things going and not worry about it affecting anything else.

[wildmyron]

Haha, perhaps I took your question a little too seriously. No worries. I understand the competing demands.

It's been nice to see you and a few of the other Life Enthusiasts from the 90's being active here. Just so you know, I've enjoyed reading your posts and recent explorations, even though I don't comment on most of the topics.

[Goldtiger997]

It's been nice to see you and a few of the other Life Enthusiasts from the 90's being active here. Just so you know, I've enjoyed reading your posts and recent explorations, even though I don't comment on most of the topics.

I second this: I have been enjoying your posts quite a lot too.

[Moosey]

Yes; it’s funny (in a good way) to collaborate with people who worked on that thing you’re collaborating on before you were born, as I’m sure a lot of other forum users closer to my age would agree.

[pcallahan]

Here's an example of something that I was able to get with an overnight run and some filtering. It's not really what I want, but it's low-hanging fruit from my output files.

16 collisions of gliders with still life constellations that produce a clean HWSS. The constellations must fit in a 12x12 box with no more than 15 live cells. I would like to claim that these are the only such collisions with the above constraints, but I have no way to be certain my code is bug-free. Maybe there is a simpler way to verify.

Code: Select all

x = 313, y = 319, rule = B3/S23
bo99bo99bo99bo$2bo99bo99bo99bo$3o97b3o97b3o97b3o5$15b2o97bo101b2o91b2o
$12bo3bo90b2o4bobo101bo91b2o$12b4o90bo2bo4bo102bobo$107bobo108b2o$12b
2o94bo4bo$13bo98bobo99b2o$12bo100bo100bo88bo5b2obo$12b2o201bo86bobo4bo
b2o$213bobo86b2o$213b2o84$bo99bo102bo96bo$2bo99bo102bo96bo$3o97b3o100b
3o94b3o5$13b2o98b2o93bo100b2o$13bobo6bo90bobo84b2o5bobo99bobo$14bo6bob
o90bo6b2o77bobo5bo101bo$21bobo97bo79bo$22bo100bo177b2o$15b2o98b2o5b2o
176bobo4bo$15b2o98b2o183b2o4bobo$307bo$205b2o$205bobo$206bo83$6bo94bo
99bo99bo$7bo94bo99bo99bo$5b3o92b3o97b3o97b3o5$bo8bo99bo95bo104b2o$obo
6bobo92b2o3bobo93bobo93b2o4bo3b2o$bo8b2o93bo4bo95bo94b2o3bobo$103bo
203bobo$103b2o110b2o91bo$4bo96b2o107bo4b2o$3bobo94bobo106bobo$4bobo94b
o108b2o$5bo85$bo104bo94bo105bo$2bo104bo94bo105bo$3o102b3o92b3o103b3o5$
10bo99b2o91bo106bo$9bobo97bobo90bobo104bobo$10b2o97b2o92b2o104b2o2$6b
2o94bo108bo90bo$2o4b2o93bobo106bobo88bobo$o101b2o106b2o90b2o$bo$2o2$
100b2o110b2o86b2o$100b2o110b2o86b2o!

I think that this would have been a job lasting a week or more 20 years ago, and I would have got tired of listening to my Linux box cranking its hard-drive and just killed it. I don't actually know.

Method: (1) use dbell's lifesrc to generate constellations pinned to left row, top column, (2) run some python to collect output into single lines per constellation and find unique patterns at canonical orientation (3) construct glider collisions, not with gencols but with a new python script that keeps the collision at the upper left and orients the pattern. (4) run output through "safestable", some code I wrote along with ptbsearch that looks for num cells, gliders, and spaceships in output.

After that, I have something I can filter with awk. Also, I can pull off the gliders from both the collision target and the collision ash to construct the graph I am really interested in for finding low period collision components.

The HWSS-producing collisions might even be useful. Most of the constellations are truly spartan: common objects with reasonable spacing. However, they are still probably not worth the cost of building just to get an HWSS later on.

And before I forget:

So for the kind of searching you are doing, newer CPU's don't help much.

The fact that I can watch giant patterns running in a browser on my phone suggests to me that something is helping. "Giant" patterns to me anyway, maybe not geminoids but big by 90s standards. At the very least, there is CPU parity between today's handheld devices and the high performance workstations of two decades ago.

[dvgrn]

The constellations must fit in a 12x12 box with no more than 15 live cells. I would like to claim that these are the only such collisions with the above constraints, but I have no way to be certain my code is bug-free. Maybe there is a simpler way to verify.

Can't help much there, except to say that previous HWSS seeds were considered pretty good if they had four or five small still lifes. Now you've reduced that to three.

Another open HWSS seed puzzle is finding a seed that throws an HWSS far enough sideways to reach a lane where other HWSSes can safely pass by the seed constellation. Also the conversion to HWSS has to happen quick enough without too many extraneous sparks, so it can edge-shoot an HWSS contribution to a Caterpillar helix.

The following two seeds are some of the cheapest and best in your 12x12 pop<15 collection, but they'd need seven more lanes of clearance to work in the context of a Caterpillar helix:

Code: Select all

x = 50, y = 49, rule = LifeHistory
.C$2BC$3CB$.4B$2.4B$3.4B$4.5B2.B$2.B.7B2C33B$.2C4BC3B2C35B$.2C.2BCBC
35B6A$5.2BCBC33BA5BA$5.3BC40BA$5.38BA4BA$5.40B2A11$32.B$31.4B$27.8B$
27.8B$27.8B$27.7BCB$26.7BC2B$24.9B3CB$23.14B$24.12B$24.12B$24.13B$24.
6BC8B$24.5BCBC5B2C$26.4BC5BCBC$27.2B.7BC$30.8B$29.6B$30.16B$29.19B$
30.2B2C10B6A$29.2BCBC9BA5BA$30.2BC16BA$31.12BA4BA$31.14B2A!

I think the lack of a cheap HWSS seed is still the sticking point for building Caterpillar's little brother; good-enough LWSS and MWSS seeds showed up in the search for recipes for the Centipede.

The HWSS-producing collisions might even be useful. Most of the constellations are truly spartan: common objects with reasonable spacing. However, they are still probably not worth the cost of building just to get an HWSS later on.

Depends on the application. The next step from Moosey's linear propagator design from this morning would be freeze-dried *WSS salvos similar to the freeze-dried slow glider salvos that we already have. With gliders we have only the choice of two phases per lane, but with *WSSes there are six choices per lane for stable targets, or twelve for p2 targets. The *WSS-slow-salvo search tree should expand quickly enough to find some fairly surprising objects with just a single-digit number of *WSSes.

[wildmyron]

Here's an example of something that I was able to get with an overnight run and some filtering. It's not really what I want, but it's low-hanging fruit from my output files.

16 collisions of gliders with still life constellations that produce a clean HWSS.

<snip results>

Method: (1) use dbell's lifesrc to generate constellations pinned to left row, top column, (2) run some python to collect output into single lines per constellation and find unique patterns at canonical orientation (3) construct glider collisions, not with gencols but with a new python script that keeps the collision at the upper left and orients the pattern. (4) run output through "safestable", some code I wrote along with ptbsearch that looks for num cells, gliders, and spaceships in output.

Part 4) seems the most likely process which could benefit from running with lifelib. Could you clarify something about parts 2) and 3) - Does the transformation to canonical orientation remove rotated and reflected versions of each constellation, and if it does how do you construct the required number of orientations of each constellation in 3)? I suppose that there are few enough constellations with symmetry that you don't lose much time by constructing all eight rotated and reflected versions and discarding the duplicates.

And before I forget:

So for the kind of searching you are doing, newer CPU's don't help much.

The fact that I can watch giant patterns running in a browser on my phone suggests to me that something is helping.

Of course I have to agree with you here. Just to clarify, I was referring to a single core from 5 years ago compared to today - and those into the future. Compared to 20-25 years ago, CPUs of 5-10 years ago have seen enormous benefit from Dennard scaling.

[pcallahan]

Part 4) seems the most likely process which could benefit from running with lifelib.

Yes, but I'd have to change other parts of my approach to use it. In addition, step 4 is also the most optimized part of my code. It is a C implementation that uses a sparse list, bit packing, and table lookup. It also avoids doing a new memory allocation once it has scaled up to what it needs. This code benchmarked well against other approaches the last time I checked (maybe 2004). That doesn't mean it can't be improved, and I'll look into lifelib if I get a chance. I don't think hash life helps, since these are all little, chaotic patterns that usually stabilize pretty fast. I can give a better indication of the scale of the problem, but I need to rerun something first. It looks like generating the collisions is slower than I realized. Not too surprising, since it's Python, but it doesn't do any Life generation. It just manipulates lists of coordinates.

Could you clarify something about parts 2) and 3) - Does the transformation to canonical orientation remove rotated and reflected versions of each constellation, and if it does how do you construct the required number of orientations of each constellation in 3)? I suppose that there are few enough constellations with symmetry that you don't lose much time by constructing all eight rotated and reflected versions and discarding the duplicates.

It duplicates some effort, but it's only a constant factor and not the limiting factor. It creates all 8 possible orientations, whether or not the pattern is symmetrical, converts them to strings, and takes the lexically first string. Then I use sort -u to dedup the strings. This file is input for generating collisions. Because gliders have glide symmetry, it only needs to try 4 orientations of the canonical target. When constructing those orientations, it also dedups the resulting patterns, so it will only try a symmetrical pattern at its distinct orientations. This is an improvement over just using gencols with gliders in four directions and it's easier for me to remove the gliders from collisions using a simple script when they come from the upper left.

Actually, apart from any particular Life algorithm, the biggest improvement would come from doing much of this in RAM and avoiding the giant file dumps of strings. Just converting a pattern back and forth from a string is way slower than generating a packed list of the resulting cells. But I am more comfortable having the artifacts to inspect for byproducts (like the HWSS collisions).

If I get back to this seriously, maybe I will refactor the whole pipeline in lifelib or whatever else is available. One question: I am using David Bell's lifesrc to generate the constellations. Is there something else available that could output constellations in a more useful format?

Anyway, for my efforts, I get a consistent negative result, now going up to 12x12 constellations of up to 15 cells.

Code: Select all

% python buildgraph.py < edges.txt 
['4b2o$3bo2bo$3bobo$b2obo$o2bo$obo$bo', '4b2o$3bo2bo$3bobo$b2obo$o2bo$obo$bo']
['2o$2o5$2o5b2o$2o5b2o', '2o$2o5$2o5b2o$2o5b2o']

This is taking edges (u, v) between small patterns meaning that v can be obtained from u by colliding it with a glider and getting another glider back. If those patterns are constellations as above, the only cycles consist of the biloaf and the 3-block resettable shifter. (If I had run this search in 1998, even up to 7x7 windows, I would have found the biloaf collision, but it really was a lot slower back then, and such a search did not seem promising.)

The glider/biloaf collision is the closest to a bona fide miracle in Life. I would never have looked for it, because how could that actually work? (OK, I think the reason might be that it has this 8-cell predecessor, so is more common than I would guess).

Code: Select all

x = 6, y = 6, rule = B3/S23
3b3o$2bo$bo$o$o$o!

When I tweak my code to produce longest non-cycle paths, I get things like:

Code: Select all

['2bo$bobo$2b2o4$bo3b2o$obo3bo$bo3bo$5b2o', '2o$2o3$bo$obo5b2o$obo5bobo$bo7bo', '2o$2o2$6b2o$6bobo$7bo2$b2o$obo$bo', '2b2o$bobo$obo$bo', '2b2o$2b2o8$2o$2o', '2o$2o5$7b2o$7b2o', 'b2o$o2bo$b2o', '11b2o$11b2o3$19b2o$19b2o4$2o$obo$b2o2$32b2o$32b2o6$42b2o$41bobo$42bo']

Each represents a constellation I can hit with a glider, get a glider back, and get the next constellation. But this is not useful if they don't make a cycle.

I still have other things to try. If I take all the ash created, including with blinkers, I can apply the same approach and see if any of those work. Maybe tomorrow.

I am getting tired of this. I thought I might see a positive result just playing around with old tools. Setting up a very careful search to get a negative result in the largest feasible range looks like the next step. (But I am just lucky to have the time to work on it right now.)

[wildmyron]

Thanks for the explanation.

If I get back to this seriously, maybe I will refactor the whole pipeline in lifelib or whatever else is available. One question: I am using David Bell's lifesrc to generate the constellations. Is there something else available that could output constellations in a more useful format?

I can't think of anything that does exactly what you want.

There are several still life enumerators, but they'll only give you strict and pseudo stll lifes up to a certain bit count. The most efficient is by simeks, discussion here.

There's a program called sngdetect, aka Stable and Glider, by Gabriel Nivasch which tried to do something very similar to what you are doing, but it only enumerated constellations of a fixed set of small objects (including blinkers). [Edit: actually, it's so long since I used this code I can't even remember if it prints out the constellations or just generates them and tests all the glider collisions]

Dave Green published a similar constellation enumeration Python script, latest version here: http://conwaylife.com/forums/viewtopic. ... 458#p57458 . I think that version just puts all the results into a layer in Golly, but it's a trivial modification to save to a file (which I did in the past but seem to have lost).

I suspect there's others, but probably nothing that does a better job than lifesrc, and if you need to modify whatever the replacement is you could just as well modify lifesrc to ouput single line rle rather than ASCII patterns.

I've got my fingers crossed that you find something with your search

Edit: There's also been other discussion on this topic previously on the forum, but I don't think anyone published any code which comes close to doing what you've already got. Previous references

http://conwaylife.com/forums/viewtopic.php?f=7&t=1063 (Just discussion)
http://conwaylife.com/forums/viewtopic.php?p=9043#p9043 (see surrounding discussion for numerous reactions of the form [G + m blocks] -> [n G + (m+p) blocks], for n, p > 0)

[pcallahan]

For benchmarking, the 12x12 15 cell survey tested 88982049 glider collisions using 987492 distinct still life targets.

I didn't keep track of how long it took to perform the collisions, but I reran the python script to generate them, and that took 184m22.373s, or a little over 3 hours. This was done on a MacBook Pro that is already several years old with 2.2 GHz Intel Core i7.

Assuming it is spending most of the time running and testing collisions, it would only help a little bit to speed up the above. If there's a faster generation algorithm or just a change that rules out failures without doing as much generation, the search time could be brought down.

As I said above, the biggest win will probably be to do the whole process in memory.

[pcallahan]

I've got my fingers crossed that you find something with your search

It seems unlikely with this particular survey. At this point, I can look for byproducts. I have a list of 5231850 collisions of a glider and still life that produce at least one glider or spaceships and contain no more than 30 cells that are not part of a glider (so that lumps non-glider spaceships with stable ash).

Code: Select all

awk '$4 + $5 > 0 && $3 - $4 * 5 <= 30'

Column 3 is the number of cells, column 4 is the number of gliders, column 5 is the number of spaceships.

I can scan this output for xWSS syntheses (like the HWSS I posted) or for multiple gliders and other things. I can also take the ash product of the collision, which might be larger and contain period-2 objects, and use that as part of the cycle in the graph, but that requires another search.

This is the first time I asked this question, but out of 88982049 collisions, 5231850 are of the form I want, or about 5.9%. So how can it be so hard to find a cycle in this graph?

It is true that collisions don't bring it back to the original set, since the target product has more cells, no bounding box limits, and may not be a still life.

It might be worth it to winnow this down to products from the original target set just to collect stats. Existence is roughly approximated by this random graph question: what is the probability of find a cycle in a random graph with m nodes and n random directed edges? Given that an empirical formula for projecting the number of collisions that are closed within a target set, I could attempt a guess at what I would need to find something

http://conwaylife.com/forums/viewtopic.php?f=7&t=1063 (Just discussion)
http://conwaylife.com/forums/viewtopic.php?p=9043#p9043 (see surrounding discussion for numerous reactions of the form [G + m blocks] -> [n G + (m+p) blocks], for n, p >= 0)

So they have a name, fluff relays. I should repost my conclusions in a real forum once I am a little more organized.

ADDED: Good is pattern, but better explanation is (he observes in the worst pseudo-Yoda ever).

Starting with 987492 seeds (stable, 12x12 box, max 15 cells), I get 1288014 collisions that produce at least one glider or spaceship and a seed from the original set. Note that some seeds may not produce anything in the original set. It would be cherry-picking to rule them out. So we have a random graph with an average fanout of about 1.3. I haven't done the calculation, but that seems consistent with a "birthday paradox" situation in which there is a reasonable probability of getting some self-cycle, but not more than one or two (which we see). I am not sure how to approach the question of longer cycles.

I do not know if these graphs are getting denser or sparser. There are factors going both ways. Bigger patterns mean more collisions. However, they are also less likely to be the result of a collision. I think at least I have the best intuition I have had so far of why these reactions are so rare.

[pcallahan]

Can't help much there, except to say that previous HWSS seeds were considered pretty good if they had four or five small still lifes. Now you've reduced that to three.

I tried collisions with the ash of the original collisions and did not get any clean HWSS syntheses (I got 83 combined of LWSS and MWSS). So it still seems to be hard to get them from "natural" seeds.

ADDED: Actually, I made a mistake and there is one synthesis. It is not from a stable seed, though. It uses a blinker in the collision.

Code: Select all

x = 9, y = 20, rule = B3/S23
bo$2bo$3o5$7b2o$7b2o$3b2o$2bo2bo$3b2o6$8bo$8bo$8bo!

And here are four that I probably missed in the first set because I was filtering for size 18 instead of 13.

Code: Select all

x = 328, y = 40, rule = B3/S23
10$11bo99bo99bo100bo$12bo99bo99bo100bo$10b3o97b3o97b3o98b3o5$22bo97b2o
94bob2o92b2o3b2o$21bobo95bo2bo93b2obo90bo2bo3bobo$22bobo95bo2bo186b2o
6bo$18bo4bo97b2o$17bobo195bo4b2o91bo$18bo95bo99bobo3b2o90bobo$21bo91bo
bo99bo97bo$20bobo89bo2bo$20b2o91b2o!