Max Home IndustryВозможно, вы думали, что такие игры, как Mario, Donkey Kong и другие, были сложными в то время, когда вы в них играли, но вы, вероятно, не догадывались, что они NP-сложны.
NP-сложные задачи в некотором смысле являются теми, которые труднее всего решить с помощью вычислительных средств, потому что время, необходимое для поиска решения, имеет тенденцию настолько быстро увеличиваться с размером проблемы, что выполнять вычисления просто непрактично. .
Теперь у нас есть некоторые результаты компьютерных ученых из Свободного университета Брюсселя и Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (CSAIL), которые содержат в себе NP-трудную проблему во многих классических играх. Это немного похоже на открытие черной дыры в центре каждой галактики. Должен ли какой-либо факт удивлять?
Компьютерные игры часто включают элемент поиска, и многие NP-сложные задачи связаны с поиском пути или некоторого расположения вещей, удовлетворяющих определенному условию. Это то, что добавляют в игры, чтобы добавить логической сложности к физическому умению нажимать кнопки в нужное время. Действительно, нажатие кнопки в нужное время не учитывается в этих доказательствах сложности — это результаты, которые применимы к идеальному игроку с бесконечной скоростью и нулевым временем реакции.
Доказательства основаны на демонстрации того, что проблема определения достижимости целевой точки из начальной точки является NP-сложной. Игры также обобщены тем, что размер доски увеличен.
С этими небольшими изменениями доказывается, что следующие игры NP-трудны:
Марио
Осел Конг
Легенда о Зельде
Metroid
Покемон
Результаты относятся к
Super Mario Bros. 1, 3, Потерянные уровни
Мир Супер Марио
Страна Донки Конга 1.3
Все игры Legend of Zelda, кроме Zelda II: The Adventure of Link
Все игры Metroid
Все ролевые игры про покемонов
Так что все платформеры NP-трудны?
Почти наверняка нет, но все «хорошие» платформеры NP-жесткие — гораздо более интересная проблема.