AMA: I'm Dave Greene, an accidental expert on Conway's Game of Life

[dvgrn]

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!

[HarHarVeryFunny]

We see people doing insane things nowadays with Conway's Life, such as simulating CPUs.

Two questions:

1) How are people building things this complex? Are there open source libraries and toolkits for this - building blocks for chunks of functionality that can be assembled?

2) For you, what are the most interesting, impressive and varied things that you've seen with Life? Is it just these increasing levels of complexity, or maybe something else?

[dvgrn]

Question 1: There are really surprisingly few "standard libraries" or tools for this kind of thing. You would think we'd have a CA editor capable of doing object-based editing by this time -- like, copy in a complete device made out of reflectors and converters, each of which is made out of still lifes and oscillators, each of which is made out of cells, and you could do "group" and "ungroup" operations and snap to the right locations to fit the circuits together correctly.

But at the moment, pretty much all we have is tools to copy and paste rectangular sections of patterns at the cell level -- plus we've got good scripting tools (in Golly) that can be used to string together whatever pieces we might want, but it's up to individual pattern-builders to write those scripts for each specific purpose.

So our "library" is pretty much just the LifeWiki and a few other pattern repositories, and we borrow liberally from existing large constructions -- but when we're building something new, we usually just build flat bitmaps, not anything with built-in annotations or metadata.

Question 2: The thing that's been the most interesting to me in the last decade or so is the increase in collaboration. Projects used to be done by just one person more often than not -- but now a very large fraction of the biggest discoveries are completed via a large group effort over the course of a few weeks or month. One big recent example has been the RCT fixed-cost universal glider synthesis project, which needed contributions from quite a few people to solve all of the tricky little sub-problems:

  https://conwaylife.com/wiki/Reverse_caber-tosser

[jaymzcampbell]

The Game of Life is a 2-dimensional cellular automata (CA), so given the 1-dimensional rule 110 has been proven to be universal / Turing-complete [1], it becomes less mysterious. Albeit the complexity of the system required to set it up to do anything "useful" would be prohibitive.

I'm currently finishing up my OU MSc and the project I picked was specifically around cellular automata - only in this case relating to them calculating any arbitary automatic sequence - which are sequences you can create from finite state machines - that really opened my eyes to the fact these sorts of very, very simple machines can, with the right (and rather complex) setup, be made to do pretty much whatever you want from a computational PoV. In that paper by Rowland and Yassawi they give a constructive proof to calculate the required update rules for a CA that outputs any particular automatic sequence. That itself gives some hints at some ways of deriving the input and rules for these systems to do some particular job. [2]

I know Wolfram often gets dunked on for ego/hubris but in Chapter 11 of a New Kind Of Science he goes into how the Rule 110 CA can be setup to "calculate" (output) other CAs. From there it starts to become a little less mysterious that these systems can generate behaviour you could imagine running on a CPU of some sort.[3]

[1] https://mirror.explodie.org/universality_in_elementary_cellu...

[2] https://arxiv.org/abs/1209.6008

[3] https://www.wolframscience.com/nks/chap-11--the-notion-of-co...

[bell-cot]

The basics, JIC anyone here is still unfamiliar with the Game:

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?

[dvgrn]

A really impressive number of discoveries have been made since 2001 -- there's been kind of a proliferation of new sub-fields, so it seems like there's never any shortage of things for newcomers to work on.

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" --

  https://conwaylife.com/wiki/Wire#2c/3_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:

  https://conwaylife.com/wiki/

[kwhitefoot]

I was unfamiliar with JIC, had to read the sentence twice to make sense of it. :-)

[mihaitodor]

Have you followed the https://codegolf.stackexchange.com/questions/11880/build-a-w... thread where Tetris was implemented using their Cogol (and low level QFTASM) programming language? I'm curious if that work led to any new insights and if it found any usage beyond implementing Tetris.

[dvgrn]

Yup, the Quest for Tetris project caused an entertaining stir for a while. The people that worked on that were the best kind of "hacker" -- fearless experimenters who didn't let their lack of Life-specific knowledge get in the way of cobbling together an amazing structure that fit the bill for simulating Tetris.

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.,

  https://conwaylife.com/wiki/8-bit_programmable_computer

