Тетрис и Вселената: как една игра отразява границите на реалността

Някои комбинации в играта са не просто сложни – те не подлежат на изчисление.

Класическата игра „Тетрис“, създадена през 1984 г. от московския програмист Алексей Пажитнов, в продължение на десетилетия се превърна не само в световно разпознаваем културен символ, но и в обект на сериозни научни анализи. Зад външната простота – трябва да поставяте падащите фигури така, че запълнените редове да изчезнат – се крие сложна математическа основа. Именно контрастът между елементарната форма и вътрешната логическа сложност превърна играта в обект на интерес в различни научни области – от теоретичната информатика до геометрията.

Сходството на механиката на Тетрис с геометричните проблеми на настилката е привлякло особеното внимание на изследователите. В тези задачи се изисква покриване на повърхността с дадени форми без застъпвания и празнини. В игровия процес това се реализира буквално: необходимо е да се подредят елементи в ограничено пространство, така че да не остане нито една празнина. Но за разлика от класическите математически модели, тук добавяме ограничение във времето, елемент на случайност и непрекъснато постъпване на нови елементи – всичко това прави анализа на поведението на системата много по-сложен.

За да се оцени сложността на тези проблеми, се използва теорията за интензивността на изчислителния труд, която класифицира проблемите според количеството ресурси, необходими за решаването им. Основното разделение е между класовете P и NP: в първия случай решението може да се намери за полиномиално време, а във втория – само да се провери. Типичен пример е Судоку: не е лесно да се попълни таблицата, но да се провери решението става сравнително бързо. Подобни главоблъсканици служат за илюстриране на разликите между тези класове.

Сред NP-проблемите има и така наречените NP-пълни – всяка друга задача от този клас може да бъде сведена до тях. Една от тях е „задачата за тройното разделяне“: трябва да определим дали е възможно да се раздели едно множество от числа на групи от три елемента с равен сбор. Например, за множеството {1, 2, 5, 6, 7, 9} има правилно разделяне: {1, 5, 9} и {2, 6, 7}, където всяка тройка дава 15. Такива разделяния обаче не винаги съществуват и установяването на това дали са възможни изисква значителни изчислителни усилия.

През 2003 г. изследователи от Масачузетския технологичен институт показаха, че една от формите на задачата за Тетрис е еквивалентна на задачата за разделяне на тройки. Те разглеждат сценарий, при който е дадена последователност от форми и се изисква да се види дали тя може да се използва за пълно разчистване на игралното поле. Празнотите в структурата били съпоставени с подмножества, а фигурите били съпоставени с елементите, които трябва да бъдат разпределени. Ако е възможно те да бъдат разделени на балансирани групи, то полето е изчистено. Това даде основание проблемът да бъде класифициран като NP-пълен, потвърждавайки изключителната му изчислителна сложност.

С увеличаване на дължината на входната последователност проблемът става все по-малко решим: броят на възможните комбинации нараства експоненциално. Дори съвременните алгоритми не могат да се справят с търсенето на всички варианти за разумно време. Дори най-мощните компютри не са в състояние да анализират всички конфигурации – сложността бързо надхвърля границите на практическата приложимост.

Но и това не е пределът. През 2004 г. Хендрик Ян Хугебум и Валтер Костерс от Лайденския университет предлагат по-различна формулировка: дадени са 40 I-образни фигури и предварително определени позиции върху празно поле. Въпросът е дали има поне един начин да се подредят фигурите така, че да не останат свободни клетки? Неочаквано се оказало, че този въпрос няма универсално алгоритмично решение: дори при безкрайно много време е невъзможно надеждно да се установи съществуването на правилна конфигурация.

Това твърдение е близко по структура до твърденията, описани в теоремите за непълнота на Гьодел. Според тях във всяка достатъчно мощна формална система непременно ще има твърдения, които не могат да бъдат нито доказани, нито опровергани. За Тетрис това означава, че някои положения не подлежат на изчерпателен анализ – те са фундаментално неразрешими в рамките на изчислителната логика.

Цялата тази теоретична сложност почти не засяга обикновената игра. Фигурите падат твърде бързо, за да се мисли за теоретични основи, и играчът трябва да действа интуитивно. Но именно в това е уникалността на Тетрис: зад външната му простота се крие многопластова логическа структура, която представлява интерес не само за играчите, но и за специалистите по алгоритми и формални системи.

Четиридесет години след създаването си играта не само не е загубила своята актуалност, но и продължава да се развива. Например техниката „rolling“, при която играчът извършва свръхбързи натискания, позволи на играта да преодолее предишните ограничения. Докато преди 29-то ниво се считаше за максимално, през 2023 г. 13-годишен играч достигна 157-мо ниво, което доведе до срив на системата. Този резултат показа колко дълбоко можете да овладеете механиката на играта, без да имате представа за скритата ѝ математика.

Какво ще донесе Тетрис в бъдеще, все още не е известно. Но вече е очевидно: зад падащите фигури не се крие само забавление. Тази игра проверява не само реакцията, но и основите на логическото мислене, превръщайки се в уникален мост между интуицията и теорията на изчисленията.