Das Spiel des Lebens (englisch Conway’s Game of Life) ist ein vom Mathematiker John Horton Conway 1970 entworfenes Spiel, basierend auf einem zweidimensionalen zellulären Automaten. Es ist eine einfache und bis heute populäre Umsetzung der Automaten-Theorie von Stanisław Marcin Ulam.

„Spiel“ versteht sich dabei nicht als Gesellschafts- oder Kampfspiel, sondern als ein Geschehen, das nach festgelegten einfachen Regeln abläuft.

Das Spielfeld

Das Spielfeld ist in Zeilen und Spalten unterteilt und theoretisch unendlich groß. Jedes Gitterquadrat ist ein zellulärer Automat (Zelle), der einen von zwei Zuständen einnehmen kann, welche oft als lebend und tot bezeichnet werden. Zunächst wird eine Anfangsgeneration von lebenden Zellen auf dem Spielfeld platziert. Jede lebende oder tote Zelle hat auf diesem Spielfeld genau acht Nachbarzellen, die berücksichtigt werden (Moore-Nachbarschaft). Der im nächsten Schritt (Generation) vorliegende Zustand jeder Zelle ergibt sich anhand einfacher Regeln aus den Zuständen ihrer Nachbarzellen.

Das Spiel kann manuell auf einem Stück Papier oder mit Computerhilfe simuliert werden. Da ein reales Spielfeld immer einen Rand hat, muss das Verhalten dort festgelegt werden. Eine Möglichkeit besteht darin, sich den Rand durch dauertote Zellen belegt zu denken, was zu „Reflexionen“ dort anstoßender Strukturen führen kann. Eine andere Möglichkeit ist ein toroides Spielfeld, dessen Ränder an den jeweils gegenüberliegenden Rand angrenzen, so dass Zustandsänderungen, die beispielsweise hinter dem rechten Rand geschehen müssten, sich am linken Rand zeigen. Computersimulationen ermöglichen andererseits die Abbildung eines tatsächlich unendlichen Spielfeldes, indem es sich im angezeigten Rahmen unbegrenzt verschieben lässt.

Anstatt auf einer quadratisch gerasterten Ebene kann die Simulation auch auf einer sechseckig gerasterten Ebene erfolgen. Dann beträgt die Zahl der Nachbarzellen nicht acht, sondern sechs. Es gibt auch dreidimensionale Game-of-Life-Simulationen.

Eine weitere Variationsmöglichkeit ist, mehr als zwei mögliche Zustände der Gitterzellen einzuführen.

Die Spielregeln

Die Folgegeneration wird für alle Zellen gleichzeitig berechnet und ersetzt die aktuelle Generation. Der Zustand einer Zelle (lebendig oder tot) in der Folgegeneration hängt nur vom aktuellen Zustand der Zelle selbst und den aktuellen Zuständen ihrer acht Nachbarzellen ab.

Die von Conway zu Anfang verwendeten Regeln sind (lebende Zellen grün dargestellt):

• Eine tote Zelle mit genau drei lebenden Nachbarn wird in der Folgegeneration „geboren“ (zum Leben erweckt). Hier hat die mittlere (tote) Zelle genau drei lebende Nachbarn und wird in der nächsten Generation leben:

• Eine lebende Zelle mit weniger als zwei lebenden Nachbarn stirbt in der Folgegeneration (an Einsamkeit). Hier hat die mittlere Zelle nur einen lebenden Nachbarn und wird in der nächsten Generation tot sein. Ob die Zelle rechts unten ebenfalls stirbt, hängt von ihren weiteren Nachbarn ab.

• Eine lebende Zelle mit zwei oder drei lebenden Nachbarn bleibt in der Folgegeneration am Leben. Hier hat die mittlere Zelle genau drei lebende Nachbarn und wird in der nächsten Generation weiterhin leben.

• Eine lebende Zelle mit mehr als drei lebenden Nachbarn stirbt in der Folgegeneration (an Überbevölkerung). Hier hat die mittlere Zelle fünf lebende Nachbarn und wird in der nächsten Generation tot sein. Dasselbe gilt für die mittlere Zelle der oberen Reihe, sie hat mindestens vier lebende Nachbarn. Die tote linke Zelle der mittleren Reihe hat auch mindestens vier lebende Nachbarn und wird daher in der nächsten Generation tot bleiben.

