The Quest for Tetris in Conways Game of Life

Vor drei Jahren stellte StackExchange-User Joe Z folgende Aufgabe: „Build a working game of Tetris in Conway’s Game of Life“. Die Aufgabe ist mit einigem Abstand die populärste und sie gilt als unerfüllbar. (via Hackaday)

Conways Game of Life ist ein sogenannter Zellulärer Automat, also eine Anordnung von Zellen (3x3 Pixel zum Beispiel), die nach bestimmten Regeln von einem Zustand zum nächsten mutieren, hatten wir gestern beim Pi-Fraktal bereits.

Mit den Teilen kann man aber nicht nur unendliche Fraktale basteln, sondern auch, sofern man die entsprechenden Regeln findet, eine Digitaluhr zum Beispiel. Oder halt Tetris. Aber für ein Game braucht man einen Computer oder zumindest eine Umgebung, in der man ein Game programmieren kann und man kann sich vorstellen: Um einen ausführbaren, auf reiner Mathematik beruhenden Computer in einer so simplen Umgebung wie Conways Game of Life zu bauen, braucht man eine ziemliche Menge von Zellulären Automaten und mit der Menge dieser steigt natürlich die Menge der Regeln und damit die Komplexität des ganzen Projekts, weshalb man für Atari2600 in Minecraft vielleicht ein paar Tage braucht, aber die genauen Regeln für einen Rechner in Game of Life zu finden – das dauert dann doch eher drei Jahre.

Das ist der Quest for Tetris und der aktuelle Status des Projekts ist anscheinend tatsächlich „actually very close to completion“, im Bild oben sieht man die AND, XOR und OR-Logig-Gates, Bild rechts ist der RAM.

Hier mal 'ne grobe Übersicht, die die Komplexität des Unterfangens in ihrer Breite aufzeigt, seriously excellent Nerdery at work:

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

Our Approach

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.