De computerwetenschapper die levenslessen vindt in games

Voor Shang-Hua Tengo, theoretische informatica is nooit puur theoretisch geweest. Teng, nu 58, is professor computerwetenschappen aan de Universiteit van Zuid-Californië en tweevoudig winnaar van de Gödelprijs, een jaarlijkse onderscheiding voor baanbrekend theoretisch werk. Maar hij streeft er vaak naar om die abstracte theorie op een praktische en speelse manier te verbinden met het dagelijks leven.

Teng, geboren in Beijing aan de vooravond van de Chinese Culturele Revolutie, kwam naar de Verenigde Staten voor een graduate school om computerarchitectuur te studeren, maar hij veranderde al snel van richting om zich te concentreren op meer abstracte wiskundige theorie. Hij promoveerde in 1991 aan de Carnegie Mellon University voor het bewijzen van een stelling over de beste manier om grafieken te verdelen: webben van punten of knopen, verbonden door lijnen of randen.

Hoewel theoretisch, had het werk praktische toepassingen - en vaak, ontdekte hij, leidden praktische toepassingen tot nieuwe theoretische inzichten. Tijdens een NASA-zomerbeurs in 1993 sloot Teng zich aan bij een team dat vloeistofdynamica simuleert met behulp van "eindige-elementen" -methoden, die complexe structuren modelleren als assemblages van vele kleine stukjes. Deze assemblages kunnen worden behandeld als grafieken, en het was de taak van Teng om de partitiemethode van zijn afstudeeronderzoek aan te passen aan deze nieuwe setting. Maar hij werd nieuwsgierig naar de partitietechniek die het NASA-team eerder had gebruikt, en begon samen met collega-computerwetenschappers de onderliggende wiskundige structuur te onderzoeken. Daniël Spielman, nu hoogleraar informatica aan de Yale University. Dat gezamenlijke onderzoeksproject was de aftrap voor een decennialange samenwerking die hen de twee Gödel-prijzen opleverde.

Het was niet de enige keer dat hij een diep verband zag tussen theorie en praktijk. "Elke keer hadden deze ogenschijnlijk volkomen praktische dingen deze prachtige wiskunde achter zich", zei Teng.

Meer recentelijk heeft Teng zijn aandacht gericht op de prachtige wiskunde achter spellen als boter-kaas-en-eieren, schaken en Go. In dergelijke "combinatorische" spellen is er geen kans en weten beide spelers altijd alles over de toestand van het bord. Toch blijven combinatorische spellen uitdagend omdat het aantal manieren waarop een spel kan worden gespeeld duizelingwekkend groot kan zijn.

Onderzoekers van de speltheorie generaliseren dergelijke spellen graag naar steeds grotere borden — waarbij boter-kaas-en-eieren worden opgeschaald van vierkanten van 3 bij 3 naar nPern, bijvoorbeeld - en kwantificeer de moeilijkheid om te bepalen welke speler zal winnen, gegeven een aanvankelijke bordstatus. De verschillende mogelijke antwoorden sorteren spellen in hetzelfde "complexiteitsklassen' die overal in de theoretische informatica opduiken.

Een beroemde complexiteitsklasse heeft de prozaïsche naam P, voor 'polynomiale tijd', en bevat het soort problemen dat grofweg in een redelijke hoeveelheid tijd kan worden opgelost. Problemen in de even beroemde klasse NP kunnen onredelijk veel tijd kosten om op te lossen, maar hun oplossingen zijn gemakkelijk te controleren. Voor problemen in een andere complexiteitsklasse, genaamd PSPACE, is zelfs een dergelijke efficiënte verificatie niet gegarandeerd. Wanneer onderzoekers nadenken over de 'diepe logica' van games voor twee spelers - 'als je X doet, en dan als ik Y doe, en dan als je Z doet', enzovoort - hebben ze het vaak over PSPACE. Maar zoals Teng heeft helpen bewijzen, is de wiskunde van combinatorische spellen niet altijd eenvoudig.

Quanta sprak onlangs met Teng om zijn pad naar computerwetenschap, de wiskunde die ten grondslag ligt aan bordspellen en de invloed van zijn vader te bespreken. Het interview is voor de duidelijkheid ingekort en bewerkt.

Hoe was het om een ​​opleiding te volgen in China?

Ik ben iets voor de Culturele Revolutie geboren en mijn vader was een universitaire afdelingsvoorzitter civiele techniek. Toen de revolutie plaatsvond, zat hij in gevangenschap op de campus. Vervolgens werd de hele campus diep het platteland in gestuurd.

Ik verzamelde afval om te verkopen totdat ik bijna de middelbare school afmaakte, en toen veranderde China plotseling. Als je studeerde, kon je naar de universiteit, en we hadden geen ander vooruitzicht op een vaste baan. Ik werd wakker en zei: "Ik moet studeren."

Hoe heb je voor informatica gekozen?

