Zum Inhalt springen

Conways Spiel des Lebens

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 8. Dezember 2004 um 23:13 Uhr durch 82.82.226.81 (Diskussion). Sie kann sich erheblich von der aktuellen Version unterscheiden.


Das Game of Life (englisch für "Spiel des Lebens") ist ein vom Mathematiker John Horton Conway entworfener zweidimensionaler zellulärer Automat. Das Spielfeld ist ein Raster quadratischer Zellen. Jede Zelle kann einen von zwei Zuständen einnehmen, die oft als lebendig und tot bezeichnet werden.

Das interessante daran ist, dass mit drei einfachen Regeln komplexe Strukturen und Mechanismen entstehen. Diese Strukturen und Mechanismen weisen Ähnlichkeiten zu solchen der biologischen und/oder technischen Welt auf. Es lassen sich auch Strukturen basteln, die logische Funktionen wie UND bzw. ODER nachbilden, oder rechnen können.

Das Spielfeld

Game of Life wird auf einem karierten Spielfeld simuliert. Perfekt wäre dabei ein unendlich großes Spielfeld, da nur so die Ränder den weiteren Verlauf nicht stören. So gibt es bestimmte Muster, Gleiter genannt, die von Zug zu Zug über das Spielfeld wandern. Sie können an den Rändern ihre Bewegungsrichtung umkehren und wieder auf eine "Siedlung", im Zweifelsfalle ihre eigene treffen und dort einen möglicherweise eingetretenen Stillstand wieder in ein neues aktives Gebiet verwandeln. Da ein unendlich großes Feld in der Realität nicht umzusetzen ist, muss über geeignete Randbedingungen nachgedacht werden. So erscheint ein Torus-förmiges Spielfeld als ideal, bei dem alles, was das Spielfeld nach unten verlässt, oben wieder herauskommt und umgekehrt, und alles, was das Spielfeld nach links verlässt, rechts wieder herauskommt und umgekehrt.

Die Sichtweisen

Was veranlasst einen Menschen, sich mit Game of Life zu beschäftigen, beziehungsweise was sieht er darin? Es gibt mindestens vier Standpunkte zu dieser Simulation:

  • 1. Das Verhalten als Gesamtes:
Für einen Teil der Leute ist es interessant, was für ein Verhalten bestimmte Regelwelten aufweisen. Ob sie explodieren oder implodieren; ob sie langsam schrumpfen; ob sie langsam "Aushärten"; ... .
  • 2a. Der Biologische Aspekt: Game of Life als Mikroskop:
Für einen anderen Teil ist Game of Life wie der Blick in ein Mikroskop. Man beobachtet die kleinen Strukturen, die man abzählen und bewerten kann. Für diesen Typus ist es immer eine Freude, wenn eine neue "Lebensform" auftaucht. Explodierende, expandierende oder gar "aushärtende" Regelwelten sind für diesen Typus uninteressant.
  • 2b. Der Chemische Aspekt: Energie und Materie:
Wenn man die Häufigkeit, die Komplexheit der Game of Life Objekte mit dem Aufwand an Energie und Zwischenschritten vergleicht, die benötigt werden, um eine bestimmte Chemische Verbindung zu bekommen, 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, Kohlendioxid und Salz. Objekte, wie Unruhe(2) und Fontaine wären dan 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.
  • 2c. Der Physikalische Aspekt: Kräfte und AWP:
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.


  • 3. 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 aufrecht erhalten, zu ihren Stationen fahren.
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.

Bekannteste Spielvariante (23/3)

Die ursprüngliche Conway-Welt, die bekannteste Spielvariante, wird durch folgende Regeln definiert:

  • Die Todes-Regel: Zellen mit mehr als drei oder weniger als zwei Nachbarn sterben.
Datei:Rules3.PNG
magenta: Zelle, die in der nächsten Generation sterben wird
grün: Nachbarn der Zelle


  • Die Geburt-Regel: Eine tote Zelle mit drei Nachbarn wird in der nächsten Generation zur lebenden Zelle.
Datei:Rules2.PNG
rot: Tote Zelle, die in der nächsten Generation geboren wird
grün: Nachbarn der Zelle

Aus diesen Regeln ergeben sich eine Reihe von Konfigurationen, die sich von Generation zu Generation nicht verändern: Ein Beispiel für ein statisches Objekt ist der Block mit den Ausmaßen 2x2; jede Zelle hat hier drei Nachbarn:

Quadro

Andere stabile Objekte sind:

Es sind auch Konfigurationen möglich, die nach einer bestimmten Anzahl von Generationen wieder ihre Ausgangskonfiguration annehmen. Die einfachste zyklische Konfiguration ist eine horizontale oder vertikale Reihe von drei lebenden Zellen. Beim horizontalen Fall wird direkt ober- und unterhalb der Zelle in der Mitte eine lebende Zelle geboren, während die äußeren beiden Zellen sterben; so erhält man eine vertikale Dreierreihe.

Eine Reihe von zehn horizontal oder vertikal aneinanderhängenden Zellen entwickelt sich sogar zu einem Objekt, das einen Zyklus von fünfzehn Generationen hat, dem Pulsator.

Beispiele oszillierender Objekte sind:

Datei:2g3 unruhe.gif Datei:4g3 unruhe.gif
Unruhe(2) Unruhe(1) 0-Laser 2-Laser
Datei:V pulsator.GIF
Pulsator Fontäne

Der Pulsator wird im englischen, aufgrund eines Zyklus mit 15 Schritten, Pentadecathlon genannt, und ist der Gleiter-Fresser. Die Fontäne ist im englischen als Tumbler bekannt.

Von besonderem Interesse sind Konfigurationen, die sich von Generation zu Generation fortbewegen und dabei ihre Gestalt erhalten. Beispiele sind 

   []       []  []
     [] <=>   [][]
 [][][]       []

   Gleiter
Segler(1) Segler(2) Segler(3)
LWSS MWSS HWSS




Ablauf einer Animation dieser drei Segler

Das r-Pentomino (hier rechts) bewirkt trotz seiner Einfachheit ein lange anhaltendes, chaotisches Wachstum.

Herausforderungen

Conway bot demjenigen einen Preis von 50 US-Dollar, der nachweisen konnte, dass mit Life unbegrenztes Wachstum möglich ist. Für einen Nachweis ist ein geordnetes Wachstum notwendig, daher waren die explosionsartigen Vermehrungen, die bei Life oft vorkommen, dafür ungeeignet. Eine Lösung war die so genannte "Gleiterkanone", die in regelmäßigen Abständen einen Gleiter, der nach vier Generationen eine verschobene Kopie von sich hervorbringt, erzeugt und dann wieder die Ursprungsform annimmt.

Es ist auch möglich, aus Kollisionen von Gleitern eine Gleiterkanone zu erzeugen. Zusammen mit der Möglichkeit, die Bahn von Gleitern durch Kollisionen mit anderen zu ändern, können so theoretisch selbstreplizierende Automaten entstehen.

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 Start-Daten.

CONWAY-3 Glider Gun Glider Eater.gif

Abweichende Regeln

Einleitung

Man kann sich auch 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 Nachbarn stirbt
  • Geburts-Regel: 1,3,5 oder 7 lebende Nachbarn erzeugen (oder erhalten) eine lebende Zelle

Wenn man in dieser Kopier-Welt eine Struktur in Form des Buchstaben H zeichnet, so werden lauter identische H-Buchstaben erzeugt.

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 zählt zunächst die Anzahl von Nachbarn auf, bei der eine Zelle nicht stirbt, und anschließend, durch einen Schrägstrich abgetrennt, die Anzahl der Nachbarn, bei der eine Zelle geboren wird.

Die klassische Conway-Welt wird also durch 23/3 beschrieben, die oben beschriebene Kopierwelt durch 1357/1357.

Sehr dicht an das klassische 23/3-Regelwerk (Zwei oder drei Nachbarn erhalten eine Zelle, drei Nachbarn erzeugen eine neue Zelle) kommen die Regelwerke 34/3 und 35/3. Insgesamt sind 262144 (218) Regelwerke denkbar, von denen die meisten jedoch uninteressant sind. Einige der interessanteren werden im Folgenden beschrieben.

Die 3/3 Welt

Statische Objekte: Bisher eines, nämlich der schon erwähnte 2*2 Block:

Quadro

Der der Conway-Welt zugeschriebene Block ist tatsächlich ein 3/3-Objekt, denn jede Zelle dieses Blocks hat 3 Nachbarn, und darum ist die Zwei-Nachbarn-Regel uninteressant.

In der 3/3 Welt gibt es zum Beispiel diese oszillierenden Objekte:

Datei:4g3 kegel.gif Datei:4g3 unruhe.gif Datei:4g3 strudel.gif
Pedal Kegel Unruhe(1) Strudel

Alle diese Objekte funktionieren auch in alle möglichen Variationen von Regelwelten bis 345678/3, also auch in den 34/3 und 35/3 Regelwelten. Nur Unruhe(1) funktioniert auch in allen Variationen, die in 2345678/3 enthalten sind, und damit auch in der Conway-Welt (23/3). Solche Objekte kann man als Wanderer bezeichnen.

Die 13/3 Welt

