Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
Programming Games

'Tetris' Recreated In Conway's 'Game of Life' (stackexchange.com) 87

In 1970 mathematician John Conway created rules for the "Game of Life," a now famous "zero-player game" where a grid of cells evolves (following Conway's rules) from an initial state proposed by the player. In 2013 someone challenged readers of StackExchange's "Programming Puzzles & Code Golf" section to devise an initial state "that will allow for the playing of a game of Tetris."

An anonymous Slashdot reader reports that "This challenge sat around, gathering upvotes but no answer, for four years. Then, it was answered." Citing the work of seven contributors, a massive six-part response says their solution took one and a half years to create, and "began as a quest but ended as an odyssey." The team created their own assembly language, known as QFTASM (Quest for Tetris Assembly) for use within Conway's mathematical universe, and then also designed their own processor architecture, and eventually even a higher-level language that they named COGOL. Their StackExchange response includes a link to all of their code on GitHub, as well as to a page where you can run the code online.

One StackExchange reader hailed the achievement as "the single greatest thing I've ever scrolled through while understanding very little."
This discussion has been archived. No new comments can be posted.

'Tetris' Recreated In Conway's 'Game of Life'

Comments Filter:
  • by ShanghaiBill ( 739463 ) on Saturday September 23, 2017 @07:53PM (#55252285)

    Conway's game of Life has been shown to be Turing Complete [wikipedia.org], so it can do anything any computer can do. You can use glider generators to construct a NAND gate, and then use NAND gates to construct any logic circuit, including a CPU.

    Someone should write a compiler to run arbitrary software inside the automaton system.

    • Someone should write a compiler to run arbitrary software inside the automaton system

      ...maybe you could run a Game of Life in it? You know, just for fun.

      • by thinkwaitfast ( 4150389 ) on Saturday September 23, 2017 @10:49PM (#55252805)
        It was done a few years ago. Very cool stuff. One of the coolest things I've ever seen.

        https://www.youtube.com/watch?v=xP5-iIeKXE8

        • Re: (Score:2, Funny)

          by Anonymous Coward

          No, no. They need to run The Game Of Life [hasbro.com].

        • by Tablizer ( 95088 )

          I'd like to see it nested a few times. Turtles allll the way down.

          • hat would take a lot of ram and a fast computer if you wanted to see any movement at the top scale.hmmm, maybe that's the reason the universe is so large, just to be able to run a few brains...
      • Yes, but requires a super resolution of many cells and many generations to represent one logic gate. ( I dont know if anyone has constructed a minimum size configuration and/or proved its the smallest.) It could be that universe is a simulation in a computer with much higher temporal and spatial resolution than our universe. The physics only need to simulated to a resolution of Planck's quantum of action. Beneath that we couldnt tell. The size of the computer in other universe could be vastly larger than o
    • They're already working on a gcc backend, so the languages GCC can compile could be compiled to run on their architecture.

    • You can use glider generators to construct a NAND gate, and then use NAND gates to construct any logic circuit, including a CPU.

      You should read the stack exchange post. They go through all of that including wires, delays, muxes, ROMs, latches, with those you then make RAM, ALUs, and finished with an entire RISC processor.

    • by tomxor ( 2379126 )

      Someone should write a compiler to run arbitrary software inside the automaton system.

      That's exactly what they did do... built up layers of abstraction, it's an interesting project.

      The building blocks of our logic gates (transistors) are a particular kind of abstraction that we don't usually have to delve into with electronics, and even than are logically simple and more statistically squishy inside... whereas with CA there is none of the same science, it's a strange logical challenge to built a transistor, a transistor might not even be a particularly productive abstraction to make - buildi

      • by mikael ( 484 )

        They made all the standard logic gates, but implementing a NOT with CA is tricky because there is no signal coming down. If a glider is the 1 bit, then no glider is the 0 bit, so you need something that acts as a timer and sends out a glider if no bit is received.

        There were some designs for hardware that made use of incremental changes or even asychronous updates and thus eliminate the need for clock lines.

  • "I Hate Nerds!" - Ogre
  • by schweini ( 607711 ) on Saturday September 23, 2017 @08:04PM (#55252317)
    I ran the code online, but can't find a way to see the lowest level of their stack, where the GoL is actually running?
    I'd also love to see their VM running!
    • by Urist McSlashdot ( 4666661 ) on Sunday September 24, 2017 @12:32AM (#55253009)
      https://sourceforge.net/projec... [sourceforge.net] Golly is an excellent resource for exploring the GoL. Download it, and go to patterns > hashlife > metapixel to find some implementations of GoL as calculated by GoL glider NAND gates and various derived structures. It's fascinating to watch unfold and frankly beyond my comprehension.
    • by Anonymous Coward

      Well, the problem is the scale. The final Tetris running Game of Life has a bounding box of 2,940,928 x 10,407,936 cells. And it's just a regular grid of OTCA metapixels. Basically looking at the low level GoL is like looking at a microprocessor at the atom level.

      You can see an OTCA cell working here:

      http://www.conwaylife.com/wiki/OTCA_metapixel

      The whole thing is just this multiplied by 1,221,941 OTCA cells being actively used in the final version.

    • by tomxor ( 2379126 )
      I'd imagine it runs pretty slow considering just how large it would be, but I know some CA engines have some pretty good optimisations for hashing out (literally) redundancy that would be very applicable with all the likely repetitions that build up the logic.
      • by mikael ( 484 )

        It's interesting to see the use of hashing to optimize the computations of the Life grid, especially the metapixels (which are like FPGA cells). Which basically reduces everything down to lookup tables.

        • Running it in Golly on my PC right now it maxes out at 4-5 million generations/second with a step size of 8^6, periodically slowing down presumably to hash some new cell configuration. It uses ~550MB of RAM. I've run the other metapixel patterns that come with Golly, but this one is mind blowing to see.

          Ironically, there's not much to look at, since there doesn't seem to be a display of the Tetris board built in.

  • by Etcetera ( 14711 ) on Saturday September 23, 2017 @08:45PM (#55252445) Homepage

    https://xkcd.com/505/ [xkcd.com]

    Conway's Game of Life is indeed Turing Complete (see also: A New Kind of Science [amazon.com]) and this is indeed pretty awesome that they were able to do this...

    • Yes, I took a look at TFA and although they didn't go about simulating the "universe" from basic laws (not that we have a theory of everything yet :) they DID start at the (sort of) particle level using something called OTCA megapixels. From these they built the fundamental logic gates and from that a (simple?) computer and from that a (simple?) language and (simple?) compiler and then wrote and compiled and ran a (simple, no colors or audio?) Tetris program!

      So if anyone tells you they don't believe that w

    • If you've read and understand where Wolfram is going in NKS, you should check out this video [youtube.com]. It's the most interesting talk I've ever seen. Yeah, he talks about himself a lot, but the last third gets very interesting.
  • This is the next step on the career ladder for enterprising redstone engineers everywhere. Anyone who can design a CPU in Minecraft should be able to do it in GoL, if they have all the extensions. The lack of a NOT gate is a bit of a pisser, but can be worked around. It seems to me if you really want a NOT gate, you can use an XOR gate and constantly pull one line high. Maybe they don't have any ways to constantly pull a line high either.

    Seriously though, I would not be surprised at all if the major contrib

  • OK, time for the next challenge. Once GCC is done, port Doom to the GoL, it is open sourced so.... Since speed is indeed an issue, part 2 of this challenge is to compile it to an FPGA so it runs at a decent speed.
    Please note there is no rush for this challenge, next week will be just fine. :)

  • I thought using the 7 standard pieces in a Tetris clone was ruled in 2012 to be a copyright infringement [slashdot.org].

  • > 'Tetris' Recreated In Conway's 'Game of Life'

    OK, it is late, but I have read that a dozen times now and I don't quite understand. "Recreated" belongs to one or possibly more than one Tetris? What kind of English is that? Are they trying to make a contraction like "Tetris is" by adding a trailing apostrophe?

    • >"OK, it is late, but I have read that a dozen times now and I don't quite understand."

      And now I see the problem- the freaky font blended the leading apostrophe into the "T." I wish I could post a screenshot of it; it really is quite amazing.

      I need to go to bed :)

  • ..Then we can reinvent the Web so we can make use of sockets and application streams as Web services instead of natively compiled applications and single points of failure. So much ad-hoc stuff out there right now!
  • Does anyone else remember the game "Sharks and Fish", source came out in Byte Magazine I think back in the 80's. Very interesting, and turns out it replicates the ebb and flow of the populations of lynx and rabbits as tracked by Canadian Fur Company trapping statistics back in the 1700's :-)

    Much more interesting than Conway's Life, I always thought. I hacked it, of course, to add plankton, whales, porpoises, and things got quite interesting then :-)

    • by Boronx ( 228853 )

      There's an old game called "matrem" out there that can create those graphs pretty well, I think. It's lions eating cows.

    • One of the demo programs on the Sinclair Spectrum was Foxes & Rabbits. Sounds like a similar concept.

  • by Anonymous Coward

    I couldn't figure out how to actually move or rotate the blocks. Arrow keys, WASD,...? No effect. So the blocks just seem to scroll down in the middle and stack up.

    The authors don't seem to mention the controls, except something about "manually editing the contents of RAM address".... ??

    Doesn't "allow for the playing of a game of Tetris" mean that you can actually, y'know, *play* Tetris?

    • by Cederic ( 9623 )

      The controls are that you enter a value into a specific RAM address. The game reads then clears that value, and moves or rotates the block based on the value.

      Clunky, but somewhat easier than writing a keyboard driver.

  • These guys made something awesome, but didn't upload a youtube video of it.
  • Can't systemd play tetis and life already?

    well someone had to say it.

  • This is really awesome. Now that you are started, could you switch to the Game of Half-Life? Some people are waiting.

"Never ascribe to malice that which is caused by greed and ignorance." -- Cal Keegan

Working...