Super Mario Bros viste sig at være NP-hård

Tilbage i januar så vi på Giovanni Vigliettas arbejde på University if Pisa i Italien, som havde bevist den beregningsmæssige kompleksitet af mange computerspil fra 80'erne og 90'erne, såsom Pac-Man og Tron.

Viglietta påpegede, at denne form for analyse er unødvendig for moderne spil, fordi de fleste inkorporerer Turing-ækvivalente scriptsprog, der nemt tillader design af uafslutelige gåder som en del af gameplayet.

Det efterlader dog stadig mange klassikere, der endnu er uklassificerede.

I dag fylder Greg Aloupis ved det frie universitet i Bruxelles i Belgien og et par venner det hul, i det mindste delvist.

Disse fyre beviser, at adskillige klassiske Nintendo-spil fra 80'erne alle er NP-hårde. Listen inkluderer de første tre inkarnationer af Super Mario Bros, Donkey Kong og alle Legend of Zelda-spillene.

Alle disse spil er grundlæggende ens, idet de starter på et bestemt tidspunkt med det formål at nå et eller andet mål. Spørgsmålet Aloupis og co stiller er dette: givet udgangspositionen, er det muligt at nå målet?

Hvis det er svært at afgøre selv dette spørgsmål, så er det bestemt svært at finde en optimal vej, siger de.

I denne sammenhæng fortsætter de med at vise, at alle spillene i det væsentlige er versioner af et andet problem kaldet 3-SAT, som er kendt for at være NP-komplet. Processen her er at vise, at 3SAT reducerer til disse problemer under visse omstændigheder, og derved bevise, at de er NP-hårde.

Så hvis din ungdom blev brugt forkert på at spille Super Mario Bros, Donkey Kong eller et af de andre spil, som disse fyre viser sig at være NP-Hårde, så kan det give lidt trøst at vide, hvor hårde de faktisk var, at du ikke spildte din tid helt. Så igen, sandsynligvis ikke!

Ref: arxiv.org/abs/1203.1895 : Klassiske Nintendo-spil er (NP-)Hårde

skjule