Results 1 to 5 of 5

Thread: Possible to apply Conway's game of life to a compressor?

  1. #1
    Member
    Join Date
    Aug 2016
    Location
    Lisbon
    Posts
    19
    Thanks
    4
    Thanked 8 Times in 8 Posts

    Possible to apply Conway's game of life to a compressor?

    The idea came to me long ago, kind of guessing or inventing new ways to find hidden patterns in a streams of data.
    Sure you all know the game of life, if not, google it and you will recognise by the image.

    I'll try to explain:

    We can represent any data as a matrix. The game of life (GoL) is a matrix of data like in 1 and 0s.
    Its rules can be tweaked as in several games variations, so different configs to be tested, or maybe bruteforce to find the better one.

    I would think that the game is (kind of) bidirectional in its progress. Like an existing snapshot or turn could be retrieved with computations.
    Let's say we have a matrix representing the data to be compressed. Then applying the GoL for several turns we can represent that data as a matrix that has lot more of either 1 or 0s, which should be compressed more than the original source.

    Think about the data to store the initial position of this matrix (compressed?) vs the bytes to store iteration 1k or whatever:
    http://pmav.eu/stuff/javascript-game-of-life-v3.1.1/

    Key point here is to achieve the GoL bidirectional, saving the parameters and applying it.
    At later stage maybe adding data at a given step to produce the desired output.
    So the other hard thing is to get the initial state (or any other state that leads to that same data). Reversing the GoL may give some possible branches or states, the more iterations, the more possibilities, up to some point of non computability due to the possible combinations, maybe making this idea unfeasible.

    What do you think?

  2. #2
    Member
    Join Date
    Mar 2016
    Location
    USA
    Posts
    49
    Thanks
    7
    Thanked 23 Times in 15 Posts
    Conway's Game of Life is not reversible (you can easily see this as many configurations end up evaporating). Sure, the later iterations will compress better, but that is because the actual information content is lost. There do exist reversible cellular automata, but they tend to be trivial and probably wouldn't reorder data in a way that would help with compression.

  3. #3
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    581
    Thanks
    225
    Thanked 218 Times in 103 Posts
    As the information of the previous rounds is lost, I agree - compression is possible in most cases, but retrieving the initial state is not easy, boiling down to some brute force algorithm trying every initial state.

    On a side note, however, Jon Sneyers, the author of FLIF, posted something similar on the Gitter chat about other cellular automata (1D + time => 2D image) a while ago. These are very similar to the Game of Life (which is a 2D + time cellular automaton) except that the information about previous states is preserved in the image. Apparently MANIAC, the compression technique used in FLIF, learns their rules and is able to compress them very well:

    Code:
    -rw-rw-r-- 1 jon jon     172 Jun 16 21:40 ca_1000rows.flif
    -rw-rw-r-- 1 jon jon   80830 Jun 16 21:40 ca_1000rows.png
    -rw-rw-r-- 1 jon jon   81668 Jun 17 07:37 ca_1000rows.webp
    -rw-rw-r-- 1 jon jon     486 Jun 16 21:33 ca_2000rows.flif
    -rw-rw-r-- 1 jon jon  318854 Jun 16 21:37 ca_2000rows.png
    -rw-rw-r-- 1 jon jon  318626 Jun 17 07:36 ca_2000rows.webp
    -rw-rw-r-- 1 jon jon    1741 Jun 16 21:43 ca_4000rows.flif
    -rw-rw-r-- 1 jon jon 1270598 Jun 16 21:38 ca_4000rows.png
    -rw-rw-r-- 1 jon jon 1260702 Jun 17 07:36 ca_4000rows.webp
    -rw-rw-r-- 1 jon jon    3833 Jun 16 21:47 ca_6000rows.flif
    -rw-rw-r-- 1 jon jon 2856266 Jun 16 21:46 ca_6000rows.png
    -rw-rw-r-- 1 jon jon 2830380 Jun 17 07:36 ca_6000rows.webp
    http://schnaader.info
    Damn kids. They're all alike.

  4. #4
    Member
    Join Date
    Mar 2016
    Location
    USA
    Posts
    49
    Thanks
    7
    Thanked 23 Times in 15 Posts
    Quote Originally Posted by schnaader View Post
    As the information of the previous rounds is lost, I agree - compression is possible in most cases, but retrieving the initial state is not easy, boiling down to some brute force algorithm trying every initial state.
    And even doing it this way, you'd need to store extra information to differentiate the possible different initial states, which would take away from your savings from the CA encoding.

  5. #5
    Member
    Join Date
    Aug 2016
    Location
    Lisbon
    Posts
    19
    Thanks
    4
    Thanked 8 Times in 8 Posts
    Quote Originally Posted by MegaByte View Post
    There do exist reversible cellular automata
    Can anyone point me to sources/papers of this?

    I think that different inputs could get the same output and vice versa, so there is no need to differentiate exactly which one it was while we have the correct data.

    Let me example with the chess board instead the conway board, sure we can agree the similarities.
    The knight is at position xy as column, row. To reach there it could have been in a max of 4 previous positions. So we have a finite small set of possibilities against infinite.
    They grow exponentially, so the iterations would be just a few, maybe half dozen at most. But the compression level should be good if we choose a path were the pieces are getting 'cleared' each round.

    In a conway board, we check as all the ways that we could get into the current position.

    With all the combinations of these "brute force" possibilities, we can get the initial data. It should be easy as using a hash (in the sense of md5 and alike) or any other way of checking the initial data.

Similar Threads

  1. .rpk Game Archive
    By Cat32 in forum Data Compression
    Replies: 1
    Last Post: 14th September 2015, 04:43
  2. My new Game Repacks - High Compression
    By hdneo in forum Data Compression
    Replies: 9
    Last Post: 10th July 2014, 23:24
  3. Game.Repack.Maker
    By Shamil Khan in forum The Off-Topic Lounge
    Replies: 4
    Last Post: 1st August 2013, 04:17
  4. Replies: 6
    Last Post: 24th April 2012, 14:50
  5. Bit guessing game
    By Shelwien in forum Data Compression
    Replies: 11
    Last Post: 24th November 2009, 02:22

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •