Računalniški znanstvenik, ki v igrah najde življenjske lekcije

za Shang-Hua Teng, teoretično računalništvo nikoli ni bilo zgolj teoretično. Zdaj 58-letni Teng je profesor računalništva na Univerzi Južne Kalifornije in dvakratni dobitnik Gödelove nagrade, letne nagrade, ki priznava prelomno teoretično delo. Toda pogosto si prizadeva to abstraktno teorijo povezati z vsakdanjim življenjem na praktičen in igriv način.

Teng, rojen v Pekingu na predvečer kitajske kulturne revolucije, je prišel v ZDA na podiplomski študij, kjer je nameraval študirati računalniško arhitekturo, vendar je kmalu spremenil smer in se osredotočil na bolj abstraktno matematično teorijo. Leta 1991 je doktoriral na univerzi Carnegie Mellon, ker je dokazal izrek o tem, kako najbolje razdeliti grafe - mreže točk ali vozlišč, povezane s črtami ali robovi.

Čeprav je bilo teoretično, je imelo delo praktično uporabo - in pogosto, je ugotovil, je praktična uporaba vodila do novih teoretičnih spoznanj. Med poletno štipendijo NASA leta 1993 se je Teng pridružil ekipi, ki simulira dinamiko tekočin z uporabo metod »končnih elementov«, ki modelirajo kompleksne strukture kot sklope številnih drobnih kosov. Te sklope je mogoče obravnavati kot grafe in Tengova naloga je bila prilagoditi metodo razdelitve iz njegove diplomske raziskave tej novi nastavitvi. Zanimala pa ga je tehnika ločevanja, ki jo je prej uporabljala Nasina ekipa, in začel je skupaj s kolegom računalniškim znanstvenikom raziskovati njeno osnovno matematično strukturo. Daniel Spielman, zdaj profesor računalništva na univerzi Yale. Ta skupni raziskovalni projekt je začel desetletja dolgo sodelovanje, ki jima je prineslo dve Gödlovi nagradi.

To ni bil edini čas, ko je videl globoko povezavo med teorijo in prakso. "Vsakič so imele te na videz popolnoma praktične stvari za seboj to čudovito matematiko," je dejal Teng.

Nedavno se je Teng posvetil čudoviti matematiki, ki stoji za igrami, kot so tic-tac-toe, šah in go. V takih "kombinatornih" igrah ni elementa naključja in oba igralca vedno vesta vse o stanju na plošči. Kljub temu so kombinatorične igre še vedno izziv, saj je število načinov, na katere se igra lahko igra, vrtoglavo veliko.

Raziskovalci teorije iger radi posplošujejo takšne igre na vedno večje deske – povečajo tik-tak-toe s polja 3 krat 3 na n-z-n, na primer — in kvantificirajte težavo pri določanju, kateri igralec bo zmagal glede na neko začetno stanje na plošči. Različni možni odgovori razvrstijo igre v isto "razredi zahtevnosti«, ki se pojavljajo skozi celotno teoretično računalništvo.

En slavni razred kompleksnosti se imenuje prozaično P, kar pomeni "polinomski čas", in vsebuje vrsto problemov, ki jih je mogoče rešiti v razumnem času, grobo rečeno. Težave v enako znanem razredu NP lahko vzamejo nerazumno veliko časa za reševanje, vendar je njihove rešitve enostavno preveriti. Za probleme v drugem kompleksnem razredu, imenovanem PSPACE, tudi tako učinkovito preverjanje ni zagotovljeno. Ko raziskovalci razmišljajo o "globoki logiki" iger za dva igralca - "če ti narediš X, potem, če jaz naredim Y, in potem, če ti narediš Z," in tako naprej - se pogosto zalotijo, da govorijo o PSPACE. Toda kot je pomagal dokazati Teng, matematika kombinatoričnih iger ni vedno enostavna.

Quanta je nedavno govoril s Tengom, da bi razpravljal o njegovi poti do računalništva, matematiki, ki je osnova družabnih iger, in očetovem vplivu. Intervju je bil zgoščen in urejen zaradi jasnosti.

Kako se je bilo izobraževati na Kitajskem?

Rodil sem se malo pred kulturno revolucijo in moj oče je bil predstojnik oddelka za gradbeništvo na univerzi. Ko se je zgodila revolucija, je bil v ujetništvu v kampusu. Potem so celoten kampus poslali globoko na podeželje.

Včasih sem zbiral smeti za prodajo, dokler nisem praktično končal nižje šole, nato pa se je Kitajska nenadoma spremenila. Če si študiral, si se lahko vpisal na fakulteto, druge možnosti za redno službo pa nismo imeli. Zbudil sem se in rekel: "Moram se učiti."

Kako ste izbrali računalništvo?

