Conways Spiel des Lebens

Grundidee und Spielfeld

Conways Spiel des Lebens, englisch Conway’s Game of Life, ist ein 1970 von John Horton Conway entworfenes Spiel auf der Grundlage eines zweidimensionalen zellulären Automaten. Ein zellulärer Automat besteht aus vielen einzelnen Zellen, deren Zustand sich nach festen Regeln verändert. Das Spiel ist kein Gesellschafts- oder Kampfspiel, sondern ein nach einfachen Regeln ablaufendes Geschehen. Es gilt als einfache und bis heute populäre Umsetzung der Automaten-Theorie von Stanisław Marcin Ulam.

Das Spielfeld ist rechtwinklig in Zeilen und Spalten unterteilt und theoretisch unendlich groß. Jedes Gitterquadrat ist eine Zelle mit genau zwei möglichen Zuständen, meist „lebend“ und „tot“. In Simulationen können diese Zustände durch Farben oder andere Zeichen dargestellt werden. Praktisch kann das Spiel auf Papier ausgeführt werden, meist übernimmt aber ein Computer die Berechnung vieler Generationen.

Weil reale Spielfelder Ränder haben, muss festgelegt werden, was dort geschieht. Man kann den Rand als dauerhaft tote Zellen auffassen, was Strukturen am Rand beeinflussen kann. Eine andere Möglichkeit ist ein toroides Spielfeld: Der rechte Rand grenzt dann an den linken, der obere an den unteren. Computersimulationen können außerdem einen Ausschnitt eines tatsächlich unendlichen Spielfeldes anzeigen, der beliebig verschoben wird.

Regeln und Entwicklung

Das Spiel läuft in Schritten ab. Zunächst wird eine Anfangsgeneration festgelegt, also ein Startmuster lebender Zellen. Aus jeder Generation wird die Folgegeneration berechnet. Der neue Zustand jeder Zelle hängt von ihrem aktuellen Zustand und den acht Nachbarzellen in ihrer 3x3-Umgebung ab. Diese Nachbarschaft heißt Moore-Nachbarschaft.

Nach Conways ursprünglicher Regel bleibt eine lebende Zelle lebendig, wenn sie genau zwei oder drei lebende Nachbarn hat. Eine tote Zelle wird geboren, wenn sie genau drei lebende Nachbarn hat. Daraus folgt: Eine lebende Zelle stirbt bei weniger als zwei lebenden Nachbarn durch Vereinsamung und bei mehr als drei lebenden Nachbarn durch Übervölkerung. Eine tote Zelle bleibt tot, wenn sie nicht genau drei lebende Nachbarn hat.

In Tabellenform bedeutet das für die Anzahl lebender Nachbarn von 0 bis 8: Bei 0, 1, 4, 5, 6, 7 und 8 ist die Zelle in der Folgegeneration tot; bei 3 lebt sie; bei 2 wird der aktuelle Zustand kopiert. Trotz dieser einfachen Regeln können aus Anfangsmustern sehr komplexe Strukturen entstehen. Manche Muster sterben vollständig aus und erzeugen eine „leere Welt“. Andere bleiben unverändert, schwingen periodisch, wachsen, zerfallen oder bewegen sich als sogenannte Raumschiffe über das Spielfeld. Bestimmte Anfangsmuster können sogar logische Funktionen wie UND und ODER simulieren; damit lassen sich komplexe Schaltungen und digitale Rechnertechnik nachbilden.

Wichtige Objektarten

Seit der Vorstellung des Spiels wurden viele typische Objekte entdeckt. Sie werden nach ihrem Verhalten über mehrere Generationen eingeteilt. Statische Objekte, auch still life oder „Stillleben“, verändern sich ohne äußeren Einfluss nicht. In ihnen haben alle lebenden Zellen zwei oder drei lebende Nachbarn, und alle toten Zellen in der Umgebung haben nicht genau drei lebende Nachbarn. Beispiele sind Block, Beehive („Bienenstock“), Boat („Boot“), Loaf („Brotlaib“), Tub („Kübel“), Barge („Kahn“), Pond („Teich“) und Eater(1) („Fresser“). Der Eater(1) kann bestimmte bewegte Objekte wie Gleiter auflösen und danach wieder in seiner ursprünglichen Position stehen.

