Az informatikus, aki életleckéket talál a játékokban

A Shang-Hua Teng, az elméleti számítástechnika soha nem volt pusztán elméleti. A most 58 éves Teng a Dél-Kaliforniai Egyetem számítástechnika professzora, és kétszeres nyertese a Gödel-díjnak. De gyakran arra törekszik, hogy ezt az elvont elméletet praktikus és játékos módon összekapcsolja a mindennapi élettel.

A kínai kulturális forradalom előestéjén Pekingben született Teng az Egyesült Államokba érkezett, hogy posztgraduális iskolát tervezzen számítógépes építészetet tanulni, de hamarosan irányt váltott, és az elvontabb matematikai elméletre összpontosított. 1991-ben doktorált a Carnegie Mellon Egyetemen, mert bebizonyított egy tételt arról, hogyan lehet a legjobban particionálni gráfokat – ponthálókat vagy csomópontokat, amelyeket vonalak vagy élek kötnek össze.

Bár elméleti volt, a munkának voltak gyakorlati alkalmazásai – és gyakran tapasztalta, hogy a gyakorlati alkalmazások új elméleti meglátásokhoz vezettek. Egy 1993-as NASA nyári ösztöndíja során Teng csatlakozott egy olyan csapathoz, amely „végeselemes” módszerekkel szimulálja a folyadékdinamikát, amely összetett szerkezeteket sok apró darabból álló összeállításként modellez. Ezek az összeállítások gráfokként kezelhetők, és Teng feladata az volt, hogy a diplomás kutatásaiból származó particionálási módszert ehhez az új beállításhoz igazítsa. De kíváncsi lett a NASA csapata által korábban alkalmazott particionálási technikára, és egy informatikustársával együtt vizsgálni kezdte annak matematikai szerkezetét. Daniel Spielman, jelenleg a Yale Egyetem informatika professzora. Ez a közös kutatási projekt elindított egy több évtizedes együttműködést, amellyel elnyerték a két Gödel-díjat.

Nem ez volt az egyetlen alkalom, hogy mély kapcsolatot látott az elmélet és a gyakorlat között. „Minden alkalommal ezek a látszólag teljesen praktikus dolgok mögött ez a gyönyörű matematika állt” – mondta Teng.

A közelmúltban Teng az olyan játékok mögött rejlő gyönyörű matematika felé fordította a figyelmét, mint a tic-tac-toe, a sakk és a Go. Az ilyen „kombinációs” játékokban nincs véletlen, és mindkét játékos mindig mindent tud a tábla állapotáról. A kombinatorikus játékok azonban továbbra is kihívást jelentenek, mivel egy játékban szédítően nagy lehet a játékmódok száma.

A játékelmélet kutatói szeretik az ilyen játékokat egyre nagyobb táblákra általánosítani – a tic-tac-toe-t 3-ról 3-ra növelik. n-által-npéldául – és számszerűsítsd annak meghatározásának nehézségét, hogy melyik játékos nyer bizonyos kezdeti táblaállapot mellett. A különböző lehetséges válaszok ugyanabba a kategóriába sorolják a játékokat.összetettségi osztályok”, amelyek az elméleti számítástechnika során felbukkannak.

Az egyik híres komplexitási osztály a P prózai elnevezése, a „polinomiális idő”, és olyan problémákat tartalmaz, amelyek durván szólva ésszerű időn belül megoldhatók. A szintén híres NP osztály problémáinak megoldása indokolatlanul sok időt vehet igénybe, de a megoldásuk könnyen ellenőrizhető. Egy másik összetettségi osztályba, a PSPACE-ba tartozó problémák esetén még az ilyen hatékony ellenőrzés sem garantált. Amikor a kutatók figyelembe veszik a kétjátékos játékok „mély logikáját” – „ha csinálsz X-et, majd ha én Y-t, majd ha Z-t” és így tovább –, gyakran azon kapják magukat, hogy a PSPACE-ról beszélnek. De ahogy Teng segített bebizonyítani, a kombinatorikus játékok matematikája nem mindig egyszerű.

Quanta nemrég beszélgetett Tenggel, hogy megvitassa a számítástechnika felé vezető utat, a társasjátékok alapjául szolgáló matematikát és apja hatását. Az interjút az egyértelműség kedvéért sűrítettük és szerkesztettük.

Milyen volt Kínában tanulni?

Valamivel a kulturális forradalom előtt születtem, apám pedig az egyetem építőmérnöki tanszékének tanszékvezetője volt. Amikor a forradalom kitört, fogságban volt az egyetemen. Aztán az egész egyetemet a vidék mélyére küldték.

Gyakorlatilag az alsó tagozat befejezéséig gyűjtöttem a szemetet, hogy eladjam, aztán hirtelen Kína megváltozott. Ha tanultál, bekerülhetsz az egyetemre, és nem volt más kilátásunk arra, hogy rendes munkánk legyen. Felébredtem, és azt mondtam: "Tanulnom kell."

Hogyan választottad a számítástechnikát?

