7 ms·
Building a working game of Tetris in Conway's Game of Life
- mettamage 9y agoThis is awesome! I didn't see it quickly but is there a way to play it or see it being played?
- onion2k 9y agoGo here http://play.starmaninnovations.com/qftasm/#jllHdnBGSP http://play.starmaninnovations.com/qftasm/#jllHdnBGSP then click 'Run' and scroll to the bottom of the page.
- keithnz 9y agoIs there a way to move the blocks?
- deleted 9y ago[deleted]
- mettamage 9y agoYes there is, see their following explanation: ### 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 ### If you do CTRL+F on the following: Direct write to RAM You can find the input field :)
- deleted 9y ago[deleted]
- Andrenid 9y agoThis is one of the most beautiful things I've seen. The effort and time and collection of talented people required to do this is just awesome. All thanks to the universal love of Tetris.
- slampig 9y agoThere's no way we aren't living in a simulation. Just wow.
- didsomeonesay 9y agoPermutation City. Don't know what else to say without spoilers. Read it.
- coupdejarnac 9y agoI just finished it. Too bad Conway's game of Life doesn't have a mechanism for evolution.
- avian 9y agoHere's a nice video showing OTCA metapixels in action, implementing Game of Life in Game of Life. https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8 It would be amazing to see this Tetris computer rendered into a video like this.
- teekert 9y agoThat is just one of the coolest things I've seen which makes me feel a bit strange inside. Like looking the universe into the soul. Like feeling how simple thing can produce complex things (but not understanding). Thanx for sharing.
- ImaCake 9y agoIf you read down the stackoverflow page long enough there is a link to a runable version of the code. http://play.starmaninnovations.com/qftasm/#jllHdnBGSP http://play.starmaninnovations.com/qftasm/#jllHdnBGSP
- isoprophlex 9y agoThis would need to be compiled into a pattern for the intermediate automaton, which is then run on the metapixel layer in GOL? I think? Anyway this is the coolest thing I've read all year, and I'm not kidding
- avian 9y agoTrue, but the runnable code on that page is several levels of abstraction removed from the actual Game of life states. The page you linked runs the code in a Javascript implementation of their CPU. That's a significant shortcut. The CPU was otherwise implemented with logic gates that were implemented with varlife circuits that were implemented with metapixels in Game of Life. None of this is present in the browser implementation. As logicallee's comment below says, the actual Game of life board behind the implementation is absolutely massive with tens of gigabytes needed to represent the state of the Tetris computer.
- tangus 9y ago"All problems in computer science can be solved by another level of indirection" --David Wheeler or Butler Lampson
- reificator 9y agoExcept the problem of too many levels of indirection.
- dragontamer 9y agoJust call a library function for that!
- KeyboardFire 9y agoWow... when this project began over a year ago, it seemed almost impossible. It's almost surreal to see the results finally all put together. (And it really goes to show how a few amazing and dedicated people working together can make incredible things.)
- paulajohnson 9y agoMy ghast is totally flabbered!
- coldcode 9y agoEven though it seems like implementing an aircraft carrier to kill a fly, what a amazing bunch of work. I wonder if you could implement this in hardware and wind up with a working computer.
- jacquesm 9y ago> I wonder if you could implement this in hardware and wind up with a working computer. Yes you can, bonus points if you can do it without a central clock.
- falcor84 9y agoWell, having some sort of a central clock to use for the Game of Life ticks is a prerequisite, right?* And then the ticks are an all-powerful global clock that you get for free. A-la Leibniz's two clocks metaphor. * Unless you're trying to go for a distributed multi-verse implementation with separate boards having their own clocks and only limited message passing between them. The more I think of it, the cooler it seems. I'm now imagining setting up Erlang/OTP on these :)
- pmontra 9y agoThe CPU they built is asynchronous. "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." I'm not sure that it qualifies as clockless but according to https://en.wikipedia.org/wiki/Asynchronous_circuit#Asynchronous_CPU https://en.wikipedia.org/wiki/Asynchronous_circuit#Asynchron... it does. BTW, congratulations to the authors of all of this. It's a huge achievement.
- peter303 9y agoIts like saying our universe is a simulation embedded in another universe. The simulation only need to be to the resolution of Plancks quantum of action. We couldnt distinguish any detail finer than that. The other universe could have a much finer resolution than our hbar. The simulator could be using a hundred grid points and time steps for grid point and time step in our universe.
- TorKlingberg 9y agoDoes the Tetris display actually appear on the Game of Life board? Cool either way!
- jk563 9y agoYes
- 3JPLW 9y agoNo, I don't believe it is. The "display" on the demo site is simply reading out the state of the RAM. While you can "see" the on bits within the RAM grid, I think it's kinda hard to discern the values from the supporting architecture. It doesn't look like they wired the RAM to a nicer display that makes it easier to read. See: https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life?answertab=votes#comment349542_142673 https://codegolf.stackexchange.com/questions/11880/build-a-w...
- TorKlingberg 9y agoI thought so. It would be nice if there was an in-game display like this simpler question: https://codegolf.stackexchange.com/questions/88783/build-a-digital-clock-in-conways-game-of-life?noredirect=1&lq=1 https://codegolf.stackexchange.com/questions/88783/build-a-d...
- forinti 9y agoI can't decide if it's cool or terrible to spend so much time on this.
- jdironman 9y agoIf you enjoy doing something then the time spent doing it is never wasted.
- kronos29296 9y agoThis is so cool. My mind is blown.
- unoti 9y agoSurely a next step should be a JavaScript interpreter, then self hosting, then running Windows and Linux in a cross compiled VM.
- kuschku 9y agoConsidering they almost have a GCC backend now, this is all "easily" possible.
- Darkstack 9y agoAs a TGM fan , this is one of the coolest stuff I have seen on HN.
- pavel_lishin 9y agoI very briefly skimmed this, and it seems like it's using a pretty standard Von Neumann architecture, right? RAM, ROM, ALU, etc. I understand that it's easier to build Tetris, or anything, using something we understand well, but I wonder what other approach would be better for building in GoL.
- vanderZwan 9y agoWell, cellular automata are grid-based, so maybe something that makes use of that spatial aspect? The only thing I can think of right now is Chuck Moore's greenarrays, which is a grid of dedicated Forth chips wired together: > Chuck Moore discusses what it takes to program a 144-core asynchronous chip that consumes only 7 pJ/inst, the idle cores taking just 100 nW while the active ones need 4mW running at 666 Mips: tight coding to minimize the number of instructions executed, reducing instruction fetches, transistor switching, and duty cycle. https://www.infoq.com/presentations/power-144-chip https://www.infoq.com/presentations/power-144-chip I don't think that in itself is a good fit, but maybe a good starting point to think about it alternative approaches? As an aside, what you're saying about it being easier to build anything we understand well applies even more when working in groups, since it's a lot harder to find a solution to a problem without a shared baseline. So it makes a lot of sense that this approach was taken here.
- harpiaharpyja 9y agoIt's actually using a Harvard architecture. From Part 4: > Harvard architecture, meaning a division between program memory (ROM) and data memory (RAM). Although this does reduce the flexibility of the processor, this helps with size optimization: the length of the program is much larger than the amount of RAM we'll need, so we can split the program off into ROM and then focus on compressing the ROM, which is much easier when it is read-only.
- stevemk14ebr 9y agoThis is one of the most impressive projects i have ever seen. By far.
- kemenaran 9y agoI have a question for more hardware-knowledgeable people than me: We know it's possible to implement logic gates in Game of Life. So would it be possible to re-purpose a VHDL compiler to emit schemas for GoL-gates or GoL-transistors? In this case, wouldn't programming a Tetris game in VHDL output a much smaller automata (avoiding the need to use huge OTCA metapixels, except maybe for display)?
- amelius 9y agoOne problem, I suppose, is that GoL is 2d, whereas VHDL output is ultimately 3d. So the problem is basically crossing wires. But I bet you can design a wire-crossing just like you can design a gate. If that's true, then VHDL to GoL would be possible.
- TFortunato 9y agoIn the hardware section of the post, they actually do show / talk about the need to construct a wire crossing, and it was used in the design..
- JepZ 9y agoDidn't know Stackoverflow is a collaborative blogging platform :-D
- logicallee 9y agoAmazing post. This part is a little funny (spoiler - this is from the end): >So, our computer (with the Tetris ROM) has a bounding box of 1,436 x 5,082. Of the 7,297,752 cells in that box, 6,075,811 are empty space, leaving an actual population count of 1,221,941. Each of those cells needs to be translated into an OTCA metapixel, which has a bounding box of 2048x2048 and a population of either 64,691 (for an ON metapixel) or 23,920 (for an OFF metapixel). That means the final product will have a bounding box of 2,940,928 x 10,407,936 (plus a few thousand extra for the borders of the metapixels), with a population between 29,228,828,720 and 79,048,585,231. With 1 bit per live cell, that's between 27 and 74 GiB needed to represent the entire computer and ROM. >I included those calculations here because I neglected to run them before starting the script, and very quickly ran out of memory on my computer. After a panicked kill command, I made a modification to the metafier script. Every 10 lines of metapixels, the pattern is saved to disk (as a gzipped RLE file), and the grid is flushed. This adds extra runtime to the translation and uses more disk space, but keeps memory usage within acceptable limits. Because Golly uses an extended RLE format that includes the location of the pattern, this doesn't add any more complexity to the loading of the pattern - just open all of the pattern files on the same layer. >K Zhang built off of this work, and created a more efficient metafier script that utilizes the MacroCell file format, which is loads more efficient than RLE for large patterns. This script runs considerably faster (a few seconds, compared to multiple hours for the original metafier script), creates vastly smaller output (121 KB versus 1.7 GB), and can metafy the entire computer and ROM in one fell swoop without using a massive amount of memory. It takes advantage of the fact that MacroCell files encode trees that describe the patterns. By using a custom template file, the metapixels are pre-loaded into the tree, and after some computations and modifications for neighbor detection, the Varlife pattern can simply be appended. What's really funny about this is that in the end, they are compressing the image. But we know what it compresses to! It compresses to this: >The final Tetris program was written in Cogol, which links to https://github.com/QuestForTetris/Cogol/blob/master/tetris.cgl https://github.com/QuestForTetris/Cogol/blob/master/tetris.c... and is... 4.71 KB. While it didn't get far enough to compress that well, in the end this a journey up and down and then a little up (because they went down too much and ran out of memory) various levels of abstraction. Very cool - and a little funny.
- 9y ago
- deleted 9y ago[deleted]
- thriftwy 9y agoI think that you can make wires and gates in Life without metapixel, that sounds like overkill. Can probably share 2 orders of magnitude whule keeping most things intact.
- ShardPhoenix 9y agoThanks to the very lucid explanations, I feel like this gave me a better understanding of why computers might be implemented in a certain way (eg why certain gates or instructions might be used - obviously a physical computer will have different constraints).