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

Что касается Шан-Хуа Тэн, теоретическая информатика никогда не была чисто теоретической. Сейчас 58-летний Тенг является профессором компьютерных наук в Университете Южной Калифорнии и двукратным лауреатом премии Гёделя — ежегодной премии, присуждаемой за новаторские теоретические работы. Но он часто пытается связать эту абстрактную теорию с повседневной жизнью как практически, так и в игровой форме.

Родившийся в Пекине накануне китайской культурной революции, Тэн приехал в Соединенные Штаты, чтобы поступить в аспирантуру, планируя изучать компьютерную архитектуру, но вскоре он изменил направление, чтобы сосредоточиться на более абстрактной математической теории. Он получил докторскую степень в Университете Карнеги-Меллона в 1991 году за доказательство теоремы о том, как лучше всего разбивать графы — сети точек или узлов, соединенных линиями или ребрами.

Хотя эта работа была теоретической, она имела практическое применение — и часто, как он обнаружил, практическое применение приводило к новым теоретическим открытиям. Во время летней стажировки НАСА в 1993 году Тенг присоединился к группе, занимающейся моделированием гидродинамики с использованием методов «конечных элементов», которые моделируют сложные структуры как сборки множества крошечных частей. Эти сборки можно рассматривать как графы, и задача Тэна состояла в том, чтобы адаптировать метод разбиения из своего дипломного исследования к этим новым условиям. Но ему стало интересно узнать о методе разбиения, который команда НАСА использовала ранее, и он вместе с коллегой-компьютерщиком начал исследовать лежащую в его основе математическую структуру. Дэниел Спилман, ныне профессор информатики Йельского университета. Этот совместный исследовательский проект положил начало многолетнему сотрудничеству, которое принесло им две премии Гёделя.

Это был не единственный раз, когда он увидел глубокую связь между теорией и практикой. «Каждый раз за этими, казалось бы, совершенно практичными вещами стояла красивая математика», — сказал Тэн.

Совсем недавно Тен обратил внимание на красивую математику, стоящую за такими играми, как крестики-нолики, шахматы и го. В таких «комбинаторных» играх нет элемента случайности, и оба игрока всегда знают все о состоянии доски. Тем не менее, комбинаторные игры остаются сложными, потому что количество вариантов игры может быть головокружительно большим.

Исследователи теории игр любят обобщать такие игры на все более крупные доски — масштабируя крестики-нолики с квадратов 3 на 3 до n-На-n, например, — и количественно оценить сложность определения того, какой игрок выиграет при некотором начальном состоянии доски. Различные возможные ответы сортируют игры на одинаковые «классы сложности», которые возникают в теоретической информатике.

Один известный класс сложности носит прозаическое название P, что означает «полиномиальное время», и содержит задачи, которые можно решить, грубо говоря, за разумное время. Задачи из не менее известного класса NP могут потребовать неоправданно много времени для решения, но их решения легко проверить. Для задач другого класса сложности, называемых PSPACE, даже такая эффективная проверка не гарантируется. Когда исследователи рассматривают «глубокую логику» игр для двух игроков — «если вы сделаете X, затем, если я сделаю Y, а затем, если вы сделаете Z» и т. д., — они часто говорят о PSPACE. Но, как помог доказать Тэн, математика комбинаторных игр не всегда проста.

Quanta недавно разговаривал с Тэном, чтобы обсудить его путь к информатике, математику, лежащую в основе настольных игр, и влияние его отца. Интервью было сокращено и отредактировано для ясности.

Каково было получать образование в Китае?

Я родился незадолго до Культурной революции, и мой отец был заведующим кафедрой гражданского строительства в университете. Когда случилась революция, он был в плену на территории кампуса. Затем весь кампус был отправлен вглубь сельской местности.

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

Как вы выбрали информатику?

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

