Informatyk, który znajduje życiowe lekcje w grach

W razie zamówieenia projektu Shang-Hua Teng, informatyka teoretyczna nigdy nie była czysto teoretyczna. Obecnie 58-letni Teng jest profesorem informatyki na Uniwersytecie Południowej Kalifornii i dwukrotnym zdobywcą nagrody Gödla, corocznej nagrody przyznawanej za przełomowe prace teoretyczne. Ale często stara się połączyć tę abstrakcyjną teorię z codziennym życiem w sposób zarówno praktyczny, jak i zabawny.

Urodzony w Pekinie w przededniu chińskiej rewolucji kulturalnej, Teng przybył do Stanów Zjednoczonych na studia podyplomowe, planując studiować architekturę komputerów, ale wkrótce zmienił kierunek, aby skupić się na bardziej abstrakcyjnej teorii matematycznej. Doktoryzował się na Uniwersytecie Carnegie Mellon w 1991 roku za udowodnienie twierdzenia o tym, jak najlepiej podzielić grafy — sieci punktów lub węzłów połączonych liniami lub krawędziami.

Chociaż praca była teoretyczna, miała praktyczne zastosowania — i często, jak stwierdził, praktyczne zastosowania prowadziły do ​​nowych spostrzeżeń teoretycznych. Podczas letniego stypendium NASA w 1993 roku Teng dołączył do zespołu symulującego dynamikę płynów przy użyciu metod „elementów skończonych”, które modelują złożone struktury jako zespoły wielu drobnych elementów. Te asamblaże można traktować jako wykresy, a zadaniem Tenga było dostosowanie metody partycjonowania z jego badań podyplomowych do tego nowego ustawienia. Ale zainteresował się techniką partycjonowania, z której wcześniej korzystał zespół NASA, i zaczął badać jej podstawową strukturę matematyczną wraz z innym informatykiem Daniela Spielmana, obecnie profesor informatyki na Uniwersytecie Yale. Ten wspólny projekt badawczy zapoczątkował trwającą od dziesięcioleci współpracę, która przyniosła im dwie nagrody Gödla.

Nie był to jedyny raz, kiedy dostrzegł głęboki związek między teorią a praktyką. „Za każdym razem te pozornie całkowicie praktyczne rzeczy miały za sobą tę piękną matematykę” – powiedział Teng.

Niedawno Teng zwrócił uwagę na piękną matematykę stojącą za grami takimi jak kółko i krzyżyk, szachy i Go. W takich „kombinatorycznych” grach nie ma elementu przypadku, a obaj gracze zawsze wiedzą wszystko o stanie planszy. Jednak gry kombinatoryczne nadal stanowią wyzwanie, ponieważ liczba sposobów na rozegranie gry może być zawrotna.

Badacze teorii gier lubią uogólniać takie gry na coraz większe plansze — skalując grę w kółko i krzyżyk z kwadratów 3 na 3 do n-przez-n, na przykład — i określić ilościowo trudność określenia, który gracz wygra, biorąc pod uwagę początkowy stan planszy. Różne możliwe odpowiedzi dzielą gry na te same „klasy złożoności”, które pojawiają się w całej teoretycznej informatyce.

Jedna słynna klasa złożoności ma prozaiczną nazwę P, oznaczającą „czas wielomianowy” i zawiera rodzaj problemów, które można rozwiązać w rozsądnym czasie, mówiąc z grubsza. Rozwiązywanie problemów z równie słynnej klasy NP może zająć nieracjonalnie dużo czasu, ale ich rozwiązania są łatwe do sprawdzenia. W przypadku problemów należących do innej klasy złożoności, zwanej PSPACE, nawet tak wydajna weryfikacja nie jest gwarantowana. Gdy badacze zastanawiają się nad „głęboką logiką” gier dwuosobowych — „jeśli ty zrobisz X, a potem ja zrobię Y, a potem ty Z” itd. — często mówią o PSPACE. Ale jak Teng pomógł udowodnić, matematyka gier kombinatorycznych nie zawsze jest prosta.

Quanta rozmawiał niedawno z Tengiem, aby omówić swoją drogę do informatyki, matematykę leżącą u podstaw gier planszowych i wpływ ojca. Wywiad został skrócony i zredagowany dla przejrzystości.

Jak to było zdobywać wykształcenie w Chinach?

Urodziłem się na krótko przed rewolucją kulturalną, a mój ojciec był kierownikiem wydziału inżynierii lądowej na uniwersytecie. Kiedy wybuchła rewolucja, był w niewoli na kampusie. Następnie cały kampus został wysłany w głąb wsi.

Zbierałem śmieci na sprzedaż, dopóki praktycznie nie skończyłem gimnazjum, a potem nagle Chiny się zmieniły. Jeśli studiowałeś, mogłeś dostać się do college'u, a my nie mieliśmy innej perspektywy na jakąkolwiek stałą pracę. Obudziłem się i powiedziałem: „Muszę się uczyć”.

Jak wybrałeś informatykę?

Po liceum chciałam studiować biologię. Nie wiem dlaczego, ale mój ojciec nie był z tego powodu zadowolony. Radziłem sobie dobrze z matematyki, a on zapytał mnie, czy chcę studiować matematykę. Powiedziałem nie. [Śmiech.] A potem powiedział: „Wiesz, jest nowa dyscyplina zwana informatyką i jest naprawdę dobra”. W jakiś sposób skłonił mnie do studiowania informatyki.

Edukacja w tym czasie była bardzo podstawowa. Nie byliśmy narażeni na większość rzeczy, a informatyka nie była nawet wydziałem; był to kierunek elektrotechnika. Ale przez zupełny przypadek zostaliśmy wyszkoleni jako studenci matematyki w zakresie rachunku różniczkowego i nauczyłem się kilku rzeczy, które ostatecznie przydały mi się w zostaniu teoretykiem. Bez tego prawdopodobnie nie miałbym szans na przejście. W dzisiejszych czasach dzieci są znacznie bardziej utalentowane: od liceum są bardziej utalentowanymi matematykami niż ja, kiedy przyjechałem do tego kraju.

Jak te luki w twojej wiedzy wpłynęły na twoje doświadczenie w szkole wyższej?

Pewnego dnia [mój doradca, Gary Miller] odkrył, że nigdy nie słyszałem o NP. To było w dyskusji. Powiedział: „Ten problem wygląda na NP-trudny”. Powiedziałem: „Aha”. On powiedział: „Nie wierzysz mi?” A potem zaczął to udowadniać iw połowie gwałtownie odwrócił się do mnie, bo właśnie tam siedziałem, i powiedział: „Wiesz, co to jest NP-trudny?” Powiedziałem nie.

Myślałem, że to mój ostatni dzień pracy z nim, ale kontynuował i przedstawił mi definicję. Powiedział: „Jeśli nie wiesz, to nie ma znaczenia, o ile jesteś w stanie myśleć”. Miał na mnie ogromny wpływ.

Jesteś przede wszystkim teoretykiem, ale przez całą swoją karierę robiłeś wypady do przemysłu. Jak ta praktyczna praca łączyła się z twoimi badaniami teoretycznymi?

W mojej pracy opracowałem kilka geometrycznych metod podziału grafów. Udało mi się wykazać, że ta rodzina metod geometrycznych daje możliwe do udowodnienia dobre cięcia dla grafów elementów skończonych.

Z polecenia mojego mentora zacząłem wygłaszać wykłady w NASA i Boeing Aerospace. Pamiętam, że w Boeingu model 3D jednego ze skrzydeł miał już blisko milion elementów — nie mogli nawet tego załadować do jednej maszyny. Chcieli więc podzielić ten wykres na różne komponenty, umieścić je na różnych maszynach o podobnym obciążeniu obliczeniowym i zminimalizować komunikację. Dlatego matematycznie formuła jest cięciem wykresu.

