211service.com
Pac-Man dimostrato NP-difficile dalla teoria della complessità computazionale
Negli ultimi anni, alcuni matematici dedicati hanno iniziato a studiare la complessità computazionale dei videogiochi. Il loro obiettivo è determinare la difficoltà intrinseca dei giochi e come potrebbero essere correlati tra loro e altri problemi.
Oggi, Giovanni Viglietta all'Università di Pisa in Italia rivela un corpo di lavoro erculeo in questo settore in cui classifica un gran numero di giochi degli anni '80 e '90 tra cui Pac-Man, Doom, Tron e molti altri.
Il lavoro di Viglietta prevede diversi passaggi. Il primo è determinare la classe di complessità computazionale a cui appartiene il gioco. Successivamente, valuta se sapere come risolvere il gioco consente anche di risolvere molti altri problemi della stessa classe, una proprietà che i teorici della complessità chiamano 'durezza'. Infine, determina se il gioco è completo, il che significa che è uno dei 'più difficili' della sua categoria.
Il suo approccio è relativamente semplice. Prima lavora attraverso una serie di prove che mostrano che qualsiasi videogioco con proprietà di gioco specifiche rientra in una certa classe di complessità.
Quindi classifica i giochi in base alle proprietà di gioco che hanno.
Ad esempio, un tipo di gioco prevede che un giocatore si muova attraverso un paesaggio visitando un certo numero di luoghi. Chiama questo 'percorso di posizione' e un esempio potrebbe essere un gioco in cui alcuni oggetti sono sparsi in un paesaggio e l'obiettivo è raccoglierli tutti.
Alcuni giochi di location traversal consentono di visitare ogni luogo una sola volta. I cosiddetti giochi di percorso monouso potrebbero includere gare di discesa.
Quindi usa la teoria dei grafi per dimostrare che qualsiasi gioco che esibisce sia percorsi di attraversamento della posizione che percorsi monouso è NP-difficile, che è la stessa classe di complessità del problema del commesso viaggiatore.
Si scopre che Pac-Man rientra in questa categoria (la prova prevede la distribuzione di pillole energetiche nel labirinto in un modo che impone percorsi monouso).
Mostra come i giochi rientrino anche in altre categorie di complessità. Ad esempio, i giochi che dispongono di cuscinetti a pressione per aprire e chiudere le porte sono difficili da PSPACE se ogni porta è controllata da due piastre a pressione. Doom rientra in questa categoria.
E così via.
L'elenco risultante è impressionante. Ecco alcuni dei suoi risultati:
Boulder Dash (First Star Software, 1984) è NP-hard.
Deflektor (Vortex Software, 1987) è in L.
Prince of Persia (Brøderbund, 1989) è completo per PSPACE.
Tron (Bally Midway, 1982) è NP-duro.
Per l'elenco completo e il ragionamento, vedere il documento di seguito.
È stato chiaramente un atto d'amore per Viglietta, dato il titolo del suo articolo: Il gioco è un duro lavoro, ma qualcuno deve farlo!
È interessante notare che questo tipo di analisi non è necessario per i giochi moderni. I giochi commerciali più recenti incorporano linguaggi di scripting equivalenti a Turing che consentono facilmente la progettazione di enigmi indecidibili come parte del gameplay, afferma.
In un certo senso, questo rende questi vecchi giochi ancora più affascinanti.
Rif: arxiv.org/abs/1201.4995 :Il gioco è un lavoro duro, ma qualcuno deve pur farlo!