Чудові фігурки
Легендарный тетрис был создан в 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.
Скрін гри. Ось так виглядала онлайн-дошка у грі між Хокінгом та Раддом. Тоді актор обіграв легендарного фізика
Мы не знаем, станут ли эти игры в будущем такой же обыденностью, как и обычные крестики-нолики, тетрис и пятнашки, но они точно вдохновят математиков создавать уникальные алгоритмы для решения практических бизнес-задач и развития технологий. В этом не приходится сомневаться.
Читати далі:
Форма Чумацького Шляху зовсім не така, як ми вважали весь цей час, з'ясували вчені
Дві суперземлі знайшли на краю населеної зони: на одній із них комфортна температура
Знайдено чорну дірку, яка знищує зірку рекордно близько до Землі