Advertisement

Conways Spiel des Lebens

Eine Einführung in zelluläre Automaten mit dem "Spiel des Lebens" von John Horton Conway

Einführung in zellulare 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 ausgewählt, 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 Zeitschitt 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 verwandte Nachbarschaften: Die Moore Nachbarschaft und die Van Neumann Nachbarschaft. Die Moore-Nachbarschaft enthält alle Nachbarzellen, auch wenn diese nur einen Eckpunkt mit der Zelle gemeinsam haben. Die Van 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.

Randbedingungen

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

Conways 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. Der Artikel bekam mehr Zuspruch, als alle vorherigen Artikel von Gardner, inklusive seinem sehr bekannten Artikel über Hexaflexagons.

Für diejenige unter euch, 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. Auch wer Interesse daran hat zu erfahren, was das Spiel des Lebens mit Terraforming auf dem Mars zu tun hat ist herzlich eingeladen es sich anzusehen.

Externer Inhalt: Video des Youtube-Kanals Numberphile

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

Regeln

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:

Folgende Darstellung verdeutlicht die Regeln anhand von Beispielmustern:

Es gibt verschiedene Wege, die Zellen am Rand des Simulationsgebietes zu behandeln. Oftmals werden die Kanten des Simulationsbereiches einfach miteinander verbunden, wodurch eine toroidale Topologie entsteht. Alternativ kann man aber auch alle Zellen ausserhalb des Simulationsbereiches als tot ansehen. Das ist hilfreich, wenn man verhindern möchte, das Muster, wie beispielsweise Gleiter, über die Kanten in das Simulationsgebiet zurückwandern.

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.
zurück      weiter

Das könnte Sie auch interessieren: