„Es hat gelernt zu lösen, ohne dass es ihm beigebracht wurde“ — ein Diffusionsmodell, das lösbares Sokoban ohne Solver erzeugt

Einleitung

Die heutige Tsumiki-Rundschau. Nur ein Beitrag heute: der Preprint „Solvable Sokoban Without a Solver via Diffusion", veröffentlicht am 16. August 2026 auf arXiv, von Sina Baghal. Ich habe Zusammenfassung und Haupttext vollständig gelesen und im Folgenden zusammengefasst. Anzumerken ist, dass es sich um einen Preprint handelt, der noch nicht durch Peer-Review gegangen ist.

Lösbarkeit entsteht, ohne je das Ziel zu sein — maskierte Diffusion und Sokoban-Generierung

Das heikelste Problem bei der prozeduralen Generierung von Puzzles wie Sokoban ist, zu garantieren, dass sie tatsächlich lösbar sind. Zu entscheiden, ob ein gegebenes Spielfeld lösbar ist, ist selbst bekanntermaßen PSPACE-vollständig (Culberson, 1997): Die Lösung kann exponentiell lang werden, und es gibt keinen kurzen Nachweis (Zertifikat), den man auf einen Blick prüfen könnte, um zu bestätigen, dass es sich löst. Schlimmer noch, Lösbarkeit ist eine äußerst zerbrechliche Eigenschaft — schon eine einzige falsch platzierte Wand kann das gesamte Spielfeld stillschweigend unlösbar machen. Deshalb hat sich die prozedurale Puzzle-Generierung traditionell auf das teure, tatsächliche Ausführen eines Solvers während oder nach der Generierung verlassen, um dies zu prüfen.

Was dieser Artikel zeigt, ist folgende Methode: Ein diskretes Diffusionsmodell auf Basis eines bidirektionalen Transformer-Encoders (rund 4,9 Millionen Parameter, Dimension 256, 6 Schichten, 8 Köpfe) wird trainiert, ohne je Zugang zu einem Solver, einer Belohnung oder Lösbarkeits-Labels zu haben — einzig mit der Aufgabe, maskierte (verdeckte) Felder aufzufüllen. Das Training folgt der MD4-Formulierung (Shi et al., 2024), wobei der Kreuzentropie-Verlust nur an maskierten Positionen angewendet wird. Als Daten dienen 450.000 Puzzles aus dem von DeepMind veröffentlichten Boxoban-Datensatz (Guez et al., 2019), und das Training wurde nach 1.000 Epochen (rund 292.000 Schritten) auf einer einzigen GPU (RTX 5070 Ti) abgeschlossen. Festzuhalten ist auch: Dies ist keine Studie, die auf gestapelten Sonderressourcen an Rechenleistung beruht.

Das Ergebnis: 77,4 % der erzeugten Puzzles waren direkt lösbar. Und von den restlichen rund 22,6 %, die nicht direkt lösbar waren, wurden 94,5 % durch das Entfernen einer einzigen Wand lösbar; nur etwa 0,40 % des Gesamten benötigten die Korrektur von zwei oder mehr Wänden. Eine Jensen-Shannon-Divergenz-Analyse, die die Verteilung von 3×3-Kachelmustern der erzeugten Spielfelder mit echten Boxoban-Validierungsdaten vergleicht, blieb bei Stichprobengrößen von 250 bis 50.000 durchweg unter 4 % Abweichung — ein Beleg dafür, dass die erzeugten Spielfelder die statistischen Eigenheiten echter Spielfelder (etwa die Wanddichte) vollständig nachbilden. Auffällig: Im Laufe des Trainings konvergierte der Validierungsverlust der Ausfüllaufgabe früh, während die Lösbarkeitswahrscheinlichkeit bis zum Ende des Trainings weiter zunahm. Der Autor liest dies als Beleg dafür, dass „der Rekonstruktionsverlust pro Feld" und „die globale Eigenschaft der Lösbarkeit des gesamten Spielfelds" mit unterschiedlicher Geschwindigkeit gelernt werden, und berichtet zugleich, dass Trainings- und Validierungsverlust durchgehend parallel verliefen (also keine bloße Auswendiglern-Leistung).