W informatyce teoretycznej często podstawowe zasady matematyczne pozostają niezmienione, nawet jeśli wygląd problemu zmienia się drastycznie, od optymalizacji do teorii gier. Kiedy przeprowadzasz badania, nie wydaje się to drastyczną zmianą.

Mówiąc o teorii gier, widziałem, że pomogłeś zaprojektować grę planszową. Jak to się stało?

Och, uwielbiam gry planszowe! Istnieją piękne powiązania z teorią złożoności. Ale przede wszystkim jestem uczniem moich uczniów.

Wygłaszałem wykład na Uniwersytecie Bostońskim na temat pięknego twierdzenia dyskretnego zwanego lematem Spernera. To bardzo proste w jednym wymiarze. Masz odcinek linii, w którym jeden koniec jest czerwony, a drugi niebieski. Dzielisz go na podsegmenty [z węzłami na obu końcach] i kolorujesz każdy nowy węzeł na czerwono lub niebiesko. Wtedy [bez względu na to, jak je pokolorujesz] wiemy, że musi istnieć segment, który ma oba kolory.

W dwóch wymiarach jest to bardzo fascynujące. Masz trójkąt, a teraz masz trzy kolory: jeden róg jest czerwony, jeden jest niebieski, a jeden jest zielony. Dzielisz ten trójkąt na mniejsze trójkąty, więc krawędzie są podzielone na segmenty. Każda zewnętrzna krawędź jest zgodna z jednowymiarową zasadą: Węzły mogą używać tylko kolorów dwóch końców. Wewnątrz trójkąta możesz zrobić wszystkie trzy kolory w dowolny sposób. Lemat Spernera mówi, że niezależnie od tego, jak to podzielisz, jeśli wykonasz to kolorowanie, musi istnieć trójkąt, który ma wszystkie trzy kolory.

Kyle Burke był moim uczniem, pracującym wówczas nad analizą numeryczną. Przyszedł do mojego biura i powiedział, że mogłaby powstać piękna gra planszowa z lematem Spernera: Dwóch graczy kolejno koloruje planszę, a ten, kto wywoła trójkolorowy trójkąt, przegrywa grę. Najlepsze gry planszowe mają zwycięzców, a nie remis, a tutaj wyraźnie ktoś wygra. Czemu? Ponieważ lemat Spernera!

Zadzwoniłem do mojego przyjaciela Davida Eppsteina z Irvine, aby porozmawiać o tym, co czyni dobrą grę planszową. Powiedział: „Dobra gra ma proste zasady i piękną planszę, i musi być trudna na PSPACE”. Ponieważ jeśli potrafisz rozwiązać to w czasie wielomianowym, komputer będzie cię bił przez cały czas.

Więc przeszliśmy przez te kryteria. Kyle zapytał: „Czy ta gra jest prosta?” Powiedziałem: „Tak, to jedno zdanie!” Zapytał: „Czy ta gra jest kolorowa?” Powiedziałem: „Zgodnie z projektem!” Potem powiedział: „Jeśli udowodnię, że jest to PSPACE-trudne, czy dostanę doktorat?” Powiedziałem, że tak, a on to zrobił. Istnieje wiele różnych aspektów jego twierdzenia. Ujawnia pewne rzeczy na temat punktów stałych, które są bardzo pięknym pojęciem w matematyce.

Czy mogę zagrać w grę w dowolnym miejscu?

Jest dostępny, z pewnymi poprawkami, Online.

W jakie gry lubisz grać?

Jestem teoretykiem gier. [Śmiech.] Bawię się trochę z moją córką, ale nie dorastałem, bawiąc się nimi. W przeciwieństwie do moich studentów, którzy grali w gry przez całe życie.

