Building a working game of Tetris in Conway's Game of Life(codegolf.stackexchange.com)
codegolf.stackexchange.com
Building a working game of Tetris in Conway's Game of Life
https://codegolf.stackexchange.com/q/11880/4881
49 comments
Wow... 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.)
Here'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
It would be amazing to see this Tetris computer rendered into a video like this.
https://www.youtube.com/watch?v=xP5-iIeKXE8
It would be amazing to see this Tetris computer rendered into a video like this.
That 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.
If 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
True, 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.
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.
This 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
Anyway this is the coolest thing I've read all year, and I'm not kidding
I 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.
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.
It'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.
> 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.
Well, 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
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.
> 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
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.
This 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.
I 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)?
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)?
One 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.
In 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..
"All problems in computer science can be solved by another level of indirection" --David Wheeler or Butler Lampson
Except the problem of too many levels of indirection.
Just call a library function for that!
My ghast is totally flabbered!
This is one of the most impressive projects i have ever seen. By far.
This is awesome! I didn't see it quickly but is there a way to play it or see it being played?
Go here http://play.starmaninnovations.com/qftasm/#jllHdnBGSP then click 'Run' and scroll to the bottom of the page.
Is there a way to move the blocks?
Yes 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 :)
###
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]
[deleted]
Didn't know Stackoverflow is a collaborative blogging platform :-D
There's no way we aren't living in a simulation. Just wow.
Permutation City.
Don't know what else to say without spoilers. Read it.
Don't know what else to say without spoilers. Read it.
I just finished it.
Too bad Conway's game of Life doesn't have a mechanism for evolution.
Too bad Conway's game of Life doesn't have a mechanism for evolution.
Thanks 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).
Even 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.
Its 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.
> 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.
Yes you can, bonus points if you can do it without a central clock.
Well, 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 :)
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 :)
The 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#Asynchron... it does.
BTW, congratulations to the authors of all of this. It's a huge achievement.
"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#Asynchron... it does.
BTW, congratulations to the authors of all of this. It's a huge achievement.
I 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.
[deleted]
Does the Tetris display actually appear on the Game of Life board? Cool either way!
No, 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-w...
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-w...
I 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-d...
Yes
This is so cool. My mind is blown.
Amazing 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.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.
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.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.
Hey, that's me!
Yes, the size of the Cogol program is a decent estimate of the Kolmogorov complexity of the Tetris program. However, you also have to account for the size of the computer (including the massive RAM bank) - the Cogol program just encodes the Tetris program.
Naturally, no general-purpose compression scheme (or even a somewhat-specific-purpose scheme like MacroCell) is going to come close to the Kolmogorov complexity. We could come up with a custom compression scheme and write a compressor and decompressor, but give us a break - we built a computer! :P
Yes, the size of the Cogol program is a decent estimate of the Kolmogorov complexity of the Tetris program. However, you also have to account for the size of the computer (including the massive RAM bank) - the Cogol program just encodes the Tetris program.
Naturally, no general-purpose compression scheme (or even a somewhat-specific-purpose scheme like MacroCell) is going to come close to the Kolmogorov complexity. We could come up with a custom compression scheme and write a compressor and decompressor, but give us a break - we built a computer! :P
:D Thanks for the reply. And great work!
As a TGM fan , this is one of the coolest stuff I have seen on HN.