Информационный портал
 ПОЛИТИКА И ОБЩЕСТВО
 ЭКОНОМИКА

    ВСЕ НОВОСТИ    |    ПОЛИТИКА И ОБЩЕСТВО    |    ЭКОНОМИКА    |    HI-TECH    |    E-BUSINESS    |    ПРОИСШЕСТВИЯ    |    НОВОСИБИРСК    |    ШОУ-БИЗНЕС
Новости / Компьютерные игры / Высчитана сложность выигрыша в компьютерные игры
 

Высчитана сложность выигрыша в компьютерные игры
Кадр из игры Pac-Man

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

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

Как оказалось, большая часть игр принадлежит к так называемому классу 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

Дата: 31.01.2012, 14:30, Источник: info.sibnet.ru, Просмотров: 726

Схожие новости по теме:

Высчитано максимально допустимое количество землян
Высчитана дата транспортного коллапса в Москве






РЕСУРСЫ РАЗДЕЛА

2024, SWEET211.RU | Сделано с любовью
Автор: Maksim Semeykin

Дизайн: Master Daemon
Web Builder Engine v.2.78c, 2004-2024

Страница создана за 0,0156 секунд
Версия сайта 3.4.4
Версия админовки 1.6.2f
SQL запросов: 5 Время: 0,015625 сек.

Сейчас: 19.03.2024, 9:17
Участник рейтинга sweet211.ru

синонимайзер текста онлайн Прошивка магнитолы Geely Atlas Прошивка магнитолы Geely Coolray Прошивка магнитолы Geely Atlas Pro Прошивка магнитолы Geely Tugella