[rosmax_1337]

Why is Conway's Game of Life so interesting? Does it prove anything or lead to insightful discoveries? The game itself seems to me, like a fun little toy at best.

[crdrost]

This won't directly answer the question, but just to give some added context: Note that in abstract mathematics (which is what Conway was doing here) you’re kinda creating building blocks, and you're kinda playing for “street cred” among the rest of the abstract mathematics community.

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.

[TimTheTinker]

A simple set of rules leads to a fascinating array of emergent phenomena, which themselves can be utilized to do all sorts of interesting things.

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/

[_akhe]

It shows that complex structures, importantly those with generative capabilities and other utilities, can evolve from a simple pattern.

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.

[abetusk]

Conway's Game of Life (GoL) provides a clear demonstration that simple rules can lead to complex behavior. The complex behavior is deep in the sense that Conway's GoL is Turing Complete [0].

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...

[meschi]

It's a cellular automaton showing complex behavior emerging from very simple rules. Through especially crafted inputs you can simulate a Turing machine or Conway's Game of Life inside itself.

[pavel_lishin]

> boojum reflector

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

[sevenseventen]

The word "boojum" originates in Lewis Carroll's "The Hunting of the Snark," an amusing epic poem about the importance of negative testing.

[bradleyy]

I've been fascinated by Cellular Automata and the Game of Life ever since seeing the art installation of _Network IV_ by James Seawright. It was at Sea-Tac Airport, and has since been removed.

There's some debate whether it was the Game of Life or some other automata, but I remember the sounds of the relays clacking and the light bulbs humming so distinctly. It certainly had a "Game of Life vibe".

Are you aware of this art installation? Ever seen it?

[cauliflower99]

