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.
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.
@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.
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.
@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.
@M.I.Wright tic tac toe should be roughly similar to the life metapixel. the result of a TTT game depends on just 9 cells.
Just realised that this doesn't have a winning criterion other than "first to post". Once the first solution is posted, it may lower the barrier to entry and result in more solutions. Maybe it would be worth adding a winning criterion before the first solution comes in. Like starting position that fits in the smallest rectangular area, or fastest run speed in terms of arena ticks. That would allow for a basic first solution using existing components for pixels and logic gates, but still leave the competition open for more innovative customised solutions later.
If it affects your decision on whether to edit in a winning criterion, there's some discussion on meta about this specific challenge.
Erm... How exactly does one provide input to said game? The standard Conway's Game Of Life provides no input other than the start state.
@Pharap As mentioned in the question statement, input is represented by manually changing the state of the automaton at a certain generation.
As of 5:10 this morning (9:10 UTC), this question is the first question in PPCG history to reach 100 votes without getting an answer! Well done everyone.
@SeeOneRhino Would the code written take any input? Otherwise it wouldn't really be a code challenge.
Can you define "Tetris" a bit more? Otherwise I could submit one cell and win, because it *is* tetris, just too small to play.
@SeeOneRhino I'd _assume_ "Tetris" to mean that you construct a metapixel-like thing that can be tiled to make as large of a board as necessary, but you'd need confirmation from OP.
Any valid answer to this will probably become the most upvoted answer on this site.
I am trying to solve this... Now, when I go to bed, I see gliders everywhere, colliding in a giant mess. My sleeps are full of nightmares where pulsating pentadecathlons block my way and Herschels are evolving to absorb me. Please, John Conway, pray for me...
The question says "randomly" generate a piece. Where does one get a source of randomness in CGOL? There's no way to get the current generation or date/time as a seed for a PRNG or anything...
@mbomb007 - take the same approach as many older games do. You have a PRNG with a static seed, and user input is fed to it. This will have the downside that the first piece is always the same. Alternatively, have your user input setup also take a PRNG seed.
@TLW Taking the seed as input is probably the best way to ensure every game can be different.
Jeff Atwood recently retweeted a link to this question: https://twitter.com/balpha/status/908320205591511041
This began as a quest but ended as an odyssey.
Quest for Tetris Processor, 2,940,928 x 10,295,296
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
- Metapixels and VarLife
- QFTASM and Cogol
- Assembly, Translation, and the Future
- New Language and Compiler
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.
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:
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.
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.
- All 7 tetrominoes
- Movement, rotation, soft drops
- Line clears and scoring
- Preview piece
- Player inputs inject randomness
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 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
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
@Christopher2EZ4RTZ This overview post details the work done by many of the project members (including the actual writing of the overview post). As such, it's appropriate for it to be CW. We were also trying to avoid one person having two posts, because that would cause them to receive an unfair amount of rep, since we're trying to keep the rep even.
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)
@SocraticPhoenix The computer and Tetris game are fast enough to be played using the JS implementation of VarLife on El'endia's website. At best, the pure-GoL implementation is 35328 times slower, thanks to the period of the OTCA metapixel. In practice, there's a bit of a speedup thanks to HashLife, but also a slowdown because of the absolutely massive GoL pattern being simulated. It's still playable, but slower and more difficult (since there's no nice RAM viewer/editor in Golly like on El'endia's website).
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.
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 `ＦＳ¿⁼ι/↓¶/↘ι` 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
How many GOL generations does this take per game tick? Game tick meaning the time between two possible inputs, the time it takes for a piece to fall one pixel or whatever defines the speed in this.