Образование в то время было очень простым. Мы не были знакомы с большинством вещей, а информатика даже не была кафедрой; это была специальность электротехника. Но по совершенно случайному стечению обстоятельств нас как студентов-математиков обучили математическому анализу, и я узнал несколько вещей, которые в конечном итоге пригодились для того, чтобы стать теоретиком. Без этого у меня, вероятно, не было бы шансов пройти. В наши дни дети гораздо более талантливы: начиная со средней школы они более одаренные математики, чем я был, когда приехал в эту страну.

Как эти пробелы в ваших знаниях повлияли на ваш опыт учебы в аспирантуре?

Однажды [мой советник Гэри Миллер] обнаружил, что я никогда не слышал о NP. Это было в обсуждении. Он сказал: «Эта задача выглядит NP-сложной». Я сказал: «Угу». Он сказал: «Ты мне не веришь?» А потом начал доказывать, а на полпути резко повернулся ко мне, потому что я как раз сидел, и сказал: «Ты знаешь, что такое NP-hard?» Я сказал нет.

Я думал, что это был последний день моей работы с ним, но он продолжил и рассказал мне определение. Он сказал: «Если вы не знаете, это не имеет значения, пока вы способны думать». Он оказал на меня огромное влияние.

Вы прежде всего теоретик, но на протяжении всей своей карьеры вы делали набеги на промышленность. Как эта практическая работа связана с вашими теоретическими исследованиями?

В своей диссертации я разработал некоторые геометрические методы разбиения графов. Мне удалось показать, что это семейство геометрических методов дает доказуемо хорошие разрезы для конечно-элементных графов.

По рекомендации наставника я стал выступать с докладами в NASA и Boeing Aerospace. Я помню, в Boeing 3D-модель одного из крыльев уже содержала около миллиона элементов — они даже не могли загрузить это в одну машину. Поэтому они хотели разрезать этот граф на разные компоненты, поместить их на разные машины с одинаковыми вычислительными нагрузками и свести к минимуму связь. Вот почему математически формула представляет собой разрез графика.

В теоретической информатике часто лежащие в основе математические принципы остаются неизменными, даже когда внешний вид проблемы резко меняется, от оптимизации до теории игр. Когда вы проводите исследование, это не кажется радикальным изменением.

Говоря о теории игр, я видел, что вы помогли разработать настольную игру. Как это произошло?

О, я люблю настольные игры! Есть прекрасные связи с теорией сложности. Но в основном я ученик своих учеников.

Я выступал в Бостонском университете с докладом о прекрасной дискретной теореме, называемой леммой Шпернера. Это очень просто в одном измерении. У вас есть отрезок, один конец которого красный, а другой — синий. Вы делите его на подсегменты [с узлами на обоих концах] и окрашиваете каждый новый узел в красный или синий цвет. Тогда [независимо от того, как вы их раскрасите] мы знаем, что должен быть сегмент, который имеет оба цвета.

В двух измерениях это очень увлекательно. У вас есть треугольник, и теперь у вас есть три цвета: один угол красный, один синий и один зеленый. Вы делите этот треугольник на меньшие треугольники, поэтому ребра разбиты на сегменты. Каждое внешнее ребро следует одномерному правилу: узлы могут использовать только цвета двух концов. Внутри треугольника вы можете сделать все три цвета как угодно. Лемма Шпернера говорит, что каким бы способом вы ни делили его, если вы делаете эту раскраску, должен быть треугольник, который имеет все три цвета.

Кайл Бёрк был моим студентом, работавшим в то время над числовым анализом. Он пришел ко мне в офис и сказал, что может быть красивая настольная игра по лемме Шпернера: два игрока итеративно раскрашивают доску, и тот, кто выведет трехцветный треугольник, проиграет. В лучших настольных играх есть победители, а не ничья, и здесь явно кто-то выиграет. Почему? Потому что лемма Шпернера!

Я позвонил своему другу Дэвиду Эппштейну из Ирвина, чтобы поговорить о том, что делает настольную игру хорошей. Он сказал: «Хорошая игра имеет простые правила и красивую доску, и она должна быть сложной для PSPACE». Потому что, если вы сможете решить ее за полиномиальное время, компьютер все время будет вас побеждать.

