In this article, I assume that you have basic familiarity with Conway’s Game of Life. If this is not the case, you can try reading an explanatory article but you will still struggle to understand much of the following content.
The day before yesterday ConwayLife.com forums saw a new member named zdr. When we the lifenthusiasts meet a newcomer, we expect to see things like “brand new” 30-cell 700-gen methuselah and then have to explain why it is not notable. However, what zdr showed us made our jaws drop.
It was a 28-cell c/10 orthogonal spaceship:
To explain why this is such a groundbreaking discovery, I should first tell you that Life spaceships can be loosely divided into two categories. Engineered ships are the ones that consist of various small components. They often have adjustable speed. However, the population of tens of thousands to millions of cells causes these spaceships to have no practical value. There is much more incentive in hunting for elementary spaceships, which can be used for complex constructions. They are found using programs such as gfind or WLS. The algorithms behind these programs are beyond the scope of my article, but the important thing is that the search time goes up exponentially as the period of the ship grows. It is most interesting to find spaceships of new speeds, and the number of speeds that low-period ships can have is unfortunately limited:
Orthogonal | Diagonal | |
---|---|---|
c/2 | Yes | Impossible |
c/3 | Yes | Impossible |
c/4 | Yes | Yes |
c/5 | Yes | Yes |
2c/5 | Yes | Impossible |
c/6 | Yes | Yes |
c/7 | Yes | Yes |
2c/7 | Yes | Impossible |
3c/7 | No | Impossible |
c/8 | No | No |
3c/8 | No | Impossible |
This table does not include oblique speeds, which causes little inconvenience because no elementary oblique ships are known.
The table above shows that ships exist for most of possible speeds, and it seems obvious that the speeds for which there are no ships have been searched by numerous people with good knowledge of search programs, powerful computers and lots of patience. As for higher periods, even the smallest searches would take years on modern computers. It appears that low-hanging fruit have been harvested clean during the 46 years of Life research… or, more precisely, it appeared so before zdr’s post.
The idea we all missed is that if the ship is really microscopic, it can be found in reasonable time despite its high period. After zdr boldly went where no man has gone before, Josh Ball set up the corresponding search in gfind and refound the spaceship in a little over an hour. zdr said that their program found it in a matter of 19 seconds.
To be frank, similar event did happen before when the aforementioned Josh Ball pulled loafer out of a hat. However, zdr’s spaceship (which is now called Copperhead, as proposed by muzik) is much more awesome for a number of reasons:
- Loafer is not so mind-bogglingly high-period.
- Copperhead was much easier to find, so it is more surprising that nobody found it before.
- Copperhead’s tail is relatively strong and can interact with other objects without breaking down.
The discovery of a new spaceship speed immediately opened a few new areas of research, which are being explored now.
Synthesis
Aidan F. Pierce came up with a Copperhead synthesis only 10 hours after the completion of the spaceship. The synthesis was inefficient, and a few people discovered better ones. The current best synthesis, made by Chris Cain, requires only 22 gliders. Its repeat time is 375 ticks, which means that a gun can start constructing the second spaceship 375 ticks after the first one. There is a 23-glider synthesis with a better repeat time of 373 ticks.
The synthesis can be substantially improved if we find this spaceship crawling out of a random soup. Adam P. Goucher has written a wonderful program called apgsearch, which is perfectly suited for this task. While the current version may be too slow to find a soup in reasonable time, highly anticipated version 3.0 can probably do the trick. Once it is found, it will appear here.
Guns
Once the synthesis was complete, building a gun was nothing but corollary-sniping. The first copperhead gun was created by myself, and a video of it is availible here. It was put together in a hurry and is therefore extremely inefficient. In particular, skilled gun builders can spot a silly mistake in the Northeast.
gmc_nxtman then made another gun with an almost optimal period of 376 ticks.
Eaters
simeks found two eaters for this ship, the better of which is shown below:
It is now time to search for a good copperhead-to-something-useful converter. The only existing one is clumsy and slow.
Sawtooths
Sawtooths often work by sending a flotilla of fast ships towards a slower ship. The more is the difference in speed, the less is the expansion factor of a sawtooth. Since expansion factor is proportional to how boring the sawtooth is, increasing the speed difference is a good thing. Dean Hickerson collided c/2 standard spaceships with c/10 copperhead to get a sawtooth with expansion factor 6:
He then made another sawtooth with expansion factor 10/3.
Puffers and rakes
Suppose a c/10 flotilla is hit by a glider. The glider turns into loads of mess, but all copperheads somehow survive and move on. The mess releases a glider, which flies into strategically placed second flotilla that is identical to the first one. Gliders continue to bounce back and forth between flotillas leaving mess behind them, and a c/10 puffer is complete! Unfortunately, this cool technique doesn’t work out easily in our case. There are no interesting interactions between a glider and a single copperhead, and it is unclear how one can place two or more copperheads so close to each other that a glider interacts with all of them. Assuming we figure it out, we can try to make a rake by perturbing the mess with copperheads so that it evolves into gliders, but that seems even less likely.
However, all this hand-waving can be turned it real puffers if we find…
Tagalongs
Tagalongs are small things that are attached to the back of a spaceship and move with it. Here is an example tagalong, called the Schick engine:
Finding a tagalong for the copperhead (or two copperheads) will be really nice. We can also try searching for pushalongs, but they are generally rarer.
Other patterns
There are a few other areas of Life exploration where the copperhead can be useful. For example, universal constructors often need to create an elbow still life very far away. It can be done by producing a copperhead, waiting for some time, and then shooting the copperhead down with a LWSS. At the moment I do not see why the copperhead can be better than the loafer in this aspect, but who knows?
hey, that’s pretty good. Though, oblique spaceships have been observed in life, like the parallel hbk.
LikeLiked by 1 person
Yeah, but not at a size my laptop can manage. They are big as the building you’re in ! Conway’s Life does NOT lend itself to knightships. It also does not lend itself to oscillators or spaceships appearing in random fields. They are uncommon, rare , extremely rare, or even have to be constructed by search programs.
LikeLike
I like it a lot. One issue, though: it could be clearer that the optimized synthesis was not based on mine at all.
LikeLike
Obilque speeds do have known spaceships since 2010.
LikeLike
Back in the 1970s, Conway showed that a universal constructor was possible, implying that spaceships exist of all rational directions Engineered spaceships like Gemini, Caterpillar, and HBK demonstrate this. However, no ‘natural’ oblique spaceships have been found yet, although there have been some near misses, suggesting that small ones do likely exist.
LikeLike
Thank you for pointing out the mistakes. I have edited the article accordingly.
The Sawtooths section literally became obsolete overnight, so I amended it, too.
LikeLike
I’m confused… is the ‘silly mistake’ that you used two edge-shooters instead of a regular gun to start off the NE salvo?
LikeLike
Exactly.
LikeLike
Pingback: Bookmarks for March 9th through March 10th : Extenuating Circumstances
Pingback: LIFE 3D - rolze | rolze
Pingback: March miscellany | Complex Projective 4-Space
Pingback: Una Nueva Configuración Interesante En El “Juego De La Vida” De Conway | Unocero
I actually felt cheated when this came out. What is zdr’s real name, what is the background behind this user and what was the “19-second algorithm” used? This last point is particularly important, because if the algorithm is not posted then it’s as good as non-existent. (Case in point: a certain Hunt Chang has claimed to have solved the intersecting Bézier curve problem at https://sites.google.com/site/curvesintersection but he refuses to release the methods. I had to write one myself for my Kinross library.)
Yes, I am Freywa on the ConwayLife forums. I used to be active there, but then I moved on to more continuous things: My Little Pony, Bézier curves, random number generation and now crosswords.
LikeLike
First of all, zdr has released the program that was used to find the copperhead. See this thread for details.
Second of all, I can remember that you had a conversation with thunk about the use of real names on the Internet. Please don’t start it all over again here.
All in all, I think one should not criticize a person who gave the CA community such an outstanding pattern.
LikeLike
Pingback: Links for March 2016 - foreXiv
Pingback: Nerd Alert 80: Not a Hot Take on Pokémon Go and the Future of News | INN News Nerds
For some 46 years, even before home computers even, I have been doing albums of Life patterns. Some 32 books (incl. a Master Index). Hopefully now I have finished and can just read it all. Getting pages numbered neatly and correcting all transcription errors fixed ,plus the occasional new pattern (oscillators,spaceships and a few puffers, lately.). A lot of long-term ancestors and diehards before 2006…
LikeLike
Eaters to destroy a copperhead (or some other painstakingly constructed spaceship, that doesn’t occur naturally)… How wasteful ! Better by far to use a Schick Flying Machine, a Cordership or a Coe-ship and create a puffer !
LikeLike
in re: 6411muriel+1164 on destroying spaceships – I AGREE !
LikeLike
A true Knightship HAS been found and it fits in a 78×31 box. In all stages it’s chaotic -and it’s unlikely any glider collision can create it. Your objection to eaters destroying artificial spaceships,as if they never were, can be extended to this monster.
It;’s been whimsily named the “Sir Robin” after Sir Robin the Brave who bravely runs away from a fight as fast as he could (see Monty Python’s Quest for the Holy Grail).
LikeLike
Pingback: New Spaceship Speed in Conway’s Game of Life « Another Word For It
Pingback: The Many Tribes of Artificial Intelligence – technoblogs
I’ve seen on some websites C/2 spaceships that look like palm trees. Resolution is not good enough to copy pattern to paper and then to a program that runs the game. Some of these websites are archived and not being updated. (Like pentadecathlon.com )
LikeLike
I am not sure what you are talking about – with enough imagination, lots of patterns can look like palm trees. I encourage you to post the low-resolution images you mentioned, and then I will probably be able to find copypastable files of those patterns.
LikeLike
You will find one at the very first image on the very first page of GoogleImages’ department of “Game of Life Line Puffers”. The shape COULD be painstakingly copied by hand onto graph paper, but it is large and with me,the larger a pattern,the more mistakes I might make. The pattern is C/3 P36 and outputs beehives. Pretty puny output for such a messy palmtree pattern. It even includes a C/3 P3 slipper spaceship,the simplest of these alien spaceships (don’t occur naturally *) at the tail.
* I THOUGHT I had a possible appearing of this slipper spaceship in the output of a collision, but maybe I just dreamed of it.
LikeLike
Hello. As you can see, I respond to comments on my blog so quickly that I might qualify for the Quickest Responder Ever award administered by the Internet Sarcasm Department.
Anyway, back to the topic. Here is the file of the pattern you were talking about:
It is in RLE format, which can be read by nearly every CA program in existence. If the program you are using doesn’t properly decode it, you should seriously consider installing Golly.
Regarding your other point, puffers are intentionally engineered to produce as little output as possible, because then they are way more useful in the construction of larger patterns. And no, there is no way you could see any c/3 ship coming out of a random soup unless you made a huge distributed search, and even then it would have been extremely unlikely.
LikeLike
At the mo, I have created a 32nd -and last- volume scrapbook. It has 2 greyships no less, and the Boojum, and some other exotic stuff. I did include the Palm Tree Puffer in Vol.26 (body is P2, but it takes 3 periods to output a block. The blocks form a long “stem”.
The greyships were troublesome to copy without errors. One I call the Angler Fish, as it has LW classic spaceships,imbedded in the trailing end. (like the degenerate males in deep-sea species)and moving as if they were alone (resorbed and then reappear).
I find from dates appended to most patterns that I started with Life in 1970, began these archive albums in 1978 continued to 2000,then paused until 2006, which a cellar flood destroyed most of my work -but not the Master Index, and some early albums stored on a higher shelf. Repair work segued into new stuff entirely (oscillators,spaceships, puffers, guns, factories, stretchers,…), As of June, 2017 I expect to have finally finished a grand archive.
LikeLike
Pingback: 深度学习,人工直觉和AGI任务 (Deep Learning, Artificial Intuition and the Quest for AGI) | Atman资讯
That LIFE websites seem to be archived and no longer updated, does not encourage me to continue.
LikeLike
Neither Pentadecathlon nor my blog should serve as an indication of the overall health of the CA community. If you go to ConwayLife forums, you will find a lot of people interested to hear about your work. If you have finished assembling your collection, you should definitely post it there.
LikeLike
I surfed the forums, but gave up. Nobody posts pics of their work, just golly gibberish. A simple plotting of a pic is all I asked.
As I said, I no longer add patterns, but carefully check page-numbering ,indexing, and master index (vo1.0) numbering. I found 1 duplication, and a few vol.ref.errors. I also replaced pages that were blotched (an older printer darkened faint blotches into big messes), and fixed some transcription bungles, cross-reference errors, as well as age-danaged oages, (Vol.1 has NO original pgs left, and only 2 orig,pages in vol.2.).
I did find 18 gliders (glide-reflection halfway through period) and one was P6 (Seal. A forum writer mentioned that.Thanks). One I created (extendible). None of these were distinguished as gliders from other diagonal spaceships. I(ich) made the distinction. I !
Just as I found 40 or so Conservative Reactjons (my term. Two or more patterns that collide to reappear rearranged, but with no other stuff in arena,xcept a bit iof junk).
All this is accomplished. I no longer research, After 47 years…
LikeLike
The Schick Engine I see as a failed puffer,as the junk exhaust lasts long enough that it lends itself to being vitalized into lasting exhaust. So my albums list it under “puffer trains” not “spaceships”.
SPARK – A 1- or 2- bit fragment that dies in 1 gen.
JUNK – A 3- bit or larger fragment that takes 2 or more gen. to die.
DIEHARD – A fragment that takes long enough to die that its longeivity/size ratio is 7 or higher. I have charted almost 200 of these, a few going more than 200 gen.
LikeLike
Pingback: LIFE 3D | rolze
Pingback: New and improved evidence of controlled demolition in the Pearl Harbor event. | Memo Of The Air
what is the palmtree glider called?
LikeLike