Build a working game of Tetris in Conway's Game of Life

  • Here is a theoretical question - one that doesn't afford an easy answer in any case, not even the trivial one.



    In Conway's Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.



    Your task is to build a cellular automaton using the rules of Conway's game of life that will allow for the playing of a game of Tetris.



    Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automaton. The displayed result must visibly resemble an actual Tetris grid.



    Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):




    • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.


    • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.


    • Fastest execution — the fewest generations to advance one tick in the simulation wins.


    • Initial live cell count — smaller count wins.


    • First to post — earlier post wins.



    Does "demonstrably working example" mean something that runs in a matter of hours, or something that can be proven correct even though it would take until the heat death of the universe to play?

    @PeterTaylor I'd say, given the solution would probably be slower than the decay of electrons, I'd say a mathematical-grade proof is required.

    @PeterTaylor and JanDvorak Even a proof would be extremely complex. It is difficult to *proove* that any tetris program in any (much more suitable than GoL) high level programming language works as intended - even more if you have to construct something out of more elementary building blocks.

    I'd already be impressed if anyone can show me a single tetris block which rotates cw and ccw within a defined number of steps. (not the simple four tiles block ;-))

    @Howard, I think a proof would have to be on the basis of "Here's a program you can examine; here's a compiler which I can prove correct".

    A Bitmap Display has been created before. Anybody who gives this a attempt might want to use it.

    @PeterTaylor: The latter would be fine.

    I'm pretty sure something like this is possible and playable. It's just that very few people have the expertise to be able to program what is probably one of the more esoteric "assembly languages" in the world.

    Do you actually have to be able to *see* the block rotating and falling etc., on the game of life grid, or is it enough just to have it logically represented somehow? If the latter then this task isn't impossibly hard - you can just take one of the existing Turing machine implementations, write a compiler for it (if that hasn't been done already), then code up Tetris in the language of your choice. But if the former then, well, I guess it's possible, but it would be a *huge* task for anyone to attempt.

    @copy Oh my... I wish I could understand this.

    @Nathaniel Preferably it would be a visible demonstration, since that's what the metapixels are for.

    @JanDvorak and PeterTaylor While it'll probably take a few thousand generations for the solution to complete a single iteration, it should be fairly easy to make it go by quickly. Golly and most other modern cellular automaton simulators have some form of speed control; in addition, since the solution will likely be repetitive, it'll cooperate nicely with Golly's Hashlife algorithm (ensuring that it'll run smoothly at any reasonably fast speed). Point being that we'll be able to see for ourselves that it works.

    Only a few thousand? Sounds more like it would take a few million.

    The OTCA metapixel has a period of 35328; the tetris unit cell will be significantly less complicated than it (can't go into as much detail as I'd like to in 600 chars), so taking into consideration that Hashlife likes powers of two, I'd aim for around 2^14 gens. Also note that using a metapixel as opposed to a central processor of some sort will make features like rotation virtually impossible. [disclaimer: I may or may not be trying my hand at a solution]

    oh, but if the OTCA metapixel's p184 clock is used, it may be easier to keep the same timing. Not sure yet.

    @M.I.Wright If you do end up going all-in for a solution, good luck to you. We all want to see you succeed.

    @M.I Wright: using a central processor is fine, but preferably the result would be visible on the screen.

    Of course! For a display I was thinking of giving data to this thing, which I think @copy posted up above if you want to see it in action... I've already started on a metapixel, though [is it fine if I submit two? :P]

    You can submit as many as you want; this question has gone unanswered for two years since I asked it.

    @ghosts_in_the_code nope, just hit an unexpected roadblock; the metapixel was *technically* finished, but it didn't work at all since the whole idea of a metapixel is that it works independently. Tetris pieces, however, take up more than one pixel, so they need to be synchronized. I'm still working out the kinks in a new idea - I can actually post a diagram+some info on how it'd work if you're interested.

    @M.I.Wright I'm not personally interested (neither am I capable) but I would recommend posting your progress anyway, because 1. People can help you find flaws in it. 2. Someone else may be able to solve it by building on your method.

    @M.I.Wright the OCTA metapixel's state change only depends on its eight neighbors. a tetris cell's state change depends on its whole row, among other things. even ignoring control input (assume we just need to simulate a step of a tetris field), the tetris metapixel is going to be much more complex than a game-of-life metapixel

    @JoeZ. this challenge might be too hard. Perhaps consider reposting something much much simpler? A tic tac toe game in life might be plausible for multiple people here to accomplish in different ways.

    I'll keep this one up, but I could definitely post a simpler one.

    @Sparr exactly! That's why I ditched the metapixel and am working on my new idea (which i'll get around to summarizing here sooner or later). I also kinda think that a tic tac toe game would be on about the same level of difficulty as this challenge.

  • PhiNotPi

    PhiNotPi Correct answer

    4 years ago

    This began as a quest but ended as an odyssey.


    Quest for Tetris Processor, 2,940,928 x 10,295,296


    The pattern file, in all its glory, can be found here, viewable in-browser here.


    This project is the culmination of the efforts of many users over the course of the past 1 & 1/2 years. Although the composition of the team has varied over time, the participants as of writing are the following:



    We would also like to extend our thanks to 7H3_H4CK3R, Conor O'Brien, and the many other users who have put effort into solving this challenge.


    Due to the unprecedented scope of this collaboration, this answer is split in parts across multiple answers written by the members of this team. Each member will write about specific sub-topics, roughly corresponding to the areas of the project in which they were most involved.


    Please distribute any upvotes or bounties across all members of the team.


    Table of Contents



    1. Overview

    2. Metapixels and VarLife

    3. Hardware

    4. QFTASM and Cogol

    5. Assembly, Translation, and the Future

    6. New Language and Compiler


    Also consider checking out our GitHub organization where we've put all of the code we've written as part of our solution. Questions can be directed to our development chatroom.




    Part 1: Overview


    The underlying idea of this project is abstraction. Rather than develop a Tetris game in Life directly, we slowly ratcheted up the abstraction in a series of steps. At each layer, we get further away from the difficulties of Life and closer to the construction of a computer that is as easy to program as any other.


    First, we used OTCA metapixels as the foundation of our computer. These metapixels are capable of emulating any "life-like" rule. Wireworld and the Wireworld computer served as important sources of inspiration for this project, so we sought to create a similar constuction with metapixels. Although it is not possible to emulate Wireworld with OTCA metapixels, it is possible to assign different metapixels different rules and to build metapixel arrangements that function similarly to wires.


    The next step was to construct a variety of fundamental logic gates to serve as the basis for the computer. Already at this stage we are dealing with concepts similar to real-world processor design. Here is an example of an OR gate, each cell in this image is actually an entire OTCA metapixel. You can see "electrons" (each representing a single bit of data) enter and leave the gate. You can also see all of the different metapixel types that we used in our computer: B/S as the black background, B1/S in blue, B2/S in green, and B12/S1 in red.


    image


    From here we developed an architecture for our processor. We spent significant effort on designing an architecture that was both as non-esoteric and as easily-implementable as possible. Whereas the Wireworld computer used a rudimentary transport-triggered architecture, this project uses a much more flexible RISC architecture complete with multiple opcodes and addressing modes. We created an assembly language, known as QFTASM (Quest for Tetris Assembly), which guided the construction of our processor.


    Our computer is also asynchronous, meaning that there is no global clock controlling the computer. Rather, the data is accompanied by a clock signal as it flows around the computer, which means we only need to focus on local but not global timings of the computer.


    Here is an illustration of our processor architecture:


    image


    From here it is just a matter of implementing Tetris on the computer. To help accomplish this, we have worked on multiple methods of compiling higher-level language to QFTASM. We have a basic language called Cogol, a second, more advanced language under development, and finally we have an under-construction GCC backend. The current Tetris program was written in / compiled from Cogol.


    Once the final Tetris QFTASM code was generated, the final steps were to assemble from this code to corresponding ROM, and then from metapixels to the underlying Game of Life, completing our construction.


    Running Tetris


    For those who wish to play Tetris without messing around with the computer, you can run the Tetris source code on the QFTASM interpreter. Set the RAM display addresses to 3-32 to view the entire game. Here is a permalink for convenience: Tetris in QFTASM.


    Game features:



    • All 7 tetrominoes

    • Movement, rotation, soft drops

    • Line clears and scoring

    • Preview piece

    • Player inputs inject randomness


    Display


    Our computer represents the Tetris board as a grid within its memory. Addresses 10-31 display the board, addresses 5-8 display the preview piece, and address 3 contains the score.


    Input


    Input to the game is performed by manually editing the contents of RAM address 1. Using the QFTASM interpreter, this means performing direct writes to address 1. Look for "Direct write to RAM" on the interpreter's page. Each move only requires editing a single bit of RAM, and this input register is automatically cleared after the input event has been read.


    value     motion
    1 counterclockwise rotation
    2 left
    4 down (soft drop)
    8 right
    16 clockwise rotation

    Scoring system


    You get a bonus for clearing multiple lines in a single turn.


    1 row    =  1 point
    2 rows = 2 points
    3 rows = 4 points
    4 rows = 8 points

    First of all +1, because this is an insanely awesome achievement (especially since you built a computer in game of life, rather than just tetris). Secondly, how fast is the computer and how fast is the tetris game? Is it even remotely playable? (again: this is awesome)

    This... this is completely insane. +1 to all answers right away.

    A warning for anyone wanting to distribute small bounties over the answers: you have to double your bounty amount each time (until you hit 500), so a single person can't give the same amount to every answer unless that amount is 500 rep.

    Wow.. just.. wow.. WELL DONE

    You guys built a processor in Game of Life... Wow. Holy ****.

    YOU DID IT...I don't know what to say...+1

    This is the single greatest thing I've ever scrolled through while understanding very little.

    I've never used the term "mindblowing" before but there's a first time for everything.... Can't even decide which part to single out as most impressive. The thought process, documentation, architecture, implementation, tools, everything is just amazing. Was a *really* interesting read. A big thank you for documenting all of this so well and a standing ovation for your efforts!

    While I have to congratulate the effort, I have to say this methodology is sort of like deciding to reinvent the wheel by gluing a bunch of tiny little modded wheels together lol. Suppose I don't have much room to talk here since I never finished the version I wanted to submit, though. Good work :)

    It's too bad there's no nice interface to the full GoL version. Maybe someone can figure out how to easily visualize the memory in Golly, and maybe figure out how to set RAM values.

    Also, the current version (http://play.starmaninnovations.com/qftasm/#jllHdnBGSP) has a bug - if you move your piece left/right until it collides with the wall, it sticks there (!) as if it had been dropped (but hanging in midair): https://i.stack.imgur.com/vYTsL.png. Since it's QFTASM though I guess this should be easy to fix!

    @nneonneo Thanks for the bug report, I will look into that. Shouldn't be too big of a fix.

    2,940,928 x 10,407,936? That doesn't sound codegolf like. I was expecting `FS¿⁼ι/↓¶/↘ι` or some equally readable insanity :P

    I guess that means ... you get the open bounty of 500 reputation points! Congratulations! Go ahead and pick another problem, and in March 2019, you'll be able to get another 500 reputation points. Keep up the good work!

    @nneonneo Fixed the bug: it didn't correctly reset the piece's column position after a failed collision check. I've adjusted the score accordingly.

    Oh shoot, since people are taking note of the fact that you've really managed to create a full-fledged computer, I think it's also worth mentioning that this actually is not the first such computer GoL has seen. That title would rightfully go to Adam P. Goucher's 2009 metacell-less universal computer+constructor -- although your 'QFTUC' is by a long shot the first to actually support a viable program :P (not to mention a real human-readable compiled language, amazing!!)

    Is there a way to graphically view the Life simulation itself? I realize it would need to execute so fast it would basically be a blur, but I'd still love to be able to watch in spite of that. It isn't quite the same that I *know* that this is GoL, but can't actually *see* it. (If this is in fact possible and I'm just not seeing how, my apologies; what am I missing?)

    @PhiNotPi Should this CW answer be excluded from future bounties? Otherwise you will receive double since you have one of the other answers, too

    So now to solve other PPCG puzzles using QFTASM or the higher-level languages?

    Obligatory XKCD. Congratulations on taking less time than "eternity" to solve this one. :^D

    Jesus christ you designed a entire programming language and CPU in conway's game of life. I ... what even is this :o

    Can this kind of thing be submitted for a doctoral thesis lol?

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM