Das "Spiel des Lebens"

Muster eines sog. Raumschiffs in Conways Game of Life

Was ist das Spiel des Lebens?

Das Spiel des Lebens, im englischsprachigen Raum auch bekannt unter dem Titel "Game of Life" oder auch nur Life, ist ein zellularer Automat, der vom britischen Mathematiker John Horton Conway im Jahr 1970 erfunden wurde. Das Spiel des Lebens gewann durch eine Veröffentlichung von Martin Gardner in der Kolumne "Mathematical Games" der Zeitschrift "Scientific American" [6] schnell an Popularität.

Eine Besonderheit des speziellen Regelsatzes von Conways "Spiel des Lebens" ist, dass er Turing-Vollständig ist. Die Turing-Vollständigkeit ist eine Eigenschaft, die beschreibt das eine Programmiersprache, eine Simulation oder ein logisches System prinzipiell geeignet ist jedes rechentechnische Problem zu lösen. Die Programmierung des "Game of Life" würde mit Mustern erfolgen, die dann in der Simulation miteinander interagieren. Im Internet gibt es mit LifeWiki eine eigenes Wiki, dass sich mit der Archivierung von Mustern in Game of Life beschäftigt. Eine Auswahl an solchen Mustern ist im hier gezeigten Applet aufgeführt.

Wegen der Einfachheit des Regelsatzes ist die Implementierung von Game of Life eine beliebte Aufgabe für Programmieranfänger. Der Quellcode des hier verwendeten "Game of Life"-Applets ist in Typescript geschrieben und kann bei GitHub herunter geladen werden. Eine Beschreibung der Implementierung des Game of Life in Python befindet sich in einem anderen Artikel auf dieser Webseite.

"Game of Life" Quellcode

Zelluläre Automaten

Ein zellularer Automat ist ein diskretes Modell, das aus einem regelmäßigen Gitter besteht, indem jede Zelle einen finiten Zustand hat. Der initiale Zustand wird gesetzt, indem jeder Zelle ein Anfangszustand zugewiesen wird. Die Simulation schreitet in diskreten Zeitschritten voran. Der Zustand einer Zelle zum Zeitpunkt t hängt nur vom Zustand ihrer Nachbarzellen im Zeitschritt t-1 und einer Reihe von festen Regeln ab.

Zellnachbarschaften

Die Zellen, die einen Einfluss auf den Zustand einer Zelle haben heißen Nachbarschaft. Bei zellularen Automaten gibt es zwei häufig verwendete Nachbarschaften: Die Moore-Nachbarschaft und die Von-Neumann-Nachbarschaft. Die Moore-Nachbarschaft enthält alle Nachbarzellen, auch wenn diese nur einen Eckpunkt mit der Zelle gemeinsam haben. Die Von-Neumann-Nachbarschaft hingegen enthält nur Zellen, die eine Kante mit einer Zelle teilen.

Moore Nachbarschaft

Van Neumann Nachbarschaft

Regeln für Game of Life

Im Spiel des Lebens kann jede Gitterzelle einen von zwei Zuständen einnehmen: tot oder lebendig. Das Spiel des Lebens wird durch vier einfache Regeln kontrolliert, die auf jede Gitterzelle im Simulationsbereich angewendet werden:

• Eine lebendige Zelle stirbt, wenn sie weniger als zwei lebendige Nachbarzellen hat.
• Eine lebendige Zelle mit zwei oder drei lebendigen Nachbarn lebt weiter.
• Eine lebendige Zelle mit mehr als drei lebenden Nachbarzellen stirbt im nächsten Zeitschritt.
• Eine tote Zelle wird wiederbelebt, wenn sie genau drei lebende Nachbarzellen hat.

Folgende Darstellung verdeutlicht die Regeln anhand von Beispielmustern:

Randbedingungen

Zellulare Automaten benutzen häufig eine toroidale Topologie des Simulationsbereichs. Das bedeutet, das gegenüberliegende Kanten des Gitters miteinander verbunden sind. Die Gitterspalte rechts außen ist der Nachbar der äußersten Gitterspalte links, die oberste Gitterzeile ist der Nachbar der untersten Gitterzeile und umgekehrt. Mit einer solchen Topologie wird ein ungehinderter Transport von Zellstatusinformationen über die Gittergrenzen hinweg gewährleistet.