Po srednji šoli sem želel študirati biologijo. Ne vem zakaj, ampak moj oče s tem ni bil najbolj zadovoljen. Pri matematiki mi je šlo dobro in vprašal me je, ali se želim ukvarjati z matematiko. Rekel sem ne. [Smeh.] In potem je rekel: "Veš, obstaja nova disciplina, imenovana računalništvo, in res je dobra." Nekako me je pahnil v študij računalništva.

Takratna izobrazba je bila zelo osnovna. Večini stvari nismo bili izpostavljeni, računalništvo pa niti ni bilo katedra; bila je smer elektrotehnika. Toda po povsem naključni sreči smo bili kot študenti matematike usposobljeni za računanje in naučil sem se nekaj stvari, ki so bile sčasoma uporabne, da sem postal teoretik. Brez tega verjetno ne bi imel možnosti za prehod. Dandanes so otroci veliko bolj nadarjeni: od srednje šole naprej so bolj nadarjeni matematiki, kot sem bil jaz, ko sem prišel v to državo.

Kako so te vrzeli v vašem znanju vplivale na vaše izkušnje s podiplomskim študijem?

Nekega dne je [moj svetovalec Gary Miller] ugotovil, da še nikoli nisem slišal za NP. Bilo je v razpravi. Rekel je: "Ta problem je videti NP-težak." Rekel sem, "Uh-huh." Rekel je: "Mi ne verjameš?" In potem je začel dokazovati in se na pol poti ostro obrnil proti meni, ker sem samo sedel tam, in rekel: "Ali veš, kaj je NP-hard?" Rekel sem ne.

Mislil sem, da je to moj zadnji dan dela z njim, a je nadaljeval in mi povedal definicijo. Rekel je: "Če ne veš, ni pomembno, dokler si sposoben razmišljati." Name je imel izjemen vpliv.

V prvi vrsti ste teoretik, vendar ste v svoji karieri posegali po industriji. Kako se je to praktično delo povezalo z vašim teoretičnim raziskovanjem?

V diplomski nalogi sem razvil nekaj geometrijskih metod za razdeljevanje grafov. Lahko sem pokazal, da je ta družina geometrijskih metod dala dokazano dobre reze za grafe s končnimi elementi.

Na mentorjevo priporočilo sem začel predavati pri Nasi in Boeing Aerospace. Pri Boeingu se spominjam, da je imel 3D model enega od kril že skoraj milijon elementov — niti tega niso mogli naložiti v en stroj. Zato so želeli ta graf razrezati na različne komponente, jih postaviti na različne stroje s podobnimi računalniškimi obremenitvami in zmanjšati komunikacijo. Zato je matematično formula izrez grafa.

V teoretičnem računalništvu so temeljna matematična načela pogosto nespremenjena, tudi če se videz problema drastično spremeni, od optimizacije do teorije iger. Ko delate raziskavo, se ne zdi, da gre za drastično spremembo.

Ko že govorimo o teoriji iger, sem videl, da ste pomagali oblikovati družabno igro. Kako se je to zgodilo?

Oh, obožujem družabne igre! Obstajajo lepe povezave s teorijo kompleksnosti. Toda večinoma sem učenec svojih učencev.

Na bostonski univerzi sem imel govor o čudovitem diskretnem izreku, imenovanem Spernerjeva lema. V eni dimenziji je zelo preprosto. Imate segment črte, kjer je en konec rdeč in en konec moder. Razdelite ga na podsegmente [z vozlišči na obeh koncih] in vsako novo vozlišče obarvate rdeče ali modro. Potem [ne glede na to, kako jih obarvate] vemo, da mora obstajati segment, ki ima obe barvi.

V dveh dimenzijah je zelo fascinantno. Imate trikotnik in zdaj imate tri barve: En vogal je rdeč, en moder in en zelen. Ta trikotnik razdelite na manjše trikotnike, tako da so robovi razdeljeni na segmente. Vsak zunanji rob sledi enodimenzionalnemu pravilu: vozlišča lahko uporabljajo samo barve obeh koncev. Znotraj trikotnika lahko po želji naredite vse tri barve. Spernerjeva lema pravi, da kakorkoli ga razdelite, če naredite to barvanje, mora obstajati trikotnik, ki ima vse tri barve.

Kyle Burke je bil moj študent, ki je takrat delal na numerični analizi. Prišel je v mojo pisarno in rekel, da bi lahko nastala čudovita družabna igra Spernerjeve leme: dva igralca iterativno obarvata ploščo in kdor ustvari trikotnik s tremi barvami, bo izgubil igro. Najboljše družabne igre imajo zmagovalce namesto izenačenega izida in tukaj bo očitno nekdo zmagal. Zakaj? Ker Spernerjeva lema!

