211service.com
Pac-Man pierādīja NP-Hard ar skaitļošanas sarežģītības teoriju
Dažu pēdējo gadu laikā daži īpaši matemātiķi ir sākuši pētīt videospēļu skaitļošanas sarežģītību. Viņu mērķis ir noteikt spēlēm raksturīgās grūtības un to, kā tās varētu būt saistītas viena ar otru un citām problēmām.
Šodien Džovanni Viglieta no Pizas universitātē Itālijā atklāj virkni Herkules darbu šajā jomā, kurā viņš klasificē lielu skaitu spēļu no 1980. un 90. gadiem, tostarp Pac-Man, Doom, Tron un daudzas citas.
Viglietta darbs ietver vairākus posmus. Pirmais ir noteikt skaitļošanas sarežģītības klasi, kurai spēle pieder. Pēc tam viņš noskaidro, vai spēles risināšanas zināšanas ļauj atrisināt arī daudzas citas problēmas tajā pašā klasē, ko sarežģītības teorētiķi sauc par “cietību”. Visbeidzot, viņš nosaka, vai spēle ir pabeigta, kas nozīmē, ka tā ir viena no “grūtākajām” savā klasē.
Viņa pieeja ir samērā vienkārša. Vispirms viņš izstrādā vairākus pierādījumus, kas parāda, ka jebkura videospēle ar īpašām spēles īpašībām ietilpst noteiktā sarežģītības klasē.
Pēc tam viņš klasificē spēles pēc to spēlēšanas īpašībām.
Piemēram, viena veida spēle ietver spēlētāju, kas pārvietojas pa ainavu un apmeklē vairākas vietas. Viņš to sauc par “atrašanās vietas apceļošanu”, un piemērs varētu būt spēle, kurā noteikti priekšmeti tiek izmētāti ap ainavu, un mērķis ir tos visus savākt.
Dažas atrašanās vietas apceļošanas spēles ļauj katru vietu apmeklēt tikai vienu reizi. Tā sauktās vienreizējās lietošanas ceļu spēles var ietvert sacensības no kalna.
Pēc tam viņš izmanto grafu teoriju, lai pierādītu, ka jebkura spēle, kurā ir gan atrašanās vietas šķērsošana, gan vienreizējas lietošanas ceļi, ir NP grūti, tā ir tāda pati sarežģītības pakāpe kā ceļojošā pārdevēja problēma.
Izrādās, ka Pac-Man ietilpst šajā kategorijā (pierādījums ietver spēka tablešu izplatīšanu pa labirintu tādā veidā, kas nodrošina vienreizējas lietošanas ceļus).
Viņš parāda, kā spēles ietilpst arī citās sarežģītības kategorijās. Piemēram, spēles ar spiediena spilventiņiem durvju atvēršanai un aizvēršanai ir PSPACE cietas, ja katras durvis kontrolē divas spiediena plāksnes. Doom ietilpst šajā kategorijā.
Un tā tālāk.
Iegūtais saraksts ir iespaidīgs. Šeit ir daži no viņa rezultātiem:
Boulder Dash (First Star Software, 1984) ir NP-hard.
Deflektor (Vortex Software, 1987) atrodas L.
Persijas princis (Brøderbund, 1989) ir pilnīgs PSPACE.
Tron (Bally Midway, 1982) ir NP-hard.
Pilnu sarakstu un pamatojumu skatiet tālāk esošajā dokumentā.
Tas nepārprotami ir bijis mīlestības darbs pret Viglietu, ņemot vērā viņa raksta nosaukumu: Spēle ir grūts darbs, bet kādam tas ir jādara!
Interesanti, ka viņš saka, ka šāda veida analīze mūsdienu spēlēm nav nepieciešama. Viņš saka, ka lielākajā daļā jaunāko komerciālo spēļu ir iekļautas Tjūringa līdzvērtīgas skriptu valodas, kas ļauj viegli izstrādāt neizšķiramas mīklas kā daļu no spēles.
Savā ziņā tas padara šīs vecās spēles vēl burvīgākas.
Atsauce: arxiv.org/abs/1201.4995 :Spēles ir smags darbs, bet kādam tas ir jādara!