Pac-Man bewiesen NP-hart durch Computational Complexity Theory

In den letzten Jahren haben einige engagierte Mathematiker damit begonnen, die Rechenkomplexität von Videospielen zu untersuchen. Ihr Ziel ist es, den inhärenten Schwierigkeitsgrad der Spiele zu bestimmen und wie sie miteinander und mit anderen Problemen zusammenhängen könnten.



Heute enthüllt Giovanni Viglietta von der Universität von Pisa in Italien eine Reihe von Herkulesarbeiten in diesem Bereich, in die er eine große Anzahl von Spielen aus den 1980er und 90er Jahren einordnet, darunter Pac-Man, Doom, Tron und viele andere.

Vigliettas Arbeit umfasst mehrere Schritte. Die erste besteht darin, die Klasse der Rechenkomplexität zu bestimmen, zu der das Spiel gehört. Als nächstes arbeitet er heraus, ob man mit dem Wissen, wie man das Spiel löst, auch viele andere Probleme derselben Klasse lösen kann, eine Eigenschaft, die Komplexitätstheoretiker „Härte“ nennen. Schließlich stellt er fest, ob das Spiel vollständig ist, also eines der „schwersten“ seiner Klasse ist.





Sein Ansatz ist relativ einfach. Er arbeitet zunächst eine Reihe von Beweisen durch, die zeigen, dass jedes Videospiel mit bestimmten Spieleigenschaften in eine bestimmte Komplexitätsklasse fällt.

Anschließend klassifiziert er die Spiele nach ihren Spieleigenschaften.

Zum Beispiel beinhaltet eine Art von Spiel, dass sich ein Spieler durch eine Landschaft bewegt und eine Reihe von Orten besucht. Er nennt dies „Location Traversal“ und ein Beispiel wäre ein Spiel, bei dem bestimmte Gegenstände in einer Landschaft verstreut sind und das Ziel ist, sie alle zu sammeln.



Bei einigen Location-Traversal-Spielen kann jeder Ort nur einmal besucht werden. Sogenannte Single-Use-Pfad-Spiele können Abfahrtsrennen beinhalten.

Anschließend verwendet er die Graphentheorie, um zu beweisen, dass jedes Spiel, das sowohl Location-Traversal- als auch Single-Use-Pfade aufweist, NP-schwer ist, das ist dieselbe Komplexitätsklasse wie das Travelling-Salesman-Problem.

Es stellt sich heraus, dass Pac-Man in diese Kategorie fällt (der Beweis beinhaltet die Verteilung von Power-Pillen im Labyrinth auf eine Weise, die Einwegpfade erzwingt).

Er zeigt, wie Spiele auch in andere Komplexitätskategorien fallen. Zum Beispiel sind Spiele mit Druckpolstern zum Öffnen und Schließen von Türen PSPACE-hart, wenn jede Tür von zwei Druckplatten gesteuert wird. Doom fällt in diese Kategorie.



Was ist eine Pingdemie?

Und so weiter.

Die resultierende Liste ist beeindruckend. Hier einige seiner Ergebnisse:

Boulder Dash (First Star Software, 1984) ist NP-hart.

Deflektor (Vortex Software, 1987) ist in L.

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

Tron (Bally Midway, 1982) ist NP-hart.

Die vollständige Liste und Begründung finden Sie im folgenden Papier.

Das war für Viglietta eindeutig eine Herzensangelegenheit, wenn man den Titel seines Artikels bedenkt: Gaming Is A Hard Job, But Someone Has To Do It!

Interessanterweise sagt er, dass diese Art der Analyse für moderne Spiele unnötig ist. Die neuesten kommerziellen Spiele enthalten Turing-äquivalente Skriptsprachen, die es leicht ermöglichen, unentscheidbare Rätsel als Teil des Gameplays zu entwerfen, sagt er.

Das macht diese älteren Spiele in gewisser Weise noch charmanter.

Ref: arxiv.org/abs/1201.4995 :Gaming ist ein harter Job, aber jemand muss ihn tun!

verbergen

Tatsächliche Technologien

Kategorie

Unkategorisiert

Technologie

Biotechnologie

Technologierichtlinie

Klimawandel

Mensch Und Technik

Silicon Valley

Computer

Mit News Magazine

Künstliche Intelligenz

Platz

Intelligente Städte

Blockchain

Reportage

Alumni-Profil

Alumni-Verbindung

Mit News Feature

1865

Meine Sicht

77 Mass Avenue

Treffen Sie Den Autor

Profile In Großzügigkeit

Auf Dem Campus Gesehen

Lerne Den Autor Kennen

Alumni-Briefe

Nicht Kategorisiert

77 Massenallee

Rechnen

Tech-Richtlinie

Lernen Sie Den Autor Kennen

Nachrichten

Wahl 2020

Mit Index

Unter Der Kuppel

Feuerwehrschlauch

Unendliche Geschichten

Pandemie-Technologieprojekt

Vom Präsidenten

Titelstory

Fotogallerie

Empfohlen