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.)
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.
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.
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.
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.
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.
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)?
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.
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
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.
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 :)
"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 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.
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.
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:
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.
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
