gerahmt|Die Figur „Gleiter“ bildet anhand der Regeln alle vier Generat­ionen eine verscho­bene Kopie ihrer selbst, wodurch sie sich „fort­bewegt“. Das Spiel des Lebens () ist ein vom Mathematiker John Horton Conway 1970 entworfenes Spiel, das auf einem zweidimensionalen zellulären Automaten basiert und eine einfache und bis heute populäre Umsetzung der Automaten-Theorie von Stanisław Marcin Ulam bildet.

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

Das Spielfeld Das Spielfeld ist rechtwinklig 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. Diese Zustände werden meist als lebend und tot bezeichnet und können beliebig dargestellt werden, etwa durch unterschiedliche Farben oder durch Besetzung mit Spielsteinen auf einem realen Spielfeld.

Das Spiel kann manuell auf einem Stück Papier gespielt werden, meist wird es aber auf einem Computer simuliert, der die Weiterführung der Generationen sehr viel schneller vornehmen kann als ein menschlicher Spieler von Hand. Da ein reales Spielfeld immer einen Rand hat, muss das Verhalten am Rand 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 (ausschnittsweise) Abbildung eines tatsächlich unendlichen Spielfeldes, das sich im angezeigten Rahmen unbegrenzt verschieben lässt.

Die Spielregeln Das Spiel läuft schrittweise ab. Zunächst wird eine Anfangsgeneration von lebenden Zellen auf dem Spielfeld definiert. Aus der vorliegenden Generation (dem Gesamtbild des Spielfeldes) wird die Folgegeneration ermittelt. Der Zustand jeder einzelnen Zelle in der Folgegeneration ergibt sich dabei nach einfachen Regeln aus ihrem aktuellen Zustand sowie den aktuellen Zuständen ihrer acht Nachbarzellen (Moore-Nachbarschaft).

Nach Conways ursprünglicher Regel lebt eine Zelle in der nächsten Runde, wenn zuvor in ihrer 3x3-Umgebung insgesamt genau drei Zellen leben, wobei sie selbst nur bei Bedarf mitgezählt wird, das heißt:

Regel Beispiele(Ausschnitt aus dem Spielfeld, lebende Zellen grün dargestellt)1. Eine lebende Zelle lebt auch in der Folgegeneration, wenn sie entweder zwei oder drei lebende Nachbarn hat.

Im Beispiel hat die lebende mittlere Zelle genau zwei lebende Nachbarn und wird in der nächsten Generation weiterhin leben. Über die anderen Zellen lässt sich ohne Kenntnis ihrer weiteren Nachbarn keine Aussage machen.2. Eine tote Zelle „wird geboren“ (lebt in der Folgegeneration), wenn sie genau drei lebende Nachbarn hat.

Im Beispiel hat die tote mittlere Zelle genau drei lebende Nachbarn und wird in der nächsten Generation leben.Aus diesen Regeln folgt umgekehrt:

(−1) Eine lebende Zelle „stirbt“ (ist in der Folgegeneration tot), wenn sie weniger als zwei (Vereinsamung) oder mehr als drei (Übervölkerung) lebende Nachbarn hat. (−2) Eine tote Zelle bleibt tot, wenn sie nicht genau drei lebende Nachbarn hat.

Im ersten Beispiel hat die mittlere Zelle nur einen lebenden Nachbarn und stirbt. Im zweiten Beispiel hat die mittlere Zelle fünf lebende Nachbarn und stirbt. Darüber hinaus haben die lebenden Zellen a und b mindestens vier (bis zu 7) lebende Nachbarn und sterben. Die tote Zelle c mit mindestens vier (bis zu 7) lebenden Nachbarn bleibt tot. Regeln von Conway’s Game of Life Anzahl lebender Nachbarn 0 1 2 3 4 5 6 7 8 Ergebnis Folgegeneration 0 0 C 1 0 0 0 0 0 C bedeutet: "Kopiere den jetzigen Zustand" Mit diesen einfachen Regeln kann aus gegebenen Anfangsmustern im Laufe des Spiels eine Vielfalt komplexer Strukturen wachsen, wobei unter „Strukturen“ die von lebenden Zellen gebildeten Formen gemeint sind. Andererseits können auch sämtliche lebenden Zellen vereinsamen und sterben, dann entsteht eine „leere Welt“. Es gibt statische Strukturen, die sich von einer zur nächsten Generation nicht ändern, andere oszillieren, indem sie sich selbst innerhalb einer endlichen Anzahl Generationen an derselben Position reproduzieren, 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 Seit seiner Vorstellung wurde Conways Spiel des Lebens intensiv untersucht; dabei wurden zahlreiche Objekte entdeckt, die aus einem gegebenen Anfangszustand entstehen können und charakteristische Verhaltensweisen zeigen. Sie werden anhand ihres Verhaltens über mehrere Generationen hinweg in Klassen eingeteilt:

