Вечеринки, концерты, мероприятия и т.д. при поддержке сайта NN-Files.ru (рекламная информация)
Мини-чат
Главная » 2012 » Январь » 30 » Итальянец посчитал сложность выигрыша в классические компьютерные игры
Итальянец посчитал сложность выигрыша в классические компьютерные игры
30.01.12 22:06
Изображения:
Итальянец Джованни Вильетта из Пизанского университета подсчитал вычислительную сложность известных компьютерных игр. Статья ученого пока не принята к публикации, однако ее препринт доступен на сайте arXiv.org.
В рамках работы Вильетта оценивал сложность вычисления последовательности действий, который приводят к победе в игре. В первой части статьи итальянец приводит серию теорем, которые позволяют связать вычислительную сложность игры с наличием в ней некоторых конкретных элементов. К последним, например, относятся рычаги, которые надо нажать, чтобы открылась некоторая дверь, призы, которые необходимо собирать, и многое другое.
Как оказалось, большая часть игр принадлежит к так называемому классу 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
Вильетта также заявил, что аналогичный анализ для современных игр смысла не имеет, так как в них могут встречаться неразрешимые головоломки.
Ссылка на новость:Прямая ссылка: /news/2012-01-30-11027 BB-код [url=/news/2012-01-30-11027]Итальянец посчитал сложность выигрыша в классические компьютерные игры[/url] HTML-код <a href="/news/2012-01-30-11027" target="_blank">Итальянец посчитал сложность выигрыша в классические компьютерные игры</a> Поделиться
Итальянец посчитал сложность выигрыша в классические компьютерные игры
Парни 1 и 2 я так понимаю вы никогда в такие не играли, поэтому попросил бы.. а я играл. Лемминги весчь! пак-мэн ваще классика, а в Дум в кооперативе по LPT порту на Win 3.1 - это ваще песнь песней царя соломона! и вообще круть компа в те времена определяль - шол ли на нём Дум2
