Комп’ютерний вчений, який знаходить життєві уроки в іграх

для Шан-Хуа Тенг, теоретична інформатика ніколи не була суто теоретичною. Зараз 58-річний Тенг є професором інформатики в Університеті Південної Каліфорнії та дворазовим лауреатом премії Геделя, щорічної нагороди, яка відзначається за новаторські теоретичні роботи. Але він часто прагне пов’язати цю абстрактну теорію з повсякденним життям у практичний і ігровий спосіб.

Народився в Пекіні напередодні Китайської культурної революції, Тенг приїхав до Сполучених Штатів для навчання в аспірантурі, плануючи вивчати комп’ютерну архітектуру, але незабаром змінив напрямок і зосередився на більш абстрактній математичній теорії. Він отримав ступінь доктора в Університеті Карнегі-Меллона в 1991 році за доказ теореми про те, як найкраще розбивати графи — мережі точок або вузлів, з’єднаних лініями або ребрами.

Хоча ця робота була теоретичною, вона мала практичне застосування — і часто, як він виявив, практичне застосування призводило до нових теоретичних ідей. Під час літньої стипендії NASA в 1993 році Тенг приєднався до команди, яка симулювала динаміку рідини за допомогою методів «кінцевих елементів», які моделюють складні структури як сукупності багатьох крихітних частин. Ці збірки можна розглядати як графіки, і завдання Тенга полягало в тому, щоб адаптувати метод розподілу з його дипломного дослідження до цієї нової обстановки. Але він зацікавився технікою розділення, яку команда NASA використовувала раніше, і почав досліджувати її основну математичну структуру разом із колегою-комп’ютерником. Деніел Спілман, нині професор інформатики Єльського університету. Цей спільний дослідницький проект поклав початок десятиліттям співпраці, яка принесла їм дві премії Геделя.

Це був не єдиний раз, коли він бачив глибокий зв’язок між теорією та практикою. «Кожного разу за цими, здавалося б, цілком практичними речами стояла прекрасна математика», — сказав Тенг.

Нещодавно Тенг звернув увагу на прекрасну математику, що стоїть за такими іграми, як хрестики-нулики, шахи та го. У таких «комбінаторних» іграх відсутній елемент випадковості, і обидва гравці завжди знають все про стан дошки. Проте комбінаторні ігри залишаються складними, оскільки кількість способів, за якими гра може розгортатися, може бути запаморочливо великою.

Дослідники теорії ігор люблять узагальнювати такі ігри на дедалі більших дошках — збільшуючи хрестики-нулики з квадратів 3 на 3 до n-за-n, наприклад — і кількісно оцінити складність визначення гравця, який переможе, враховуючи певний початковий стан дошки. Різні можливі відповіді сортують ігри в однакові "класи складності», які виникають у теоретичній інформатиці.

Один відомий клас складності має прозаїчну назву P, що означає «поліноміальний час», і містить проблеми, які можна розв’язати за розумний проміжок часу, грубо кажучи. Розв’язання задач у не менш відомому класі NP може зайняти невиправдано багато часу, але їх рішення легко перевірити. Для проблем іншого класу складності, який отримав назву PSPACE, навіть така ефективна перевірка не гарантується. Коли дослідники розглядають «глибоку логіку» ігор для двох гравців — «якщо ви зробите X, а потім, якщо я зроблю Y, а потім, якщо ви зробите Z» і так далі, — вони часто говорять про PSPACE. Але, як Тенг допоміг довести, математика комбінаторних ігор не завжди проста.

Quanta нещодавно розмовляв із Теном, щоб обговорити його шлях до інформатики, математику, що лежить в основі настільних ігор, і вплив свого батька. Інтерв’ю було скорочено та відредаговано для ясності.

Як це було здобувати освіту в Китаї?

Я народився трохи раніше Культурної революції, і мій батько був завідувачем факультету цивільної інженерії в університеті. Коли сталася революція, він був у полоні на території університету. Тоді весь кампус був відправлений углиб сільської місцевості.

Раніше я збирав сміття, щоб продати його, поки я практично не закінчив молодшу школу, а потім раптом Китай змінився. Якщо ти навчався, ти міг вступити до коледжу, і в нас не було іншої перспективи мати якусь постійну роботу. Я прокинувся і сказав: «Мені потрібно вчитися».

Як ви обрали інформатику?

Після школи я хотіла вивчати біологію. Не знаю чому, але батько був цим не дуже задоволений. З математикою я йшов добре, і він запитав мене, чи хочу я займатися математикою. Я сказав ні. [Сміється.] А потім він сказав: «Знаєте, є нова дисципліна під назвою інформатика, і вона дуже хороша». Якось він підштовхнув мене до спеціальності інформатика.

Освіта на той час була дуже базовою. Ми не стикалися з більшістю речей, а інформатика навіть не була кафедрою; це була спеціальність електротехніка. Але завдяки абсолютно випадковій долі ми, як студенти математики, навчалися обчисленню, і я навчився кількох речей, які згодом стали корисними для того, щоб стати теоретиком. Без цього я, ймовірно, не мав би жодного шансу пройти. Сьогодні діти набагато талановитіші: починаючи зі середньої школи, вони є більш обдарованими математиками, ніж я був, коли приїхав до цієї країни.

Як ці прогалини у ваших знаннях вплинули на ваш досвід аспірантури?

Одного разу [мій радник Гері Міллер] виявив, що я ніколи не чув про NP. Це було в дискусії. Він сказав: «Ця проблема виглядає NP-складною». Я сказав: "Угу". Він сказав: «Ти мені не віриш?» А потім він почав це доводити, а на півдорозі різко повернувся до мене, тому що я просто сидів там, і сказав: «Ти знаєш, що таке NP-hard?» Я сказав ні.

Я думав, що це був мій останній день роботи з ним, але він продовжив і сказав мені визначення. Він сказав: «Якщо ви не знаєте, це не має значення, якщо ви здатні думати». Він справив на мене величезний вплив.

Ви насамперед теоретик, але протягом вашої кар’єри ви робили набіги в індустрію. Як ця практична робота пов’язана з вашими теоретичними дослідженнями?

У своїй дисертації я розробив деякі геометричні методи для розбиття графів. Я зміг показати, що це сімейство геометричних методів дає доказово хороші скорочення для кінцево-елементних графів.

За рекомендацією свого наставника я почав виступати з доповідями в NASA та Boeing Aerospace. Я пам’ятаю, що в Boeing 3D-модель одного з крил уже мала близько мільйона елементів — вони навіть не могли завантажити це в одну машину. Тож вони хотіли розділити цей графік на різні компоненти, розмістити їх на різних машинах із подібним обчислювальним навантаженням і мінімізувати зв’язок. Ось чому з математичної точки зору формула є розрізом графіка.

У теоретичній інформатиці математичні принципи, що лежать в основі, часто залишаються незмінними, навіть коли вигляд проблеми різко змінюється, від оптимізації до теорії ігор. Коли ви проводите дослідження, це не відчувається як кардинальна зміна.

Говорячи про теорію ігор, я бачив, що ви допомогли створити настільну гру. Як це сталося?

О, я люблю настільні ігри! Існують чудові зв’язки з теорією складності. Але здебільшого я учень своїх учнів.

Я виступав із доповіддю в Бостонському університеті про чудову дискретну теорему під назвою лема Шпернера. Це дуже просто в одному вимірі. У вас є відрізок, один кінець якого червоний, а інший синій. Ви розділяєте його на підсегменти [з вузлами на обох кінцях] і фарбуєте кожен новий вузол або в червоний, або в синій колір. Тоді [незалежно від того, як ви їх розфарбовуєте], ми знаємо, що має бути сегмент, який має обидва кольори.

У двох вимірах це дуже захоплююче. У вас є трикутник, і тепер у вас є три кольори: один кут червоний, один синій і один зелений. Ви ділите цей трикутник на менші трикутники, тому ребра розбиваються на сегменти. Кожне зовнішнє ребро дотримується одновимірного правила: вузли можуть використовувати лише кольори двох кінців. Всередині трикутника ви можете зробити всі три кольори як завгодно. Лема Спернера говорить, що як би ви не розділили це, якщо ви розфарбовуєте, має бути трикутник, який має всі три кольори.

Кайл Берк був моїм учнем і працював над чисельним аналізом у той час. Він прийшов до мене в офіс і сказав, що може бути гарна настільна гра з лемою Спернера: два гравці ітеративно розфарбовують дошку, і той, хто створить трикутник з трьох кольорів, програє гру. У найкращих настільних іграх є переможці, а не нічия, і тут явно хтось виграє. чому Тому що лема Шпернера!