Gegenüberliegende Zeilen/Spalten sind verbunden und bilden eine toroidale Topologie des Simulationsbereiches

Zellen außerhalb des Gitters werden behandelt, als seien sie "tot".

Bei einem anderen Typ von Randbedingung behandelt man alle Zellen außerhalb des Gitters, als hätten sie einen festen Zustand. Für das Spiel des Lebens bedeutet das sie werden behandelt, als seien sie tot. Der Vorteil dieser Randbedingungen für das Spiel des Lebens ist, das die entstehenden Muster, wie z.B. Gleiter daran gehindert werden an der gegenüberliegenden Kante des Simulationsbereichs wieder in diesen einzutreten. Damit kann beispielsweise die Zerstörung einer Gleiterkanone durch die von ihr produzierten Gleiter verhindert werden. (Mehr Details zu Gleitern folgen im nächsten Kapitel)

Beispielmuster

In einen typischen Durchlauf des Spiels des Lebens werden bestimmte Muster häufig auftreten. Einige davon sind statisch (Stillleben), andere oszillieren und wieder andere bewegen sich durch das Simulationsgebiet. Einige Muster sind sogar in der Lage andere Muster zu erzeugen. Die folgende Tabelle gibt einen Überblick über häufig auftretende Muster im Spiel des Lebens.

Stillleben

Stillleben sind statische Strukturen, die sich im Verlauf der Zeit nicht ändern.

Block

Der Block ist das häufigste "still life". Er besteht aus vier Zellen, die einen 2x2 Block bilden. Ein Block ist ein sogenannter "eater". Das bedeutet, das er andere Muster zerstören kann ohne selbst strukturell Schaden zu nehmen.

Beehive (deutsch: Bienenstock):

Ein "still life", das aus 6 Zellen besteht. Das am zweithäufigsten vorkommende Stillleben.

Loaf (deutsch: Laib):

Ein aus 7 Zellen bestehendes Stillleben. Das am dritthäufigsten vorkommende Stillleben.

Oszillatoren

Oszillatoren sind Strukturen, die sich periodisch mit der Zeit wiederholen, ihre Position dabei aber beibehalten.

Raumschiffe

Raumschiffe sind Strukturen, die sich über das Spielfeld des "Game of Life" bewegen.

Über John Horton Conway

John Horton Conway (Foto: Thane Plambeck; 2005; Bild wurde farbangepasst und neu zugeschnitten)

John Horton Conway (26 Dezember 1937 in Liverpool, UK; † 11 April 2020 in New Brunswick, USA) war ein britischer Mathematiker. Er beschäftigte sich mit endlichen Gruppen, Knotentheorie, Zahlentheorie, Kodierungstheorie, kombinatorischer Spieltheorie und leistete viele Beiträge zur Unterhaltungsmathematik.

Conway wuchs in Liverpool auf. Den ersten Teil seiner Karriere verbrachte er an der Universität von Cambridge. Später wechselte er in die USA zur Universität von Princeton, wo er den Lehrstuhl von John von Neumann übernahm, den er bis zum Ende seiner Karriere inne hatte. Für seine Arbeiten erhielt er 1971 den Berwick Preis sowie 1987 den Pólya-Preis von der London Mathematical Society. Im Jahr 1981 wurde er Fellow der Royal Society. 1992 wurde er in die American Academy of Arts and Sciences gewählt und erhielt im Jahr 2000 den Leroy P. Steele Prize der American Mathematical Society.