Mit diesen vier einfachen Regeln kann aus gegebenen Anfangsmustern im Laufe des Spiels eine Vielfalt komplexer Strukturen wachsen. Es gibt statische Strukturen, die sich von einer zur nächsten Generation nicht ändern, andere oszillieren, indem sie nach einer endlichen Anzahl Generationen wieder vorliegen, wieder andere wachsen oder vergehen. Manche Strukturen, sogenannte Raumschiffe, bewegen sich orthogonal oder diagonal auf dem Spielfeld fort, indem sie aufgrund der Regeln verschobene Kopien von sich selbst erzeugen.

Sogar logische Funktionen wie UND und ODER lassen sich durch bestimmte Anfangsmuster simulieren. Damit können dann sogar komplexe Funktionen der Schaltungslogik und digitalen Rechnertechnik nachgebaut werden.

Es existieren andere Varianten des Game of Life, bei denen Conways Regeln geändert oder ergänzt werden. Beispiele sind im Abschnitt Abweichende Regeln aufgeführt.

Die Objekte

Auf dem Spielfeld zeigt sich mit jedem Generationsschritt eine Vielfalt komplexer Strukturen. Einige typische Objekte lassen sich aufgrund eventuell vorhandener besonderer Eigenschaften in Klassen einteilen: sie verschwinden, bleiben unverändert, verändern sich periodisch (oszillieren), bewegen sich auf dem Spielfeld fort, wachsen unaufhörlich usw.

Sichtweisen

Die Beschäftigung mit Game of Life kann unter verschiedenen Sichtweisen erfolgen, wie etwa:

1. Das Verhalten als Gesamtes:
   Für einige Leute ist es interessant, was für ein Verhalten bestimmte Regelwelten aufweisen, zum Beispiel ob sie explodieren oder implodieren, ob sie langsam schrumpfen oder ob sie langsam „aushärten“.
2. Der biologische Aspekt: Game of Life als Mikrokosmos:
   Für andere ist Game of Life wie der Blick in ein Mikroskop. Man beobachtet die kleinen Strukturen, die man abzählen und bewerten kann. Hier freut man sich somit besonders, wenn eine neue „Lebensform“ auftaucht. Explodierende, expandierende oder gar „aushärtende“ Regelwelten sind hierbei uninteressant.
3. Der ökonomische Aspekt: Game of Life als Modell des Computerhandels der Finanzmärkte:
   Gemäß der Algorithmen des Computerhandels kauft man ein Produkt, wenn einige, aber nicht zu viele und nicht zu wenige Nachbarn es ebenfalls bereits besitzen. Wenn zu wenige es haben, verkauft man, bevor es ganz wertlos wird. Wenn zu viele es haben, verkauft man, bevor die Blase platzt.
4. Der chemische Aspekt: Energie und Materie:
   Wenn man die Häufigkeit und die Komplexität der Game-of-Life-Objekte mit dem Aufwand an Energie und Zwischenschritten vergleicht, die benötigt werden, um eine bestimmte chemische Verbindung zu erhalten, so kann man die unterschiedlichen Life-Objekte auf unterschiedliche energetische Niveaus setzen. Objekte, die bei jedem Ablauf vorkommen, wären dann auf dem Niveau von Wasser, Kohlenstoffdioxid und Natriumchlorid. Objekte, wie Unruh(2) und Fontäne, wären dann beispielsweise auf einem Niveau wie Salzsäure und Natronlauge, und Objekte wie die Segler (LWSS, MWSS und HWSS), die auch zufällig entstehen können, wären schon auf dem Niveau relativ komplexer Verbindungen.
5. Der physikalische Aspekt: Kräfte und Anfangswertproblem:
   Selbst die einfachsten physikalischen Gesetze können beliebig komplexes Verhalten als Gesamtes zeigen. Rein deterministisch/mechanisch können (beliebig) kleine Abweichungen der Startbedingung zu ganz unterschiedlichen Ergebnissen führen. Somit lässt sich ein Anfangswertproblem formulieren, worauf chaotisches Verhalten folgt. Es folgen Endzustände, Schwingungen, Wachstum, aber auch dauerhaft unregelmäßiges Verhalten.