Я подзвонив своєму другові Девіду Еппштейну з Ірвіна, щоб поговорити про те, що робить настільну гру хорошою. Він сказав: «Хороша гра має прості правила та красиву дошку, і вона має бути складною для PSPACE». Тому що, якщо ви можете розв’язати це за поліноміальний час, комп’ютер завжди перемагатиме вас.

Тож ми пройшли ці критерії. Кайл запитав: «Ця гра проста?» Я сказав: «Так, це одне речення!» Він запитав: «Ця гра барвиста?» Я сказав: «Задумом!» Потім він сказав: «Якщо я доведу, що це складно для PSPACE, чи зможу я отримати ступінь доктора філософії?» Я сказав так, і він зробив. Є багато різних аспектів його теореми. Він розкриває певні речі про фіксовані точки, які є дуже красивою концепцією в математиці.

Чи можу я грати в гру будь-де?

Він доступний із деякими налаштуваннями, онлайн.

У які ігри ти любиш грати?

Я теоретик ігор. (Сміється.) Я трохи граю зі своєю дочкою, але я не виріс, граючи з ними. На відміну від моїх учнів, які все життя грали в ігри.

Яку ще роботу ви виконали з математики настільних ігор?

У нас був а папір Нещодавно про відкрите запитання: якщо ви помістите разом дві поліноміально-часові ігри, пліч-о-пліч, чи це зробить їх складними для PSPACE? На кожному ході ви можете зіграти лише одну з них. Це називається підсумовуванням ігор.

Що означає зібрати дві гри разом?

У стародавній грі Go, коли ви кладете достатньо каменів, ви отримуєте багато окремих арен, тож у певному сенсі ви граєте в суму ігор. Ви повинні турбуватися про цей кут і той кут. Ви хочете виграти все, але це не означає, що ви повинні виграти кожну частину.

Це філософськи цікаво, правда? Ніби у вас війна, і в ній багато битв, але ваша увага обмежена. У будь-який момент ви можете прийняти лише одне рішення на одному з полів бою, а ваш супротивник може або відповісти, або подвоїтися на іншому полі бою. Я намагався пояснити це батькові. Коли ви граєте на суму ігор, це насправді означає: як ви програєте стратегічно?

Ми довели це для двох ігор, але ви можете зібрати три ігри разом, і теорема все ще вірна: три ігри з поліноміальним часом, зібрані разом, можуть стати складними для PSPACE.

Оскільки він підштовхнув вас до інформатики, як ваш батько реагував на різну роботу, яку ви виконували протягом багатьох років?

Він часто запитував мене: «Навіщо ти це робиш?» Працюючи в теорії, часто не маєш результату роками, і він це розумів поступово. Раніше я міг говорити про метод скінченних елементів — вони також вчать це в цивільному будівництві. Але я не міг зрозуміти, як говорити про цю розважальну математику.

Тоді я подумав про ідіому, яка походить від цього відомого китайського роману під назвою Троєцарствіє. Один із персонажів, Чжуге Лян, був майже ідеальним стратегом, і ідіома говорить: «Три лагодителі взуття краще, ніж Чжуге Лян». Його використовують у такий легковажний спосіб, щоб сказати, що троє звичайних людей можуть бути ідеальними, коли зведуть свої голови разом. Але якщо поглянути на історію цієї ідіоми, то в різних регіонах речі вимовлялися по-різному, і «поправник взуття» мав те саме звучання, що й «польовий генерал». Тож там сказано: «Три польові генерали разом краще, ніж цей ідеальний стратег».

Я сказав батькові, що це саме та теорема, яку ми довели підсумовуванням ігор. Польові генерали представляють [алгоритми розв’язання] ігор із поліноміальним часом: на кожному полі бою вони знають, як перемагати. Але найважче знати, коли програти, а не як виграти в кожній із складових ігор. Якщо хтось може грати в таку важку гру, він дійсно найкращий стратег. Польові генерали не приймають таких глибоких логічних рішень, але чомусь, якщо їх гарно поєднати, вони не гірші за цього ідеального стратега.

Я сказав своєму татові: «Нарешті я зрозумів цю математичну теорему, яка еквівалентна одній із наших відомих ідіом!» На той час йому було 94 роки, він був дуже кмітливим, і він сказав: «Це гарна спроба». Я його не зовсім переконав. Це була моя остання технічна розмова з ним; через кілька місяців він помер. Кожного разу, коли я думаю про те, щоб пояснити свою роботу, це моя родзинка.