Wie Computer Puzzle-Level erzeugen und warum Prüfen zählt

2011 kartierten Julian Togelius, Georgios Yannakakis, Kenneth Stanley und Cameron Browne ein schnell wachsendes Feld und gaben ihm einen Namen: suchbasierte prozedurale Content-Generierung. Ihr Überblick ordnet Generatoren danach, was sie erzeugen, wie dieser Inhalt im Programm dargestellt wird und vor allem, wie seine Qualität bewertet wird. Der suchbasierte Ansatz behandelt Leveldesign als Optimierung. Kandidaten erzeugen, jeden mit einer Bewertungsfunktion benoten, die besten behalten und variieren, und das Ganze wiederholen, oft mit evolutionären Algorithmen, die aus der Biologie entlehnt sind.

In der Bewertungsfunktion steckt das Design. Sie kann ein Level direkt messen (wie viele Teile, wie viel freie Fläche), per Simulation (einen künstlichen Spieler es versuchen lassen und schauen, was passiert) oder interaktiv (echte Spieler fragen). Alles hat seinen Preis. Direkte Maße sind billig, aber oberflächlich. Simulation ist genauer, braucht aber ein Programm, das das Spiel tatsächlich spielen kann. Menschen zu fragen ist am genauesten und bei Weitem am langsamsten.

Bei einem Schiebepuzzle kann man sich das leicht vorstellen. Ein Kandidat ist ein Raster mit Steinen darauf. Eine Variation verschiebt einen Stein, fügt einen hinzu oder entfernt einen. Ein direktes Maß könnte zählen, wie voll das Feld ist; ein simulationsbasiertes Maß übergibt das Feld einem Solver und hält fest, ob es sich lösen lässt und wie lang der gefundene Weg ist. Behalte die Felder mit guter Wertung, variiere sie erneut, und nach Tausenden Runden hat sich der Generator in Richtung dessen bewegt, was die Bewertungsfunktion belohnt. Das ist seine Stärke und seine Gefahr: Er findet genau das, wonach du gefragt hast, einschließlich Feldern, die die Zahlen erfüllen und den Spieler langweilen.

Quellen1Quelle 1Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 172–186.

Eine andere Schule setzt am anderen Ende an. Statt Felder zu evolvieren und zu hoffen, dass gute dabei herauskommen, schlugen Adam Smith und Michael Mateas vor, den Raum akzeptabler Designs ausdrücklich zu beschreiben, als Menge logischer Bedingungen, und einen allgemeinen Solver Felder finden zu lassen, die sie erfüllen. Mit einer Technik namens Answer Set Programming kann ein Designer Regeln schreiben wie „der Ausgang muss erreichbar sein“ oder „dieses Teil muss sich mindestens zweimal bewegen“ und bekommt nur Felder, die sich daran halten.

Der Reiz für Puzzle-Design liegt auf der Hand. Viele Dinge, die ein Feld interessant machen, sind Bedingungen: Dieser Stein muss von jenem blockiert werden, dieser Schlüssel muss gebraucht werden. Sie aufzuschreiben zwingt einen Designer zu sagen, was er eigentlich will, und diese Disziplin ist für Menschen so nützlich wie für Maschinen.

Quellen2Quelle 2Smith, A. M., & Mateas, M. (2011). Answer set programming for procedural content generation: A design space approach. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 187–200.

Egal welcher Generator: Ein Puzzle muss zuerst lösbar sein, und das zu beweisen ist oft der schwierigste Schritt. Noor Shaker, Mohammad Shaker und Julian Togelius standen damit bei Cut the Rope vor einer Herausforderung, einem Physik-Puzzle mit kontinuierlicher Zeit und kontinuierlichem Raum, bei dem Suche mit roher Gewalt aussichtslos ist. Ihre Antwort war ein schlussfolgernder Agent, der in jedem Zustand nur sinnvolle Züge vorschlug. Das verkleinerte die Suche so weit, dass eine einfache Tiefensuche Lösungen finden und bestätigen konnte, dass die erzeugten Level spielbar waren.