Итак, мы прошлись по этим критериям. Кайл спросил: «Эта игра простая?» Я сказал: «Да, это одно предложение!» Он сказал: «Эта игра красочная?» Я сказал: «По замыслу!» Затем он сказал: «Если я докажу, что это сложно для PSPACE, смогу ли я получить докторскую степень?» Я сказал да, и он сделал. Есть много различных аспектов его теоремы. Он раскрывает некоторые вещи, связанные с фиксированными точками, которые представляют собой очень красивое понятие в математике.

Могу ли я играть в игру где угодно?

Он доступен, с некоторыми настройками, онлайн.

В какие игры ты любишь играть?

Я теоретик игр. [Смеется.] Я немного играю со своей дочерью, но я не вырос, играя с ними. В отличие от моих учеников, которые всю жизнь играли в игры.

Какую еще работу вы проделали по математике настольных игр?

У нас был бумаги недавно об открытом вопросе: если вы соедините две игры, решаемые за полиномиальное время, бок о бок, сделает ли это их PSPACE-сложными? На каждом ходу вы можете сыграть только одну из них. Это называется суммированием игр.

Что значит совместить две игры?

В древней игре Го, когда вы кладете достаточное количество камней, вы получаете много отдельных арен, так что в некотором смысле вы играете в сумму игр. Вы должны беспокоиться об этом углу и о том углу. Вы хотите выиграть все, но это не значит, что вы должны выиграть каждую часть.

Философски интересно, правда? Как будто у тебя война, и на ней много сражений, но твое внимание ограничено. В любой момент вы можете принять только одно решение на одном из полей боя, а ваш противник может либо ответить, либо удвоить ставку на каком-то другом поле боя. Я пытался объяснить это отцу. Когда вы играете по сумме игр, это на самом деле означает: как вы проигрываете стратегически?

Мы доказали это для двух игр, но вы можете объединить три игры, и теорема по-прежнему верна: три игры с полиномиальным временем, взятые вместе, могут стать сложными для PSPACE.

Поскольку он подтолкнул вас к компьютерным наукам, как ваш отец отреагировал на другую работу, которую вы выполняли на протяжении многих лет?

Он часто спрашивал меня: «Зачем ты это делаешь?» Работая в теории, часто у тебя годами нет результата, и он понял это постепенно. Раньше я мог говорить о методе конечных элементов — его тоже учат в строительстве. Но я не мог понять, как говорить об этой занимательной математике.

Затем я подумал об идиоме, заимствованной из известного китайского романа под названием Троецарствие. Один из персонажей, Чжугэ Лян, был почти идеальным стратегом, и поговорка гласит: «Три мастера по ремонту обуви лучше, чем Чжугэ Лян». Он используется таким беззаботным способом, чтобы сказать, что три обычных человека могут быть идеальными, если они объединят свои мысли. Но если вы посмотрите на историю этой идиомы, то увидите, что в разных регионах слова произносились по-разному, и слово «обувной ремонтник» звучало так же, как «полевой генерал». Поэтому он говорит: «Три полевых генерала вместе лучше, чем этот идеальный стратег».

Я сказал отцу, что это именно та теорема, которую мы доказали суммированием игр. Полевые генералы представляют [алгоритмы решения] игр с полиномиальным временем: на каждом поле битвы они знают, как победить. Но самое сложное — это знать, когда проигрывать, а не как выиграть в каждой из составных игр. Если кто-то может играть в эту сложную игру, он действительно лучший стратег. Полевые генералы не принимают таких глубоких логических решений, но каким-то образом, если их хорошо сложить, они ничем не хуже этого идеального стратега.

Я сказал отцу: «Наконец-то я понял эту математическую теорему, эквивалентную одной из наших знаменитых идиом!» В то время ему было 94 года, он был очень сообразителен, и он сказал: «Хорошая попытка». Я не совсем убедил его. Это был мой последний технический разговор с ним; через несколько месяцев он прошел. Всякий раз, когда я думаю об объяснении своей работы, это мой основной момент.