Pac-Man visade sig vara NP-hård genom beräkningskomplexitetsteori

Under de senaste åren har några hängivna matematiker börjat studera beräkningskomplexiteten hos videospel. Deras mål är att bestämma spelens inneboende svårighetsgrad och hur de kan vara relaterade till varandra och andra problem.



Idag avslöjar Giovanni Viglietta vid University if Pisa i Italien en mängd herkulesiska verk inom detta område där han klassificerar ett stort antal spel från 1980- och 90-talen inklusive Pac-Man, Doom, Tron och många andra.

Vigliettas arbete omfattar flera steg. Den första är att bestämma vilken klass av beräkningskomplexitet som spelet tillhör. Därefter tar han reda på om att veta hur man löser spelet också gör att du kan lösa många andra problem i samma klass, en egenskap som komplexitetsteoretiker kallar 'hårdhet'. Slutligen avgör han om spelet är komplett, vilket betyder att det är ett av de 'svåraste' i sin klass.





Hans tillvägagångssätt är relativt okomplicerat. Han arbetar först igenom ett antal bevis som visar att alla videospel med specifika spelegenskaper faller i en viss komplexitetsklass.

Han klassificerar sedan spelen efter spelegenskaper de har.

En typ av spel innebär till exempel att en spelare rör sig genom ett landskap och besöker ett antal platser. Han kallar detta 'platsöverskridande' och ett exempel skulle vara ett spel där vissa föremål är strödda runt ett landskap och målet är att samla dem alla.



Vissa spel om platsöverskridande tillåter att varje plats endast besöks en gång. Så kallade engångsspel kan innefatta störtlopp.

Han använder sedan grafteori för att bevisa att alla spel som uppvisar både platsövergång och engångsvägar är NP-hårda, det är samma klass av komplexitet som problemet med resande säljare.

Det visar sig att Pac-Man faller i denna kategori (beviset innebär att man distribuerar kraftpiller runt labyrinten på ett sätt som tvingar fram engångsvägar).

Han visar hur spel faller in i andra komplexitetskategorier också. Till exempel är spel som har tryckkuddar för att öppna och stänga dörrar PSPACE-hårda om varje dörr styrs av två tryckplattor. Doom faller inom denna kategori.



fungerar det att knacka på en läskburk

Och så vidare.

Resultatlistan är imponerande. Här är några av hans resultat:

Boulder Dash (First Star Software, 1984) är NP-hård.

Deflektor (Vortex Software, 1987) är i L.

Prince of Persia (Brøderbund, 1989) är PSPACE-komplett.

Tron (Bally Midway, 1982) är NP-hård.

För hela listan och resonemang, se artikeln nedan.

Det har helt klart varit ett kärleksarbete för Viglietta, med tanke på titeln på hans papper: Gaming är ett hårt jobb, men någon måste göra det!

Intressant nog säger han att den här typen av analys är onödig för moderna spel. De senaste kommersiella spelen innehåller Turing-ekvivalenta skriptspråk som enkelt tillåter design av oavgjorda pussel som en del av spelet, säger han.

På ett sätt gör det dessa äldre spel ännu mer charmiga.

Ref: arxiv.org/abs/1201.4995 :Spel är ett hårt jobb, men någon måste göra det!

Dölj

Faktisk Teknik

Kategori

Okategoriserad

Teknologi

Bioteknik

Teknisk Policy

Klimatförändring

Människor Och Teknik

Silicon Valley

Datoranvändning

Mit News Tidningen

Artificiell Intelligens

Plats

Smarta Städer

Blockchain

Huvudartikel

Alumnprofil

Alumnikoppling

Mit News-Funktion

1865

Min Syn

77 Mass Ave

Möt Författaren

Profiler I Generositet

Ses På Campus

Alumnbrev

Nyheter

Tidningen Mit News

Val 2020

Med Index

Under Kupolen

Brandslang

Oändliga Berättelser

Pandemic Technology Project

Från Presidenten

Cover Story

Fotogalleri

Rekommenderas