Итальянец посчитал сложность выигрыша в классические компьютерные игры

Pac-Man

Итальянец Джованни Вильетта из Пизанского университета подсчитал вычислительную сложность известных компьютерных игр. Статья ученого пока не принята к публикации, однако ее препринт доступен на сайте arXiv.org.

В рамках работы Вильетта оценивал сложность вычисления последовательности действий, который приводят к победе в игре. В первой части статьи итальянец приводит серию теорем, которые позволяют связать вычислительную сложность игры с наличием в ней некоторых конкретных элементов. К последним, например, относятся рычаги, которые надо нажать, чтобы открылась некоторая дверь, призы, которые необходимо собирать, и многое другое.

Как оказалось, большая часть игр принадлежит к так называемому классу NP - это задачи, решающиеся за полиномиальное время на недетерминированной машине Тьюринга (то есть машине, программа которой допускает развилки). Также нашлись игры, принадлежащие к классу P (полиномиальное время на детерминированной машине Тьюринга), L (задачи, решаемые с привлечением логарифмически зависящего от начальных данных количества памяти детерминированной машиной Тьюринга), NL (то же, что и L, только машина недетрминированная) и PSPACE.

Кроме этого, несколько задач оказались NP-полными и PSPACE-полными. По сути это самые сложные задачи в своих классах - к ним за полиномиальное время можно свести любую задачу из данного класса. Например, к NP-полным задачам относится задача коммивояжера - поиск замкнутого кратчайшего пути в графе, который проходит по каждой вершине хотя бы один раз.

Полный список результатов выглядит следующим образом:

  1. Boulder Dash (1984) - сложность NP
  2. Deflektor (1987) - сложность L
  3. Doom (1993) - сложность PSPACE
  4. Lemmings (1991) - сложность NP
  5. Lode Runner (1983) - сложность NP
  6. Mindbender (1989) - сложность NL
  7. Pac-Man (1980) - сложность NP
  8. Pipe Mania (1989) - NP-полная игра
  9. Prince of Persia (1989) - PSPACE-полная игра
  10. Puzzle Bobble 3 (1996) - NP-полная игра
  11. Skweek (1989) - NP-полная игра
  12. Starcraft (1998) - сложность NP
  13. Tron (1982) - сложность NP

Вильетта также заявил, что аналогичный анализ для современных игр смысла не имеет, так как в них могут встречаться неразрешимые головоломки.

Обсудить
Наука и техника00:0630 ноября
Красноармейцы в финском плену. Лагерь в области Париккала

«Красноармейцы — голодные и нищие колхозники»

Сталин обрек тысячи солдат на мучительную смерть и подарил Финляндию Гитлеру
Они ушли
Русские покидают Сирию. Там остаются тысячи террористов, а войне не видно конца
«Этим проклятым американцам мы еще покажем!»
Афганцы полюбили русских и возненавидели США
Кровавый конвейер
На Гаити круглый год режут и свежуют скот
Реджеп Тайип ЭрдоганВ спину не больно
Россия забыла обиды и взахлеб дружит с Турцией
Дональд ТрампСвоих не бросаем
План Трампа: спасти богатых и сэкономить на бедных
Домашние заготовки
Почему российской строительной сфере не обойтись без отечественных алюминиевых панелей
Выплюнь бяку
Личинки, тараканы и ДНК человека — на что можно нарваться в батоне колбасы
«Меня не убили, просто развели»
Россиянка влюбилась по уши и лишилась жилья
Что-то встало за окном
Строения, вызывающие самые пошлые ассоциации
С собой не увезешь
Как живут российские олигархи за границей
Его ворсейшество
Бессмертные ковры возвращаются на стены российских квартир