Dies ist eine Regelwelt mit wenigen oszillierenden Objekten. Die meisten Objekte sind "verkrüppelt".

Wenigstens die drei folgenden, oszillierenden Objekte gibt es:

Pingpong O1G3(2) 
    []
  []    []
  []    []
  []  []

 Pseudo-Gleiter

Als eine Variante der 13/3-Regelwelt kann man die 135/35-Regelwelt betrachten.

Die 34/3 Welt

Oszillierende Objekte der 34/3 Welt

Datei:4g3 kegel.gif Datei:4g3 unruhe.gif Datei:4g3 strudel.gif
Strange Frosch O4G3(3) O4G3(4) Pedal Kegel Unruhe(1) Strudel

Neben Strange und Frosch kommen auch die 3/3-Objekte Pedal, Kegel, Unruhe(1) und Strudel vor.

Die 35/3 Welt

In der 35/3 Welt gibt es zum Beispiel diese vier sich bewegenden Objekte:

Schwimmer(1) Schwimmer(2) 35/3-Segler 35/3-Mover

Ebenso wie in der 34/3 Regelwelt kommen die oszillierenden Objekte: Pedal, Kegel, Unruhe(1) und Strudel in der 35/3 Regelwelt vor.


Die 24/3 Welt

Statische Objekte: 

  [][]      []       [][]          [][]
  []      []  []   []    []        []
[][]        []     []    []    [][]  []
                     [][]      []  []

Oszillierende Objekte:

O24-3(1) O24-3(3) Seegurke O24-3(4)

Die 245/3 Welt

Neben den oszillierenden Objekten, die auch in der 24/3-Regelwelt vorkommen, existieren hier auch noch ein paar andere oszillierende Objekte.

Das besondere aber ist das Vorkommen eines sich bewegenden 7-Zyklen Objekts, das in seiner Art der Bewegung einer Qualle ähnelt: 

    []
  []  []
        []
      []

  Qualle

Antiwelten

Zu jeder Regel-Welt gibt es eine Antiregelwelt, in der Form, das alles invertiert ist. Also alle Zellen, die sonst tot sind leben, und alle Zellen die sonst leben sind tot. Dies zeigt sich im Ablauf durch ein Schwarzes Feld, auf dem die Strukturen weiß sind.

Um eine solche Antiregel-Welt zu erzeugen, kann man die Regeln in Form eines Schalterfeld darstellen:
Datei:Rules leer.PNG
G steht für geboren.
T steht für sterben.

Datei:Rules conway.PNG
Conway-Regeln

bedeutet, bei drei Nachbarn wird eine tote Zelle lebendig, bei keinem oder einem und vier bis acht Nachbarn stirbt eine Zelle, und ansonsten bleibt der Zustand einer Zelle unangetastet.

Wenn man die Zustände des Schalterfelds um 180° rotiert (nicht spiegelt oder kippt):
Datei:Rules anti conway.PNG
Anti-Conway-Regeln

dann bekommt man die Antiregeln.

Das funktioniert für alle Regeln.

Tabelle mit unterschiedlichen "Game of Life"-Regeln

Regel-Bezeichnung:   Kommentar:                                          
-------------------------------------------------------------------------
      3/3   G3   
     13/3  1G3
     23/3  2G3       Original Conways "Game of Life"
     34/3  4G3
     35/3  5G3
    236/3  26G3      explodierend. Teilweise mit den Strukturen aus 23/3
   135/35  1G35      erweitertes 13/3
1357/1357  G1357     Ein Kopiersystem, wobei jeweils eine einzige kleine
                     Struktur wunderbare Muster hervorzaubern kann.
    24/35  ----

Anti-Regeln:                   Kommentar:
-------------------------------------------------------------------------
01234678/0123478   6G0123478   Anti-Conway
01234678/0123678   4G0123678   Anti-4G3
   02468/02468      G02468     Anti-Kopiersystem


"Game of Life" mit übergehenden Regelwelten

Denkbar sind "Game of Life"-Simulationen, bei denen abgegrenzte Bereiche (zum Beispiel linke und rechte Seite) jeweils einer anderen Regelwelt unterzogen werden. Dabei könnte man sich bewegende Wanderer, die in beiden Regelwelten existieren können, aufspüren.

Andere "Game of Life"-Formen

Es wäre und ist auch denkbar anstatt auf quadratisch gerasterten Ebenen die Simulation auf einer sechseckigen, gerasterten Ebene zu "spielen". Dann wäre die maximale Zahl der Nachbarn nicht acht sondern sechs. Verschiedentlich gab es auch schon dreidimensionale "Game of Life"-Simulationen.

Siehe auch

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Conways_Spiel_des_Lebens&oldid=3600361“