6. Game of Life als Automat:
   Es gibt den Typus des Game-of-Life-Interessierten, der hauptsächlich an der Konstruktion von Automaten interessiert ist, also solchen Strukturen, die wie eine Maschine oder Fabrik arbeiten. Es gibt einen Verband aus Strukturen, der entfernt Ähnlichkeit mit einem Rollfeld eines Flughafens hat, auf dem ständig Flugzeuge starten, und dazwischen die Fahrzeuge, die den Betrieb aufrechterhalten, zu ihren Stationen fahren.
7. Game of Life als Rechnermodell: Es ist möglich, mithilfe komplexer Startmuster eine Universelle Turing-Maschine und deren Eingabe zu modellieren. Conway’s Game of Life ist damit Turing-vollständig. Theoretisch lässt sich jedes algorithmische Problem, das man mit einem Computer lösen kann, auch allein durch Game of Life berechnen.
8. Game of Life in der Theoretischen Informatik als Entscheidungsproblem:
   Man kann zeigen, dass es keinen Algorithmus gibt, der als Eingabe zwei beliebige Game-of-Life-Konfigurationen erhält und in allen Fällen entscheiden kann, ob eine Konfiguration aus der anderen entstehen kann oder nicht. Diese Frage ist damit unentscheidbar.

Conways Herausforderung

Conway bot demjenigen einen Preis von 50 US-Dollar, der nachweisen konnte, dass mit Conways Spiel des Lebens unbegrenztes Wachstum möglich ist. Da für einen eindeutigen Beweis ein geordnetes Wachstum notwendig ist, waren die chaotischen explosionsartigen Vermehrungen ungeeignet.

Die erste Lösung für dieses Problem – eine so genannte Gleiterkanone, die in regelmäßigen Abständen einen Gleiter hervorbringt – wurde 1970 von dem amerikanischen Mathematiker Bill Gosper präsentiert. Der Gleiter erzeugt innerhalb von vier Generationen eine verschobene Kopie von sich selbst, und somit kann die Kanone an derselben Stelle den nächsten Gleiter erzeugen.

Es ist möglich, aus Kollisionen von Gleitern eine Gleiterkanone zu erzeugen. Damit kann die Bewegungsrichtung der Gleiter geändert werden, und es besteht die theoretische Möglichkeit, selbstreplizierende Automaten zu konstruieren.

In der oberen Bildhälfte befindet sich die Gleiter-Kanone, die in 30 Generationen einmal pulsiert und dabei einen Gleiter erzeugt. Im rechten, unteren Teil des Bildes befindet sich der Gleiter-Fresser, der in 15 Generationen einmal pulsiert und bei jeder zweiten Pulsation einen Gleiter zerstört. Die Gleiter bewegen sich von der Bildmitte nach rechts unten. Links unten läuft der Generationen-Zähler mit. In der Bildbeschreibung befinden sich Links zu dem die Animation erzeugenden GW-BASIC-Programm und zu den Startdaten.

Mittlerweile wurden unüberschaubar viele Konstellationen gefunden, die ähnlich wie die einfache Gleiterkanone laufend Zellen produzieren. Neben Gleitern und verschiedenen Seglern sind sogar komplexe Kanonen gefunden worden, die selbst Gleiterkanonen „feuern“. Zusammen mit anderen nützlichen Gebilden, wie sich fortbewegende Kanonen, Gleiter-Reflektoren oder Relays (Gebilde, die etwa Gleiter für einige Generationen bremsen), bilden sie Werkzeuge für das Entwerfen komplexer Automaten wie etwa der Turingmaschine. Dies beweist, dass Conway’s Game of Life Turing-vollständig ist.

Im Jahr 2012 wurde erstmals eine Konstellation vorgestellt, die in der Lage ist, ein Spielfeld zu simulieren, das den Regeln von Conways Spiel des Lebens entsprach (Selbstsimulation).

Abweichende Regeln

