Dataforskeren som finner livsleksjoner i spill

Til Shang-Hua Teng, teoretisk informatikk har aldri vært rent teoretisk. Nå 58, er Teng professor i informatikk ved University of South California og to ganger vinner av Gödel-prisen, en årlig pris som anerkjenner banebrytende teoretisk arbeid. Men han prøver ofte å koble den abstrakte teorien til hverdagen på både praktiske og lekne måter.

Født i Beijing på tampen av den kinesiske kulturrevolusjonen, kom Teng til USA for å planlegge forskerskolen for å studere dataarkitektur, men han endret snart retning for å fokusere på mer abstrakt matematisk teori. Han tok doktorgraden ved Carnegie Mellon University i 1991 for å bevise et teorem om hvordan man best deler grafer - nett av punkter, eller noder, forbundet med linjer eller kanter.

Selv om det var teoretisk, hadde arbeidet praktiske anvendelser - og ofte, fant han, førte praktiske anvendelser til ny teoretisk innsikt. Under et NASA-sommerstipend fra 1993 ble Teng med i et team som simulerte væskedynamikk ved å bruke "finite-element"-metoder, som modellerer komplekse strukturer som sammenstillinger av mange små biter. Disse samlingene kan behandles som grafer, og Tengs oppgave var å tilpasse partisjoneringsmetoden fra sin doktorgradsforskning til denne nye settingen. Men han ble nysgjerrig på partisjoneringsteknikken som NASA-teamet hadde brukt tidligere, og begynte å undersøke den underliggende matematiske strukturen sammen med en annen dataforsker Daniel Spielman, nå professor i informatikk ved Yale University. Det felles forskningsprosjektet startet et tiår langt samarbeid som ga dem de to Gödel-prisene.

Det var ikke den eneste gangen han så en dyp kobling mellom teori og praksis. "Hver gang hadde disse tilsynelatende helt praktiske tingene denne vakre matematikken bak seg," sa Teng.

Nylig har Teng rettet oppmerksomheten mot den vakre matematikken bak spill som tikken, sjakk og Go. I slike "kombinatoriske" spill er det ingen tilfeldighet, og begge spillerne vet alltid alt om brettets tilstand. Likevel er kombinatoriske spill fortsatt utfordrende fordi antallet måter et spill kan spilles ut på kan være svimlende stort.

Spillteoriforskere liker å generalisere slike spill til stadig større brett – skalere opp tikken fra 3 x 3 ruter til n-av-n, for eksempel - og kvantifiser vanskeligheten med å avgjøre hvilken spiller som vil vinne gitt en innledende brettstatus. De forskjellige mulige svarene sorterer spill i samme "kompleksitetsklasser” som dukker opp gjennom teoretisk informatikk.

En kjent kompleksitetsklasse går under det prosaiske navnet P, for "polynomisk tid", og inneholder den typen problemer som kan løses på rimelig tid, grovt sett. Problemer i den like kjente klassen NP kan ta urimelig lang tid å løse, men løsningene deres er enkle å sjekke. For problemer i en annen kompleksitetsklasse, kalt PSPACE, er ikke en slik effektiv verifisering garantert. Når forskere vurderer den "dype logikken" i tospillerspill - "hvis du gjør X, og så hvis jeg gjør Y, og så hvis du gjør Z," og så videre - finner de ofte at de snakker om PSPACE. Men som Teng har bidratt til å bevise, er matematikken i kombinatoriske spill ikke alltid likefrem.

Quanta snakket med Teng nylig for å diskutere veien til informatikk, matematikken som ligger til grunn for brettspill og farens innflytelse. Intervjuet er komprimert og redigert for klarhet.

Hvordan var det å ta utdanning i Kina?

Jeg ble født litt før kulturrevolusjonen, og faren min var avdelingsleder ved universitetet i sivilingeniør. Da revolusjonen skjedde, var han i fangenskap på campus. Så ble hele campus sendt langt ut på landsbygda.

Jeg pleide å samle søppel for å selge inntil jeg praktisk talt var ferdig med ungdomsskolen, og så endret Kina seg plutselig. Hvis du studerte kunne du komme inn på college, og vi hadde ingen andre utsikter til å ha noen vanlig jobb. Jeg våknet og sa: "Jeg må studere."

Hvordan valgte du informatikk?

