Одну из самых культовых игр в истории написал советский программист Алексей Пажитнов на «Электронике-60» в 1984 году.
Наверное, каждый из нас думал, что при должной сноровке партия «Тетриса» может длиться бесконечно. Но математика утверждает обратное:
🟢В основе игры — семь геометрических фигур из четырёх квадратов, тетрамино (от «тетро» — четыре, по аналогии с домино): I, O, T, L, J, S и Z. Игроку нужно вращать и складывать их так, чтобы заполнить горизонтальную линию.
🟢 Причина проигрышей — в самих фигурах. Самые коварные — S и Z: они создают наклоны и пустоты, которые почти невозможно закрыть.
🟢Ещё один важный нюанс: поле в классическом «Тетрисе» имеет ширину 10 клеток. Но если взять все семь фигур и сложить их без единого пробела, получится прямоугольник шириной в 8 клеток. То есть поле устроено так, что возникают промежутки, которые уже нельзя закрыть.
«Непобедимость» игры подтверждают и теоретические результаты
Сам вопрос — можно ли, имея фиксированный порядок фигур и стартовое поле, полностью очистить его в конце игры, — сводится к классической NP-полной задаче 3-разбиения. Алгоритм, который всегда играл бы идеально, потребовал бы ресурсов, растущих экспоненциально.
В терминах теории сложности это одна из тех задач, которые слишком трудны для эффективного решения даже компьютером. Вот доказательства:
🤒 статья исследователей из MIT 2002 года, где показано, что решение требует экспоненциального времени и универсальной «выигрышной» стратегии не существует
🤒 брошюра учёных из Лейденского университета: они доказали, что даже если оставить только «палку» — самую удобную фигуру, — при определённых условиях задача всё равно может стать неразрешимой
🤒 видео о школьнике из США, который в 2023 году «прошёл» игру до конца. Он продержался 38 минут, набрал максимальные 999 999 очков и дошёл до 157 уровня — раньше это удавалось только ИИ. Дальше игра зависла из-за ограничений кода
Мораль: на практике у любой идеи есть технический предел. В «Тетрис» невозможно выиграть, но можно бесконечно пытаться.
✅Делитесь своими рекордами в комментариях! И ставьте реакции, если интересно прочитать разбор ещё одной культовой игры. Есть догадки, о чём мы хотим рассказать?
#как_устроено