Datavetaren som får livslektioner i spel

För Shang-Hua Teng, teoretisk datavetenskap har aldrig varit rent teoretisk. Nu 58 år, är Teng professor i datavetenskap vid University of Southern California och tvåfaldig vinnare av Gödelpriset, ett årligt pris som uppmärksammar banbrytande teoretiskt arbete. Men han strävar ofta efter att koppla den abstrakta teorin till vardagen på både praktiska och lekfulla sätt.

Född i Peking på tröskeln till den kinesiska kulturrevolutionen, kom Teng till USA för en forskarskola för att studera datorarkitektur, men han ändrade snart riktning för att fokusera på mer abstrakt matematisk teori. Han doktorerade vid Carnegie Mellon University 1991 för att bevisa ett teorem om hur man bäst delar upp grafer - vävar av punkter, eller noder, förbundna med linjer eller kanter.

Även om det var teoretiskt hade arbetet praktiska tillämpningar - och ofta, fann han, ledde praktiska tillämpningar till nya teoretiska insikter. Under ett NASA-sommarstipendium 1993 gick Teng med i ett team som simulerade vätskedynamik med hjälp av "finite-element"-metoder, som modellerar komplexa strukturer som sammansättningar av många små bitar. Dessa sammansättningar kan behandlas som grafer, och Tengs uppgift var att anpassa uppdelningsmetoden från sin doktorandforskning till denna nya miljö. Men han blev nyfiken på uppdelningstekniken som NASA-teamet hade använt tidigare och började undersöka dess underliggande matematiska struktur tillsammans med andra datavetare Daniel Spielman, nu professor i datavetenskap vid Yale University. Det gemensamma forskningsprojektet startade ett decennierlångt samarbete som gav dem två Gödelpriser.

Det var inte enda gången han såg en djup koppling mellan teori och praktik. "Varje gång hade dessa till synes helt praktiska saker denna vackra matematik bakom sig," sa Teng.

På senare tid har Teng riktat sin uppmärksamhet mot den vackra matematiken bakom spel som tic-tac-toe, schack och Go. I sådana "kombinatoriska" spel finns det ingen slump, och båda spelarna vet alltid allt om brädets tillstånd. Ändå är kombinatoriska spel fortfarande utmanande eftersom antalet sätt som ett spel kan spelas ut kan vara svindlande stort.

Spelteoretiska forskare gillar att generalisera sådana spel till allt större brädor – att skala upp tic-tac-toe från 3 x 3 rutor till n-förbi-n, till exempel — och kvantifiera svårigheten att avgöra vilken spelare som kommer att vinna med tanke på något initialt brädtillstånd. De olika möjliga svaren sorterar spel i samma "komplexitetsklasser” som dyker upp genom hela teoretisk datavetenskap.

En berömd komplexitetsklass går under det prosaiska namnet P, för "polynomtid", och innehåller den typen av problem som kan lösas på en rimlig tid, grovt sett. Problem i den lika berömda klassen NP kan ta orimligt lång tid att lösa, men deras lösningar är lätta att kontrollera. För problem i en annan komplexitetsklass, kallad PSPACE, garanteras inte ens en sådan effektiv verifiering. När forskare överväger den "djupa logiken" i spel för två spelare - "om du gör X, och sedan om jag gör Y, och sedan om du gör Z" och så vidare - finner de ofta att de pratar om PSPACE. Men som Teng har hjälpt till att bevisa, är matematiken i kombinatoriska spel inte alltid okomplicerad.

Quanta pratade med Teng nyligen för att diskutera hans väg till datavetenskap, matematiken bakom brädspelen och hans fars inflytande. Intervjun har förtätats och redigerats för tydlighetens skull.

Hur var det att få en utbildning i Kina?

Jag föddes strax före kulturrevolutionen, och min far var ordförande vid universitetsavdelningen i civilingenjör. När revolutionen inträffade var han i fångenskap på campus. Sedan skickades hela campus djupt ut på landsbygden.

Jag brukade samla sopor för att sälja tills jag praktiskt taget slutade gymnasiet, och sedan förändrades plötsligt Kina. Om du studerade kunde du komma in på college, och vi hade inga andra utsikter att ha något vanligt jobb. Jag vaknade och sa: "Jag måste plugga."

Hur valde du datavetenskap?