Középiskola után biológiát akartam tanulni. Nem tudom miért, de apám nem nagyon örült ennek. Jól ment a matek, és megkérdezte, hogy akarok-e matekozni. Azt mondtam, nem. [Nevet.] Aztán azt mondta: "Tudod, van egy új tudományág, a számítástechnika, és ez nagyon jó." Valahogy ösztökélt informatika szakra.

Az akkori oktatás nagyon alapvető volt. A legtöbb dolognak nem voltunk kitéve, és az informatika még csak nem is tanszék; villamosmérnöki szak volt. De egy teljesen véletlenszerű szerencsén keresztül matematikai tanulókká képeztek ki bennünket számítástechnikában, és megtanultam néhány dolgot, amelyek végül hasznosak voltak ahhoz, hogy elméleti szakember lehessen. Enélkül valószínűleg nulla esélyem lett volna a továbbjutásra. Manapság a gyerekek sokkal tehetségesebbek: középiskolától kezdve tehetségesebb matematikusok, mint én voltam, amikor ebbe az országba jöttem.

Hogyan befolyásolták ezek a hiányosságok az ismereteiben az érettségivel kapcsolatos tapasztalatait?

Egy napon [tanácsadóm, Gary Miller] rájött, hogy soha nem is hallottam az NP-ről. Egy vitában volt. Azt mondta: "Ez a probléma NP-nehéznek tűnik." Azt mondtam: "Aha." Azt mondta: "Nem hiszel nekem?" Aztán elkezdett bizonygatni, és félúton élesen felém fordult, mert éppen ott ültem, és azt mondta: "Tudod, mi az az NP-hard?" Azt mondtam, nem.

Azt hittem, ez volt az utolsó napom, amikor vele dolgoztam, de folytatta, és elmondta a definíciót. Azt mondta: "Ha nem tudod, nem számít, amíg képes vagy gondolkodni." Óriási hatással volt rám.

Ön elsősorban teoretikus, de karrierje során behatolt az iparba. Hogyan kapcsolódott ez a gyakorlati munka az Ön elméleti kutatásához?

Dolgozatomban néhány geometriai módszert dolgoztam ki gráfok particionálására. Meg tudtam mutatni, hogy ez a geometriai módszercsalád bizonyíthatóan jó vágásokat ad végeselem gráfokhoz.

Mentorom javaslatára elkezdtem előadásokat tartani a NASA-nál és a Boeing Aerospace-nél. Emlékszem, a Boeingnél az egyik szárny 3D-s modellje már közel egymillió elemet tartalmazott – ezt még egy gépbe sem tudták betölteni. Ezért ezt a grafikont különböző komponensekre akarták felvágni, különböző, hasonló számítási terhelésű gépekre rakni, és minimalizálni a kommunikációt. Ezért matematikailag a képlet grafikonvágás.

Az elméleti számítástechnikában a mögöttes matematikai alapelvek gyakran változatlanok még akkor is, ha a probléma megjelenése drasztikusan megváltozik, az optimalizálástól a játékelméletig. Amikor kutatást végez, nem érzi magát drasztikus változásnak.

Ha már a játékelméletről beszélünk, azt láttam, hogy segítettél egy társasjáték tervezésében. Hogyan történt?

Ó, imádom a társasjátékokat! Gyönyörű összefüggések vannak a komplexitáselmélettel. De leginkább a tanítványaim tanítványa vagyok.

A Bostoni Egyetemen tartottam előadást egy gyönyörű diszkrét tételről, amelyet Sperner lemmájának hívnak. Egy dimenzióban nagyon egyszerű. Van egy szakasza, amelynek egyik vége piros, a másik vége kék. Alszegmensekre osztja [mindkét végén csomópontokkal], és minden új csomópontot pirosra vagy kékre színez. Akkor [nem számít, hogyan színezed őket] tudjuk, hogy kell lennie egy szegmensnek, amely mindkét színt tartalmazza.

Két dimenzióban nagyon lenyűgöző. Van egy háromszöged, és most három színed van: az egyik sarok piros, egy kék és egy zöld. Ezt a háromszöget kisebb háromszögekre osztja, így az élek szegmensekre törnek. Mindegyik külső él követi az egydimenziós szabályt: A csomópontok csak a két vég színét használhatják. A háromszögön belül mindhárom színt tetszőlegesen elkészítheti. Sperner lemmája azt mondja, hogy akárhogyan is osztja, ha ezt a színezést végzi, akkor egy háromszögnek kell lennie, amelyben mindhárom szín megtalálható.

Kyle Burke a tanítványom volt, és akkoriban numerikus elemzésen dolgozott. Eljött az irodámba, és azt mondta, hogy lehet egy gyönyörű társasjáték Sperner lemmájából: Két játékos ismétlődően kiszínez egy táblát, és aki előidéz egy háromszínű háromszöget, az elveszíti a játékot. A legjobb társasjátékok inkább nyernek, mint döntetlenek, és itt egyértelműen valaki nyer. Miért? Mert Sperner lemmája!

