Building a working game of Tetris in Conway's Game of Life
codegolf.stackexchange.com
codegolf.stackexchange.com
https://www.youtube.com/watch?v=xP5-iIeKXE8
It would be amazing to see this Tetris computer rendered into a video like this.
Anyway this is the coolest thing I've read all year, and I'm not kidding
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.
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.
> 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.
> 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.
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)?
###
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 :)
Don't know what else to say without spoilers. Read it.
Too bad Conway's game of Life doesn't have a mechanism for evolution.
Yes you can, bonus points if you can do it without a central clock.
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 :)
"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.
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...
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.
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