Conway has said GOL is not something he is particularly pleased got as famous as it did. (Ref: https://youtu.be/R9Plq-D1gEk?t=600)

Why do you think that is?

Edit: This is the video I meant: https://www.youtube.com/watch?v=E8kUJL04ELA

[gnramires]

What I got from his interviews is not that he disliked the GoL, it's just he disliked the GoL overshadowing everything else he did (basically, becoming the GoL guy). He personally didn't see much more interesting mathematics that could be done after answering basic questions like universality (although it's likely he wasn't aware of everything the community was up to). Also, it's clear he seemed to come to terms with it in his final interviews (including the second one you linked) :)

I've played around with several CAs and Conway's rules stands out to me as one of the most interesting still, for many reasons (like simplicity, interesting patterns, long lived structures).

[JoeDaDude]

A silly question and a PSA:

1. There was a two-player game called The Immigration Game [1] using GoL rules. Has anyone actually played this? Even better, has anyone developed an AI to play it? Is there really much of a game there?

2. The PSA: The Immigration Game was described in Lifeline, a 1970's era (typewritten!) newsletter about GoL. I managed to obtain a set of them. I've been planning to scan them and make them available online. I don't think there is any ground breaking info in them, after all, folk were programming on mainframes (surreptitiously).

[1]. https://boardgamegeek.com/boardgame/129088/the-immigration-g...

[dvgrn]

My sense is that people don't usually play the Immigration Game for very long -- it just doesn't seem all that interesting to most folks ... and so there hasn't been much interest in developing a computer opponent for the game.

It seems to be rather difficult to convert cellular automata into any kind of playable game. If it's an arcade game then it's usually too arbitrary, and if it's a puzzle game then it's usually way too easy or way too difficult. There have been some good efforts, but they're mostly only playable by dedicated Lifenthusiasts, and that's ... well... not a very large market!

Re: the LIFELINE public service announcement -- no need to do the scanning and online-ing. That's been done already, though there's still some review and typing-up work left for someone to do:

  https://conwaylife.com/wiki/Category:Lifeline_issues

[JoeDaDude]

Decades ago, I read an article in Byte magazine discussing various implementations of GoL. The article ended with an implementation in one line of APL. What are the chances you (or anyone) still has that article, and that one line program?

[dvgrn]

Heh -- "if you need more than one line of APL you do not fully understand your problem".

  https://news.ycombinator.com/item?id=1041500

People have done similar things in all kinds of languages by now:

  https://codegolf.stackexchange.com/questions/3434/shortest-game-of-life

[RBerenguel]

This video constructs a GoL in APL (not one liner). It is quite understandable even if you don’t know APL (I had just started tinkering with APL when I first found it I think): https://m.youtube.com/watch?v=a9xAKttWgP4

In case somebody is curious to see how it might look like.

[kirubakaran]

    life←{⊃1 ⍵ ∨ .∧ 3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

[p1esk]

Is there a 3d equivalent of the game? What would be different about it?

[dvgrn]

There's been quite a lot of experimentation with 3D versions of Conway's Life -- including rules where you can easily emulate Life on a 2D slice of the 3D plane. Carter Bays did some investigations and published papers back in the 1980's:

  https://conwaylife.com/wiki/Three-dimensional_cellular_automaton

There's been a little bit of revived interest lately, when newer versions of Golly ( https://golly.sourceforge.io/ ) started to include at least some support for 3D rules. Other programs have been showing up recently, though some of them are more ways of visualizing the history of a 2-dimensional rule in three dimensions.

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.

[tromp]

Carter Bays wrote a paper "Candidates for the Game of Life in Three Dimensions" on that back in 1987 [1] and another in 2006 as mentioned on Wikipedia [2]:

[1] https://content.wolfram.com/sites/13/2018/02/01-3-1.pdf

[2] https://en.wikipedia.org/wiki/3D_Lifex

[cornstalks]

This was posted yesterday: https://news.ycombinator.com/item?id=40124682

[npinsker]

What are the coolest problems that have been recently solved?

What are the coolest open problems you'd like to see solved?

[dvgrn]

It's hard to choose one these days -- a whole pile of open problems actually got solved in the last few years, like omniperiodicity, glider syntheses of really complicated things like spacefillers, fixed-cost universal construction (it only takes fifteen gliders to build anything buildable) and still lifes and oscillators that solve the "unique father problem" (i.e., there are groups of cells that, if they're found in the Life universe at any point, they must have been there from the beginning of time.) So now I don't know what to wish for next!

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.

[bilsbie]

What’s the largest world we can run these days?

Are they run on gpus now?

Has anyone looked into ASICs?

Is caching heavily used for optimization?

[dvgrn]

Yup, there's an increasing amount of GPU use these days, mostly related to soup searching -- see https://catagolue.hatsya.com/home for the software and a tabulation of results from the last several years of collaborative searching.

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:

  https://conwaylife.com/forums/viewtopic.php?&p=153609#p153609

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.

[paulgerhardt]

Not a question but as a fellow Life enthusiast I thought I’d surface an alternative Life hack I made a few years ago based on physical Kong Bucks from Stephenson’s Snow Crash: https://kong.cash/

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

[lugao]

What's your take on continuous life? SmoothLife, Lenia and Bert Wang-Chak Chan work in general?

[dvgrn]

I think SmoothLife and Lenia are great fun -- lots of highly watchable "eye candy" tends to get produced by those types of experiments. The better you get at running experiments, the more new behavior you can turn up:

  https://www.youtube.com/c/Slackermanz

There's a channel on the ConwayLife Lounge on Discord called "#exotic-ca" that's devoted to these kinds of explorations. I just simply haven't had time to dig into those topics much, but if I could clone myself I'd definitely assign one copy to playing around with that kind of thing.

[openrisk]

Over the years there must have been countless interesting generalizations of Life. I wonder if there is good concise reference that classifies and groups the main ideas that have been proven "productive", in the sense that they open up non-trivially different and interesting types of dynamic behavior?

A while ago I was toying with the idea of introducing a "macro" stimulus. Basically coupling the local rules of the game to global metrics like how many nodes are alive. This is emulating a bit agent based modeling in economics and in particular the role of regulators raising or lowering rates, alternatively a physical system exposed to higher or lower temperature. But what happens (at least with a simple implementation) is that whatever "stimulus" is introduced tends to overwhelm the known patterns, there seems to be little new "emergent" behavior in the coupled system.

https://www.openriskmanagement.com/game_of_life_with_macroec...

[dvgrn]

I don't know about "concise", but one place to start for references is the LifeWiki. We've been trying to extend the non-Conway's-Life part of the wiki for a few years now, to cover more of the OCA space ("Other Cellular Automata"):

  https://conwaylife.com/wiki/Cellular_automaton
  https://conwaylife.com/wiki/OCA

There's an "Other Cellular Automata" board on conwaylife.com/forums and several channels on the ConwayLife Lounge on Discord -- "#naturalistic", "#circuitry", "#exotic-ca" -- that collect discussions on these kinds of topics.

[smusamashah]

1. Are there any practical/real life applications for Game of Life?

2. Has any discovery made in life been used in real life or any practical application?

[neoneye2]

It's great for generating synthetic data for training LLMs for solving Abstraction & Reasoning Corpus (ARC) by François Chollet. Game of life helps the LLMs with a 2D understanding of the world.

https://github.com/fchollet/ARC

[c22]

This is like asking about the practical applications of chess. They're probably mostly nth-order effects.

[thrww0300392]

What would be your advice/roadmap for someone who wants to start with automated exploration of emergent behaviour in systems that are similar to GoL?

I think it would be interesting to try transfering some of the automated search techniques to Minecraft's redstone mechanics, even though it probably doesn't fit the definition of a celular automata. Redstone is a feature in a videogame Minecraft that acts similar to logic circuits. Because building mechanics in Minecraft is inately restrictive (building is snapped to the 3d grid of "blocks", and there is only a limited number of blocks that all have predefined behaviour), there is naturally a community of people using redstones in ways that serve no purpose to the core gameplay loop, such as flying machines (think GoL's ships) [0], computers (since Minecraft's redstone is practically Turing-complete) [1] [2] or printers/autobuilders [3]. I would go so far as to say that redstone is the GoL for nerdy Zoomers.

[0] https://minecraft.fandom.com/wiki/Tutorials/Flying_machines

[1] https://www.minecraftforum.net/forums/minecraft-java-edition...

[2] https://minecraft.fandom.com/wiki/Tutorials/Redstone_compute...

[3] https://minecraft.fandom.com/wiki/Tutorials/Printing

[dvgrn]

I'm thinking the most successful "automated exploration" so far has been Catagolue's method: simply generate a whole lot of random-soup initial configurations, run them until they settle, and then poke through the ashes looking for interesting stuff:

  https://catagolue.hatsya.com/census

Seems like that gets the most emergent-behavior bang for your buck. All the other "automated search techniques" that I can think of are too specifically tailored to some particular problem.

[JoshuaMHanson]

Thank you for the link to the book. I have always been interested in how to make the starting shapes. I am going to study the book more but started to realize that there are re-usable shapes that can be used to make more complex shapes (early, still, oscillators, gliders, etc..). This seems to be what I was looking for with the starting x/y and then the rule combo and pattern.

I was also thinking there must be a better way than knowing exactly how big the board is vs an infinite board. Also making the edges either always dead or alive VS letting the shapes pass through like pac-man.

Here is my horrible implementation using HTML canvas, JS/JQuery.

https://github.com/JoshuaMichaelHanson/GOL/blob/master/js/go...

Yes, I also made a new green account so as to not dox myself with my other accounts.

[nomilk]

I haven't studied CS or bio. Do I understand correctly that what makes cellular automata special is they're approachable and demonstrate how complexity can emerge from simple rules (e.g. analogously to how life may have come to be)?

Do other games (or simulations) demonstrate similar ideas, or are cellular automata a rare case?

[dvgrn]

I'd say there's no shortage of demonstrations of complexity emerging from the iteration of simple rules -- fractals like the Mandelbrot set, simple edge-matching rules for aperiodic tilings, the logistic map, etc., etc.

What makes Conway's Life particularly "catchy" (along with other 2D CAs) seems to be the motion. Humans love watching stuff move, especially when the motion is partly predictable and partly surprising -- i.e., like a screen-saver, not like TV static. And they like watching things blow up. A lot of Lifenthusiasts probably got their start by aiming gliders at carefully balanced Life patterns and gleefully watching the resulting explosions... it's a lot more fun than actually blowing things up, because you can always hit Undo and run it all over again, no harm done!