Game of Life

Zelluläre Automaten am Beispiel des "Spiels des Lebens" von John Horton Conway

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.

(Muster entnommen aus der LifeWiki)

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.

Van Neumann Neighborhood and Moore Neighborhood
Links: Moore-Nachbarschaft einer Zelle; Rechts: 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:

Bild mit Beschreibung der Regeln für Game of Life

Randbedingungen

Zellulare Automaten benutzen häufig eine toroidale Topolgie 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.

Opposing Edges of the Simulation domain are Connected
Verschiedene Randbedingungen für das Spiel des Lebens; Links: Gegenüberliegende Zeilen/Spalten sind verbunden und bilden eine toroidale Topologie des Simulationsbereiches; Rechts: Zellen ausserhalb des Gitters werden behandelt, als seien sie "tot".

Bei einem anderen Typ von Randbedingung behandelt man alle Zellen ausserhalb 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
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
Blinker:
Der kleinste und häufigste Oszillator.
Toad (deutsch: Kröte):
Oszillator mit Periode 2. Der zweithäufigste natürlich vorkommende Oszillator.
Beacon (deutsch: Leuchtfeuer):
Der am dritthäufigsten vorkommende Oszillator. Besteht aus zwei sich horizontal berührenden Blöcken.
Raumschiffe
Der Gleiter:
Gleiter sind Muster, die sich diagonal über das Simulationsgebiet bewegen. Sie sind die kleinsten und häufigsten Raumschiffe.
Leichtes Raumschiff:
Ein oszillierendes Objekt, das sich orthogonal über das Simulationsgebiet bewegt. Es ist das kleinste sich orthogonal fortbewegende Raumschiff.
Weekender:
Ein sich orthogonal fortwewegendes Raumschiff, größer als das vorige Muster.

Die Erfindung von "Game of Life"

Für diejenige, die der englischen Sprache mächtig sind, sei hier auf ein Interview verwiesen, das der englischsprachige Youtube-Kanal Numberphile [1] mit John Conway geführt hat. Darin werden unter anderem die Ursprünge des Zellularen Automaten erklärt. Wer Interesse hat zu erfahren, was das Spiel des Lebens mit Terraforming auf dem Mars zu tun sollte es sich ansehen.

Externer Inhalt: Video des Youtube-Kanals Numberphile

Video (Englisch): John Horton Conway im Interview mit dem Youtube-Kanal Numberphile.

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 Resourcen 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?)

Externer Inhalt: Video des Youtube Kanals von Phillip Bradbury

Video: "Life in Life" von Phillip Bradbury [3]. Erzeugt mit dem simulator Golly unter Verwendung des OCTA-Metapixels

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.

Externer Inhalt: Video des Youtube Kanals von Tim Hutton

Video: SmoothLife zeigt viele der bekannten Strukturen aus dem Spiel des Lebens, wie z.B. die Gleiter. Die Visualisierung von SmoothLife erinnert jedoch sehr stark an biologisches Leben. (Video © 2012; Tim Hutton)

Trivia

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

Referenzen

  1. “Inventing Game of Life - Numberphile.” Youtube, Interview mit John Conway auf dem Youtube-Kanal von numberphile (englischsprachig), Web.
  2. “Life in Life.” Youtube, Kanal von Phillip Bradbury, Web.
  3. “OTCAmetapixel - How does is work” Eine Webseite mit Erklärungen zum Octa-Metapixel (englischsprachig), Web.
  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
zurück     

Das könnte Sie auch interessieren: