Der Informatiker, der in Spielen Lektionen fürs Leben findet

Aussichten für Shang-Hua Teng, Theoretische Informatik war nie rein theoretisch. Der 58-jährige Teng ist Professor für Informatik an der University of Southern California und zweifacher Gewinner des Gödel-Preises, einer jährlichen Auszeichnung für bahnbrechende theoretische Arbeiten. Aber er versucht oft, diese abstrakte Theorie auf praktische und spielerische Weise mit dem Alltag zu verbinden.

Teng wurde am Vorabend der chinesischen Kulturrevolution in Peking geboren und kam in die Vereinigten Staaten, um an einer Graduiertenschule Computerarchitektur zu studieren, änderte aber bald die Richtung, um sich auf abstraktere mathematische Theorien zu konzentrieren. Er promovierte 1991 an der Carnegie Mellon University für den Beweis eines Theorems darüber, wie man Graphen am besten aufteilt – Netze aus Punkten oder Knoten, die durch Linien oder Kanten verbunden sind.

Obwohl die Arbeit theoretisch war, hatte sie praktische Anwendungen – und oft, so stellte er fest, führten praktische Anwendungen zu neuen theoretischen Einsichten. Während eines NASA-Sommerstipendiums 1993 schloss sich Teng einem Team an, das die Strömungsdynamik mit „Finite-Elemente“-Methoden simulierte, die komplexe Strukturen als Ansammlungen vieler winziger Teile modellieren. Diese Assemblagen können als Graphen behandelt werden, und Tengs Aufgabe bestand darin, die Partitionierungsmethode aus seiner Abschlussforschung an diese neue Umgebung anzupassen. Aber er wurde neugierig auf die Partitionierungstechnik, die das NASA-Team zuvor verwendet hatte, und begann, die zugrunde liegende mathematische Struktur zusammen mit einem anderen Informatiker zu untersuchen Daniel Spielmann, jetzt Professor für Informatik an der Yale University. Dieses gemeinsame Forschungsprojekt war der Beginn einer jahrzehntelangen Zusammenarbeit, die ihnen die beiden Gödel-Preise einbrachte.

Es war nicht das einzige Mal, dass er eine tiefe Verbindung zwischen Theorie und Praxis sah. „Jedes Mal hatten diese scheinbar absolut praktischen Dinge diese schöne Mathematik hinter sich“, sagte Teng.

In jüngerer Zeit hat Teng seine Aufmerksamkeit auf die schöne Mathematik hinter Spielen wie Tic-Tac-Toe, Schach und Go gerichtet. Bei solchen „kombinatorischen“ Spielen gibt es keinen Zufall, und beide Spieler wissen immer alles über den Zustand des Bretts. Kombinatorische Spiele bleiben jedoch eine Herausforderung, da die Anzahl der Möglichkeiten, wie ein Spiel gespielt werden kann, schwindelerregend groß sein kann.

Spieltheorieforscher verallgemeinern solche Spiele gerne auf immer größere Bretter – und skalieren Tic-Tac-Toe von 3-mal-3-Quadraten auf n-By-n, zum Beispiel – und die Schwierigkeit zu quantifizieren, zu bestimmen, welcher Spieler bei einem anfänglichen Board-Status gewinnen wird. Die unterschiedlichen Antwortmöglichkeiten sortieren Spiele in die gleiche „Komplexitätsklassen“, die in der gesamten theoretischen Informatik auftauchen.

Eine berühmte Komplexitätsklasse trägt den prosaischen Namen P für „polynomiale Zeit“ und enthält die Art von Problemen, die grob gesagt in angemessener Zeit gelöst werden können. Die Lösung von Problemen in der ebenso berühmten Klasse NP kann unangemessen viel Zeit in Anspruch nehmen, aber ihre Lösungen sind leicht zu überprüfen. Für Probleme in einer anderen Komplexitätsklasse namens PSPACE ist selbst eine solch effiziente Verifikation nicht garantiert. Wenn Forscher die „tiefe Logik“ von Zwei-Spieler-Spielen betrachten – „wenn Sie X machen, und dann, wenn ich Y mache, und dann, wenn Sie Z machen“ und so weiter –, sprechen sie oft über PSPACE. Aber wie Teng mitbewiesen hat, ist die Mathematik kombinatorischer Spiele nicht immer einfach.

Wie viel sprach kürzlich mit Teng über seinen Weg zur Informatik, die Mathematik, die Brettspielen zugrunde liegt, und den Einfluss seines Vaters. Das Interview wurde aus Gründen der Übersichtlichkeit gekürzt und bearbeitet.

Wie war es, in China eine Ausbildung zu bekommen?

Ich wurde kurz vor der Kulturrevolution geboren, und mein Vater war Universitätslehrstuhl für Bauingenieurwesen. Als die Revolution stattfand, war er auf dem Campus in Gefangenschaft. Dann wurde der ganze Campus tief ins Grüne geschickt.

Früher habe ich Müll gesammelt, um ihn zu verkaufen, bis ich praktisch mit der Mittelschule fertig war, und dann hat sich China plötzlich verändert. Wenn man studierte, konnte man aufs College gehen, und wir hatten sonst keine Aussicht auf einen regulären Job. Ich wachte auf und sagte: „Ich muss lernen.“

Wie haben Sie sich für Informatik entschieden?

Ich wollte nach dem Abitur Biologie studieren. Ich weiß nicht warum, aber mein Vater war nicht sehr glücklich darüber. Ich war gut in Mathe und er fragte mich, ob ich Mathe machen wolle. Ich sagte nein. [Lacht.] Und dann sagte er: „Weißt du, es gibt eine neue Disziplin namens Informatik, und sie ist wirklich gut.“ Irgendwie brachte er mich dazu, Informatik zu studieren.

Die damalige Ausbildung war sehr einfach. Wir waren mit den meisten Dingen nicht vertraut, und Informatik war nicht einmal eine Abteilung; es war ein Hauptfach in Elektrotechnik. Aber durch völlig zufälligen Zufall wurden wir als Mathematikstudenten in Analysis ausgebildet, und ich lernte ein paar Dinge, die schließlich nützlich waren, um Theoretiker zu werden. Ohne das hätte ich wahrscheinlich null Chance gehabt zu bestehen. Heutzutage sind die Kinder viel begabter: Von der High School an sind sie begabtere Mathematiker als ich es war, als ich in dieses Land kam.

Wie haben sich diese Wissenslücken auf Ihre Erfahrungen mit der Graduiertenschule ausgewirkt?

Eines Tages entdeckte [mein Berater Gary Miller], dass ich noch nie von NP gehört hatte. Es war in einer Diskussion. Er sagte: „Dieses Problem sieht NP-schwer aus.“ Ich sagte: „Uh-huh.“ Er sagte: „Du glaubst mir nicht?“ Und dann fing er an, es zu beweisen, und in der Mitte drehte er sich scharf zu mir um, weil ich nur da saß, und er sagte: „Weißt du, was NP-schwer ist?“ Ich sagte nein.

Ich dachte, das wäre mein letzter Arbeitstag mit ihm, aber er fuhr fort und erklärte mir die Definition. Er sagte: „Wenn du es nicht weißt, spielt es keine Rolle, solange du denken kannst.“ Er hatte einen enormen Einfluss auf mich.

Sie sind in erster Linie Theoretiker, haben sich aber im Laufe Ihrer Karriere immer wieder in die Industrie gewagt. Wie verband sich diese praktische Arbeit mit Ihrer theoretischen Forschung?

In meiner Diplomarbeit habe ich einige geometrische Methoden zur Partitionierung von Graphen entwickelt. Ich konnte zeigen, dass diese Familie geometrischer Methoden nachweislich gute Schnitte für Finite-Elemente-Graphen liefert.

Auf Empfehlung meines Mentors begann ich, Vorträge bei der NASA und Boeing Aerospace zu halten. Ich erinnere mich, dass bei Boeing das 3D-Modell eines der Flügel bereits fast eine Million Elemente hatte – sie konnten nicht einmal das in eine Maschine laden. Also wollten sie diesen Graphen in verschiedene Komponenten zerlegen, sie auf verschiedenen Maschinen mit ähnlicher Rechenlast platzieren und die Kommunikation minimieren. Aus diesem Grund ist die Formel mathematisch gesehen ein Graphenschnitt.