Statische Objekte Statische Objekte, im Jargon auch still life („Stillleben“), sind Objekte, die sich im Spielverlauf ohne äußere Einflüsse nicht weiter verändern können, da in ihnen alle lebenden Zellen 2 oder 3 lebende Nachbarn haben und damit am Leben bleiben, während alle toten Zellen, auch in der unmittelbaren Umgebung, nicht genau drei lebende Nachbarn haben und damit tot bleiben.

Statische Objekte bleiben häufig als „Überreste“ von Wachstumsvorgängen auf dem Spielfeld zurück und bestehen unverändert fort, bis sie von einem bewegten Objekt oder einem wachsenden Bereich berührt werden.

Einige statische Objekte: 60px 60px 60px 60px 60px 60px 60px 60px Name Block Beehive(„Bienenstock“) Boat(„Boot“) Loaf(„Brotlaib“) Tub(„Kübel“) Barge(„Kahn“) Pond(„Teich“) Eater(1)(„Fresser“)

Der Block kann auch als Reflektor für bewegte Objekte dienen, beispielsweise in der Gosper Glider Gun. Der Eater(1) heißt so, weil er einige bewegte Objekte, beispielsweise von links oben auftreffende Gleiter, durch Interaktion „fressen“ (d. h. restlos auflösen) kann und anschließend wieder an derselben Position auf dem Feld steht. Der Loaf (auch „Turner“ genannt) kann, wenn er an einer bestimmten Position von einem Gleiter getroffen wird (in der oberigen Darstellung: rechts unten), den Gleiter auflösen und sich um 180° drehen.

Oszillierende Objekte Hierbei handelt es sich um Objekte, die zwar auch „statisch“ in dem Sinne sind, dass sie ihre Position auf dem Spielfeld beibehalten, sich jedoch von Generation zu Generation verändern, bis sie nach einer endlichen Anzahl von Generationen wieder den Ausgangszustand erreichen. Wie bei den Stillleben gilt dies nur, solange alle direkt angrenzenden Zellen tot sind und das Objekt „isolieren“.

Sehr einfach und häufig ist der Blinker, eine horizontale oder vertikale Reihe von drei lebenden Zellen. In der nächsten Generation werden die zwei äußeren Zellen der Reihe tot sein, während orthogonal zwei Zellen geboren werden, so dass die Figur um 90° gedreht wieder erscheint.

Eine Reihe von zehn horizontal oder vertikal aneinander hängenden Zellen entwickelt sich zu einem Oszillator mit 15 Generationen, dem Pulsator.

Beispiele oszillierender Objekte:

Blinker Unruh(1) Unruh(2) 0-Laser 2-Laser Pulsator Fontäne Datei:2g3 z5.gif Name Blinker Uhr Kröte Bipole Tripole Pulsator Tümmler Oktagon Zyklusdauer 2 2 2 2 2 15 14 5

Der Pulsator wird im Englischen Pentadecathlon genannt, da sein Zyklus 15 Schritte dauert. Er kann, ebenso wie oben der Eater(1), Gleiter fressen. Der Tümmler, auch Stehaufmännchen genannt, wird im englischen als Tumbler bezeichnet.

Raumschiffe und Gleiter Raumschiffe sind (zumeist oszillierende) Objekte, die – wie die Oszillatoren – innerhalb weniger Generationen eine Kopie ihrer selbst erzeugen, aber an anderer Position des Spielfelds. Das erweckt den Eindruck, sie würden sich über das Spielfeld „bewegen“. Dies ist ein Beispiel der dem Spiel innewohnenden Emergenz: Die Regeln des Spiels sagen nichts über sich fortbewegende Formen aus, und doch bewirken sie genau das.

