AMA: I'm Dave Greene, an accidental expert on Conway's Game of Life
I drifted into the Conway's Life research community in 2001 when I won a small cash prize for a lucky discovery of something called a "boojum reflector". My involvement has gradually snowballed since then. Off and on I've helped maintain various Life-related mailing lists and blogs, the Life Lexicon, and more recently the conwaylife.com forums and LifeWiki.
Another thing I stumbled into was helping Nathaniel Johnson complete an improbably thorough 480-page Conway's Life textbook, with end-of-chapter exercises and everything. The book could be used to teach a college-level class on the subject. https://conwaylife.com/book/ has a free PDF download for the book.
So... I'm not the cleverest Lifenthusiast by a long shot, but for a random question about the Game of Life, I'm more likely to know something about it than at least 99.9999% of the world's population. Ask me anything!
155 comments
[ 3.9 ms ] story [ 207 ms ] thread[1] https://content.wolfram.com/sites/13/2018/02/01-3-1.pdf
[2] https://en.wikipedia.org/wiki/3D_Lifex
There are a couple of big difficulties that seem to prevent 3D rules from getting a lot of attention. It's just plain a lot more computationally intensive to emulate 3D rules. Also it's a lot harder to see what's going on in the middle of an active 3D pattern -- a lot of the detail tends to get hidden.
The big surprise that I've been spending the most time on lately is the utterly strange result that if you can build something by colliding gliders together -- no matter now many gliders and no matter how big the final pattern is -- then you can also build it by starting with exactly fifteen gliders in an otherwise empty Life universe:
It's a mind-bending result -- partly just a mathematical trick, since you end up encoding a whole lot of information in the space between the gliders -- but it's just really amazing that all the details have actually been figured out to make the trick work, and that it's possible to simulate the whole process on a personal computer.What are the coolest open problems you'd like to see solved?
I suppose if I get a free wish for anything I want, I'd love to see a glider synthesis for Sir Robin, which a big oblique spaceship discovered in 2018. It's currently way beyond our ability to figure out how to build it out of gliders -- but twenty years ago the same was true of just about every Life spaceship, and now we have recipes for dozens of them.
The problem at the moment is that nobody can see how to direct those searches toward a predecessor that's made entirely out of gliders -- it's clear that the Sun will burn out long before a trial-and-error search would be at all likely to return a result.
We can easily make a huge number of non-Sir-Robin predecessor patterns that will evolve into Sir Robin -- and we can find ancestor patterns for most of those predecessors, too -- but each step backward always produces something that's a little bigger, a little blobbier, and a little more random and chaotic looking than Sir Robin was... so ultimately all we're doing is making the problem more difficult with each step.
Here’s the Hacker News discussion from when this was discovered: https://news.ycombinator.com/item?id=33797799
Dave, I’m still regularly blown away by this discovery. I don’t know what else there is to be said, but do you have any other comments regarding this?
Development of the RCT has slowed down a bit, though there's a hyper-optimized version in the works that will build a spacefiller instead of a Hensel decimal counter as its example pattern:
https://conwaylife.com/forums/viewtopic.php?p=180134#p180134
There's also another long-awaited project in the works, that will use quite a bit of the same technology along with some new ideas -- a unidimensional (one cell thick) spaceship:
https://conwaylife.com/forums/viewtopic.php?f=2&t=2040
It's improbably complex and awkward, of course, just like an RCT pattern, and it's huge though nowhere near as huge as an RCT pattern -- but there will be one phase of the spaceship that fits in a 1xN bounding box.
One thing that particular piques my interest is the diversity of possible automata, not just forms in any particular one, but diversity of rule sets as well.
What do you think is special about the GOL rule set compared to other life-like rules?
Do you think it was a historical accident this particular rule set became so famous, or not?
Are there alternatives you are also interested in?
On the other hand, Conway had some very specific criteria for the rule he was looking for. "B3/S23" is about as simple a set of rules as you can find for a range-1 Moore-neighborhood outer totalistic cellular automaton on a square grid.
So unless Conway's eye had happened to get caught by some slightly more complicated rule before he and his team happened on B3/S23, he'd be quite likely to settle on "B3/S23" all over again. It's one of the few candidates for the simplest rule that does obviously interesting things and seems likely to allow for computational universality. I mean, there are untold numbers of equally promising rules in larger rulespaces like the "isotropic non-totalistic" rules
... but most of those have rulestrings like "B2ci3ai4c8/S02ae3eijkq4iz5ar6i7e": it's just not anywhere near as simple to describe the rules, as it is for Life.---------------
If we meet up with an alien civilization some day, it would be extremely amusing if we happened to show them some Life patterns and they said (in so many words) "Hey! You know about Pnurflpeef's Game of Life?!?" Not a likely scenario, by any means, but not quite impossible either.
In 2001 I had already been playing around with things like the Mandelbrot set and aperiodic tilings and Douglas Hofstadter's strange loops for quite a few years, so I knew the kinds of magical things that the iterative application of simple rules could produce.
It seems like I rarely have dreams about Life patterns, though it does happen. Maybe some people with better-resolution imaginations might have a different experience, but Life patterns need a lot of precision and focus, and in my dreams everything is always fluid and shifting and I can never find my car keys or my homework, let alone any interesting Life configurations.
That absolutely sounds like a codename from one of cstross's Laundry Files novels. (I think "boojum" was actually part of one, but I don't recall which.)
edit: found it, it was from A Colder War, which is a great novellette: https://www.infinityplus.co.uk/stories/colderwar.htm
"For the Snark _was_ a Boojum, you see."
and ended up writing the other umpteen dozen verses just so that that would make sense as a punch line.
Negative testing is trying to invalidate the sample
The hunting of the snark is written in a way that reads like "normal English" from a distance. The sentences flow fine, the words look about right if you squint. So it passes a lot of "positive tests", in that it matches our expectations for what language looks like.
You have to "negative test" the story to realize you don't know the definitions for any of the words, and that the plot is uninterpretable.
Same idea as Kahneman's system 1 that comes up with instant answers, or ChatGPT hallucinating facts by association that "look right".
It challenges the reader to try to model and define a Wodwo, but provides basically no information on what a wodwo is, aside from the fact that it is something that itself is struggles to define it's relation and connection to the world.
In my opinion, it highlights how we are all physical perception machines looking for meaning and identity, but meaning and identity can not be physically perceived.
https://allpoetry.com/poem/8495307-Wodwo-by-Ted-Hughes
The Snark is described in detail, with but a single additional caution that some Snarks are Boojums, with no description whatsoever of the difference. And, in the end, only a Boojum is found.
The band of snark-hunters are _also_ described in detail, almost always emphasizing the things that they cannot do or the additional risks of having them along, but they're brought along anyway.
https://conwaylife.com/wiki/Period-24_glider_gun#Other_perio... https://conwaylife.com/wiki/Period-25_glider_gun https://conwaylife.com/wiki/Period-48_glider_gun https://conwaylife.com/wiki/Period-15_glider_gun https://conwaylife.com/wiki/Period-16_glider_gun
Are there any configs (I mean, those having any interesting behaviour) with intention having more than 4 symmetry parts? Or at least just more quadro symmetry configs? I am absolutely sure (since today) there are some for any 2^n, just all unfound.
Any attemts to create Conway's life on hexagon map with apropriate rules?
upd: for a single stream of gliders, what config gives as many gliders per 100 generations as possible? No matter what else it does, I just want a line of gliders with as little space as possible.
-- There have definitely been a number of people over the years exploring various outer-totalistic rules on a hex grid, and (to a lesser extent) isotropic non-totalistic rules: see
-- The smallest period at which gliders can follow one another is period 14. We don't have a true period-14 gun yet, though. The closest we have is a "pseudo-period" gun -- actually period 28, but it generates two gliders per period, so you end up with a period-14 stream:I came across excitable media recently and found it fascinating.
Do you have any other examples of cellular automata you found interesting or worth pursuing?
I'm not sure the "probability" part of the question is even well-defined, let alone answerable, unless you state a specific rulespace -- two-state range-1 Moore-neighborhood CAs on a square lattice, or three-state range-2 isotropic CAs on a hexagonal lattice, or what have you.
Basically, you just have to be able to demonstrate a working universal logic gate (a NAND gate or a NOR gate) in a candidate rule, and you've pretty much got Turing-machine equivalence.
The problem is, a lot more rules are computationally universal than you'd think when you first look at them. This is because it's often possible to get a candidate rule to act like a completely different rule, by filling the universe with something other than empty space.
So you can't just try out a few random-soup patterns, dash off a quick proof that "this rule necessarily explodes uncontrollably in all directions, so it's impossible for any circuitry to survive" or anything along those lines. What if you start with a universe of all ON cells, or a checkerboard of ON and OFF?
There are lots of rules where signals can propagate beautifully through that kind of non-empty medium, and occasionally some kind of Turing-complete mechanism might be found there, along the lines of what Matthew Cook did with Rule 110. So you really have to look at a lot of options before you can say for sure that a rule does not support universal computation -- and so far, it seems like a very tricky problem to automate the process of looking.
(I'm quite sure that I don't do anything "revolutionary" myself -- I just try to encourage Conway's Life research to continue. Discoveries have kept building on previous discoveries for fifty years now, and I'm just really curious to see what will happen next.)
For music generation you'd want to somehow avoid ending up with the music "going boring" when the highway appears... As with a lot of math-inspired art (I guess I'm thinking about Mandelbrot-set colorizations here) the key is going to be in very specific presentation choices -- color choices for still frames or videos, or the specific method of mapping sounds to frames in a Langton's Ant evolution. So you'll just need to have (or develop) tools to try a lot of options and see what looks the most compelling.
Still frames are probably not going to be that interesting -- the fun part about CAs is the predictable-yet-surprising motion, which can be either the usual visual form or converted to sound somehow.
A recent version of Golly ( https://golly.sourceforge.io ) added support for listening to evolving patterns -- see pop-sounds.py / pop-sounds.lua in the Scripts directory. That reduces patterns to a single dimension in an obvious way (just looking at population), ignoring a lot of the 2D complexity. No doubt there are a lot of other possible avenues to explore there.
https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
And generalizing Games from there:
https://en.wikipedia.org/wiki/Life-like_cellular_automaton
Question #1: How far has Lifeology(?) advanced since 2001, for people similar to your younger self (without awesome skills, or huge time investment) to have a chance at making their own lucky discoveries, and becoming modest Somebodies in the community?
Question #2: How highly (or otherwise) would you rate Wikipedia's articles on Conway's Game of Life, and closely-related topics?
There are definitely areas that haven't really been explored fully yet, like the use of SAT solvers in new and inventive ways to tackle difficult Life problems that are currently just beyond our reach.
Just for example, there's the problem of finding a fast elbow for a 2c/3 "signal wire" --
It's not clear if SAT solvers can be applied usefully to glider synthesis questions, like "is it possible to collide gliders to build a Sir Robin spaceship?" At the moment that particular question seems way beyond reach, but maybe in a few years we'll be running an AI that is experimentally setting up new SAT solver problems, and something will pop up that we just haven't managed to think of yet.Question 2: Wikipedia's articles tend to be very good quality -- partly because if they weren't, there are a lot of Lifenthusiasts with some experience maintaining the LifeWiki who would immediately go and fix any technical errors that might show up on Wikipedia. But the really detailed documentation on Life is definitely kept in the LifeWiki, not on Wikipedia:
Citation?
I'm willing to believe that someone used the gambit to win against an engine, but in response I would've expected the engines to be modified to restore their absolute dominance against human players.
So, I would be very interested to see any evidence that this gambit continued to work against the version of the engine released after the gambit's effectiveness became widely known.
https://ppqty.com/anyone-beaten-stockfish/
The qualifier "serious" is needed because GM Andrew Tang won games at hyperbullet time controls (15 seconds) against a weaker version of Stockfish.
Article is dated Oct 2023.
Are they run on gpus now?
Has anyone looked into ASICs?
Is caching heavily used for optimization?
Caching is very very heavily used for running the biggest universes, which are truly mind-bendingly large. Golly's "HashLife" algorithm can in practice handle patterns that are over a trillion cells in each dimension:
Patterns with interesting behavior very often have a lot of repeating patterns, with the interesting stuff happening as complex interactions between those predictable patterns. HashLife capitalizes on remembering interactions that it has seen before, so basically the more memory your computer has available, the better HashLife will do in the long run at simulating that type of pattern.Mostly, of course, the census just reports piles and piles of blinkers and blocks and beehives and boats and everything else that you almost always see when you run a random scribble -- but every now and then something turns up that has never ever been seen in the history of Life, and that turns out to be useful and building new mechanisms that weren't possible before:
Life being Turing complete, it's also not difficult to build a pattern with an unknown fate -- like a Fermat-prime calculator that will stop growing if it ever finds a sixth Fermat prime, or the Collatz-sequence simulator described here:
https://conwaylife.com/wiki/Fate#Unknown_fate
In fact, the game of life is Turing complete -- you can build whole processors[0] or programming languages in it. You can even implement the game of life in the game of life. Someone did that and implemented infinite zooming between GOL levels.[1]
[0] https://github.com/nicolasloizeau/scalable-gol-computer
[1] https://oimo.io/works/life/
This is kind of true in all academic publishing, that your success is due to your publications’ ability to inspire follow-up publications. But for abstract mathematics the “street cred” follows three rules: you get more cred based on,
• the wimpier the building blocks look
• the larger and more complex the structures you can build with them
• the more memorable or intuitive the blocks are (so like marketing... SK-calculus is the same as lambda calculus but lambda can say “I am the abstract mathematics of template substitution!” while SK-calculus can't, directly.)
All a way to say that the field is full of “fun little toys” and the key about criterion (2) is that we have figured out how to build structures of arbitrary complexity in Life, because we have discovered it is Turing-complete. It therefore is also NP-hard and a lot of other good stuff. Really revitalized work into cellular automata by giving some good marketing, which led to Stephen Wolfram's success etc etc.
> which led to Stephen Wolfram's success etc etc.
Wolfram's A New Kind of Science takes the idea a bit too far, in my opinion. It's an exposition of the hypothesis that the underlying stratum of life and the universe is, like cellular automatons, discrete—and therefore can be understood in terms of discrete processes, which he views as analogous to real life. He points to emergence in cellular automatons as evidence that an analogous emergent phenomenon was the reason biological life came into existence.
Mathematically and philosophically, it's a very interesting idea, but I'd hope that at this stage in scientific history, we'd understand that step 2 to validating an interesting hypothesis is testing it.
[1] https://mathworld.wolfram.com/PrincipleofComputationalEquiva...
eg: Lawrence Gray in his 12 page review: https://www.ams.org/notices/200302/fea-gray.pdf
Cosma Shalizi's infamous Rare Blend of Monster Raving Egomania and Utter Batshit Insanity review: http://bactra.org/reviews/wolfram/
The local update rules provide an analogy to our universe with a kind of built in "speed of light" of how fast information can propagate in the system. Further, since there is a system clock of sorts, the system is massively parallel with further analogies to our universe.
The game looks like a toy but note that many profound models are also "toy-like". Ising systems, precolation models, Bethe lattices, self avoiding walks, etc. all provide seeding grounds for deep insights into our physical world. Just as an aside, I heard a quote, which I can't find anywhere, about how Maxwell playing with magnets could have been considered him playing with frivolous toys but his setup was critical to him figuring out the underlying mechanics of electromagnetism.
On one hand, I sort of agree that there's a lot of uninteresting exploration but on the other hand, taking a step back, GoL research is exploring the more general space of cellular automata and how it could potentially map to real world simulation. For example, how small can a system be before it can do arbitrary computation? Can all patterns emerge eventually (no, garden of eden style patterns)? What do rotationally invariant patterns looks like? Can you "copy" arbitrary patterns from some setup? If so, how fast? Is it dependent on how big it is, or how complex it is? etc. GoL provides a sandbox in order to answer these questions and potentially give insight into other systems as well.
In my opinion, one of the reasons for the popularity of GoL is because it was created right when computers became commodities, allowing hackers, amateur mathematicians and others to program something simple, that could be heavily optimized for limited hardware, and create intricate and complex behavior. There was a quote somewhere, that I'm also having trouble finding, about how, at one point, GoL simulations accounted for a significant portion of wasted compute.
[0] https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Undeci...
God doesn’t play the GoL.
It's a fun toy because it's implemented in pixels with arbitrary rules, but the concept is exportable to other domains.
The eeriness of it I think comes from that we still don't understand a lot about the world - concepts like consciousness, the origin of the universe, origin of life - or, any mystery where we don't understand how a whole became greater than the sum of its parts - when you see a model like this, it shows visually how such unknown complexities probably originated in far simpler forms.
When I see those epic Game of Life videos where there's a giant stealth bomber looking structure steaming across the screen creating sub-processes in its wake, to me it's like a blue whale moving through the ocean, or a vast alien spaceship silently yet steadily barreling through the void of space.
There's an ominous intelligence that seems to emerge out of what was once simple, binary, unconscious, incapable.
Conway regularly attended the bi-annual Gatherings for Gardner in Atlanta for quite a while, but by the time I started attending he could no longer travel that far.
Each note is an actual flexible polyimide PCB containing a hardware storage wallet - the PCBs are translucent in parts or solid in others depending on a copper pour but overprinted with ink using a special UV process - but one of the security features is when one holds a note up to the light one can see a Game or Life program which when executed emits a corresponding number of gliders and oscillators as the notes value. This feature is to prevent one from “washing” a note and printing a different value as is done with $5 and $100 US bills for instance as the copper pour is “baked” into the medium.
Writing a c program to encode arbitrary numbers into a Game of Life program was a very fun distraction during an otherwise thorny project that involved connecting people from the print world to people from the electronics world while shaving a few thousand cycles off a crypto library with ECDSA P256 operations before the smart phone powering the chips via NFC turned off. Real engineering work to bring cryptographic proof of authenticity that unfortunately gets written off as a 'crypto scam' when the poc token attached to the circuit boards was the least interesting part.
One can see some of the denominations here: https://twitter.com/NoviolNFT/status/1341468948416512000
[0]: https://www.amazon.com/Alien-Information-Theory-Psychedelic-...
The project has at least one unnecessary extra layer of abstraction in it, but somehow nobody has quite gotten around to rebuilding it 100x smaller. A "HashLife-friendly" version could run thousands of times more quickly in Golly.
Since then, several people have invented their own independent computer architectures in Conway's Life, so that kind of experimentation is still going on. See, e.g.,