I underestimated a CS puzzle...again. (Backwards Conway's Game of Life)

Welcome back, and I hope you enjoy this mess of a three-year project… It turns out backing up in a cellular automaton can be an insanely difficult problem. This started as a "play button" project, but turned into an obsession. I recently came to the conclusion that there's no long-term winning this game (it has been shown to be NP hard, so I don't feel that bad) but AGH it should be easier than it is!
Join me in this video as I dive through the much fabled Game of Life, take a hike through a very strange space, and organize a dinner party. It's going to be a great time.

Check out the second channel with bonus content and Q&A videos!

Special thanks to my top Patreon supporters!
birdiesnbritts
John Sosa Trustham
Vladimir Shklovsky
Aloysius Sparglepartz
Jason Whatley
Lohann Paterno Coutinho Ferreira
Jeffrey Mckishen
nothings
Eugene Pakhomov
Glenn Willen
R520
Nick F
Mirko Rener
Chris Connett
Tyler Filla
Miles Freeman
Benjamin Manns
MPG
Seth Reuter
Danny Thomas
Toby T
Lucy Fur
tiaz
Chris Duvarney
Nick Wage
John T

Media Credits:

E's Jammy Jams - The Entertainer
YouTube Music License

Silent Partner - Pink Lemonade
YouTube Music License

Chapters:
0:00 Conway's Game of Life
3:04 Playing GoL in reverse is hard
6:56 How to think in more dimensions
15:55 Drawing maps (both real and configurational)
19:33 The failure of gradient ascent
23:16 SAT solvers (dark CS magic)
28:54 Rephrasing the question and getting results

[AlphaPhoenixChannel]

FAQ and corrections in this comment!
2) Yes, there will be a part 2 video, but no, it's not coming out next. these programming videos are monstrous to edit because they're all animations and I can't stand to look at this project anymore. hopefully the next video is something fun with the high speed camera!
3) I'd love to see more people take a crack at this! Someone on Patreon wrote a fantastic algorithm this week that could take loads of steps backwards on a glider, but apparently struggled with the larger "play button" pattern I was using.
4) ...

[Tandanuu]

Bro just made a whole series about entropy and thermodynamics and now he’s surprised that reversing something like Game of Life is hard? :D

[satibel]

"we did it not because it was easy, but because we thought it would be easy"
(Naive developer discovering that the algorithm they are trying to reverse is not bijective)

[brothertyler]

Surpised you didn't show a solved rubics cube and ask the viewer to try to figure out what unsolved state it began from

[digantamukhopadhyaydex]

also afaik z3 doesn't have any progress bar, did u find that at all anxiety inducing? like if you had stopped the solve 1.9wk after start, maybe you would have missed a solution that you could have found with just one more day of solving

[MooImABunny]

I really love how Gerrymandering is relatively much more computationally easier than reversing GoL states.
Like, oh, making this cool pattern pop out? insanely hard, computationally intensive.
Abusing loopholes in a democratic system leading to political corruption? yeah dude, it's a walk in the park

[moth.monster]

Another problem which is NP-hard is placing conveyor belts in Factorio.

Someone made a modified SAT solver that just makes custom belt balancers for you.

[jonasmaier]

24:10 to be completely precise, it is not known if NP-hard problems require non-polynomial time to solve (but it is widely believed to require exponential time and all current SAT solvers are running in exponential time (with some heuristics to hopefully be fast in easy cases)). Just one of those open problems in computer science.

[Schlimbinger]

This reminds me of something. A while ago a buddy and me made something similar using langtons ant. We used multiple ants at different starting positions to “encrypt” a message.

The world the ants reside in basically was a 2d-grid representation of the input message bytes. They then would do their thing for many iterations.

Just a fun project, nothing serious. But it was nice to see your message emerge from “random” noise :D

Never thought about how one could crack it but it would not surprise me if it’s relatively easy lol

[harold]

Have you looked at zero-suppressed decision diagrams also, they "break down" (by running out of memory) more often than SAT solvers but when they work they enable you to ask questions about the entire space of solutions (instead of just getting one of them, as SAT would, making you generate them one-by-one with extra constraints). Such as you can ask how many solutions there are, or even a list of pairs of how many solutions there are for each number of "live" cells, or find the solutions with the most or least life cells.

[OrangeC]

Oh yeah! My favorite Blokus tile is the pentomino that's, like, a 2x2 square with another square attached to it. I don't really think it's the *coolest* one but, it's pretty unique all things considered so it ends up being my favorite

[andytroo]

the game of life is turing complete - assuming you have enough grid space ... does that mean solving this is a limited space halting problem?

also, solution to sat: "I can't get no satisfaction 'cause I try and i try and i try" - Description of brute force SAT solving strategies, [Jagger, Richards, et al.; published in "Out of Our Hands, 1965, available online]

[mshonle]

The N always stands for Nondeterministic. The NP-hard problems in NP are those that can be *verified* in polynomial time. It’s an open problem (with a million dollar prize!) to prove or disprove if all the problems verifiable in polynomial time can be decided in polynomial time. — So, polynomials are still very much involved!

(Note: the qualifier of “NP-hard in NP” in necessary, because there are undecidable problems that are NP-hard: the Halting problem is famously undecidable, but it’s trivially easy to reduce any NP problem to the halting problem: simply prepend a string representing a Turing machine that solves that NP problem. Likewise, if the N actually stood for “non” then it would include the halting problem as well.)

[carnac]

Awesome video and explanation!! This reminds me of my research area of inverse problems, where one aims to reconstruct the object of interest from indirect measurements.

As an example, in Computed Tomography (CT), we reconstruct the image of the imaged target from x-rays projected through the target. The information of the inner structures is encoded into the measured x-rays, which have been attenuated proportionally to the attenuation different tissues (for example very high in bones and lower in soft tissues). Commonly, the inverse problem is formulated using a model for the x-ray attenuation, known as the forward model and the sough after image is obtained by iteratively minimising the difference between the measured data and the predicted data produced by the forward model applied to the estimated image. Often, however, the problems are ill-posed, meaning that the solution might be non-unique, have many local maximum/minima, or noise can have a detrimental effect on the solution. In these cases we often employ regularisation, which imposes assumptions on the solution (such as smoothing) and makes the problem less ill-posed and more feasible to solve.

Although this problem is completely different to ones I'm accustomed to, there are many parallels. The forward model is the algorithm that runs the game of life, the indirect measurements (measured x-rays in CT) are the starting point, the final sough after image (CT image) is the final image you are after for and problems with optimisation (local minima/maximima) are common. Very cool to video!

[johnreiland]

Around the 7:30 mark, when you are explaining Configuration Space, the music is quite loud, to the degree that I think it becomes an obstacle to cognition. Love your videos, not hating on you or them, just wanted to mention this small spot that I think can be improved.

[Drawliphant]

"Conways Game of Death" completely fair name because it kills the developer

[Kargoneth]

It's like trying to reverse a hash.

[joshuascholar]

I get SO frustrated with other people's videos because they DON'T understand the problem they're looking at to the depth you do and they don't explain it. Thank you for making the first video I've seen in a long time that lacks the hand waving of incomprehension.

[powndy]

2^36 *1ms /16 cores =2 months. Just saying

[ohadcohen]

5 minutes into the video and I was screaming at the screen USE SAT SOLVERS! Glad you went there eventually, and I hope you had a wonderful eureaka moment :)