Man kann zwischen den diagonalen Raumschiffen (zum Beispiel Gleiter und Qualle) und den orthogonalen Raumschiffen (zum Beispiel Segler) unterscheiden. Diagonale Raumschiffe verschieben ihre Position in beiden Dimensionen des Spielfeldes, orthogonale nur in einer. Alle Raumschiffe bewegen sich auf einem unendlichen Spielfeld unendlich fort (solange sie auf kein anderes Objekt treffen, das ihre Replikation beeinflusst) und hinterlassen keine Spur (dann wären es Puffer).

Beispiele für Raumschiffe sind: Gleiter Gleiter Gleiter Animation Segler(1) (LWSS) (Light-Weight Spaceship) lightweight spaceship Segler(2) (MWSS) (Middle-Weight Spaceship) middleweight spaceship Segler(3) (HWSS) (Heavy-Weight Spaceship) heavyweight spaceship

drei Segler Ablauf einer Animation dieser drei Segler

Raumschiffe haben eine strukturell bedingte Geschwindigkeit, die sich als Quotient aus der Verschiebung pro Periode und der dafür benötigten Generationenzahl ergibt. Als Bezugswert gilt die Lichtgeschwindigkeit c mit einer Zelle Verschiebung pro Periode. Beispiel: der Gleiter benötigt vier Generationen, um ein Feld weiter in der Ursprungsform zu erscheinen, und hat damit die Geschwindigkeit c/4. Die drei Segler haben auch Perioden von vier Generationen, kommen dabei aber zwei Felder weit und besitzen damit die Geschwindigkeit 2c/4 oder c/2. Da eine beliebige Struktur immer nur unmittelbar angrenzende Zellen in der folgenden Generation verändern kann, nicht aber „die übernächste“, ist eine Geschwindigkeit über c von Raumschiffen oder Wachstumsvorgängen im Spiel nicht möglich.

Das Hacker-Emblem nach Eric Steven Raymond ist vom Gleiter abgeleitet.

Gleiterkanonen rechts|mini|Gosper glider gun besteht aus einem bewegten Doppelobjekt mit zwei Blöcken als Reflektoren. Alle 30 Generationen entsteht ein Gleiter. Gleiterkanonen (glider guns) sind oszillierende Objekte, die regelmäßig Gleiter absondern, die schräg von ihnen wegfliegen. Gosper glider gun, von der alle 30 Generationen ein Gleiter ausgeht, wurde bereits im November 1970 entdeckt, nur einen Monat nach dem Erscheinen des Spiels an sich.LifeWiki: Gosper glider gun, abgerufen am 24. Mai 2022

Puffer Die Puffer kann man zu den Raumschiffen zählen, wobei die Puffer im Gegensatz zu den Raumschiffen eine Spur von Objekten hinterlassen. Meist sind dies statische oder pulsierende unbewegte Objekte, es kann sich jedoch auch um Gleiter oder Segler handeln.

Andere Objekte Außerdem gibt es Anfangskonfigurationen, die innerhalb endlich vieler Zeitschritte ein leeres Spielfeld erzeugen.

Eine weitere Möglichkeit sind völlig chaotische oder explodierende Muster. Das f-Pentomino (auch r-Pentomino genannt) bewirkt trotz seiner Einfachheit ein reichhaltiges Wachstum, das über 1102 Generationen chaotisch erscheint, bis das Spielfeld vom 1103. Schritt an eine – von sechs wegfliegenden Gleitern abgesehen – oszillierende Welt bildet. Dazwischen entstehen andere interessante Strukturen, zum Beispiel ab Schritt 774 die Bienenkönigin, die zwischen zwei Hindernissen hin und her fliegen kann. Das f-Pentomimo ist das einzige rechtwinklige Objekt aus weniger als 6 lebenden Zellen, das eine so aktive Welt erzeugt, alle anderen wachsen nach spätestens 10 Generationen nicht weiter.

Ein anderes solches Objekt ist die Zahl 42 (mit jeder Ziffer auf 3 mal 5 Kästchen), die nach 196 Schritten einige statische Objekte sowie 2 Gleiter produziert.Conway’s game of life (in html 5) auf Math Fail

Gleitersynthese