Jeg ville studere biologi etter videregående. Jeg vet ikke hvorfor, men faren min var ikke særlig fornøyd med det. Jeg gjorde det bra i matte, og han spurte meg om jeg ville gjøre matte. Jeg sa nei. [Ler.] Og så sa han: "Du vet, det er en ny disiplin som heter datavitenskap, og den er veldig bra." På en eller annen måte presset han meg til hovedfag i informatikk.

Utdanningen på den tiden var veldig grunnleggende. Vi ble ikke utsatt for det meste, og informatikk var ikke engang en avdeling; det var hovedfag i elektroteknikk. Men ved helt tilfeldig flaks ble vi opplært som matematikkstudenter i kalkulus, og jeg lærte et par ting som til slutt var nyttige for å bli teoretiker. Uten det hadde jeg nok hatt null sjanse til å bestå. I disse dager er barna mye mer talentfulle: Fra videregående er de mer begavede matematikere enn jeg var da jeg kom til dette landet.

Hvordan påvirket disse hullene i kunnskapen din opplevelse av forskerskolen?

En dag oppdaget [rådgiveren min, Gary Miller,] at jeg aldri hadde hørt om NP. Det var i en diskusjon. Han sa: "Dette problemet ser NP-hardt ut." Jeg sa: "Uh-he." Han sa: "Tror du meg ikke?" Og så begynte han å bevise det, og halvveis snudde han seg skarpt mot meg, fordi jeg bare satt der, og han sa: "Vet du hva NP-hardt er?" Jeg sa nei.

Jeg trodde det var min siste dag å jobbe med ham, men han fortsatte og fortalte meg definisjonen. Han sa: "Hvis du ikke vet, spiller det ingen rolle, så lenge du er i stand til å tenke." Han hadde en enorm innvirkning på meg.

Du er først og fremst en teoretiker, men gjennom hele karrieren har du gjort inntog i industrien. Hvordan hang dette praktiske arbeidet sammen med din teoretiske forskning?

I oppgaven min utviklet jeg noen geometriske metoder for partisjonering av grafer. Jeg var i stand til å vise at denne familien av geometriske metoder ga beviselig gode kutt for finite-element grafer.

Etter min mentors anbefaling begynte jeg å holde foredrag hos NASA og Boeing Aerospace. Hos Boeing husker jeg at 3D-modellen av en av vingene allerede hadde nærmere en million elementer - de kunne ikke engang laste det inn i én maskin. Så de ønsket å kutte denne grafen i forskjellige komponenter, sette dem på forskjellige maskiner med lignende beregningsbelastninger og minimere kommunikasjonen. Det er derfor matematisk formelen er en grafkuttet.

I teoretisk informatikk er ofte de underliggende matematiske prinsippene uendret selv når utseendet til problemet endres drastisk, fra optimalisering til spillteori. Når du gjør forskningen, føles det ikke som en drastisk endring.

Apropos spillteori så jeg at du var med på å designe et brettspill. Hvordan skjedde det?

Å, jeg elsker brettspill! Det er vakre sammenhenger med kompleksitetsteori. Men for det meste er jeg studenten til elevene mine.

Jeg holdt en tale ved Boston University om et vakkert diskret teorem kalt Sperners lemma. Det er veldig enkelt i én dimensjon. Du har et linjestykke der en ende er rød og en ende er blå. Du deler den inn i undersegmenter [med noder i begge ender] og farger hver ny node enten rød eller blå. Så [uansett hvordan du farger dem] vet vi at det må være et segment som har begge fargene.

I to dimensjoner er det veldig fascinerende. Du har en trekant, og nå har du tre farger: Ett hjørne er rødt, ett er blått og ett er grønt. Du deler denne trekanten i mindre trekanter, slik at kantene brytes i segmenter. Hver ytterkant følger den endimensjonale regelen: Noder kan bare bruke fargene til de to endene. Inne i trekanten kan du gjøre alle tre fargene som du vil. Sperners lemma sier at uansett hvordan du deler det, hvis du gjør denne fargeleggingen, må det være en trekant som har alle tre fargene.

Kyle Burke var min student, og jobbet med numerisk analyse på den tiden. Han kom til kontoret mitt og sa at det kunne være et vakkert brettspill av Sperners lemma: To spillere fargelegger et brett iterativt, og den som induserer en trefarget trekant vil tape spillet. De beste brettspillene har vinnere i stedet for uavgjort, og her vil helt klart noen vinne. Hvorfor? Fordi Sperners lemma!

