Construct 3 Tetris

[Klacee Sawatzky]

Thefirst step to building such a system is to figure out the base set of logical operations that you will find useful when designing an arithmetic chip, a storage chip, and a communication system between chips. Here are 15 chips that we will want access to:

This is a very empowering exercise. In the beginning, I was struggling to remember my logic class. By the end, I had all these cool mental tricks that I was developing to think about how the logic flows and to translate these logical operations into the language of my own body (which often meant translating them to visual or programming metaphors in English that I understood well)

Part of the confusion is the names. These names come from the sound + communication engineering world, where you would literally "multiplex" multiple inputs into a single controller, which would then give you a switch to select the signal that you want, and maybe even another switch to "route" (Demultiplex) that signal to one of many outputs channels.

You can think of logical operations a bit like following a recipe. You have some amount of meaningful input data (raw ingredients), and then you can combine logical gates to create \u201Cchips\u201D (logic gates are just a simple type of chip) that predictably alter your data using logic, like steps in the recipe. With enough steps (and fancy math tricks), you can take a small number of variables and compute incredibly sophisticated information. This is how graphing calculators work. Provide the slope and it can plot a graph for you, just by performing predictable, logical steps on your input data.

reminder: a chip is just any technology that turns binary inputs into binary outputs. These are all \u201Clogic chips\u201D, so they transform the binary inputs according to the logical operation they are named after. If this is still confusing, watch the crash course above.

The amazing, cool, exciting, remarkable, brilliant thing, though, is that as soon as I design a chip, I can use it in all my future designs! I can invent new logical technologies that I can then combine to invent even more new technologies, and so on\u2026

This is an addicting feedback loop, and it\u2019s impossible to describe what it feels like in words to use something you just invented to invent a new thing. You just have to try it yourself. Go ahead and invent these 15 gates for yourself, I dare you. If you want a buddy to consult, shoot me a message.

Part of the confusion is the names. These names come from the sound + communication engineering world, where you would literally \\\"multiplex\\\" multiple inputs into a single controller, which would then give you a switch to select the signal that you want, and maybe even another switch to \\\"route\\\" (Demultiplex) that signal to one of many outputs channels.

5. now you have 8 output lines, each of which says: if[sel=000]: in[0]; if[sel=001]: in[1];... if[sel=111]: in[7]; Only one can ever be true at a time since they\u2019re mutually exclusive, and each corresponds to one of the 8 inputs.

A combination circuit just means combining many lower-level circuits of the same type into a higher level one. I can construct a 16-way MUX directly via AND and not gates (or even just from NAND), or I can construct it using 3 MUX4Ways, which I could each construct using 3 basic MUX. If this doesn\u2019t mean anything to you, I\u2019d recommend going to youtube or starting the course :) message me if you want help

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 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.

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:

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.

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.

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.

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.

The OTCA metapixel is a 2048 2048 period 35328 unit cell that was constructed by Brice Due... It has many advantages... including the ability to emulate any Life-like cellular automaton and the fact that, when zoomed out, the ON and OFF cells are easy to distinguish...

What Life-like cellular automata means here is essentially that cells are born and cells survive according to how many of their eight neighbor cells are alive. The syntax for these rules is as follows: a B followed by the numbers of live neighbors that will cause a birth, then a slash, then an S followed by the numbers of live neighbors that will keep the cell alive. A bit wordy, so I think an example will help. The canonical Game of Life can be represented by the rule B3/S23, which says that any dead cell with three live neighbors will become alive and any live cell with two or three live neighbors will remain alive. Otherwise, the cell dies.

Despite being a 2048 x 2048 cell, the OTCA metapixel actually has a bounding box of 2058 x 2058 cells, the reason being that it overlaps by five cells in every direction with its diagonal neighbors. The overlapping cells serve to intercept gliders - which are emitted to signal the metacells neighbors that it's on - so that they don't interfere with other metapixels or fly off indefinitely. The birth and survival rules are encoded in a special section of cells at the left side of the metapixel, by the presence or absence of eaters in specific positions along two columns (one for birth, the other for survival). As for detecting the state of neighboring cells, here's how that happens:

3a8082e126