9.2 Conway’s Game of Life

Im Folgenden widmen wir uns einem der berühmtesten aller zellulären Automaten: Conway’s Game of Life. Falls du noch nichts vom Game of Life gehört hast, das Video unten bietet einen spannenden Einstieg:

from IPython.display import YouTubeVideo
YouTubeVideo("CgOcEZinQ2I")

Die Regeln des Game of Life gehen so: Auf einem Grid befinden sich Zellen, welche in einem Moment einen von zwei Zustände annehmen können: tot oder lebendig. In jedem Zeitschritt entscheidet sich, ob eine tote Zelle zum Leben erwacht, eine lebendige Zelle stirbt oder am Leben bleibt. Geburt, Leben und Tod hängen dabei von den 8 Nachbarzellen einer Zelle ab.

Die genauen Regeln lauten so:

1. Eine tote Zelle mit genau drei lebenden Nachbarn wird in der Folgegeneration neu geboren.

2. Lebende Zellen mit weniger als zwei lebenden Nachbarn sterben in der Folgegeneration an Einsamkeit.

3. Eine lebende Zelle mit zwei oder drei lebenden Nachbarn bleibt in der Folgegeneration am Leben.

4. Lebende Zellen mit mehr als drei lebenden Nachbarn sterben in der Folgegeneration an Überbevölkerung.

Quelle: Wikipedia

Wichtig ist, dass diese Regeln in jedem Zeitschritt für jede Zelle “gleichzeitig” angewendet werden. Wir haben also eine synchrone Aktualisierung der “Agenten” bzw. Zellen. Erst nehmen alle Zellen denselben Zustand der Welt wahr, reagieren für die anderen Zellen nicht wahrnehmbar darauf und setzen intern ihren neuen Zustand für den nächsten Zeitrschritt fest. Erst wenn alle Zellen ihren neuen Status intern festgelegt haben, ersetzen alle Zellen ihren alten Status durch den soeben ermittelten neuen Status.

Übrigens

Bekannt wurde das “Game of Life” durch eine Veröffentlichung von Martin Gardner im Jahr 1970. Den Text des Original-Artikels findest du hier.

Unten siehst du zwei Videos einer Implementierung des Game of Life mit Python und der Animierung mit Matplotlib + Celluloid.

from IPython.display import Video
Video("game_of_life_video1.mp4", embed = True, width = 600)

Video("game_of_life_video2.mp4", embed = True, width = 600)

Das Game of Life hat keinen direkten sozialwissenschaftlichen Inhalt, ist aber vom Prinzip her wie eine agentenbasierte Modellierung, wie wir sie auch in den Sozialwissenschaften programmieren würden, aufgebaut, sodass wir damit sehr gut die Programmierung von ABM mittels objektorientierter Programmierung üben können. Und es zeigt wieder einmal, wie einfache Regeln auf der Mikroebene komplexe Phänomene auf der Makroebene hervorbringen können. Würden wir die Regeln der Mikroebene nicht kennen, würden wir beim Blick auf das Video vielleicht denken, dass wir dort unvorhersehbare, zufällige Dynamiken sehen. Aber so ist es nicht. Die zu sehende Dynamik ist komplett determiniert und bei Kenntnis der Regeln können wir jeden Schritt des Systems ableiten. Daher kann uns das Game of Life dazu motivieren auch für das scheinbar komplexeste aller Systeme, die Gesellschaft, nach den generierenden Regeln auf der Mikroebene zu suchen.

Bestimmte, gezielt angeordnete Startbedingungen des Game of Life führen zu enorm “komplexen” Systemen, wie im untigen Video zu sehen ist. Denke immer daran, die Abfolge ist nicht einprogrammiert - sie entsteht allein aus einer bestimmten Anordnung der Zellen zu Beginn und der daran anschließenden wiederholten Anwendung der immer gleichen Regeln des Game of Life.

YouTubeVideo("C2vgICfQawE")

Unten im Video gibt es ein Interview mit dem leider kürzlich an “Corona” verstorbenen John Conway, in dem er über die Entstehung des Game of Life spricht.

YouTubeVideo("R9Plq-D1gEk")

Aufgabe 1

Unten siehst du eine mögliche Implementierung des Game of Life. Die Zellen, welche im Game of Life die “handelnden Akteure” sind, werden als eigene Objekt-Klasse implementiert. Allerdings fehlt der Klasse Cell eine wichtige Methode, welche überprüft, wie viele Nachbarzellen lebendig sind und entsprechend den eigenen, nächsten Lebendigkeitsstatus festlegt. Gleich wird es deine Aufgabe sein, diese fehlende Methode namens set_next_status() zu implementieren.

• Versuche den untigen Code so gut es geht nachzuvollziehen.

• Kopiere den Code in ein eigenes Python-Skript und führe diesen aus. Trotz der fehlenden Methode sollte der Code ohne Fehler laufen und nach einiger Zeit sollte ein Video auf deinem Computer auftauchen. Allerdings passiert aufgrund der fehlenden Methode set_next_status() nichts im Video.

Aufgabe 2

• Ersetze in der Cell-Methode set_next_status() das Wörtchen pass durch richtigen Code. Die Methode set_next_status() sollte nach den obigen Regeln des Game of Life den nächsten Lebendigkeitsstatus ermitteln und im Cell-Attribut next_status abspeichern.

  • Die Methode set_next_status() sollte zunächst alle Nachbarzellen der Zelle durchgehen und zählen, wie viele Nachbarzellen lebendig sind. Jede Zelle kann über das Attribut neighbor_cells auf alle Nachbarzellen zugreifen. Eine lebendige Nachbarzelle weist auf dem Attribut status den Wert 1 und eine tote Nachbarzelle den Wert 0 auf.

  • Nachdem ermittelt wurde, wie viele Nachbarzellen leben, muss mittels mehrerer If-Statements und entsprechend der obigen Regeln des Game of Life festgelegt werden, ob die Zelle im nächsten Zeitschritt tot oder lebendig ist.

  • Der ermittelte Lebendigkeitsstatus für den nächsten Zeitschritt muss dann im Cell-Attribut next_status eingespeichert werden.

• Wenn du alles richtig gemacht hast, solltest du nun nach Ausführung des Codes eine Animation erhalten, welche die typischen Dynamiken des Game of Life beinhaltet.

• Verändere Parameter wie z.B. die Größe des Grids und die Länge der Zeitschritte und führe den Code aus.

• Gerne kannst du mit anderen Verhaltensregeln für die Zellen oder Farben herumexperimentieren.

Eine (unvollständige) Implementierung

import random
import celluloid as cld
import matplotlib.pyplot as plt

class Cell:
    def __init__(self, row_pos, col_pos):
        """Zellen-Attribute festlegen"""
        
        # Zeilen-Position der Zelle auf Grid
        self.row_pos = row_pos
        
        # Spalten-Position der Zelle auf Grid
        self.col_pos = col_pos
        
        # Lebendigkeits-Status der Zelle (1="lebend", 2="tot"). Wird anfangs zufällig festgelegt.
        self.status = random.randint(0, 1)
        
        # Lebendigkeits-Status der Zelle im nächsten Zeitschritt. (999="noch unbestimmt")
        self.next_status = 999
        
        # Liste, in welche alle Nachbarzellen eingespeichert werden
        self.neighbor_cells = []
    
    
    def find_neighbor_cells(self, grid):
        """Sucht alle 8 Nachbarn der Zelle auf Grid und speichert diese im Cell-Attribut 'neighbor_cells'."""
        
        # Anzahl der Zeilen und Spalten des Grids herausfinden
        n_rows = len(grid)
        n_cols = len(grid[0])
        
        # Zeilenposition überhalb, eigene Zeilenposition und die Zeilenposition unterhalb durchgehen
        for row_deviation in [-1, 0, 1]:
            
            # Spaltenposition links, eigene Spaltenposition und die Spaltenposition rechts durchgehen
            for col_deviation in [-1, 0, 1]:
                
                # Zeilenposition und Spaltenposition der Nachbarzelle berechnen
                neighbor_row = (self.row_pos + row_deviation) % n_rows
                neighbor_col = (self.col_pos + col_deviation) % n_cols
                
                # Nachbarzelle auswählen
                neighbor_cell = grid[neighbor_row][neighbor_col]
                
                # Wenn es eine Nachbarzelle ist und nicht man selbst
                if neighbor_cell != self:
                    # als Nachbarzelle einspeichern
                    self.neighbor_cells.append(neighbor_cell)
                
    
    def set_next_status(self):
        """Prüft, wie viele Nachbarzellen lebendig sind und 
        leitet daraus für sich selbst den nächsten Lebendigkeitsstatus ab."""
        pass
        
        
    def update_status(self):
        """Ersetzt den aktuellen Lebendigkeitsstatus durch den nächsten Lebendigkeitsstatus."""
        if self.next_status != 999:
            self.status = self.next_status
            self.next_status = 999

def create_grid(n_rows, n_cols):
    """Erstellt ein Grid als geschachtelte Liste, welche Cell-Objekte enthält.
    Zudem wird für jede Zelle die Nachbarschaft herausgesucht und eingespeichert."""
    
    # Geschachtelte Liste erstellen und Cell-Objekte einfügen
    grid = []
    for i in range(n_rows):
        row = []
        for j in range(n_cols):
            cell = Cell(row_pos=i, col_pos=j)
            row.append(cell)
        grid.append(row)
    
    # Nachbarzellen finden und einspeichern
    for row in grid:
        for cell in row:
            cell.find_neighbor_cells(grid)
    
    return grid


def create_color_matrix(grid):
    """
    Erstellt ein grafisch darstellbares Abbild des Grids, wobei der Lebendigkeitsstatus der Zellen farblich kodiert werden.
    Eine tote Zelle wird mit der Farbe weiss, eine lebendige Zelle mit der Farbe schwarz kodiert.
    """
    color_matrix = []
    for row in grid:
        color_row = []
        for cell in row:
            if cell.status == 0:
                color = [255, 255, 255]
            else:
                color = [0, 0, 0]
            
            color_row.append(color)
        color_matrix.append(color_row)
    
    return color_matrix

# Matplotlib & Celluloid-Objekte für grafische Darstellung/Animation erstellen
fig, ax = plt.subplots()
camera = cld.Camera(fig)

# Das Grid mit Zellen erstellen
grid = create_grid(50, 50)

# Simulationsloop
# für jeden Zeitschritt
for tick in range(1000):
    
    # Grafische Darstellung
    # Grid in farblich darstellbare Matrix übersetzen, diese als Diagramm darstellen und Foto davon schießen
    color_matrix = create_color_matrix(grid)
    plt.imshow(color_matrix)
    camera.snap()
    
    # Synchrone Aktualisierung Schritt 1: Interne Veränderung
    # jede Zelle durchgehen und nächsten Lebendigkeitsstatus festlegen
    for row in grid:
        for cell in row:
            cell.set_next_status()
    
    # Synchrone Aktualisierung Schritt 2: Veränderung sichtbar machen
    # jede Zelle durchgehen und den nächsten Lebendigkeitsstatus in den aktuellen Lebendigkeitsstatus umwandeln
    for row in grid:
        for cell in row:
            cell.update_status()
    
    
# Animation erstellen & speichern
animation = camera.animate()
animation.save("game_of_life.mp4", fps=10, dpi=500)