7 ms·
Finding Mona Lisa in the Game of Life
- enriquto 6y ago> Running ~1000 iterations for a 483px wide Mona Lisa on the google colab GPU runtime only takes around 40 seconds!. Compared to the CPU version which takes several hours to do the same for a smaller image Isn't this excruciatingly slow? I remember my old 486 computer did run life at full-screen full-resolution in realtime (probably 25fps at 800x600 ?) How it has come to that after 20 years? How can a 20 year old CPU outperform a modern GPU by one order of magnitude? Is it all fault of lots of useless intermediary language layers?
- zbendefy 6y agoprobably 99% of time shuffling data around, 1% of time calculating
- Marazan 6y agoThat's not 1000 iterations of GoL. That's a thousand iterations of trying to find the best seed.
- enriquto 6y agoI stand corrected. The numbers were too way off to make sense at all!
- deleted 6y ago[deleted]
- xaedes 6y agoRegarding the speed of GoL itself: The JAX implementation of GoL he used should be able to do 10 billion cells / second http://www.bnikolic.co.uk/blog/python/jax/2020/04/19/game-of-life-jax.html http://www.bnikolic.co.uk/blog/python/jax/2020/04/19/game-of... > Speed of execution > Looking into speed of execution was not a primary goal, but in case people are interested initial: study suggests this code will do about 10 billion cells / second on the Google Colab GPU runtime. For comparision this simple numba optimized GoL propagation function achieves roughly one billion cells per second on CPU (i7-9700K): @numba.jit def propagate_jit(arr, result): h, w = arr.shape for y in range(1,h-1): for x in range(1,w-1): result[y,x] = arr[y,x] num_neighbors = ( arr[y-1,x-1] + arr[y-1,x] + arr[y-1,x+1] + arr[y,x-1] + arr[y,x] + arr[y,x] + arr[y+1,x-1] + arr[y+1,x] + arr[y+1,x+1] ) if num_neighbors == 3: result[y,x] = 1 elif num_neighbors < 2 or num_neighbors > 3: result[y,x] = 0 arr = np.random.randint(0,2,(700,480)) arr2 = arr.copy() %timeit propagate_jit(arr, arr2) # 333 µs ± 2.64 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 700*480*1e6/333 # 1009009009.009009 Btw: The not numba optimized implementation will run in 806ms on my system. The optimization gives a speedup of over 2400.
- UncleOxidant 6y agoNot entirely sure what @numba.jit is doing here as I haven't used numba - is it compiling to native CPU code? Another approach to speed up GoL would be to use a lookup table. 2^9 entries. It's kind of like having the sum pre-calculated. Using the lookup table approach with @numba.jit would probably be even faster yet.
- 7373737373 6y agoFor a similar challenge: https://en.wikipedia.org/wiki/Proof_game https://en.wikipedia.org/wiki/Proof_game
- xirbeosbwo1234 6y agoThis is of something I've often seen in GPU-accelerated code: people get really amazing speedups because they're comparing to something that started out dog slow. Every example given is 10 generations or fewer, so 1000 iterations is probably not more than 10,000 generations. That should not take several hours to run. The code looks reasonable enough to me, so I assume this is just Python being Python.
- jphoward 6y agoMy understanding is Conway's game of life can be done by simply convolving a 3x3 array of all ones (except a central 0) through every pixel, and then looking at the results of that convolution to see if the pixel is dead or alive, e.g. https://stackoverflow.com/questions/46196346/why-does-my-game-of-life-simulation-slow-down-to-a-crawl-within-seconds-matplot https://stackoverflow.com/questions/46196346/why-does-my-gam... If that's the case, would a nice solution be to model it as a recurrent neural network, e.g. pytorch or jax, with a single convolutional layer, with a single kernel, which you don't backprop to, and then try to minimise to loss with reference to the target image, by backpropagating to the input image? It then becomes highly analogous to Google's deepdream, but instead of optimising the image for the output class, you optimise it to the output image.
- PartiallyTyped 6y agoWhat you are suggesting is the idea behind StyleTransfer. Given two images, A, B, and a neural network F, you repeatedly modify B using ∂ L(F(A),F(B))/∂B, where L is the loss function, A contains the style and B is the input image.
- andersource 6y agoThat's an interesting approach. The problem is that the function to be applied after the convolution is binary, hence not differentiable. You could replace it with a soft variation, my (wild) guess is it would still be difficult to converge: * If the transitions are too sharp it will behave like the stepwise, non-differentiable original * If the transitions are too soft, the optimization will converge to some middle-state compromise that will not behave as desired when binarized But that's just speculation. Also interesting to note that in the very relevant Kaggle competition [0], top solutions don't mention differentiable approaches (as far as I've seen, I admit I haven't looked too deeply). [0] https://www.kaggle.com/c/conways-reverse-game-of-life-2020/discussion?sort=votes https://www.kaggle.com/c/conways-reverse-game-of-life-2020/d...
- deleted 6y ago[deleted]
- jpalomaki 6y agoAs a next step: how simple can you make the initial state. Can you have something that occupies much less space, but then grows to something that resembles the target image.
- fxj 6y agoIsn't this the goal of an image compression tool? Can we have efficient lossless compression with GoL? That would work with any data. Would it be better than bzip2 or png?
- cnity 6y agoThis is a fascinating idea. Using some kind of sufficiently chaotic (and deterministic) process shared among two people, one could simply reference a time and region of the state of that process that contains the data to be sent.
- jmiskovic 6y agoThis is same as giving starting digit in π, right? Not usable for compression, and encryption folks would file it under security-by-obscurity.
- npteljes 6y agoThis is I think what cryptographic hashes are meant to achieve.
- PartiallyTyped 6y agoThis is part of modern encryption. To be more specific, we have blocks and a deterministic cryptographically secure rng, we seed the rng with a public key that is broadcasted, we then encrypt blocks and then combine them together with the number produced by the rng and create the next block of encrypted data. You may be wondering, why do we even do this? The answer is simple, "the image is encrypted, but everyone can see the penguin". In a less cryptic manner, encrypting blocks simply maps them from one space to another, but is a reversible operation and, as any function does, is deterministic and returns the exact same value every time. The consequence of this determinism, is that identical blocks will always produce the same value and thus, the content is still somewhat visible and in some cases it could leak information. By combining blocks together along with a PRNG, we hide the mapping by requiring that the recipient solves the first block before decrypting further data and we don't end up leaking information.
- matsemann 6y agoGotta be used for some capture-the-flag or so, where after running it a clue to the next step is revealed. I also wonder how effective this would be as a compression algorithm (just for the fun of it). Are the black&white spots too noisily distributed to make it compressable, or better than the resulting image after running GoL? Also interesting that so little data is needed for my brain to understand it's a picture of the David statue.
- alpaca128 6y ago> I also wonder how effective this would be as a compression algorithm My guess is it would be the opposite of compression in many cases, due to the number of required cells you need to store. Using weird, creative ways of encoding data tends to be bad for compression, and in the very best case you'd have something that competes with JPEG but is much slower. It's an enticing idea, just like that concept of encoding arbitrary data by looking for the exact same bit pattern in decimal places of Pi and then storing that position. But reality is often disappointing, and it doesn't really work because more often than not you'll need more space to store the decimal position than the original information.
- davguerrero 6y agoThis could be useful using least significant bit steganography to embed the start state and maybe a QR code as the end state, or something else able to withstand the noisy output.
- ismail261 6y agohttps://bit.ly/3qq4iAX https://bit.ly/3qq4iAX
- andersource 6y agoKaggle recently hosted a very relevant competition - "Conway's Reverse Game of Life" [0]. A write-up of the 1st place might be an interesting read [1]. [0] https://www.kaggle.com/c/conways-reverse-game-of-life-2020/overview https://www.kaggle.com/c/conways-reverse-game-of-life-2020/o... [1] https://www.kaggle.com/c/conways-reverse-game-of-life-2020/discussion/200980 https://www.kaggle.com/c/conways-reverse-game-of-life-2020/d...
- bondarchuk 6y agoVery nice! Some states have multiple ancestors, some have none, so these are "dead ends" when going backwards. But when you are just looking for an approximation of the final state, as in TFA, you can probably accept quite some perturbation, which could make it significantly easier to go backwards in a naive way and sometimes miss a few cells in the process.
- andersource 6y agoYeah, I think it's very interesting because there's a lot of freedom in measuring the similarity and also other aspects of the process, for example optimizing for a "simple" starting configuration as mentioned in other comments.
- UncleOxidant 6y ago> Some states have multiple ancestors, some have none Yeah, this is what I didn't understand about that particular Kaggle competition. It doesn't seem possible that you could learn some general set of rules that would allow you to predict previous states with much accuracy.
- UncleOxidant 6y agoI read the writeup where someone applied a genetic algorithm to this problem and I guess what I found disappointing was that it wasn't a general solution that could learn any general cases or rules, it was just very specific for each example provided. It's not like you could train it on a set of examples and then give it a new example and it would be able to do it any quicker or more accurately.
- montebicyclelo 6y agoI did the same thing, but with gradient descent. You can create a soft version of the game of life, that is differentiable. Here is my messy collab notebook: [1] [1] https://colab.research.google.com/drive/12CO3Y0JgCd3DVnQeNSB3J8WaZGAVo0Ln?usp=sharing https://colab.research.google.com/drive/12CO3Y0JgCd3DVnQeNSB... Edit: only 1 step though, not 4, as in the OP. I couldn't get my differentiable version to converge more than 1 step into the past.
- montebicyclelo 6y agoNote, skip to the bottom to see the resulting plots. Here gradient descent is used to try and predict random game of life games [1] [1] https://colab.research.google.com/drive/1NKWRarxM-ar18x1ON71Aji2y_t5zHZQJ?usp=sharing https://colab.research.google.com/drive/1NKWRarxM-ar18x1ON71...
- hardmath123 6y agoSee also, a post from mid-2020 that does something similar with a "softened" Life: http://hardmath123.github.io/conways-gradient.html http://hardmath123.github.io/conways-gradient.html
- montebicyclelo 6y agoThat's a really nice write up. It's insane how similar our approaches are. Could it be a case of [1] (but on a non grand scale) :P? I can list my sources of inspiration: [2] [3] [4]. I also tried training convolutional networks, using the soft life set-up, but failed to get them to converge. [1] https://en.wikipedia.org/wiki/Multiple_discovery https://en.wikipedia.org/wiki/Multiple_discovery [2] https://kevingal.com/blog/mona-lisa-gol.html https://kevingal.com/blog/mona-lisa-gol.html [3] https://arxiv.org/abs/1910.00935 https://arxiv.org/abs/1910.00935 [4] https://nicholasrui.com/2017/12/18/convolutions-and-the-game-of-life/ https://nicholasrui.com/2017/12/18/convolutions-and-the-game...
- UncleOxidant 6y ago> I also tried training convolutional networks, using the soft life set-up, but failed to get them to converge. Do you have any idea why that might be? It seems like convolution would be a natural for this problem.
- lnyan 6y agoA similar post can be found here (2020, implemented with backsearch): https://news.ycombinator.com/item?id=22552006 https://news.ycombinator.com/item?id=22552006 https://kevingal.com/blog/mona-lisa-gol.html https://kevingal.com/blog/mona-lisa-gol.html
- ineiti 6y agoDid you consider something like the following to speed up the calculation? This method can go forward _really_ fast. Not sur e if it can also go backward... https://pzemtsov.github.io/2015/04/24/game-of-life-hash-tables-and-hash-codes.html https://pzemtsov.github.io/2015/04/24/game-of-life-hash-tabl...
- ineiti 6y agoIn fact I wanted to point to the following... Googling 'hash' put me to the wrong page. https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife
- hardmath123 6y agoSimilar post from mid-2020, using PyTorch instead of JAX, and using a "continuous" (gradient-based) hill-climbing: http://hardmath123.github.io/conways-gradient.html http://hardmath123.github.io/conways-gradient.html And the HN discussion from the time: https://news.ycombinator.com/item?id=23095190 https://news.ycombinator.com/item?id=23095190
- jansan 6y agoIt never fails to amaze me what an infinite number of monkeys with keyboards are able to achieve if you give them enough time :)
- sethbannon 6y agoThis comment may be too meta but this post just made me appreciate Hacker News so much! Classic creative hacking guided by nothing but pure curiosity. Love it!
- atum47 6y agoSome years ago I did a similar thing using genetic algorithm. I was researching it's use in generative art. Here's a video of it in action: https://youtu.be/xgAigVfpIYc https://youtu.be/xgAigVfpIYc
- sjg1729 6y agoThe parenthetical "(Consider a loaf of bread, with each slice being dithered Mona Lisa)." is one of my favorites of any technical article
- lubesGordi 6y agoSo my understanding is that the Game of Life is an undecidable system, so you basically can't write a solvable system of equations that will tell you that your initial state will produce a Mona Lisa. Even after reading the article I don't really understand what he's doing to make this happen. And especially after stating that most states are Garden of Eden states! Can anyone ELI5?
- OscarCunningham 6y agoIt's a decidable problem to evolve the Game of Life fowrard a fixed number of generations. The undecidable thing is to determine the eventual fate of a pattern, e.g. 'does it ever die out completely?'. Even then you can answer this question for large classes of patterns, just not all of them.
- aflag 6y agoMoreover, it is just like any other code you write. It's undecidable whether a function you write will ever stop in the general case, but I'm pretty sure you are able to easily prove most of your functions are going to finish.
- lubesGordi 6y agoOkay well you can 'simulate' the GoL forward and see what it's going to be in a few fixed number of generations. That's basically how you do anything with these undecidable systems. I'm not clear on how he got some state that looks like a Mona Lisa when most or almost all states that look like a Mona Lisa are Garden of Eden states, and then from there worked backwards (I'm not clear on if/how you can go backwards in GoL).
- ris 6y agoI suspect slightly better (or faster) results would be achieved if instead of comparing against a specific dithering pattern nominated by the author, they instead compared downscaled candidate patterns against the greyscale target image.
- beefman 6y agoPreviously: https://news.ycombinator.com/item?id=26374009 https://news.ycombinator.com/item?id=26374009
- fudged71 6y agoA very interesting form of steganography. Has anyone run GOL on "random" noise images to see if they result in any decipherable output? :)