Tschüss, Zellen: Game of Life als kontinuierliche Version
Ich interessiere mich ja für Themen im Umkreis des Artificial Life – nicht, um in dem Bereich zu forschen, sondern einfach als Hobby. Das Gebiet des Artificial Life ist eine gigantische Spielwiese. Man versucht, künstliche Systeme aus einfachsten Bestandteilen herzustellen – aber so, dass sie vielleicht ein paar der Eigenschaften von lebenden, biologischen Systemen innehaben. Es gibt viele Ansätze, solch ein künstliches System zu basteln, die meisten Systeme werden einfach mehr oder weniger aufwändig simuliert – kostet wenig, ist schön zum Ansehen, und ist einfacher auszuwerten. Ein gutes Beispiel ist meine Diplomarbeit, in der Schwarmverhalten einfach entsteht. Bringt nun einer dieser Ansätze spontan ein Systemverhalten hervor, das man aus den Regeln des Systems nicht ohne weiteres erkennen konnte, spricht man häufig von „emergentem Verhalten“ oder schlicht „Emergenz“. Dazu unten gleich noch kurz mehr.
Ein sehr bekanntes Beispiel für ein Artificial-Life-System sind sogenannte Zelluläre Automaten. Das sind im Grunde Kästchenwelten, also diskrete Welten meist einer oder zwei Dimensionen. Jedes Kästchen kann verschiedene Zustände innehaben. Auch die Zeit ist diskret, sie läuft in Zeitschritten und in jedem Zeitschritt ergibt sich der Zustand eines Kästchens (auch Zelle genannt) aus den Zuständen seiner Nachbarkästchen im vorherigen Zeitschritt. Mit anderen Worten, ein Kästchen bestimmt seinen Zustand anhand einer Übergangstabelle („Regel“ genannt) rein lokal – also ohne Kenntnis der Gesamtwelt. Bilden sich nun riesige, Kästchenübergreifende Systeme und Strukturen heraus, sprechen viele Leute wieder von Emergenz. Das interessante an Zellulären Automaten ist, dass man wirklich alle Zeitschritte durchrechnen muss und meist nicht einfach eine Formel finden kann, die den Zustand eines Kästchens für einen beliebigen Zeitschritt vorhersagt.
Nach der allgemeinen Einführung nun endlich mal was konkretes: Der bekannteste der Zellulären Automaten ist Conway's Game of Life. Es wurde von John Conway entwickelt, einem britischen Mathematiker, der Spaß an solchen mathematischen Spielchen hatte. Das Game of Life ist eine 2D-Kästchenwelt, wie Rechenpapier. Jede Zelle kann zwei Zustände einnehmen: Tot oder lebendig. Es ist klar, dass jede Zelle auf Rechenpapier von 8 anderen Zellen eingekreist wird. Ich habe gesagt, dass jede Zelle ihren Zustand für den nächsten Zeitschrift anhand ihrer lokalen Nachbarschaft „ausrechnet“, und so ist es auch hier. Es heißt Game of Life, also passiert das ganze biologisch motiviert:
- Lebendige Zellen sterben an Einsamkeit, wenn sie weniger als zwei lebendige Nachbarn haben. Sie sterben an Überbevölkerung, wenn sie mehr als drei lebendige Nachbarn haben. Bei zwei und drei lebenden Nachbarn bleiben sie unverändert lebendig.
- Tote Zellen leben im nächsten Zeitschritt, wenn sie exakt drei lebendige Nachbarn haben.
Diese Regeln reichen aus, um eine Vielzahl von Figuren aus lebenden Zellen zu basteln. Manche dieser Figuren sind „Stilleben“, bleiben also wie sie sind, weil jede ihrer Zellen eben entweder genau zwei oder genau drei lebendige Nachbarn hat. Manche sind periodisch: Sie verändern sich, Zellen sterben also und erwachen zum Leben, sie nehmen aber irgendwann wieder ihren Anfangszustand ein. Interessant sind periodische Figuren, bei denen der Anfangszustand, wenn er wieder erreicht ist, im Vergleich zu vorher verschoben ist. Diese nennt man „Spaceships“, da sie sich sozusagen durch den Raum bewegen. Eines der bekanntesten und einfachsten Spaceships ist der sogenannte „Glider“. Er ist rechts abgebildet, klickt mal drauf, dann seht ihr ihn in Bewegungm, lebende Zellen sind schwarz (© 2008, Wikipedia, Autor: Dhatfield).
Weiter interessante Figurenarten sind sogenannte „Metusehlas“, das sind Figuren, die aus möglichst einfachen Anfangszuständen möglichst lange unvorhersehbares Gewimmel erzeugen. Zigtausende Schritte aus einer einstelligen Anzahl gesetzten Anfangszellen sind keine Seltenheit. Es gibt eine riesige Fangemeinde, das Game of Life ist internetweit extrem populär. Eine vielzahl von Personen hat riesige Figuren aus abertausenden Zellen zusammengesetzt. Also können wir direkt mal ein paar Videos ansehen, die das ganze noch mehr illustrieren.
Als erstes gibt es ein Video, was noch einmal die Regeln vorstellt, und zwar bis Minute 1:10. Spult also vor, wenn ihr wollt, denn danach kommen alle möglichen Figuren(-Arten) des Game of Life (lebende Zellen sind weiß). Das ist mit die beste Zusammenstellung an riesigen Figuren, die ich bis jetzt gesehen habe. Insbesondere die Aufstellung an riesigen Spaceships bei 2:56 ist der Hammer, und ich bin mir gerade nicht vollends sicher, aber ich glaube, das Gebilde bei 2:29 ist die sagenumwobene Turingmaschine. Muss ich noch mal in meinem Script schauen, was ich zu Artificial Life mal vorbereitet, aber nie veröffentlicht habe (nur das Neuronale-Netze-Script hat es bis dahin geschafft). Die vielen kleinen Dinger, die da umherflitzen, sind übrigens oftmals Glider, wie der oben beschriebene. Alle diese höchst komplizierten Formationen aus teilweise abertausenden interagierenden „lebenden“ Zellen entstehen nur auf der Basis der einfachen, oben beschriebenen Regeln, ich habe hier nichts unterschlagen. Man braucht also keine komplizierten Systembestandteile, um Verhalten zu erzeugen, das derart kompliziert ist, dass es den Betrachter überrascht. Das ist genau, was landläufig „Emergenz“ genannt wird.
Hier gibt es auch noch ein Video, in dem jemand riesige Areale aus lebenden Zellen kreiert hat – die wieder Game of Life spielen (lebende Zellen wieder weiß). Ein „Meta-Game-of-Life“, sozusagen. Freak Stuff. Auf Youtube lassen sich jede Menge weitere solcher Videos finden.
Nach dieser trichterförmigen Kurzeinführung ins Game of Life, das ja ein Zellulärer Automat ist, die wiederum oft als Teil des Artificial Life gesehen werden, geht es nun zu dem, was ich euch eigentlich zeigen will: Einer kontinuierlichen Variante des Game of Life. Man mag jetzt denken, was für ein Widerspruch, er redet die ganze Zeit über diskrete Systeme mit diskretem Raum und diskreter Zeit und diskreten Zuständen – warum kommt jetzt was kontinuierliches? Und kann so etwas überhaupt so faszinierend funktionieren, wenn es gar keine abgetrennten Zellen gibt? Und wenn ja, wozu dann überhaupt noch zelluläre Automaten? Seht selbst! Erst erkläre ich auf saloppe, möglichst unmathematische Art und Weise, was dort getan wurde – und danach gibt es auch ein Video.
Das ganze wird in diesem Blogartikel auf 0fps heruntergebrochen und beschrieben (vielen Dank an Ralf fürs Einsenden). Wer Interesse an mehr mathematischen Details hat, kann dort gerne gucken, ich breche es für diese Kurzbeschreibung noch weiter herunter – mein Ziel ist immer, dass eine populär-Erklärung so gut wie formelfrei sein muss. Man erzeugt ein kontinierliches Game of Life, indem man drei Schritte durchführt:
Man schafft die Zustände 0 und 1 (tot und lebendig) ab und ersetzt sie durch den kontinuierlichen Bereich von 0 bis 1. Salopp gesagt, alle Zwischenwerte zwischen tot und lebendig sind jetzt möglich.
Man schafft das Kästchengitter ab und sieht die Welt als ein kontinuierliches zweidimensionales Feld an – mit anderen Worten: Eine Ebene. Ein unendliches Blatt Papier, meinetwegen. Statt voneinander abgetrennten Zellen, gibt es also jetzt einfach nur noch Punkte auf unserer Ebene, die beliebig nah oder weit voneinander entfernt sein können, ohne Mitbestimmung irgendeines Gitters. Und statt den Zuständen 0 und 1 hat jeder dieser Punkte zu jeder Zeit einen Zustand im Bereich 0 bis 1. Theoretisch könnten jetzt also beliebig feine Strukturen entstehen, die wir gar nicht sehen können. Damit das nicht passiert, haben sich die Macher noch eines kleinen mathematischen Tricks bedient und eine Mindestgranularität im Kontinuum vorgegeben – sozusagen eine „Minimalfeinheit“, die Strukturen haben dürfen, damit wir sie noch sehen. Diese Minimalfeinheit h entspricht dem, was wir von früher aus dem diskreten Game of Life als Zellenbreite kannten. Nun wissen wir genug, um grob zu definieren, was denn das, was wir als Zellenzustand kannten, in unserem neuen Game of Life ist. Dazu ziehen wir um unseren Ort x, für den wir das wissen wollen, einen Kreis mit Radius h. Ist in diesem Kreis eine große Fläche nahe 1, wird x größer. Ist dem nicht so, bleibt der Zustand von x klein, also in der Nähe von null. Mathematisch sagen wir, wir integrieren im Radius h um x.
Man schafft die Lebe- und Sterbe-Übergangsregel ab. Dazu gießt man die diskrete Version der Übergangsregel in eine kleine mathematische Formel, man bastelt sich sozusagen eine Tabelle, in der 0 oder 1 herauskommt. Man sieht die harten Übergänge zwischen 0 und 1, und lässt diese einfach mathematisch „verschwimmen“, so dass man weichere Konturen hat. Bleibt als einziges Problem: Es gibt ja keine wirklichen Zellen mehr (wir haben sie ja extra abgeschafft). Wie also bestimmen wir die Zahl der „lebenden Zellen drumherum“, die wir im diskreten Game of Life verwendet haben? Die Antwort ist einfach: Wenn wir für unsere Zelle den Ort x die kontinuierliche Version der „Anzahl der Nachbarn“ wissen wollen, machen wir es wie beim Bestimmen des Ortszustands selbst. Wir ziehen einen Kreis um x, nur diesmal mit Radius 3·h. Drei „kontiniuerliche Zellenbreiten“, sozusagen, also ganz wie im diskreten Game of Life. Hier hatte die Nachbarschaft einer Zelle auch die Größe 3·3, oder?
Was haben wir nun alles zusammen? Wir haben eine kontinuierliche Ebene statt einem Gitter, mit Orten statt Zellen, wir haben einen kontinuierlichen Zustandsbereich statt zwei diskreten zuständen, wir haben eine kontinuierliche, unscharfe Zustandsübergangsregel, und wir wissen, wie wir überhaupt Zustände aus unseren Orten gewinnen können, nämlich in dem wir Kreise darum ziehen und schauen, was darin ist. Fehlt noch die Zeit.
Man erschafft eine kontinuierliche Zeit. Das ist für uns am einfachsten vorzustellen: Wir kennen die Zeit nur kontinuierlich. Das Game of Life kannte bis jetzt aber nur abgetrennte Zeitschritte. Für so etwas gibt es bekannte mathematische Werkzeuge, in unserem Fall spezielle Gleichungen, die „kontinuierliche Änderung“ eines Systems ausdrücken, genannt Differentialgleichungen. Ich gehe darauf hier nicht näher ein, fragt einen Physiker eurer Wahl, die müssen ihr halbes Grundstudium damit verbringen . Nachdem man selbst die Zeit von ihren Schritten befreit hat, hat man ein komplett kontinuierliches Game of Life.
Bleibt als letztes Problem: Computer rechnen nur diskret. Aber keine Angst, es war jetzt nicht alles umsonst, es gibt viele wohlbekannte Rechenverfahren, die die Berechnung und Abtastung von kontinuierlichen Systemen näherungsweise ermöglichen. Tja, und nach dem ich euch so lange auf die Folter gespannt habe: So sieht es aus! Herrlich lebensecht, oder?
Hier gibt es noch eine größere HD-Version ohne die coole Musik. Und hier hat sogar jemand eine 3D-Version gebastelt.
Was bleibt? Es bleibt das Versprechen von oben, dass ich noch was zur Emergenz sage. Wikipedia definiert, ungefähr wie ich oben auch schon salopp meinte: „Die Emergenz […] ist die spontane Herausbildung von neuen Eigenschaften oder Strukturen eines Systems infolge des Zusammenspiels seiner Elemente. Dabei lassen sich die emergenten Eigenschaften des Systems nicht – oder jedenfalls nicht offensichtlich – auf Eigenschaften der Elemente zurückführen, die diese isoliert aufweisen.“ Aha. Soso. Man sieht den kleinen, lokalen Regeln des Systems also nicht auf Anhieb an, was auf der Gesamtebene passieren wird. Genauer: Wir sehen es ihnen nicht an. Wirklich? Einer der am meisten bemühten Begriffe eines gesamten Forschungsgebiets ist also primär dadurch definiert, dass der Mensch etwas nicht versteht?
Genau das denke ich. Vor ein paar Jahren habe ich einen Kolloquiumsvortrag im Interdisziplinären Zentrum für Komplexe Systeme der Uni Bonn gehalten. Im Anschluss entfachte sich unter reger Beteiligung eines anwesenden Genetikprofessors eine große Diskussion rund um das Gebiet des Artificial Life, und darüber, was Emergenz überhaupt ist. Der musste dann unheimlich lachen, als ich spontan bei noch anwesendem Artificial-Life-Publikum gesagt habe: „Emergenz ist, wenn wir uns wundern.“
Und genau das ist die kürzeste Definition, die ich bis heute gefunden habe.