Oszillierende Objekte verändern sich von Generation zu Generation, kehren aber nach einer endlichen Zahl von Generationen wieder in den Ausgangszustand zurück. Sie bleiben dabei an derselben Position, solange sie isoliert sind. Ein sehr einfaches Beispiel ist der Blinker, eine Reihe von drei lebenden Zellen, die sich in jedem Schritt um 90° dreht; seine Zyklusdauer beträgt 2. Weitere Beispiele sind Uhr, Kröte, Bipole und Tripole mit Zyklusdauer 2, der Pulsator mit 15 Generationen, der Tümmler mit 14 und das Oktagon mit 5.

Raumschiffe erzeugen nach wenigen Generationen eine Kopie ihrer selbst an einer anderen Position. Dadurch wirken sie so, als bewegten sie sich. Diagonale Raumschiffe wie der Gleiter verschieben sich in beiden Dimensionen, orthogonale Raumschiffe wie Segler nur in einer Dimension. Auf einem unendlichen Spielfeld bewegen sie sich weiter, solange sie nicht auf andere Objekte treffen. Ihre Geschwindigkeit ergibt sich aus Verschiebung pro Periode. Der Gleiter braucht vier Generationen, um ein Feld weiter in der Ursprungsform zu erscheinen, und hat Geschwindigkeit c/4. Die drei Segler LWSS, MWSS und HWSS haben ebenfalls Perioden von vier Generationen, kommen aber zwei Felder weit und haben c/2. Mehr als c, also eine Zelle Verschiebung pro Periode, ist nicht möglich, weil eine Struktur nur unmittelbar benachbarte Zellen in der nächsten Generation beeinflussen kann.

Besondere Muster und Beispiele

Gleiterkanonen sind oszillierende Objekte, die regelmäßig Gleiter erzeugen. Die Gosper glider gun wurde im November 1970 entdeckt, nur einen Monat nach dem Erscheinen des Spiels. Von ihr geht alle 30 Generationen ein Gleiter aus. Sie besteht aus einem bewegten Doppelobjekt mit zwei Blöcken als Reflektoren. Diese Entdeckung war wichtig, weil Conway 50 US-Dollar für den Nachweis ausgesetzt hatte, dass unbegrenztes Wachstum im Spiel möglich ist. Bill Gosper präsentierte 1970 die erste Lösung.

Puffer ähneln Raumschiffen, hinterlassen aber eine Spur von Objekten. Diese Spur kann aus statischen oder pulsierenden unbewegten Objekten bestehen, aber auch aus Gleitern oder Seglern. Andere Anfangskonfigurationen erzeugen innerhalb endlich vieler Schritte eine leere Welt. Ein Beispiel aus dem Artikel verschwindet nach 54 Generationen vollständig.

Ein bekanntes chaotisches Startmuster ist das f-Pentomino, auch r-Pentomino genannt. Trotz seiner Einfachheit erzeugt es ein reichhaltiges Wachstum, das über 1102 Generationen chaotisch erscheint. Ab dem 1103. Schritt bleibt, abgesehen von sechs wegfliegenden Gleitern, eine oszillierende Welt übrig. Ab Schritt 774 entsteht unter anderem die Bienenkönigin, die zwischen zwei Hindernissen hin und her fliegen kann. Das f-Pentomino ist das einzige rechtwinklige Objekt aus weniger als 6 lebenden Zellen, das eine so aktive Welt erzeugt; alle anderen wachsen nach spätestens 10 Generationen nicht weiter. Ein weiteres Beispiel ist die Zahl 42, dargestellt mit jeder Ziffer auf 3 mal 5 Kästchen; sie produziert nach 196 Schritten einige statische Objekte sowie 2 Gleiter.

Eine Gleitersynthese ist ein Spielfeldzustand, bei dem Gleiter aus dem Unendlichen aufeinander zufliegen und durch ihre Kollision ein anderes benanntes Objekt erzeugen. Für alle stationären Objekte und bis zu 14-zelligen Oszillatoren sind Gleitersynthesen bekannt. Zufällige Anfangszustände heißen soup („Suppe“); der Artikel nennt als Beispiel ein 100×100 torusförmiges Spielfeld mit 31,25 % lebenden Zellen zu Beginn.