Bilal Kartal, Nick Sohre und Stephen Guy gingen bei Sokoban, dem klassischen Kistenschiebe-Puzzle, einen anderen Weg. Ihr Generator baut Puzzles durch simuliertes Spielen mit Monte-Carlo-Baumsuche, sodass jedes erzeugte Puzzle schon durch seine Konstruktion lösbar ist. Auch Schiebepuzzles sind ein harter Fall: Das allgemeine Problem ist PSPACE-vollständig, wie unsere Geschichte der Schiebepuzzles erklärt, es gibt also keine bekannte Abkürzung, die jedes Feld schnell löst.

Quellen3Quelle 3Shaker, N., Shaker, M., & Togelius, J. (2013). Evolving playable content for Cut the Rope through a simulation-based approach. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 9(1), 72–78.4Quelle 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.

Ein Feld kann lösbar und trotzdem öde sein, oder nur auf einem Weg lösbar, den kein Mensch finden würde. Kartal und Kollegen gingen das direkt an. In einer Nutzerstudie suchten sie nach Merkmalen von Feldern, die sich billig berechnen ließen und damit zusammenhingen, wie schwierig Menschen die Puzzles fanden, fassten sie zu einer Bewertungsfunktion zusammen und bestätigten dann in einer zweiten Studie, dass höher bewertete Puzzles als schwieriger wahrgenommen wurden. Schwierigkeit musste also von Menschen gelernt und nicht einfach angenommen werden.

Yannakakis und Togelius verallgemeinern den Punkt in ihrem Rahmenwerk für erlebnisgesteuerte prozedurale Content-Generierung: Modelliere das Erleben des Spielers, ob aus Verhalten, Selbstauskünften oder Physiologie, und erzeuge Inhalte, die es gestalten. Das ist ein ehrgeiziges Ziel, und der ehrliche Stand der Technik ist, dass Modelle von Spaß und Frust noch grob sind. Bei einem Puzzle lassen sich Qualitäten wie Eleganz, das befriedigende „Aha“ und Fairness immer noch leichter erkennen als berechnen. Was Fairness für Spieler bedeutet, betrachten wir in was ein Puzzle fair wirken lässt.

Quellen4Quelle 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.5Quelle 5Yannakakis, G. N., & Togelius, J. (2011). Experience-driven procedural content generation. IEEE Transactions on Affective Computing, 2(3), 147–161.

Für Spieler ergibt sich daraus eine nützliche Faustregel. „Unendlich viele Level“ sagt dir, dass es einen Generator gibt; es sagt dir nicht, wie seine Level getestet werden. Halte Ausschau nach Spielen, die sagen, wie sie ihre Felder prüfen, und sei vorsichtig, wenn die Schwierigkeit wahllos springt. Das ist oft ein Zeichen, dass nichts sie modelliert.

Ein paar weitere Zeichen für eine gut gemachte Puzzle-Sammlung, ob generiert oder nicht: Neue Ideen werden einzeln eingeführt, wie es die Forschung zum Tempo von Puzzles empfiehlt; Felder wirken eigenständig statt wie Beinahe-Kopien mit einem verschobenen Teil; und wenn du feststeckst, glaubst du, dass es eine Lösung gibt. Letzteres ist am schwersten vorzutäuschen, und Generatoren haben am längsten daran gearbeitet, es sich zu verdienen.

Die 2.000 Felder von OutBrick sind eine feste, gestaltete Sammlung und kein Strom, der auf deinem Gerät erzeugt wird, und bei jedem wurde der Lösungsweg vor dem Erscheinen anhand der Regeln des Spiels selbst nachgespielt. Diesen Prozess, einschließlich der Frage, warum ein Solver, dem das Budget ausgeht, „unbekannt“ und nicht „unmöglich“ bedeutet, beschreiben wir in wie wir 2.000 Schiebepuzzle-Felder geprüft haben. Ein Solver beweist, dass es einen Weg gibt; er beweist nicht, dass das Feld Spaß macht, und deshalb wird das Tempo gesondert beurteilt. Das Ergebnis kannst du dir selbst anschauen, im heutigen Tagesfeld.