Zu seinen, bei Nichtmathematikern, bekanntesten Arbeiten zählt die Erfindung des "Spiels des Lebens" (engl. "Game of Life). Conway selbst sagte in einem Interview mit dem Youtube-Kanal Numberphile [7], dass er das "Spiel des Lebens" nicht besonders interessant fand und die Aufmerksamkeit, die es erzeugte nicht nachvollziehen konnte. Seiner Meinung nach überschattete "Game of Life" wichtigere mathematische Errungenschaften, weshalb er es zeitweise hasste darauf angesprochen zu werden. Mit zunehmendem Alter sah er es aber als eine Errungenschaft an, auf die er stolz war [7].

Am 11. April 2020 starb Conway an den Komplikationen einer COVID-19 Erkrankung.

Die Erfindung von "Game of Life"

Der englischsprachige Youtube-Kanal Numberphile [1] hat im Jahr 2014 ein Interview mit John Conway geführt. Darin werden unter anderem die Ursprünge des Zellularen Automaten erklärt und warum Conway ein gespaltenes Verhältnis zu seiner Simulation hatte. Nebenbei wird erläutert, was Spiel des Lebens mit Terraforming auf dem Mars zu tun hat.

Neue Entwicklungen

Durch seine Entdeckung im Jahre 1970 war das Spiel des Lebens (engl.: Game of Life) bereits in der Anfangszeit der Computertechnik sehr beliebt. Für seine Umsetzung benötigt man wenig Ressourcen und so wurde es in den achtziger Jahren des letzten Jahrhunderts von fast jedem Computerbegeisterten sofort auf den damals aufkommenden 8 Bit Heimcomputern implementiert. Es wurde schnell zu einer Art "Hello World" der Computerprogrammierung. Was viele Menschen daran fasziniert ist, das ein sehr einfacher Regelsatz für beliebig komplizierte Muster verantwortlich sein kann. Im folgenden Kapitel wollen wir kurz neuere Entwicklungen zum Spiel des Lebens aufgreifen.

Das OCTA-Metapixel

In dem Interview auf der vorhergehenden Seite hat John Conway bereits erwähnt, das man mit dem Spiel des Lebens beliebige Berechnungen anstellen kann. Was das bedeutet, zeigt auf beeindruckende Weise das Octa-Metapixel. Das ist ein komplexes Muster in Game of Life, welches seinerseits die Regeln von Game of Life implementiert. Vereinfacht gesagt implementiert das Octa-Matapixel Game of Life in Game of Life! (Wen erinnert das noch an den Film Inception?)

Der Grundbaustein dieser Simulation ist das OCTA-Metapixel [3]. Dabei handelt es sich um eine 2048 x 2048 Einheitszelle, die von Brice Due im Jahr 2006 entworfen wurde. Eine Einheitszelle ist ein Gebilde, das in der Lage ist andere zellulare Automaten nachzubilden (oder auch sich selbst). Es gab bereits vorher andere Einheitszellen für das Spiel des Lebens, wie z.B. die P5760 Einheitszelle, allerdings ist das OCTA-Metapixel dahingehend einzigartig, das es einer Zelle sehr ähnlich sieht.

Smooth Life

Smooth Life ist der Name für eine Erweiterung des Spiels des Lebens auf einen kontinuierlichen Simulationsbereich. Anstelle von diskreten Zuständen werden Gleitkommazahlen verwendet. Die Regeln von SmoothLife wurden von Stephan Rafler [5] entworfen. Das hier gezeigte Video wurde von Tim Hutton mit SmoothLife erstellt. Eine ausführlichere Sammlung von SmoothLife videos kann auf dem SmoothLife Videokanal bestaunt werden.

Trivia / Eastereggs

• Wenn man bei Google nach "Conways Game Of Life" sucht, wird rechts oben auf der Ergebnisseite das Spiel des Lebens angezeigt. (Javascript muss aktiviert sein)

Quellenangaben

1. “Inventing Game of Life - Numberphile.” Youtube, Interview mit John Conway auf dem Youtube-Kanal von numberphile (englischsprachig), youtube.com, 2014.
2. “Life in Life.” Youtube, Kanal von Phillip Bradbury, youtube.com
3. “OTCAmetapixel - How does is work” Archivierter Link einer Webseite mit Erklärungen zum Octa-Metapixel (englischsprachig), Archive.org.
4. “OTCA metapixel” Artikel bei LifeWiki mit Erklärungen zum OCTA-Metapixel (englischsprachig), Web.
5. “Generalization of Conway's "Game of Life" to a continuous domain - SmoothLife” Stephan Rafler, 2011
6. The fantastic combinations of John Conway's new solitaire game "life"", Scientific American 223, Seiten 120-123, Martin Gardner, Oktober 1970
7. “Does John Conway hate his Game of Life?” Youtube, Interview mit John Conway auf dem Youtube-Kanal von numberphile (englischsprachig), youtube.com, 2014