Jag ville läsa biologi efter gymnasiet. Jag vet inte varför, men min pappa var inte särskilt nöjd med det. Jag klarade mig bra i matte, och han frågade mig om jag ville göra matte. Jag sa nej. [Skrattar.] Och sedan sa han, "Du vet, det finns en ny disciplin som heter datavetenskap, och den är riktigt bra." På något sätt knuffade han mig till att studera datavetenskap.

Utbildningen på den tiden var väldigt grundläggande. Vi var inte utsatta för det mesta, och datavetenskap var inte ens en institution; det var en huvudämne i elektroteknik. Men av en helt slumpmässig tur utbildades vi till matematikelever i kalkyl, och jag lärde mig några saker som så småningom var användbara för att bli teoretiker. Utan det hade jag nog haft noll chans att passera. Nuförtiden är barnen mycket mer begåvade: Från gymnasiet och framåt är de mer begåvade matematiker än jag var när jag kom till det här landet.

Hur påverkade dessa luckor i dina kunskaper din upplevelse av forskarskolan?

En dag upptäckte [min rådgivare, Gary Miller,] att jag aldrig hade hört talas om NP. Det var i en diskussion. Han sa, "Det här problemet ser NP-svårt ut." Jag sa, "äh-ha." Han sa: "Tror du mig inte?" Och sedan började han bevisa det, och halvvägs vände han sig skarpt mot mig, för jag satt där, och han sa: "Vet du vad NP-hårt är?" Jag sa nej.

Jag trodde att det var min sista dag att arbeta med honom, men han fortsatte och berättade definitionen för mig. Han sa, "Om du inte vet spelar det ingen roll, så länge du kan tänka." Han hade en enorm inverkan på mig.

Du är i första hand teoretiker, men under hela din karriär har du gjort inhopp i industrin. Hur kopplade detta praktiska arbete till din teoretiska forskning?

I mitt examensarbete utvecklade jag några geometriska metoder för att dela upp grafer. Jag kunde visa att denna familj av geometriska metoder gav bevisligen bra snitt för finita element-grafer.

På min mentors rekommendation började jag hålla föredrag på NASA och Boeing Aerospace. På Boeing minns jag att 3D-modellen av en av vingarna redan hade nära en miljon element - de kunde inte ens ladda det i en maskin. Så de ville klippa den här grafen i olika komponenter, sätta dem på olika maskiner med liknande beräkningsbelastningar och minimera kommunikationen. Det är därför matematiskt formeln är en grafklippning.

Inom teoretisk datavetenskap är ofta de bakomliggande matematiska principerna oförändrade även när problemets utseende förändras drastiskt, från optimering till spelteori. När du gör forskningen känns det inte som en drastisk förändring.

På tal om spelteori så såg jag att du hjälpte till att designa ett brädspel. Hur hände det?

Åh, jag älskar brädspel! Det finns vackra samband med komplexitetsteori. Men för det mesta är jag mina elevers elev.

Jag höll ett föredrag vid Boston University om ett vackert diskret teorem som heter Sperners lemma. Det är väldigt enkelt i en dimension. Du har ett linjesegment där ena änden är röd och ena änden är blå. Du delar upp den i undersegment [med noder i båda ändar] och färgar varje ny nod antingen röd eller blå. Sedan [oavsett hur du färgar dem] vet vi att det måste finnas ett segment som har båda färgerna.

I två dimensioner är det väldigt fascinerande. Du har en triangel, och nu har du tre färger: Ett hörn är rött, ett är blått och ett är grönt. Du delar upp denna triangel i mindre trianglar, så kanterna bryts i segment. Varje ytterkant följer den endimensionella regeln: Noder kan bara använda färgerna på de två ändarna. Inuti triangeln kan du göra alla tre färgerna som du vill. Sperners lemma säger att hur som helst du delar det, om du gör den här färgningen måste det finnas en triangel som har alla tre färgerna.

Kyle Burke var min student och arbetade med numerisk analys vid den tiden. Han kom till mitt kontor och sa att det kunde finnas ett vackert brädspel av Sperners lemma: Två spelare färglägger ett bräde iterativt, och den som framkallar en trefärgad triangel kommer att förlora spelet. De bästa brädspelen har vinnare snarare än oavgjort, och här kommer helt klart någon att vinna. Varför? För Sperners lemma!