Ik wilde na de middelbare school biologie gaan studeren. Ik weet niet waarom, maar mijn vader was daar niet zo blij mee. Ik deed het goed in wiskunde, en hij vroeg me of ik wiskunde wilde doen. Ik zei nee. [Lacht.] En toen zei hij: "Weet je, er is een nieuwe discipline genaamd informatica, en die is echt goed." Op de een of andere manier spoorde hij me aan om informatica te studeren.

Het onderwijs in die tijd was erg basic. We werden niet blootgesteld aan de meeste dingen, en informatica was niet eens een afdeling; het was een major in elektrotechniek. Maar door totaal willekeurig geluk werden we opgeleid als wiskundestudenten in calculus, en ik leerde een paar dingen die uiteindelijk nuttig waren om theoreticus te worden. Zonder dat had ik waarschijnlijk geen enkele kans gehad om te slagen. Tegenwoordig zijn de kinderen veel getalenteerder: vanaf de middelbare school zijn ze meer begaafde wiskundigen dan ik was toen ik naar dit land kwam.

Hoe hebben die hiaten in je kennis je ervaring op de graduate school beïnvloed?

Op een dag ontdekte [mijn adviseur, Gary Miller,] dat ik nog nooit van NP had gehoord. Het was in discussie. Hij zei: "Dit probleem ziet er NP-hard uit." Ik zei: "Uh-huh." Hij zei: "Geloof je me niet?" En toen begon hij het te bewijzen, en halverwege draaide hij zich scherp naar mij toe, omdat ik daar gewoon zat, en hij zei: "Weet je wat NP-hard is?" Ik zei nee.

Ik dacht dat dit mijn laatste dag was dat ik met hem werkte, maar hij ging verder en vertelde me de definitie. Hij zei: "Als je het niet weet, maakt het niet uit, zolang je maar kunt denken." Hij had een enorme impact op mij.

Je bent in de eerste plaats een theoreticus, maar gedurende je hele carrière heb je uitstapjes gemaakt naar de industrie. Hoe sloot dit praktische werk aan op je theoretisch onderzoek?

In mijn thesis heb ik een aantal geometrische methoden ontwikkeld voor het verdelen van grafieken. Ik kon aantonen dat deze familie van geometrische methoden aantoonbaar goede bezuinigingen opleverde voor eindige-elementengrafieken.

Op aanraden van mijn mentor begon ik lezingen te geven bij NASA en Boeing Aerospace. Ik herinner me dat het 3D-model van een van de vleugels bij Boeing al bijna een miljoen elementen bevatte - ze konden dat niet eens in één machine laden. Dus wilden ze deze grafiek in verschillende componenten knippen, ze op verschillende machines met vergelijkbare rekenbelasting plaatsen en de communicatie minimaliseren. Daarom is de formule wiskundig gezien een grafieksnede.

In de theoretische informatica blijven de onderliggende wiskundige principes vaak ongewijzigd, zelfs als het uiterlijk van het probleem drastisch verandert, van optimalisatie tot speltheorie. Als je het onderzoek doet, voelt het niet als een drastische verandering.

Over speltheorie gesproken, ik zag dat je hebt geholpen met het ontwerpen van een bordspel. Hoe is dat gebeurt?

Oh, ik ben dol op bordspellen! Er zijn mooie verbanden met de complexiteitstheorie. Maar meestal ben ik de leerling van mijn leerlingen.

Ik gaf een lezing aan de Universiteit van Boston over een prachtige discrete stelling genaamd het lemma van Sperner. Het is heel eenvoudig in één dimensie. Je hebt een lijnstuk waarvan het ene uiteinde rood is en het andere uiteinde blauw. Je verdeelt het in subsegmenten [met knooppunten aan beide uiteinden] en kleurt elk nieuw knooppunt rood of blauw. Dan [ongeacht hoe je ze kleurt] weten we dat er een segment moet zijn dat beide kleuren heeft.

In twee dimensies is het erg fascinerend. Je hebt een driehoek en nu heb je drie kleuren: een hoek is rood, een is blauw en een is groen. Je verdeelt deze driehoek in kleinere driehoeken, zodat de randen in segmenten worden opgedeeld. Elke buitenrand volgt de eendimensionale regel: knooppunten kunnen alleen de kleuren van de twee uiteinden gebruiken. Binnen de driehoek kun je alle drie de kleuren op elke gewenste manier doen. Het lemma van Sperner zegt dat, hoe je het ook verdeelt, als je deze kleuring toepast, er een driehoek moet zijn die alle drie de kleuren heeft.

Kyle Burke was mijn student en werkte destijds aan numerieke analyse. Hij kwam naar mijn kantoor en zei dat er een prachtig bordspel van Sperner's lemma zou kunnen zijn: twee spelers kleuren herhaaldelijk een bord en wie een driehoek met drie kleuren veroorzaakt, verliest het spel. De beste bordspellen hebben winnaars in plaats van een gelijkspel, en hier zal duidelijk iemand winnen. Waarom? Omdat het lemma van Sperner!