Jakie inne prace wykonałeś na temat matematyki gier planszowych?

Mieliśmy papier niedawno o otwartym pytaniu: jeśli położysz obok siebie dwie gry, które można rozwiązać w czasie wielomianowym, czy sprawi to, że będą one trudne w PSPACE? W każdym ruchu możesz zagrać tylko jeden z nich. Nazywa się to sumowaniem gier.

Co to znaczy połączyć ze sobą dwie gry?

W starożytnej grze Go, kiedy ułożysz wystarczającą liczbę kamieni, otrzymasz wiele oddzielnych aren, więc w pewnym sensie grasz w sumę gier. Musisz się martwić o ten róg i tamten róg. Chcesz wygrać całość, ale to nie znaczy, że musisz wygrać każdą część.

To filozoficznie interesujące, prawda? To tak, jakbyś miał wojnę, która ma wiele bitew, ale twoja uwaga jest ograniczona. W dowolnym momencie możesz podjąć tylko jedną decyzję na jednym polu bitwy, a twój przeciwnik może albo odpowiedzieć, albo podwoić się na innym polu bitwy. Próbowałem to wytłumaczyć ojcu. Kiedy grasz w sumę gier, tak naprawdę oznacza to: Jak przegrywasz strategicznie?

Udowodniliśmy to dla dwóch gier, ale można połączyć trzy gry, a twierdzenie jest nadal prawdziwe: trzy gry w czasie wielomianowym razem mogą stać się PSPACE-trudne.

Odkąd popchnął cię w kierunku informatyki, jak twój ojciec zareagował na różne prace, które wykonywałeś przez lata?

Często pytał mnie: „Dlaczego to robisz?”. Pracując w teorii, często nie ma się latami żadnych rezultatów i stopniowo to zrozumiał. Na początku mogłem mówić o metodzie elementów skończonych — uczą tego też w inżynierii lądowej. Ale nie mogłem wymyślić, jak rozmawiać o tej rekreacyjnej matematyce.

Wtedy pomyślałem o idiomie wywodzącym się z tej słynnej chińskiej powieści pt Opowieści o Trzech Królestwach. Jeden z bohaterów, Zhuge Liang, był prawie doskonałym strategiem, a idiom brzmi: „Trzej szewcy są lepsi niż Zhuge Liang”. Używa się go w ten beztroski sposób, aby powiedzieć, że troje przeciętnych ludzi może być doskonałych, gdy połączą swoje głowy. Ale kiedy spojrzysz na historię tego idiomu, w różnych regionach wymawiano różne rzeczy, a „naprawiacz butów” brzmiał tak samo jak „generał polowy”. Mówi się więc: „Trzech generałów polowych razem jest lepszych niż ten doskonały strateg”.

Powiedziałem ojcu, że dokładnie to twierdzenie udowodniliśmy sumując gry. Generałowie polowi reprezentują [algorytmy rozwiązywania] gier wielomianowych: na każdym polu bitwy wiedzą, jak wygrać. Ale najtrudniejszą częścią jest wiedzieć, kiedy przegrać, a nie jak wygrać każdą z gier składowych. Jeśli ktoś potrafi grać w tę trudną grę, jest naprawdę najlepszym strategiem. Generałowie polowi nie podejmują tak głęboko logicznych decyzji, ale jeśli dobrze je połączyć, nie są gorsi od tego doskonałego stratega.

Powiedziałem tacie: „W końcu zdałem sobie sprawę z tego twierdzenia matematycznego, które odpowiada jednemu z naszych słynnych idiomów!” Miał wtedy 94 lata, był bardzo bystry i powiedział: „To dobra próba”. Nie do końca go przekonałem. To była moja ostatnia techniczna rozmowa z nim; kilka miesięcy później przeszedł. Ilekroć myślę o wyjaśnieniu mojej pracy, jest to dla mnie najważniejsze.