Poklical sem svojega prijatelja Davida Eppsteina iz Irvina, da bi se pogovoril o tem, kaj naredi dobro družabno igro. Rekel je: "Dobra igra ima preprosta pravila in lepo tablo ter mora biti težka za PSPACE." Ker če ga lahko rešiš v polinomskem času, bi te računalnik ves čas premagal.

Torej smo šli skozi ta merila. Kyle je rekel: "Je ta igra preprosta?" Rekel sem: "Ja, to je en stavek!" Rekel je: "Je ta igra barvita?" Rekel sem: "Načrtovano!" Potem je rekel: "Če dokažem, da je težko za PSPACE, lahko pridobim doktorat?" Rekel sem da in on je. Obstaja veliko različnih vidikov njegovega izreka. Razkriva nekatere stvari o fiksnih točkah, ki so zelo lep koncept v matematiki.

Ali lahko igram igro kjer koli?

Na voljo je z nekaj prilagoditvami, na spletu.

Katere igre najraje igraš?

Sem teoretik iger. [Smeh.] Malo se igram s hčerko, vendar nisem odraščal ob igranju z njimi. Za razliko od mojih študentov, ki igrajo igrice vse življenje.

Kaj ste še delali na področju matematike družabnih iger?

Imeli smo papirja nedavno o odprtem vprašanju: Če postavite dve polinomsko-časovno rešljivi igri skupaj eno ob drugi, ali bosta zaradi tega PSPACE-težki? Pri vsaki potezi lahko igrate samo enega od njih. To se imenuje seštevanje iger.

Kaj pomeni sestaviti dve igri skupaj?

V starodavni igri Go, ko odložite dovolj kamnov, dobite veliko ločenih aren, tako da na nek način igrate vsoto iger. Skrbeti moraš za ta in tisti kotiček. Želite zmagati v celoti, vendar to ne pomeni, da morate zmagati vsak del.

To je filozofsko zanimivo, kajne? Kot da imate vojno in veliko bitk, a vaša pozornost je omejena. V vsakem trenutku lahko sprejmete samo eno odločitev na enem od bojišč, vaš nasprotnik pa se lahko odzove ali podvoji na drugem bojišču. To sem poskušal razložiti očetu. Ko igrate seštevek iger, to v resnici pomeni: Kako strateško izgubljate?

To smo dokazali za dve igri, vendar lahko sestavite tri igre skupaj in izrek še vedno velja: tri igre s polinomskim časom, sestavljene skupaj, lahko postanejo zahtevne za PSPACE.

Kako se je vaš oče odzval na drugačna dela, ki ste jih opravljali v preteklih letih, ker vas je usmeril v računalništvo?

Pogosto me je vprašal: "Zakaj to počneš?" Če delaš v teoriji, pogosto leta nimaš rezultata, in to je razumel postopoma. Na začetku bi lahko govoril o metodi končnih elementov - to učijo tudi v gradbeništvu. Ampak nisem mogel ugotoviti, kako naj govorim o tej razvedrilni matematiki.

Potem sem pomislil na idiom, ki izhaja iz tega znanega kitajskega romana, imenovanega Romantika treh kraljestev. Eden od likov, Zhuge Liang, je bil skoraj popoln strateg in idiom pravi: "Trije popravljalci čevljev so boljši od Zhugeja Lianga." Na ta lahkoten način se uporablja za besedo, da so lahko trije povprečni ljudje popolni, ko strnejo glave skupaj. Toda ko pogledate zgodovino tega idioma, so se stvari v različnih regijah izgovarjale drugače in "popravljalec čevljev" je imel enak zvok kot "terenski general". Torej pravi: "Trije terenski generali skupaj so boljši od tega popolnega stratega."

Očetu sem rekel, da je ravno to izrek, ki smo ga dokazali s seštevkom iger. Terenski generali predstavljajo [algoritme za reševanje] polinomskih časovnih iger: Na vsakem bojišču vedo, kako zmagati. Toda težji del je vedeti, kdaj izgubiti, ne pa, kako zmagati v vsaki od sestavnih iger. Če lahko nekdo igra tako težko igro, je res najboljši strateg. Terenski generali ne sprejemajo teh globokih logičnih odločitev, a nekako, če jih lepo sestavite skupaj, niso nič slabši od tega popolnega stratega.

Očetu sem rekel: "Končno sem spoznal ta matematični izrek, ki je enakovreden enemu od naših slavnih idiomov!" Takrat je bil star 94 let, zelo bister in je rekel: "To je dober poskus." Nisem ga čisto prepričal. To je bil moj zadnji tehnični pogovor z njim; nekaj mesecev kasneje je umrl. Kadarkoli razmišljam o razlagi svojega dela, je to moj vrhunec.