Jeg ringte vennen min David Eppstein fra Irvine for å snakke om hva som gjør et godt brettspill. Han sa: "Et godt spill har enkle regler og et vakkert brett, og det må være PSPACE-hardt." For hvis du kan løse det i polynomisk tid, vil en datamaskin slå deg hele tiden.

Så vi gikk gjennom disse kriteriene. Kyle sa: "Er dette spillet enkelt?" Jeg sa: "Ja, det er én setning!" Han sa: "Er dette spillet fargerikt?" Jeg sa: "Etter design!" Så sa han: "Hvis jeg beviser at det er PSPACE-hardt, kan jeg få en Ph.D.?" Jeg sa ja, og det gjorde han. Det er mange forskjellige fasetter av teoremet hans. Den avslører visse ting om faste punkter, som er et veldig vakkert konsept i matematikk.

Kan jeg spille spillet hvor som helst?

Den er tilgjengelig, med noen justeringer, på nett.

Hvilke spill liker du å spille?

Jeg er en teoretiker av spill. [Ler.] Jeg leker litt med datteren min, men jeg vokste ikke opp med å spille dem. I motsetning til elevene mine, som har spilt spill hele livet.

Hvilket annet arbeid har du gjort med matematikk i brettspill?

Vi hadde en papir nylig om et åpent spørsmål: Hvis du setter to polynom-tidsløselige spill sammen, side ved side, ville det gjøre dem PSPACE-harde? Ved hvert trekk kan du bare spille ett av dem. Dette kalles summering av spill.

Hva vil det si å sette sammen to spill?

I det eldgamle spillet Go, når du legger ned nok steiner, får du mange separate arenaer, så på en eller annen måte spiller du en sum av spill. Du må bekymre deg for dette hjørnet og det hjørnet. Du vil vinne hele greia, men det betyr ikke at du må vinne hver del.

Det er filosofisk interessant, ikke sant? Det er som om du har en krig, og den har mange kamper, men oppmerksomheten din er begrenset. Når som helst kan du bare ta en enkelt avgjørelse på en av slagmarkene, og motstanderen din kan enten svare eller doble på en annen slagmark. Jeg prøvde å forklare dette til faren min. Når du spiller en sum av spill, betyr det egentlig: Hvordan taper du strategisk?

Vi beviste det for to spill, men du kan sette tre spill sammen og teoremet er fortsatt sant: Tre polynom-tidsspill sammen kan bli PSPACE-harde.

Siden han presset deg mot informatikk, hvordan reagerte faren din på det forskjellige arbeidet du har gjort gjennom årene?

Han spurte meg ofte: "Hvorfor gjør du dette?" Arbeider i teorien, ofte har du ikke noe resultat i årevis, og han forsto det gradvis. Tidlig kunne jeg snakke om finite-element-metoden - det lærer de også i sivilingeniør. Men jeg kunne ikke finne ut hvordan jeg skulle snakke om denne rekreasjonsmatematikken.

Så tenkte jeg på et formspråk som stammer fra denne berømte kinesiske romanen kalt Romance of the Three Kingdoms. En av karakterene, Zhuge Liang, var nesten en perfekt strateg, og formspråket lyder: "Tre skofiksere er bedre enn Zhuge Liang." Det brukes på denne letthjertede måten å si at tre gjennomsnittlige mennesker kan være perfekte når de setter hodet sammen. Men når du ser på historien til dette formspråket, ble ting uttalt forskjellig i forskjellige regioner, og "skofikser" hadde samme lyd som "feltgeneral." Så det står: "Tre feltgeneraler sammen er bedre enn denne perfekte strategen."

Jeg sa til faren min at det var akkurat det teoremet vi beviste med summeringen av spill. Feltgeneralene representerer [algoritmer for å løse] polynom-tidsspill: På hver slagmark vet de hvordan de skal vinne. Men den vanskelige delen er å vite når man skal tape, ikke hvordan man vinner hvert av komponentspillene. Hvis noen kan spille det harde spillet, er de virkelig den beste strategen. Feltgeneralene tar ikke disse dype logiske avgjørelsene, men hvis du setter dem pent sammen, er de ikke verre enn denne perfekte strategen.

Jeg sa til faren min: "Jeg skjønte endelig denne matematiske teoremet som tilsvarer et av våre berømte idiomer!" Han var 94 på den tiden, veldig skarp, og han sa: "Det er et godt forsøk." Jeg overbeviste ham ikke helt. Det var min siste tekniske samtale med ham; noen måneder senere gikk han bort. Hver gang jeg tenker på å forklare arbeidet mitt, er dette høydepunktet mitt.