[HN Gopher] Finding Mona Lisa in the Game of Life
___________________________________________________________________
Finding Mona Lisa in the Game of Life
Author : mseri
Score : 351 points
Date : 2021-03-08 11:02 UTC (11 hours ago)
(HTM) web link (avinayak.github.io)
(TXT) w3m dump (avinayak.github.io)
| jansan wrote:
| It never fails to amaze me what an infinite number of monkeys
| with keyboards are able to achieve if you give them enough time
| :)
| enriquto wrote:
| > 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?
| xaedes wrote:
| Regarding 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...
|
| > 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 us +- 2.64 us
| 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 wrote:
| Not 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.
| zbendefy wrote:
| probably 99% of time shuffling data around, 1% of time
| calculating
| Marazan wrote:
| That's not 1000 iterations of GoL. That's a thousand iterations
| of trying to find the best seed.
| enriquto wrote:
| I stand corrected. The numbers were too way off to make sense
| at all!
| [deleted]
| 7373737373 wrote:
| For a similar challenge: https://en.wikipedia.org/wiki/Proof_game
| xirbeosbwo1234 wrote:
| This 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.
| davguerrero wrote:
| This 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.
| lubesGordi wrote:
| So 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 wrote:
| It'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 wrote:
| Moreover, 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 wrote:
| Okay 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 wrote:
| I 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.
| sethbannon wrote:
| This 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!
| jphoward wrote:
| My 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-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.
| [deleted]
| PartiallyTyped wrote:
| What 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 wrote:
| That'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/d...
| jpalomaki wrote:
| As 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 wrote:
| Isn'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 wrote:
| This 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.
| npteljes wrote:
| This is I think what cryptographic hashes are meant to
| achieve.
| PartiallyTyped wrote:
| This 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.
| jmiskovic wrote:
| This is same as giving starting digit in p, right? Not
| usable for compression, and encryption folks would file it
| under security-by-obscurity.
| shawnz wrote:
| Imagine the "sufficiently chaotic process" is simply
| listing out all the possible data sequences in order, for
| example 0 1 10 11 100 etc.
|
| Then, "referencing a region" of the state is basically the
| same as just giving the value. The nth value is just n
| itself.
|
| So clearly that doesn't give you any advantage. Why would
| randomizing the data sequences make it any more efficient
| on average?
|
| Although if you specifically choose the ordering of the
| sequences so that common sequences are easy to represent
| and uncommon sequences are hard to represent, then you
| basically have Huffman coding/arithmetic coding.
| cnity wrote:
| Because you can bias the process to be more likely to
| represent data relevant to your domain.
|
| Note: I'm not in any way a compression expert, so while
| it may be obvious to you/others, it's a little
| interesting for me to think of compression in this way
| (sending parameters to a shared process, instead of
| sharing the raw data).
| 1-more wrote:
| I've often thought of that, a compression thing that says
| "start with this small board state, run for so many
| generations, go sample this area of the board, and maybe
| apply this run-length-encoded binary patch" but computing
| that initial state is, uhhhhh, a lot. A huge amount. Too
| freaky. But maybe there's a cellular automaton that is easier
| to run in reverse to find such a thing? This becomes a
| question for the real computer scientists.
| altgoogler wrote:
| The approach described here is very lossy, and very
| inefficient since you have to search a huge number of
| permutations to find reasonable results.
|
| It would be an interesting experiment to implement lossless
| compression, but it likely wouldn't achieve high compression
| ratios or be nearly as efficient as a purpose built
| algorithm.
| jerf wrote:
| The problem in general with this approach is that the amount
| of bits it takes to identify the correct decoded value
| exceeds the amount of bits it takes to simply write down the
| correct encoded value.
|
| People have been proposing similar algorithms for the last
| few decades. It's really become the "Free energy is being
| suppressed by the man!" of compression algorithms. One of the
| more popular is "just identify where your value is in pi!",
| which fails for that reason.
|
| One problem is that in order to analyze such algorithms you
| really need to count your bits carefully. For instance in the
| pi case people sometimes think "well, I just need two
| numbers, the distance into pi and the length", but those "two
| numbers" may need arbitrarily unbounded numbers of bits to
| represent.
|
| GoL has its own problem which is that if you construct a
| "random" state that didn't start "naturally" the odds of it
| being a Garden of Eden state are essentially 1. Can you even
| call it an "image compression" tool when it can't represent
| an image of any pure color _at all_ , let alone in a
| compressed format?
| alpaca128 wrote:
| Exactly, I know first hand that it's easy to believe in
| such admittedly creative ideas. But thinking it through was
| fun and cleared up my misunderstanding; in the end the
| information itself cannot be compressed, one can only
| reduce redundancies. And an arbitrarily chosen algorithm
| tends to do a really bad job with that on average.
| dcanelhas wrote:
| Haha that's really creative though. Makes me wonder if
| there is anything useful "stored" in pi that could be
| represented with, say, 2 64-bit integers.
| klyrs wrote:
| Further "compression" -- you only want the index of the
| first occurrence of a given string. Thus, you create a
| table of offsets for each string length, where index 0 is
| the first unique string of length n, index 1 is the
| second, etc. This allows you to elide the issue that
| indices can be arbitrarily large. Of course, the table is
| hard to compute for large n, and the resulting
| "compression" has indices at worst the size of the
| original data... so it's gonna be super efficient at
| compressing the bits of pi, and no worse than unity on
| average.
| ismail261 wrote:
| https://bit.ly/3qq4iAX
| atum47 wrote:
| Some 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
| sjg1729 wrote:
| The parenthetical "(Consider a loaf of bread, with each slice
| being dithered Mona Lisa)." is one of my favorites of any
| technical article
| matsemann wrote:
| Gotta 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 wrote:
| > 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.
| lnyan wrote:
| A similar post can be found here (2020, implemented with
| backsearch):
|
| https://news.ycombinator.com/item?id=22552006
|
| https://kevingal.com/blog/mona-lisa-gol.html
| andersource wrote:
| Kaggle 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/o...
|
| [1] https://www.kaggle.com/c/conways-reverse-game-of-
| life-2020/d...
| bondarchuk wrote:
| Very 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 wrote:
| Yeah, 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 wrote:
| > 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 wrote:
| I 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.
| adenozine wrote:
| Well, that's sort of the case for genetic algorithms.
|
| You might be aware of genetic programming? There may be
| papers already out there, but the idea is representing a
| programs source as a genome, and then performing the familiar
| processes (mutation, crossover, selection) on those.
|
| Anyhow, that would produce something more general. A genetic
| algorithm is traditionally a single shot thing.
| UncleOxidant wrote:
| > You might be aware of genetic programming?
|
| Actually been playing with Cartesian Genetic Programming
| (CGP) recently.
|
| > Anyhow, that would produce something more general.
|
| Not really, at least as far as I can tell with CGP. I was
| evolving a circuit to solve the 8-bit parity problem (kind
| of the 'Hello world' of CGP - it solves this problem
| surprisingly quickly). There wasn't any way to use that
| information to evolve a circuit to solve the 16-bit parity
| problem - you've gotta start again from scratch. There may
| be some proposed solutions to this kind of issue in CGP -
| I'm still reading papers.
| ineiti wrote:
| Did 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-tabl...
| ineiti wrote:
| In fact I wanted to point to the following... Googling 'hash'
| put me to the wrong page.
|
| https://en.wikipedia.org/wiki/Hashlife
| montebicyclelo wrote:
| I 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/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.
| hardmath123 wrote:
| See also, a post from mid-2020 that does something similar with
| a "softened" Life: http://hardmath123.github.io/conways-
| gradient.html
| montebicyclelo wrote:
| That'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
|
| [2] https://kevingal.com/blog/mona-lisa-gol.html
|
| [3] https://arxiv.org/abs/1910.00935
|
| [4] https://nicholasrui.com/2017/12/18/convolutions-and-the-
| game...
| montebicyclelo wrote:
| Note, 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-
| ar18x1ON71...
| hardmath123 wrote:
| Similar post from mid-2020, using PyTorch instead of JAX, and
| using a "continuous" (gradient-based) hill-climbing:
| http://hardmath123.github.io/conways-gradient.html
|
| And the HN discussion from the time:
| https://news.ycombinator.com/item?id=23095190
___________________________________________________________________
(page generated 2021-03-08 23:00 UTC)