Pac-Man okazał się NP-trudny dzięki teorii złożoności obliczeniowej

W ciągu ostatnich kilku lat kilku oddanych matematyków zaczęło badać złożoność obliczeniową gier wideo. Ich celem jest określenie nieodłącznej trudności gier i tego, jak mogą być one powiązane ze sobą i innymi problemami.

Dzisiaj Giovanni Viglietta z Uniwersytetu w Pizie we Włoszech ujawnia zbiór herkulesowych prac w tej dziedzinie, w których klasyfikuje dużą liczbę gier z lat 80. i 90., w tym Pac-Man, Doom, Tron i wiele innych.

Praca Viglietty składa się z kilku etapów. Pierwszym z nich jest określenie klasy złożoności obliczeniowej, do której należy gra. Następnie zastanawia się, czy wiedza o tym, jak rozwiązać grę, pozwala również rozwiązać wiele innych problemów w tej samej klasie, właściwość, którą teoretycy złożoności nazywają „twardością”. Na koniec określa, czy gra jest ukończona, co oznacza, że ​​jest jedną z „najtrudniejszych” w swojej klasie.

Jego podejście jest stosunkowo proste. Najpierw analizuje szereg dowodów pokazujących, że każda gra wideo o określonych właściwościach rozgrywki należy do określonej klasy złożoności.

Następnie klasyfikuje gry zgodnie z ich właściwościami związanymi z rozgrywką.

Na przykład jeden rodzaj gry polega na tym, że gracz porusza się po krajobrazie i odwiedza wiele lokacji. Nazywa to „przemierzaniem lokalizacji”, a przykładem może być gra, w której pewne przedmioty są rozrzucone wokół krajobrazu, a celem jest zebranie ich wszystkich.

Niektóre gry z przechodzeniem lokacji pozwalają na odwiedzenie każdej lokacji tylko raz. Tak zwane gry na ścieżce jednorazowego użytku mogą obejmować wyścigi zjazdowe.

Następnie wykorzystuje teorię grafów, aby udowodnić, że każda gra wykazująca zarówno przemierzanie lokalizacji, jak i ścieżki jednorazowego użytku jest NP-trudna, to ta sama klasa złożoności, co problem komiwojażera.

Okazuje się, że Pac-Man należy do tej kategorii (dowód dotyczy rozprowadzania pigułek mocy po labiryncie w sposób wymuszający ścieżki jednorazowego użytku).

Pokazuje też, jak gry zaliczają się do innych kategorii złożoności. Na przykład gry, w których znajdują się podkładki naciskowe do otwierania i zamykania drzwi, są trudne do PSPACE, jeśli każde drzwi są kontrolowane przez dwie płyty naciskowe. Doom należy do tej kategorii.

I tak dalej.

Otrzymana lista jest imponująca. Oto kilka jego wyników:

Boulder Dash (First Star Software, 1984) jest NP-trudny.

Deflektor (Vortex Software, 1987) jest w języku L.

Prince of Persia (Brøderbund, 1989) jest kompletnym PSPACE.

Tron (Bally Midway, 1982) jest NP-twardy.

Pełną listę i uzasadnienie można znaleźć w artykule poniżej.

To najwyraźniej była praca z miłości do Viglietty, biorąc pod uwagę tytuł jego artykułu: Gra to ciężka praca, ale ktoś musi to zrobić!

Co ciekawe, mówi, że tego rodzaju analiza jest zbędna w nowoczesnych grach. Jak mówi, większość ostatnich gier komercyjnych zawiera języki skryptowe równoważne Turingowi, które z łatwością umożliwiają projektowanie nierozstrzygalnych łamigłówek w ramach rozgrywki.

W pewnym sensie to sprawia, że ​​te starsze gry są jeszcze bardziej urocze.

Nr ref.: arxiv.org/abs/1201.4995 :Granie to ciężka praca, ale ktoś musi to zrobić!

ukryć