Насколько сложной может быть простая игра? «Тетрис» доходит до предела возможностей суперкомпьютеров и удивляет математиков

Будучи ребёнком 1990-х годов, я не мог обойти стороной игру-бестселлер «Тетрис». Созданный в 1984 году российским программистом Алексеем Пажитновым, «Тетрис» быстро стал блокбастером, и за прошедшие годы в него сыграли сотни миллионов человек. Я сам часами играл в него на Game Boy, пытаясь расположить падающие фигуры так, чтобы они как можно плотнее заполняли игровое поле. Со временем игры эти блоки начинают падать все быстрее и быстрее, и мои большие пальцы едва успевали за управлением игрой.

В принципе, все игры — даже такие разные, как Candy Crush Saga, Magic: The Gathering и Wordle, — можно изучать с точки зрения математики. Но «Тетрис» имеет много особых связей с математикой. Например, цель игры сильно напоминает геометрические задачи о паркете, в которых вы определяете, можно ли покрыть область бесконечно большим набором плиток без зазоров.

Но особенно интригует математиков сложность «Тетриса». В частности, исследователи задавались вопросом о вычислительной мощности, необходимой для того, чтобы определить, возможно ли в принципе «решить» «Тетрис» (и как это сделать), с такими начальными условиями, как конечное число фигур и способность знать порядок их появления. Оказалось, что именно такая постановка вопроса ставит «Тетрис» в ряд самых сложных с математической точки зрения игр.

Определяя сложность

Изучая теорию сложности, математики и информатики стремятся охарактеризовать сложность решения задач. Они определили несколько классов сложности, или категорий, включая P- и NP-задачи. Условно говоря, P-задачи легко решаются обычными компьютерами, в то время как NP-задачи более сложны, но в случае, если у вас есть возможное решение, его правильность легко проверить. (NP-задачи можно представить себе как головоломку судоку: на заполнение полей могут уйти часы, но на проверку правильности решения уйдёт всего несколько минут).

Чтобы определить сложность задачи, нужно сравнить разные задачи друг с другом. Если каждый алгоритм, решающий задачу A, может решить и задачу B, то A сложнее B. Или, как говорят математики: B «сводится» к A. Это значит, что, сравнив «Тетрис» с другой известной P- или NP-задачей, можно определить сложность игры.

Как же выбрать хороший способ сравнения? Компьютерные учёные могут обратиться к так называемым NP-полным задачам, к которым можно свести все остальные NP-задачи. Одна из них – проблема 3-разбиения.

Проблема 3-разбиения посвящена вопросу о том, можно ли разделить заданное множество целых чисел, например {1, 2, 5, 6, 7, 9}, на подмножества с тремя элементами в каждом так, чтобы сумма чисел в подмножествах была одинаковой. Для {1, 2, 5, 6, 7, 9} таким разделением будет {1, 5, 9} и {2, 6, 7}. Сумма содержимого каждого подмножества равна 15. Такое деление возможно не для каждого заданного множества. Выяснить, существует оно или нет, оказывается чрезвычайно сложно: проблема 3-разбиения NP-полна.

В 2003 году информатики из Массачусетского технологического института продемонстрировали, что вопрос о том, можно ли очистить поле «Тетриса» в данной игровой ситуации, сам по себе можно свести к задаче 3-разделения. Для этого исследователи приравняли пробелы в игре «Тетрис» к подмножествам задачи, а падающие фигуры — к множествам чисел, которые нужно разделить.

Таким образом, учёные показали, что если множество чисел можно разделить на трехэлементные подмножества с одинаковой суммой, то и игровое поле «Тетриса» можно полностью опустошить. Тем самым они доказали, что вопросы «Можно ли разделить множество на тройки?» и «Можно ли опустошить игровое поле „Тетриса“?» идентичны с математической точки зрения.

Этот вывод означает, что головоломка о том, можно ли правильно расположить заданные фигуры, относится к категории NP-полных задач, что делает «Тетрис» очень сложной игрой. Чем длиннее последовательность фигур, которую содержит игра, тем больше времени требуется компьютеру, чтобы определить её разрешимость. И действительно, обычные компьютеры будут перегружены очень быстро: не существует алгоритма, способного эффективно решить эту задачу.

«Тетрис» достигает пределов вычислимости

Тетрис обладает ещё более сложными свойствами, как показали в своей работе 2004 года информатики Хендрик Ян Хугебум и Вальтер Костерс из Лейденского университета в Нидерландах. Они рассмотрели несколько иной вопрос. Предположим, что вы наблюдаете за игрой в «Тетрис», в которой есть только «палка» – длинная фигура в форме буквы I. Если бы я дал вам заранее определённое количество способов падения, скажем, 40 палок на изначально пустом поле «Тетриса», смогли бы вы определить, есть ли среди этих восьми способов такой, при котором доска окажется пустой?

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

Конечно, эти вопросы, скорее всего, никак не повлияют на ваш успех в «Тетрисе». При той скорости, с которой падают фигуры, времени на обдумывание математических задач практически не остаётся.

Тем не менее, примечательно, что спустя более 40 лет «Тетрис» продолжает расти и развиваться, несмотря на то, что игра остаётся практически неизменной. Например, техника игры, известная как «роллинг» (позволяющая управлять игрой очень быстро на приставке NES), позволила продвинуться дальше, чем когда-либо прежде. В прошлом 29-й уровень считался непреодолимым пределом. Но в 2023 году 13-летний подросток побил все предыдущие рекорды, пройдя до 157-го уровня, из-за чего игра даже упала. Остаётся только ждать и смотреть, какие сюрпризы приготовит «Тетрис» в будущем.