Just under 3 years ago, a codegolf.SE user created this challenge:
Build a working game of Tetris in Conway’s Game of Life
As of writing, this challenge is the most upvoted unanswered question on the site, by a large margin. Some users have predicted that the challenge will never be answered. I say, this will not be due to a lack of trying. I am currently involved in a large, serious, and very promising attempt to build a programmable computer in GoL. This is… the Quest for Tetris.
As of writing, there are three core developers working on this project, although there have been several additional users participating in the dedicated chat room.
- PhiNotPi (me) – I consider myself the “project leader.” I’ve probably done the plurality of physical logic gate/circuit design and construction, although little actual programming. I was the initiator of this solving attempt.
- El’endia Starman – He created Variations of Life, the mixed-rule CA simulator that has been the “base of operations” for most of our work so far. He has also discovered several logic gates.
Cᴏɴᴏʀ O’Bʀɪᴇɴ – He is currently programming the tile-based circuit simulator, on which we will develop most of the more complex logic circuits of the computer.
We stand on the shoulders of giants. There are two main sources from which we are basing our computer design:
- The OTCA metapixel was created by Brice Due in 2006. It is a square-shaped GoL construction that is capable of emulating any life-like rule (that is, 2-state Moore-neighborhood outer totalistic rule). The details of its inner workings are beyond the scope of this project, but the ability to program cells independently of their neighbors is the key to this project.
- The wireworld computer was built by David Moore and Mark Owen in 1992. It is (as far as I’m aware), the only CA-based computer of similar complexity and usability. We intend on using several similar methods in the construction of our computer. His website describes several parts of the computer, but unfortunately lacks the thoroughness I would prefer (and which I will attempt to provide in this series of blog posts).
We are building our computer on several layers of abstraction.
- The Game of Life is the lowest level, of course.
- Next is the OTCA metapixel, which is used to emulate a larger grid of cells. These cells can contain a variety of rules. We are using the rules B/S (for background), B1/S, B2/S, and B12/S1.
- By stringing certain types of metapixels together, we can create wires, down which signals can flow (in the form of “highly controlled spaceships”). We can also create logic gates that take signals as input and give other signals as output. All of the basic logic units will be of comparable size and delay, allowing further abstraction.
- Logic gates can be arranged to build logic circuits, like adders, multiplexers, memory cells, etc.
- These circuits can be combined to form a functional, although basic, computer.
- The computer can be programmed to have Tetris.
These steps will be broken down into more detail in additional blog posts.
We have finished the majority of logic gate discovery, and are now working on building larger circuits. Some of our work will still be done with hand-crafting compact circuits, but eventually our circuit design work will be tile-based, without needing to simulate the underlying circuitry. Our current bottleneck is the programming of this tile-based circuit simulator.