Super Mario Bros ha dimostrato di essere NP-Hard

A gennaio abbiamo esaminato il lavoro di Giovanni Viglietta dell'Università di Pisa, in Italia, che aveva dimostrato la complessità computazionale di molti giochi per computer degli anni '80 e '90, come Pac-Man e Tron.

Viglietta ha sottolineato che questo tipo di analisi non è necessario per i giochi moderni perché la maggior parte incorpora linguaggi di scripting equivalenti a Turing che consentono facilmente la progettazione di enigmi indecidibili come parte del gameplay.

Tuttavia, ciò lascia ancora molti classici che non sono ancora classificati.

Oggi, Greg Aloupis della Libera Università di Bruxelles in Belgio e un paio di amici riempiono quel buco, almeno in parte.

Questi ragazzi dimostrano che diversi giochi Nintendo classici degli anni '80 sono tutti NP-hard. L'elenco include le prime tre incarnazioni di Super Mario Bros, Donkey Kong e tutti i giochi di Legend of Zelda.

Tutti questi giochi sono essenzialmente gli stessi in quanto iniziano in un punto specifico con l'obiettivo di raggiungere un obiettivo. La domanda che Aloupis e co si fanno è questa: data la posizione di partenza, è possibile raggiungere l'obiettivo?

Se è difficile decidere anche su questa domanda, allora è sicuramente difficile trovare un percorso ottimale, dicono.

In questo contesto, continuano a mostrare che tutti i giochi sono essenzialmente versioni di un altro problema chiamato 3-SAT, che è noto per essere NP-completo. Il processo qui è mostrare che 3SAT si riduce a questi problemi in determinate circostanze, dimostrando così che sono NP-difficili.

Quindi, se la tua giovinezza è stata sprecata giocando a Super Mario Bros, Donkey Kong o uno qualsiasi degli altri giochi che questi ragazzi si dimostrano NP-Hard, allora sapere quanto siano stati davvero difficili potrebbe fornire un piccolo conforto sul fatto che non hai perso completamente il tuo tempo. Poi di nuovo, probabilmente no!

Rif: arxiv.org/abs/1203.1895 : I giochi Nintendo classici sono (NP-)difficili

nascondere