Man kann sich abweichende Regeln zum klassischen Game of Life vorstellen. Das folgende Regelwerk definiert beispielsweise ein sich reproduzierendes System, eine „Kopierwelt“.

• Todes-Regel: Eine Zelle mit genau 0, 2, 4, 6 oder 8 lebenden Nachbarn stirbt (oder bleibt tot).
• Geburts-Regel: 1, 3, 5 oder 7 lebende Nachbarn erzeugen (oder erhalten) eine lebende Zelle.

Diese Regeln kann man auch als „Anzahl Modulo 2“ zusammenfassen.

Wenn man in dieser Kopierwelt zum Beispiel eine Struktur in Form des Buchstaben H zeichnet, so werden lauter identische H-Buchstaben erzeugt. Bei größeren Ausgangsmustern sorgt dieses Regelwerk sogar selbständig für ein Auseinanderrücken der vorher kollidierenden Kopien. Die Kopien der Ausgangsmuster treten bei Zyklennummern auf, die ein Vielfaches von 4 sind. Bei größeren Ausgangsmustern treten sie aber nicht bei jedem Vielfachen von 4 auf. Wendet man diese Regel auf ein Feld der Größe 15×15 an, so sterben nach der 15. Generation immer alle Zellen aus.

Um sich beim Vergleich verschiedener Regelwerke eine umständliche Umschreibung der Regeln zu ersparen, existiert eine Kurzschreibweise für die Regeln von Game of Life: Man setzt zunächst (in aufsteigender Reihenfolge) die Ziffern der Anzahl von Nachbarn aneinander, bei der eine Zelle überlebt, und anschließend, durch einen Schrägstrich abgetrennt, die Ziffern, die den Werten entsprechen, bei der eine Zelle geboren wird. Die klassische Conway-Welt wird also durch 23/3 beschrieben, die oben beschriebene Kopierwelt durch 1357/1357. Es wurden auch Regeln für mehrdimensionale Räume entwickelt. Hier entstehen aber natürlich Darstellungsprobleme. Sehr dicht an das Verhalten nach dem klassischen 23/3-Regelwerk von Conway (zwei oder drei Nachbarn erhalten eine Zelle, drei Nachbarn erzeugen eine neue Zelle) kommen die Regelwerke 34/3 und 35/3. Die Anzahl aller möglichen Regelwerke ergibt sich aus der Anzahl der Möglichkeiten, Ziffern zwischen 0 und 8 vor und nach dem Schrägstrich auszuwählen. Insgesamt sind daher ${\displaystyle {2^{9}}\cdot {2^{9}}=2^{18}=262144}$ Regelwerke denkbar, von denen die meisten jedoch nur wenige, triviale Eigenschaften aufweisen. Einige der interessanteren Regelwerke werden im Folgenden beschrieben.

Siehe auch

• Conway-Folge
• Kombinatorische Spieltheorie

Weblinks

• Ausführliches Wiki über Conway’s Game of Life (englischsprachig)
• Das Game of life simuliert das Game of life, Video
• Game of life dreidimensional (2015), Video
• Game of Life Universal Turing Machine, Video
• Game of Life, Quelltext mit ThreeJS (JavaScript)

Literatur

Nathaniel Johnston und Dave Greene: Conway's Game of Life. Mathematics and Construction. 2022. ISBN 978-1-7948-1696-1. Online verfügbar (PDF; 91 MB).

Einzelnachweise

1. ↑ LifeWiki: Gosper glider gun, abgerufen am 24. Mai 2022
2. ↑ Conway’s game of life (in html 5) auf Math Fail
3. ↑ LifeWiki: Glider synthesis, abgerufen am 24. Mai 2022
4. ↑ Paul Rendell: A Turing Machine in Conway’s Game of Life, extendable to a Universal Turing Machine. Abgerufen am 9. Januar 2011. 
5. ↑ Turtles, all the way down. Or gliders. Or glider turtles. Blogpost über Selbstsimulation mit Video
6. ↑ otcametapixel.blogspot.de
7. ↑ Uri Wilensky.: NetLogo Models Library: Cellular Automata / Life. Abgerufen am 27. November 2018 (englisch).