In der theoretischen Informatik bleiben die zugrunde liegenden mathematischen Prinzipien oft unverändert, auch wenn sich das Erscheinungsbild des Problems drastisch ändert, von der Optimierung zur Spieltheorie. Wenn Sie die Forschung betreiben, fühlt es sich nicht wie eine drastische Veränderung an.

Apropos Spieltheorie, ich habe gesehen, dass Sie an der Entwicklung eines Brettspiels mitgewirkt haben. Wie ist das passiert?

Oh, ich liebe Brettspiele! Es gibt schöne Verbindungen zur Komplexitätstheorie. Aber meistens bin ich der Schüler meiner Schüler.

Ich hielt an der Boston University einen Vortrag über einen schönen diskreten Satz namens Sperners Lemma. Es ist sehr einfach in einer Dimension. Sie haben ein Liniensegment, bei dem ein Ende rot und ein Ende blau ist. Sie teilen es in Untersegmente [mit Knoten an beiden Enden] und färben jeden neuen Knoten entweder rot oder blau. Dann [egal wie Sie sie einfärben] wissen wir, dass es ein Segment geben muss, das beide Farben hat.

In zwei Dimensionen ist es sehr faszinierend. Du hast ein Dreieck und jetzt drei Farben: Eine Ecke ist rot, eine blau und eine grün. Sie teilen dieses Dreieck in kleinere Dreiecke, sodass die Kanten in Segmente unterteilt werden. Jede Außenkante folgt der eindimensionalen Regel: Knoten können nur die Farben der beiden Enden verwenden. Innerhalb des Dreiecks können Sie alle drei Farben beliebig gestalten. Das Lemma von Sperner besagt, dass es bei dieser Färbung ein Dreieck geben muss, das alle drei Farben hat, egal wie Sie es teilen.

Kyle Burke war zu dieser Zeit mein Schüler und arbeitete an numerischer Analysis. Er kam in mein Büro und sagte, es könnte ein schönes Brettspiel von Sperners Lemma geben: Zwei Spieler färben iterativ ein Brett, und wer ein dreifarbiges Dreieck induziert, verliert das Spiel. Die besten Brettspiele haben eher Gewinner als ein Unentschieden, und hier wird eindeutig jemand gewinnen. Warum? Denn Sperners Lemma!

Ich habe meinen Freund David Eppstein aus Irvine angerufen, um mit ihm darüber zu sprechen, was ein gutes Brettspiel ausmacht. Er sagte: „Ein gutes Spiel hat einfache Regeln und ein schönes Brett, und es muss PSPACE-schwer sein.“ Denn wenn Sie es in polynomieller Zeit lösen könnten, würde Sie ein Computer ständig schlagen.

Also sind wir diese Kriterien durchgegangen. Kyle sagte: „Ist dieses Spiel einfach?“ Ich sagte: "Ja, es ist ein Satz!" Er sagte: „Ist dieses Spiel bunt?“ Ich sagte: „Mit Absicht!“ Dann sagte er: „Wenn ich beweise, dass es PSPACE-schwer ist, kann ich dann promovieren?“ Ich sagte ja, und er tat es. Es gibt viele verschiedene Facetten seines Theorems. Es enthüllt bestimmte Dinge über Fixpunkte, die ein sehr schönes Konzept in der Mathematik sind.

Kann ich das Spiel überall spielen?

Es ist verfügbar, mit einigen Optimierungen, Online.

Welche Spiele spielst du gerne?

Ich bin Spieltheoretiker. [Lacht.] Ich spiele ein bisschen mit meiner Tochter, aber ich bin nicht damit aufgewachsen, sie zu spielen. Im Gegensatz zu meinen Schülern, die ihr ganzes Leben lang Spiele gespielt haben.

Welche anderen Arbeiten haben Sie zur Mathematik von Brettspielen gemacht?