Sichtweisen und Berechenbarkeit

Game of Life kann auf verschiedene Arten betrachtet werden. Als Gesamtsystem kann man untersuchen, ob eine Regelwelt explodiert, implodiert, langsam schrumpft oder statisch wird und „aushärtet“. Aus biologischer Sicht wirkt es wie ein Mikrokosmos, in dem kleine Strukturen entstehen, gezählt und bewertet werden. Der ökonomische Vergleich im Artikel sieht lebende und tote Zellen ähnlich wie Marktentscheidungen: Zu wenige Nachbarn oder zu viele Nachbarn führen zum Verschwinden, ein mittleres Maß erhält oder erzeugt Strukturen.

Aus chemischer Sicht lassen sich Häufigkeit und Komplexität von Objekten mit energetischen Niveaus vergleichen. Aus physikalischer Sicht zeigt das Spiel, dass einfache deterministische Regeln sehr komplexe Entwicklungen hervorbringen können; kleine Unterschiede in der Startbedingung können zu sehr verschiedenen Ergebnissen führen. Dadurch entsteht ein Anfangswertproblem mit Endzuständen, Schwingungen, Wachstum oder dauerhaft unregelmäßigem Verhalten.

Für die Informatik ist besonders wichtig, dass Conway’s Game of Life als Rechnermodell dienen kann. Mit komplexen Startmustern lassen sich eine Universelle Turing-Maschine und deren Eingabe modellieren. Das Spiel ist damit Turing-vollständig: Theoretisch kann jedes algorithmische Problem, das ein Computer lösen kann, auch allein durch Game of Life berechnet werden. Außerdem ist eine bestimmte Entscheidungsfrage unentscheidbar: Es gibt keinen Algorithmus, der für zwei beliebige Game-of-Life-Konfigurationen immer entscheiden kann, ob die eine aus der anderen entstehen kann.

Regelvarianten und Spielfeldvarianten

Neben Conways Originalregeln gibt es viele abweichende Regelwelten. Eine Kurzschreibweise beschreibt zuerst, bei wie vielen Nachbarn eine Zelle überlebt, und danach, getrennt durch einen Schrägstrich, bei wie vielen Nachbarn eine Zelle geboren wird. Conways klassische Welt heißt 23/3: Zwei oder drei Nachbarn erhalten eine lebende Zelle, drei Nachbarn erzeugen eine neue. Die Kopierwelt wird als 1357/1357 beschrieben. Bei ihr stirbt eine Zelle mit genau 0, 2, 4, 6 oder 8 lebenden Nachbarn oder bleibt tot; 1, 3, 5 oder 7 lebende Nachbarn erzeugen oder erhalten eine lebende Zelle. Das lässt sich als „Anzahl Modulo 2“ zusammenfassen.

Insgesamt sind 2^9 · 2^9 = 2^18 = 262144 Regelwerke denkbar, weil für die Nachbarzahlen 0 bis 8 jeweils ausgewählt werden kann, ob sie vor und nach dem Schrägstrich gelten. Viele davon haben nur triviale Eigenschaften. Genannt werden unter anderem die 3/3-Welt, die meistens schnell bis auf wenige Teile leer wird, die 13/3-Welt mit wenigen Oszillatoren, die 34/3- und 35/3-Welten, die dem klassischen Verhalten nahekommen, sowie 24/3, 245/3 und 125/36. Zu jeder Regelwelt gibt es außerdem eine Antiregelwelt, in der lebende und tote Zellen vertauscht sind; Anti-Conway wird als 01234678/0123478 angegeben.

Auch das Spielfeld selbst kann verändert werden. Statt eines quadratischen Gitters ist ein sechseckiges Gitter möglich; dort hat jede Zelle nicht acht, sondern sechs Nachbarzellen. Es gibt außerdem dreidimensionale Game-of-Life-Simulationen und Varianten mit mehr als zwei Zuständen der Gitterzellen. Denkbar sind auch Simulationen, in denen verschiedene abgegrenzte Bereiche unterschiedlichen Regelwelten folgen und man bewegliche Objekte sucht, die in beiden Regelwelten existieren können.