- PVSM.RU - https://www.pvsm.ru -
Математический анализ [1] сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Проще говоря, это математически очень сложные задачи, сравнимые с задачей коммивояжёра или проблемой раскраски графа.
Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Кроме того, отдельные игры других серий принадлежат к классу NP, а некоторые игры из серии Zelda — к классу PSPACE.
Конечно, коммерческие версии игры Mario специально были спроектированы так, чтобы уровни можно было пройти, но в рамках данного исследования учёные изменили уровни, чтобы свести игру к логической задаче о выполнимости булевых формул и проверить, можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула стала истинной. В качестве переменных в этой формуле выступают противники и бонусы на игровом поле. Если они позволяют пройти уровень до конца, значит, формула истинна. Если уровень пройти невозможно, значит, существует противоречие.
С точки зрения разработчика NP-полные игры представляют сложность, потому что изначально нет лёгкого способа проверить, существует ли возможность пройти игру до конца. С другой стороны, такие игры будут очень интересными для игроков, пишет New Scientist [2].
Автор: alizar
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/3587
Ссылки в тексте:
[1] Математический анализ: http://arxiv.org/abs/1203.1895
[2] пишет New Scientist: http://www.newscientist.com/article/mg21328565.100-mario-is-hard-and-thats-mathematically-official.html
Нажмите здесь для печати.