Разбираемся в сложных вещах и рассказываем, как тетрис, пятнашки и другие компьютерные игры помогают математикам создавать новые алгоритмы для решения бизнес-задач.
Чудные фигурки
Легендарный тетрис был создан в 80-х годах прошлого века Алексеем Пажитновым. Математик работал в вычислительном центре Академии наук СССР: изучал ИИ, распознавание компьютером человеческой речи и одновременно увлекался головоломками. Идея тетриса родилась благодаря настольной игре «Пентамино» — Пажитнов решил создать версию настолки для ЭВМ, но остановился на другом варианте, где элементы были сложены из четырёх квадратов (вместо пяти, как в «Пентамино»).
Одну из первых версий игры Пажитнов выпустил на советском микрокомпьютере «Электроника-60»
Цель тетриса — перемещать и вращать падающие геометрические фигуры, чтобы сформировать полные ряды внизу игрового поля, набирая очки. С практической точки зрения — это игра на быстроту реакции и концентрацию внимания, а математики на это смотрят под другим углом. Ученые проанализировали вычислительную сложность алгоритма тетриса и определили, что она относится к классу NP-полных — non-deterministic polynomial; для таких нет эффективных алгоритмов решения.
Ключевая проблема в том, что объем необходимых для поиска решения вычислений экспоненциально растет с увеличением количества переменных (размера задачи). Например, если параметров четыре, то нужно 16 итераций, а если 100, — то 2^100, это больше, чем атомов во Вселенной (!). Обычный компьютер при грамотной настройке может делать несколько миллиардов таких итераций в секунду. Соответственно, маленькие NP-задачи он легко решит перебором, а когда переменных станет заметно больше 15, перестанет решать.
Что касается тетриса. Размер задачи у классической игры небольшой: на отдельном шаге есть текущий ландшафт в стакане (игровом поле) — это параметр, он на объем вычислений значимо не влияет. Есть информация о текущей и следующей фигуре — это две группы переменных: для каждой фигуры есть максимум четыре (хотя для квадрата — всего одна) ориентации в пространстве и максимум 10 координат «посадки» фигур. У каждого хода — 40 состояний, у двух — 1 600, больше информации нет, это маленькая NP-задача. Хотя и тетрис можно усложнить: увеличить количество клеток до 100 и сделать так, чтобы игрок знал не только, какая будет следующая фигура, но и сотня последующих, то появились бы проблемы.
Другие NP-полные игры вы тоже знаете не понаслышке: сапер, судоку, пятнашки и даже некоммерческая версия «Супер Марио». Несмотря на простоту их правил, при определенных условиях их размерность растет, компьютер не может предложить идеальное решение. Почему математиков это волнует? Потому что выбрать наилучший маршрут, оптимизировать процесс или расписание — тоже задачи класса NP.
Классический «Марио» выглядел так
Логические игры — крайне удобный полигон для тестирования алгоритмов и их программного воплощения. Головоломки чаще всего «чистые», без разного рода исключений из правил, которые присущи практическим задачам. Пространство состояний таких задач имеет регулируемую размерность, причем при масштабировании свойства не меняются (например, пятнашки 2×2, 4×4, 3×6). Все состояния при этом описываются одинаково. Математическое описание головоломок, как правило, тоже не такое сложное, как у жизненных проблем.
Время «квантовых» игрушек
Та же задача о рюкзаке (как уместить больше вещей в ограниченное пространство) вполне напоминает игру в тетрис, а эффективный результат будет полезен логистическим компаниям, потому что позволит не тратить ресурсы впустую. Если для какой-то из этих задач или игр будет найден «полиномиально быстрый» алгоритм, то и любая другая проблема из класса NP сможет быть решена так же «быстро». В теории в этом помогут квантовые компьютеры, но пока существуют лишь прототипы этих вычислительных машин будущего. В 2018 году для описания текущего состояния производства квантовых процессоров даже придумали новое понятие — эра NISQ (noisy intermediate-scale quantum era), или время недоквантовых технологий.
Пока ученые трудятся над улучшением квантовых процессов, руководители компаний ищут современные аналоги, помогающие оптимизировать работу производства. Таким «заменителем» стали квантово-вдохновленные алгоритмы, которые находят на 95–99% оптимальное решение на обычных компьютерах. В России этим занимается QuSolve — задачи, над которыми работает компания, относятся к классу NP, а математики разрабатывают и совершенствуют алгоритмы для решения бизнес-задач. В QuSolve для теста собственного солвера (решателя) использовали пятнашки, что помогло найти пару ошибок в алгоритме и внести дополнения в интерфейс программного комплекса.
Неужели современные ученые только и делают, что думают над тем, как все усовершенствовать и оптимизировать? Конечно, нет. В свободное от работы время они продолжают придумывать игры. Большинство игр разработчики уже смогли превратить в NP, добавив немного магии квантовых физических явлений.
Так за последние 10 лет появились квантовые шашки, квантовый морской бой и квантовые крестики-нолики. Особую популярность завоевали квантовые шахматы, по которым даже проводятся турниры, а чемпиону присваивается звание гроссмейстера. Большинство новых «квантовых игр» построено на фундаментальном принципе квантовой механики — суперпозиции.
Например, шахматные фигуры могут находиться в нескольких местах доски одновременно, а значит, сложнее защищаться и нападать — это делает партию непредсказуемой и зрелищной. В 2016 году даже сняли короткометражку, в которой показана партия в квантовые шахматы между Стивеном Хокингом и актером Полом Раддом, известным по роли человека-муравья в киновселенной Marvel.
Скрин игры. Вот так выглядела онлайн-доска в игре между Хокингом и Раддом. Тогда актер обыграл легендарного физика
Мы не знаем, станут ли эти игры в будущем такой же обыденностью, как и обычные крестики-нолики, тетрис и пятнашки, но они точно вдохновят математиков создавать уникальные алгоритмы для решения практических бизнес-задач и развития технологий. В этом не приходится сомневаться.
Источник: hightech.fm