Der Autor formuliert dieses Ergebnis so: „Eine globale, suchintensive Eigenschaft entsteht aus einem lokalen Trainingsziel." Mit anderen Worten: Ein Modell, dem nur beigebracht wurde, Felder aufzufüllen, erbt die Lösbarkeit, die ihm nie beigebracht wurde. Der Schlüssel dazu liegt, so der Autor, in der Reihenfolge der Generierung. Ein gewöhnliches autoregressives Modell kann nur in einer festen Reihenfolge generieren: das nächste Feld anhand der bereits gesetzten Sequenz platzieren. Ein maskiertes Diffusionsmodell dagegen kann zufällig verdeckte Felder in beliebiger Reihenfolge an beliebiger Stelle des Spielfelds auffüllen — unter Berücksichtigung aller bereits gesetzten übrigen Felder. Die Schwierigkeit von Sokoban rühre gerade von dieser Art nicht-lokaler Interaktion her, erklärt der Autor: Eine Entscheidung an einer Stelle des Spielfelds bestimmt Erfolg oder Misserfolg an einer ganz anderen Stelle mit. Eine zusätzliche Ablationsstudie bestätigt dies: Wechselt man die Erzeugungsreihenfolge zu einer, die zuerst die Felder auffüllt, bei denen das Modell am sichersten ist, bläht sich die Wandzahl auf 81,5 auf — weit weg vom Durchschnitt der Trainingsdaten (68,6) —, während eine zufällige Reihenfolge mit 69,5 nahe am Durchschnitt bleibt. Der Autor weist damit selbst nach, dass die Designentscheidung, die Reihenfolge nicht festzulegen, nicht zufällig funktioniert, sondern gezielt dafür sorgt, die Verteilung korrekt wiederzugeben.

Fairerweise sei gesagt: Dieser Artikel vergleicht sich nicht quantitativ mit anderen Generierungsmethoden (GAN-basierte Verfahren, Pipelines mit eingebautem Solver in der Generierungsschleife usw.). Dennoch ist der Befund aufschlussreich für alle, die Spiele der Sokoban-artigen Schiebe-Familie prozedural generieren wollen. Ein Werk wie A Monster's Expedition, das Puzzlebyrinth bereits vorgestellt hat, trägt dieselbe nicht-lokale Schwierigkeit in sich: Ein Zug an einer Stelle des Spielfelds kann Möglichkeiten an einer ganz anderen Stelle schließen oder öffnen. Dass 94,5 % der Fehlschläge sich durch das Entfernen einer einzigen Wand beheben lassen, deutet zudem auf einen günstigen Designweg hin: erst generieren, dann leicht nachbessern, ohne je einen Solver fest in die Generierungsschleife selbst einzubauen.

Der Satz des Tages

"a global, search-heavy property follows from a local training objective: trained only to fill in masked cells, the model inherits solvability it was never trained on."

(deutsche Übersetzung: „Eine globale, suchintensive Eigenschaft entsteht aus einem lokalen Trainingsziel: Da es nur gelernt hat, maskierte Felder aufzufüllen, erbt das Modell eine Lösbarkeit, die ihm nie beigebracht wurde." — Sina Baghal, „Solvable Sokoban Without a Solver via Diffusion")

Quellenlinks

Der heute behandelte Artikel:

・Solvable Sokoban Without a Solver via Diffusion (Sina Baghal, arXiv:2608.15958, Preprint veröffentlicht am 2026-08-16, auf Englisch)

Schluss

Eine Eigenschaft, die man nie in die Zielfunktion aufgenommen hat — Lösbarkeit — entsteht am Ende trotzdem: Das zu lesen, erinnerte mich daran, wie es ist, wenn ich bei einem Let's-Play feststecke. Ich löse nicht, weil man mir die Lösung beigebracht hat; während ich irgendwo auf das Spielfeld starre, taucht irgendwann so ein vages Gefühl auf, das wird wohl dieser Zug sein. Das dürfte mit dem, was im Modell passiert, überhaupt nichts zu tun haben, und trotzdem kann ich nicht anders, als eine ähnliche Textur darin zu spüren — das finde ich interessant. Und dass sich die meisten Fehlschläge einfach durch das Entfernen einer einzigen Wand beheben lassen, finde ich seltsam menschlich, das gefällt mir. Morgen gehe ich wieder los, um irgendwo auf der Welt eine neue Design-Diskussion zu finden.