211service.com
Pac-Man beviste NP-hård ved beregningsmæssig kompleksitetsteori
I de sidste par år er nogle få dedikerede matematikere begyndt at studere computerspils beregningsmæssige kompleksitet. Deres mål er at bestemme den iboende sværhedsgrad af spillene, og hvordan de kan være relateret til hinanden og andre problemer.
I dag afslører Giovanni Viglietta ved University if Pisa i Italien en samling af herkulisk arbejde på dette område, hvor han klassificerer et stort antal spil fra 1980'erne og 90'erne, herunder Pac-Man, Doom, Tron og mange andre.
Vigliettas arbejde involverer flere trin. Den første er at bestemme den klasse af beregningsmæssig kompleksitet, som spillet tilhører. Dernæst finder han ud af, om det at vide, hvordan man løser spillet også giver dig mulighed for at løse mange andre problemer i samme klasse, en egenskab, som kompleksitetsteoretikere kalder 'hårdhed'. Til sidst afgør han, om spillet er komplet, hvilket betyder, at det er et af de 'sværeste' i sin klasse.
Hans tilgang er forholdsvis ligetil. Han gennemgår først en række beviser, der viser, at ethvert videospil med specifikke spilegenskaber falder ind under en vis kompleksitetsklasse.
Derefter klassificerer han spillene efter spilegenskaber, de har.
For eksempel involverer en type spil en spiller, der bevæger sig gennem et landskab, og besøger en række steder. Han kalder dette 'placeringsgennemgang', og et eksempel ville være et spil, hvor visse genstande er strøet rundt i et landskab, og målet er at samle dem alle.
Nogle lokationsgennemløbsspil tillader, at hver lokation kun kan besøges én gang. Såkaldte single use path-spil kan omfatte downhill-løb.
Han bruger derefter grafteori til at bevise, at ethvert spil, der udviser både stedgennemgang og engangsstier, er NP-hårdt, det er samme kompleksitetsklasse som problemet med rejsende sælger.
Det viser sig, at Pac-Man falder ind under denne kategori (beviset involverer at distribuere kraftpiller rundt i labyrinten på en måde, der gennemtvinger engangsveje).
Han viser, hvordan spil også falder ind under andre kompleksitetskategorier. For eksempel er spil, der har trykpuder til at åbne og lukke døre, PSPACE-hårde, hvis hver dør styres af to trykplader. Doom falder ind under denne kategori.
Og så videre.
Den resulterende liste er imponerende. Her er et par af hans resultater:
Boulder Dash (First Star Software, 1984) er NP-hård.
Deflektor (Vortex Software, 1987) er i L.
Prince of Persia (Brøderbund, 1989) er PSPACE-komplet.
Tron (Bally Midway, 1982) er NP-hård.
For den fulde liste og begrundelse, se papiret nedenfor.
Det har tydeligvis været et kærlighedsarbejde for Viglietta, givet titlen på hans papir: Gaming er et hårdt job, men nogen skal gøre det!
Interessant nok siger han, at denne form for analyse er unødvendig for moderne spil. De seneste kommercielle spil inkorporerer Turing-ækvivalente scriptsprog, der nemt tillader design af uafgørlige gåder som en del af gameplayet, siger han.
På en måde gør det disse ældre spil endnu mere charmerende.
Ref: arxiv.org/abs/1201.4995 :Gaming er et hårdt arbejde, men nogen skal gøre det!