Post on 05-Apr-2015
transcript
Seminar über Algorithmen
Sokoban ist PSPACE-vollständig
Inhalt
Einführung in Sokoban Vorstellen des Sokoban-Problems Das Sokoban-Problem ist PSPACE-
vollständig, via– Sokoban-Problem liegt in PSPACE– Sokoban-Problem ist PSPACE-schwer
Sokoban
Das Spielfeld besteht aus: Pusher
Sokoban
Das Spielfeld besteht aus: Pusher Kisten
Sokoban
Das Spielfeld besteht aus: Pusher Kisten Kistenzielfeldern
Sokoban
Das Spielfeld besteht aus: Pusher Kisten Kistenzielfeldern Feldern
Sokoban
Das Spielfeld besteht aus: Pusher Kisten Kistenzielfeldern Feldern Wänden
Mögliche Pusher-Bewegungen
Mögliche Pusher-Bewegungen
Nach oben
Mögliche Pusher-Bewegungen
Nach oben Nach unten
Mögliche Pusher-Bewegungen
Nach oben Nach unten Nach links
Mögliche Pusher-Bewegungen
Nach oben Nach unten Nach links Nach rechts
Pushen
Genau eine Kiste kann in Bewegungs-richtung verschoben werden
Pushen
Genau eine Kiste kann in Bewegungs-richtung verschoben werden
Das neue Feld der Kiste muß frei sein
Ziel des Spiels
Jede Kiste muß auf ein Kistenzielfeld gebracht werden
Ziel des Spiels
Jede Kiste muß auf ein Kistenzielfeld gebracht werden
Sokoban-Problem
Ist eine Konfiguration lösbar? Ja, da eine Folge von Pusher-Bewegungen
existiert, die zu einer Lösung führt. Nein, da ein Argument für die Unlösbarkeit
existiert.
Beispielargument für einen unlösbaren Fall
Die Kiste kann nicht mehr bewegt werden und steht auf keinem Zielfeld
Beispielargument für einen unlösbaren Fall
Die Kiste kann bewegt werden, aber nicht mehr auf ein Zielfeld
Beispielargument für einen unlösbaren Fall
Beide Kiste können nicht mehr bewegt werden. Die linke ist auf keinem Zielfeld
Sokoban liegt in NSPACE(n)
Nicht-deterministische Turing-Maschine rät Zug um Zug
Es gibt keine Lösung falls nach Schritten keine Lösung gefunden ist
Benötigt linearen Platzbedarf für die Konfiguration
k
nkn *)(
Sokoban liegt in PSPACE
Savitch´s theorem:
Daraus folgt:
Also: Sokoban liegt in PSPACE
))(())((
:gilt )(mit :Funktion jedeFür 2 nfSPACEnfNSPACE
nnfNNf
PSPACEnSPACEnNSPACE )()( 2
Sokoban ist PSPACE-schwer
Reduktion vom Entscheidungsproblem für Turing-Maschinen mit linear beschränktem Band
Reduktion
Turing-Maschine mit Wort → Sokoban Rätsel
Turing-Maschine akzeptiert Wort
Sokoban-Rätsel ist lösbar
Einbahnstraße
Einbahnstraße
Der Weg von A nach B
Einbahnstraße
Der Weg von A nach B Das Bauteil ist
wieder im Ausgangszustand
Kiste ist auf Zielfeld
Einbahnstraße
Felder, an denen die Kiste nie stehen darf
Kiste ist im Bauteil gefangen und keine andere kommt zum Zielfeld
Einbahnstraße
Kein Weg führt von B nach A in einer Lösung
Einbahnstraße
Kein Weg führt von B nach A in einer Lösung
Einbahnstraße
Kein Weg führt von B nach A in einer Lösung
Heimkehrer
Heimkehrer
Felder, an denen keine Kisten stehen dürfen– Rosa ist durch die
jeweils andere Kiste blockiert
Keine Kiste kann hinein bzw. heraus
Heimkehrer
Die Blockierung des rosanen Feldes ist durch die Verschiebung aufgehoben
Heimkehrer
Pusher am Ziel B Kisten sind nicht
auf Zielfeldern
Heimkehrer
Heimkehrer
Das Bauteil ist wieder im Ausgangszustand
Kisten befinden sich auf den Zielfeldern
Durchlauf-Zurücksetzer
Durchlauf-Zurücksetzer
Zugang zum Mittelteil über– Eingang A ist
blockiert
Durchlauf-Zurücksetzer
Zugang zum Mittelteil über– Eingang A ist
blockiert– B ist Ausgang
Durchlauf-Zurücksetzer
Zugang über Heimkehrer
Durchlauf-Zurücksetzer
Verlassen über B nicht möglich– Heimkehrer
enthält offene Kisten
– Alle Zugänge zum Mittelteil blockiert
Durchlauf-Zurücksetzer
Öffnen der Blockierung
von A
Durchlauf-Zurücksetzer
Verlassen des Mittelteils nur durch R
Durchlauf-Zurücksetzer
Eingang A nicht mehr blockiert
Durchlauf-Zurücksetzer
Durchlauf-Zurücksetzer
Durchlauf-Zurücksetzer
Jede Kiste ist auf Zielfeld
Das Bauteil ist wieder im Ausgangs-zustand
Überführung
Pfade existieren nur von:
– A zu A´ bzw. A´ zu A– B zu B´ bzw. B´ zu B
Alle Kisten sind initial und nach Durchlauf auf Zielfeldern
Kreuzung
Verbindung von Pfaden
Zelleinheit
Repräsentiert eine Zelle des Turing-Maschinen-Bands
Beinhaltet das Steuerwerk der Turing-Maschine
Endlicher Automat
Heimkehrer beim Bandsymbol
Heimkehrer
Nur der Rückweg des gelesen Buchstabens ist offen
Simulation
Simulation
Probleme:
1. Die Turing-Maschine akzeptiert bevor alle Zelleinheiten gelesen sind.
2. Die Turing-Maschine liest jeden Buchstaben, akzeptiert aber nicht.
Simulation
Die entscheidende Kiste
Reduktionskosten
Konstruktion einer Zelleinheit– pro Bandbuchstabe und Zustand werden konstant viele
Bauteile (ohne Überführungen) benötigt– Es gibt maximal Überführungen
Die Zelleinheit läßt sich in Zeit konstruieren
n Kopien werden modifziert und verbunden, in O(n) Zeit
Reduktion ist polynomiell
))*(( 2zbO
)( 2nO
Quellen
Joseph C. Culberson: Sokoban is PSPACE-complete
Dorit Dor und Uri Zwick: Sokoban and other motion planning problems
Sokoban für Windows http://sourceforge.net/projects/sokobanyasc/
Sokoban Seite der University of Alberta http://www.cs.ualberta.ca/~games/Sokoban/
Exponentielle Lösung