Ik belde mijn vriend David Eppstein uit Irvine om te praten over wat een goed bordspel is. Hij zei: "Een goed spel heeft eenvoudige regels en een mooi bord, en het moet PSPACE-moeilijk zijn." Want als je het in polynomiale tijd kunt oplossen, zou een computer je de hele tijd verslaan.

Dus we hebben die criteria doorgenomen. Kyle zei: "Is dit spel eenvoudig?" Ik zei: "Ja, het is één zin!" Hij zei: "Is dit spel kleurrijk?" Ik zei: "Door ontwerp!" Toen zei hij: "Als ik bewijs dat het PSPACE-moeilijk is, kan ik dan promoveren?" Ik zei ja, en hij deed het. Er zijn veel verschillende facetten van zijn stelling. Het onthult bepaalde dingen over vaste punten, wat een heel mooi concept is in de wiskunde.

Kan ik het spel overal spelen?

Het is beschikbaar, met wat aanpassingen, online..

Welke games speel je graag?

Ik ben een speltheoreticus. [Lacht.] Ik speel een beetje met mijn dochter, maar ik ben niet opgegroeid met ze te spelen. In tegenstelling tot mijn studenten, die hun hele leven games hebben gespeeld.

Welk ander werk heb je gedaan op het gebied van de wiskunde van bordspellen?

We hadden een papier onlangs over een open vraag: als je twee in polynoom-tijd oplosbare spellen naast elkaar zou zetten, zouden ze dan PSPACE-moeilijk worden? Bij elke zet kun je er maar één spelen. Dit wordt sommatie van games genoemd.

Wat betekent het om twee games samen te voegen?

Als je in het oude spel Go genoeg stenen neerlegt, krijg je veel afzonderlijke arena's, dus in zekere zin speel je een optelsom van spellen. Je moet je zorgen maken over deze hoek en die hoek. Je wilt alles winnen, maar dat betekent niet dat je elk onderdeel moet winnen.

Het is filosofisch interessant, toch? Het is alsof je een oorlog voert, en er zijn veel veldslagen, maar je aandacht is eindig. Je kunt op elk moment slechts één beslissing nemen op een van de slagvelden, en je tegenstander kan reageren of verdubbelen op een ander slagveld. Ik probeerde dit aan mijn vader uit te leggen. Als je een optelsom van spellen speelt, betekent dat eigenlijk: hoe verlies je strategisch?

We hebben het voor twee games bewezen, maar je kunt drie games samenvoegen en de stelling is nog steeds waar: drie polynoom-tijdgames samen kunnen PSPACE-moeilijk worden.

Hoe reageerde je vader op het verschillende werk dat je in de loop der jaren hebt gedaan, sinds hij je in de richting van informatica duwde?

Hij vroeg me vaak: "Waarom doe je dit?" In theorie werken heb je vaak jarenlang geen resultaat, en dat begreep hij gaandeweg. Al vroeg kon ik praten over de eindige-elementenmethode - dat leren ze ook in de civiele techniek. Maar ik wist niet hoe ik over deze recreatieve wiskunde moest praten.

Toen dacht ik aan een idioom dat is afgeleid van deze beroemde Chinese roman genaamd Romantiek van de drie koninkrijken. Een van de personages, Zhuge Liang, was bijna een perfecte strateeg, en het idioom luidt: "Drie schoenmakers zijn beter dan Zhuge Liang." Het wordt op deze luchtige manier gebruikt om te zeggen dat drie gemiddelde mensen perfect kunnen zijn als ze de hoofden bij elkaar steken. Maar als je naar de geschiedenis van dit idioom kijkt, werden dingen in verschillende regio's anders uitgesproken, en 'schoenenmaker' klonk hetzelfde als 'veldgeneraal'. Dus er staat: "Drie veldgeneraals samen zijn beter dan deze perfecte strateeg."

Ik zei tegen mijn vader dat dat precies de stelling is die we hebben bewezen met de optelling van spellen. De veldgeneraals vertegenwoordigen [algoritmen voor het oplossen van] polynomiale tijdspellen: op elk slagveld weten ze hoe ze moeten winnen. Maar het moeilijkste is om te weten wanneer je moet verliezen, niet hoe je elk van de samenstellende spellen moet winnen. Als iemand dat moeilijke spel kan spelen, is hij echt de beste strateeg. De generaals in het veld nemen deze diepgaande logische beslissingen niet, maar op de een of andere manier, als je ze mooi bij elkaar zet, zijn ze niet slechter dan deze perfecte strateeg.

Ik zei tegen mijn vader: "Ik realiseerde me eindelijk deze wiskundige stelling die overeenkomt met een van onze beroemde uitdrukkingen!" Hij was toen 94, heel scherp, en hij zei: "Dat is een goede poging." Ik heb hem niet helemaal overtuigd. Dat was mijn laatste technische gesprek met hem; een paar maanden later ging hij voorbij. Telkens als ik eraan denk om mijn werk uit te leggen, is dit mijn hoogtepunt.