Felhívtam David Eppstein barátomat Irvine-ből, hogy beszéljek arról, mitől jó egy társasjáték. Azt mondta: „Egy jó játéknak egyszerű szabályai és szép táblája van, és PSPACE-keménynek kell lennie.” Mert ha polinomiális időben meg tudod oldani, akkor egy számítógép állandóan megverne.

Tehát ezeken a kritériumokon mentünk keresztül. Kyle megkérdezte: – Ez a játék egyszerű? Azt mondtam: "Igen, ez egy mondat!" Azt kérdezte: „Színes ez a játék?” Azt mondtam: Tervezve! Aztán azt mondta: „Ha bebizonyítom, hogy PSPACE-nehéz, szerezhetek Ph.D.-t?” Igent mondtam, és ő meg is tette. Tételének sokféle oldala van. Elárul bizonyos dolgokat a fix pontokról, amelyek nagyon szép fogalom a matematikában.

Bárhol játszhatom a játékot?

Elérhető, némi finomítással, online.

Milyen játékokkal szeretsz játszani?

Én a játékok teoretikusa vagyok. [Nevet.] Játszom egy kicsit a lányommal, de nem úgy nőttem fel, hogy játszom velük. Ellentétben a tanítványaimmal, akik egész életükben játszottak.

Milyen egyéb munkát végzett a társasjátékok matematikájával kapcsolatban?

Volt egy papír nemrég egy nyitott kérdésről: Ha két polinomidőben megoldható játékot egymás mellé raksz, attól PSPACE-nehezek lesznek? Minden lépésnél csak egyet játszhatsz belőlük. Ezt hívják a játékok összegzésének.

Mit jelent két játékot összerakni?

Az ősi Go játékban, ha elég követ raksz le, sok különálló arénát kapsz, tehát bizonyos értelemben több játékot játszol. Aggódnod kell ezért a sarokért és azért a sarokért. Meg akarod nyerni az egészet, de ez nem jelenti azt, hogy minden részt meg kell nyerned.

Filozófiailag érdekes, nem? Olyan, mintha háború lenne, és sok csatája lenne, de a figyelmed véges. Bármelyik pillanatban csak egyetlen döntést hozhatsz az egyik csatatéren, és az ellenfeled vagy válaszolhat, vagy duplázhat egy másik csatatéren. Ezt próbáltam elmagyarázni apámnak. Ha egy összeget játszol, az valójában azt jelenti: Hogyan veszítesz stratégiailag?

Két játékra bebizonyítottuk, de három játékot össze lehet rakni, és továbbra is igaz a tétel: Három polinomiális idejű játék összeadva PSPACE-keménysé válhat.

Mióta az informatika felé terelte, hogyan reagált édesapja az évek során végzett különféle munkáira?

Gyakran kérdezte tőlem: „Miért csinálod ezt?” Elméleti munkával gyakran évekig nincs eredménye, és ezt fokozatosan megértette. Már az elején beszélhetnék a végeselem módszerről – ezt tanítják az építőmérnökökben is. De nem tudtam rájönni, hogyan beszéljek erről a rekreációs matematikáról.

Aztán eszembe jutott egy idióma, amely ebből a híres kínai regényből származik A három királyság romantikája. Az egyik szereplő, Zhuge Liang, szinte tökéletes stratéga volt, és a idióma így hangzik: „Három cipőjavító jobb, mint Zhuge Liang”. Ezzel a könnyed módon azt mondják, hogy három átlagos ember tökéletes lehet, ha összedugja a fejét. De ha megnézzük ennek az idiómának a történetét, a dolgokat különbözőképpen ejtették ki a különböző régiókban, és a „cipőjavító” ugyanazt a hangot adta, mint a „terepi tábornok”. Így szól: „Három tábornok együtt jobb, mint ez a tökéletes stratéga.”

Azt mondtam apámnak, hogy pontosan ezt a tételt bizonyítottuk a játékok összegzésével. A mezei tábornokok [algoritmusokat a megoldáshoz] képviselnek polinomiális idejű játékokat: Minden csatatéren tudják, hogyan kell nyerni. De a nehéz rész az, hogy tudjuk, mikor kell veszíteni, nem pedig az, hogy hogyan lehet megnyerni az egyes játékokat. Ha valaki tud ilyen kemény játékot játszani, akkor valóban ő a legjobb stratéga. A tábornokok nem hozzák meg ezeket a mély logikai döntéseket, de ha szépen összerakjuk őket, nem rosszabbak ennél a tökéletes stratégánál.

Azt mondtam apámnak: „Végre rájöttem erre a matematikai tételre, amely egyenértékű az egyik híres idiómánkkal!” 94 éves volt ekkor, nagyon éles, és azt mondta: „Ez egy jó próbálkozás.” nem egészen győztem meg. Ez volt az utolsó technikai beszélgetésem vele; néhány hónappal később elment. Valahányszor arra gondolok, hogy elmagyarázzam a munkámat, ez a legfontosabb.