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

Итальянец Джованни Вильетта из Пизанского университета подсчитал вычислительную сложность известных компьютерных игр Игры одевалки http://www.odevalkina.ru/ Статья ученого пока не принята к публикации.

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

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

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

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

Boulder Dash (1984) – сложность NP
Deflektor (1987) – сложность L
Doom (1993) – сложность PSPACE
Lemmings (1991) – сложность NP
Lode Runner (1983) – сложность NP
Mindbender (1989) – сложность NL
Pac-Man (1980) – сложность NP
Pipe Mania (1989) – NP-полная игра
Prince of Persia (1989) – PSPACE-полная игра
Puzzle Bobble 3 (1996) – NP-полная игра
Skweek (1989) – NP-полная игра
Starcraft (1998) – сложность NP
Tron (1982) – сложность NP

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

Итальянец посчитал сложность выигрыша в игры одевалки Итальянец посчитал сложность выигрыша в игры одевалки Reviewed by ollbiz.com on января 31, 2012 Rating: 5
Технологии Blogger.