Jag ringde min vän David Eppstein från Irvine för att prata om vad som gör ett bra brädspel. Han sa: "Ett bra spel har enkla regler och en vacker bräda, och det måste vara PSPACE-hårt." För om du kan lösa det i polynomtid, skulle en dator slå dig hela tiden.

Så vi gick igenom dessa kriterier. Kyle sa: "Är det här spelet enkelt?" Jag sa, "Ja, det är en mening!" Han sa: "Är det här spelet färgglatt?" Jag sa, "enligt design!" Sedan sa han: "Om jag bevisar att det är PSPACE-svårt, kan jag få en doktorsexamen?" Jag sa ja, och det gjorde han. Det finns många olika aspekter av hans teorem. Det avslöjar vissa saker om fixpunkter, som är ett väldigt vackert begrepp inom matematik.

Kan jag spela spelet var som helst?

Den är tillgänglig, med några justeringar, nätet.

Vilka spel gillar du att spela?

Jag är en spelteoretiker. [Skrattar.] Jag leker lite med min dotter, men jag växte inte upp med att spela dem. Till skillnad från mina elever, som har spelat spel hela livet.

Vilket annat arbete har du gjort med matematiken i brädspel?

Vi hade en papper nyligen om en öppen fråga: Om du sätter två polynom-tidslösliga spel tillsammans, sida vid sida, skulle det göra dem PSPACE-hårda? Vid varje drag kan du bara spela ett av dem. Detta kallas summering av spel.

Vad innebär det att sätta ihop två spel?

I det antika spelet Go, när du lägger ner tillräckligt med stenar, får du många separata arenor, så i någon mening spelar du en summa spel. Du måste oroa dig för det här hörnet och det hörnet. Du vill vinna hela grejen, men det betyder inte att du måste vinna varje del.

Det är filosofiskt intressant, eller hur? Det är som om du har ett krig, och det har många strider, men din uppmärksamhet är begränsad. När som helst kan du bara fatta ett enda beslut på ett av slagfälten, och din motståndare kan antingen svara eller dubbla på något annat slagfält. Jag försökte förklara detta för min far. När du spelar en summa spel betyder det egentligen: Hur förlorar du strategiskt?

Vi bevisade det för två spel, men du kan sätta ihop tre spel och satsen är fortfarande sann: Tre polynom-tidsspel tillsammans kan bli PSPACE-hårda.

Sedan han pressade dig mot datavetenskap, hur reagerade din far på det annorlunda arbete du har gjort under åren?

Han frågade mig ofta: "Varför gör du det här?" Arbetar i teorin, ofta har du inget resultat på flera år, och han förstod det gradvis. Tidigt kunde jag prata om finita elementmetoden - det lär de också ut inom anläggningsteknik. Men jag kunde inte komma på hur jag skulle prata om den här rekreationsmatematiken.

Sedan tänkte jag på ett formspråk som härrörde från denna berömda kinesiska roman som heter Roman av de tre kungadömena. En av karaktärerna, Zhuge Liang, var nästan en perfekt strateg, och formspråket lyder: "Tre skofixare är bättre än Zhuge Liang." Det används på det här lättsamma sättet för att säga att tre genomsnittliga människor kan vara perfekta när de slår ihop sina huvuden. Men när man tittar på historien om detta idiom, uttalades saker olika i olika regioner, och "skofixare" hade samma ljud som "fältgeneral." Så det står, "Tre fältgeneraler tillsammans är bättre än den här perfekta strategen."

Jag sa till min far att det var precis den sats vi bevisade med summeringen av spel. Fältgeneralerna representerar [algoritmer för att lösa] polynom-tidsspel: På varje slagfält vet de hur man vinner. Men det svåra är att veta när man ska förlora, inte hur man vinner vart och ett av de ingående spelen. Om någon kan spela det svåra spelet är de verkligen den bästa strategen. Fältgeneralerna fattar inte dessa djupa logiska beslut, men på något sätt om du sätter ihop dem snyggt är de inte värre än den här perfekta strategen.

Jag sa till min pappa: "Jag insåg äntligen detta matematiska sats som motsvarar ett av våra berömda idiom!" Han var 94 vid den tiden, mycket skarp, och han sa: "Det är ett bra försök." Jag övertygade honom inte riktigt. Det var mitt sista tekniska samtal med honom; några månader senare gick han bort. När jag tänker på att förklara mitt arbete är det här min höjdpunkt.