Wir hatten ein Krepppapier neulich zu einer offenen Frage: Wenn Sie zwei in Polynomzeit lösbare Spiele nebeneinander stellen würden, wären sie dann PSPACE-schwer? Bei jedem Zug können Sie nur einen von ihnen spielen. Dies wird Summierung von Spielen genannt.

Was bedeutet es, zwei Spiele zusammenzufügen?

Wenn Sie im alten Spiel Go viele Steine ​​ablegen, erhalten Sie viele separate Arenen, also spielen Sie in gewisser Weise eine Summe von Spielen. Sie müssen sich um diese Ecke und jene Ecke kümmern. Sie wollen das Ganze gewinnen, aber das bedeutet nicht, dass Sie jeden Teil gewinnen müssen.

Es ist philosophisch interessant, oder? Es ist, als hättest du einen Krieg, und es gibt viele Schlachten, aber deine Aufmerksamkeit ist endlich. Auf einem der Schlachtfelder kannst du zu jedem Zeitpunkt nur eine einzige Entscheidung treffen, und dein Gegner kann entweder reagieren oder auf einem anderen Schlachtfeld verdoppeln. Ich habe versucht, das meinem Vater zu erklären. Wenn Sie eine Summe von Spielen spielen, heißt es wirklich: Wie verlieren Sie strategisch?

Wir haben es für zwei Spiele bewiesen, aber Sie können drei Spiele zusammenstellen, und das Theorem ist immer noch wahr: Drei Polynomzeitspiele zusammengenommen können PSPACE-schwer werden.

Wie hat Ihr Vater auf die verschiedenen Arbeiten reagiert, die Sie im Laufe der Jahre geleistet haben, seit er Sie zur Informatik gedrängt hat?

Er fragte mich oft: „Warum tust du das?“ In der Theorie hat man oft jahrelang kein Ergebnis, und das verstand er nach und nach. Schon früh konnte ich über die Finite-Elemente-Methode sprechen – das lehren sie auch im Bauingenieurwesen. Aber ich konnte nicht herausfinden, wie ich über diese Freizeitmathematik sprechen sollte.

Dann dachte ich über eine Redewendung nach, die von diesem berühmten chinesischen Roman namens „ Romantik der drei Königreiche. Einer der Charaktere, Zhuge Liang, war ein fast perfekter Stratege, und die Redewendung lautet: „Drei Schuhfixierer sind besser als Zhuge Liang.“ Es wird auf diese unbeschwerte Weise verwendet, um zu sagen, dass drei durchschnittliche Menschen perfekt sein können, wenn sie ihre Köpfe zusammenstecken. Aber wenn man sich die Geschichte dieser Redewendung ansieht, wurden die Dinge in verschiedenen Regionen unterschiedlich ausgesprochen, und „Schuhfixierer“ hatte denselben Klang wie „Feldgeneral“. So heißt es: „Drei Feldgeneräle zusammen sind besser als dieser perfekte Stratege.“

Ich sagte zu meinem Vater, das ist genau der Satz, den wir mit der Summierung von Spielen bewiesen haben. Die Feldgeneräle repräsentieren [Algorithmen zum Lösen] polynomieller Zeitspiele: Auf jedem Schlachtfeld wissen sie, wie man gewinnt. Aber der schwierige Teil ist zu wissen, wann man verliert, nicht wie man jedes der Komponentenspiele gewinnt. Wenn jemand dieses harte Spiel spielen kann, ist er wirklich der beste Stratege. Die Feldgeneräle treffen diese tiefenlogischen Entscheidungen nicht, aber irgendwie, wenn man sie gut zusammenfügt, sind sie nicht schlechter als dieser perfekte Stratege.

Ich sagte zu meinem Vater: „Ich habe endlich diesen mathematischen Satz erkannt, der einer unserer berühmten Redewendungen entspricht!“ Er war damals 94, sehr schlau, und er sagte: „Das ist ein guter Versuch.“ Ich konnte ihn nicht ganz überzeugen. Das war mein letztes technisches Gespräch mit ihm; ein paar Monate später starb er. Wenn ich daran denke, meine Arbeit zu erklären, ist dies mein Highlight.