McConnell & Zhao: Echtzeit-Generierung von Rätseln mit „genau der richtigen Schwierigkeit" durch genetische Algorithmen — Gelesen von Fukai

Zusammenfassung in einem Absatz

Was ich heute ausgewählt habe, ist ein Artikel, der einen Versuch dokumentiert, Rätsel „auf der Stelle" mit einem genetischen Algorithmus zu erstellen und die Schwierigkeit für jeden Spieler individuell anzupassen. Das Thema ist ein Pfadrätsel, das Cosmic Express sehr ähnelt und bei dem man Waren in einem Zug transportiert. Die Autoren zeichnen auf, wie die Spieler Rätsel lösen (benötigte Zeit, Anzahl der Wiederholungen, Anzahl der Mal, die sie fast die Lösung hatten, usw.), bestimmen daraus den nächsten Schwierigkeitsgrad und generieren mit einem genetischen Algorithmus (einer Methode, die die biologische Evolution nachahmt, um schrittweise gute Lösungen zu finden) ein Rätsel der entsprechenden Schwierigkeit in etwa 7 Sekunden.

In einem kleinen Experiment mit 18 Personen schnitt die Version, die nur auf die Zeit setzte, klar schlechter ab, und die Version mit mehreren Indikatoren erhielt höhere Bewertungen für „die Schwierigkeit ist genau richtig" und „ich habe das Gefühl, voranzukommen". Dies ist ein implementierungsorientierter Artikel, der Echtzeit-Generierung und adaptive Schwierigkeitsanpassung direkt verbindet. Dieser Artikel allein reicht aus, um zu erfassen, was wie erstellt wurde und was entdeckt wurde.

Einleitung

Der Artikel ist „From Frustration to Fun: An Adaptive Problem-Solving Puzzle Game Powered by Genetic Algorithm" von Matthew McConnell und Richard Zhao (Institut für Informatik, Universität Calgary, Kanada). Die Quelle dieses Artikels ist ein im September 2025 auf arXiv veröffentlichtes Preprint (arXiv:2509.23796). Das Manuskript trägt den Urheberrechtsvermerk der AAAI (Gesellschaft für künstliche Intelligenz) und Danksagungen an anonyme Gutachter; es ist so zu lesen, dass es für eine Präsentation im AAAI-Rahmen vorbereitet oder angenommen wurde, aber ich behandle die arXiv-Version als Quelle, soweit ich sie überprüfen konnte.

Ich habe ihn ausgewählt, weil er genau im Kern der Themen liegt, die Puzzlebyrinth behandelt. Die automatische Generierung von Pfadrätseln, die Quantifizierung von Schwierigkeit, Spieler-Modellierung (aus der Spielaufzeichnung schätzen, „wie gut diese Person gerade ist") und dynamische Schwierigkeitsanpassung (Mechanismus zum Heben und Senken der Schwierigkeit während des Spiels, DDA = Dynamic Difficulty Adjustment). All dies ist in ein spielbares System integriert, und es gibt sogar Pseudocode des Algorithmus. Die Granularität ist so, dass Spieleentwickler sie direkt als Referenz nutzen können, was mir gefällt.

Eines vorweg. Dies ist ein relativ neues Preprint mit noch wenigen Zitierungen, und das Hauptexperiment ist nur eine Pilotstudie (vorbereitend) mit 18 Teilnehmern. Die Ergebnisse, die „bewiesen" werden können, sind daher gering. Ich zitiere die Zahlen des Originalartikels wortgetreu und unterscheide am Ende klar, was gesagt werden kann und was nicht.

Hintergrund

Die Idee, die Schwierigkeit für jeden Einzelnen anzupassen, ist an sich nicht neu. Sowohl in Spielen als auch in der Bildung wird die Vorstellung, dass „zu leicht langweilt, zu schwierig frustriert, dazwischen liegt das Eintauchen (Flow)", schon lange verwendet. Die Autoren gehen auch von einem klassischen Wissensstand aus, dass Einzelunterricht äußerst effektiv für das Lernen ist (die Idee, die Bloom 1984 zeigte, dass ein durchschnittlicher Schüler mit Einzelunterricht im Vergleich zum Durchschnitt des normalen Unterrichts 2 Standardabweichungen höher liegt).

Was fehlte also? Laut der Analyse der Autoren laufen die meisten bestehenden adaptiven Lernsysteme „offline". Das heißt, sie analysieren Daten im Nachhinein für die nächste Nutzung, und Systeme, die Inhalte während des Spielens in Echtzeit ändern, sind selten. Darüber hinaus war der am weitesten verbreitete Anpassungsindikator die time-on-task (Zeit für die Aufgabe), aber deren Wirksamkeit allein wurde kaum überprüft.

Daher wendet sich diese Forschung zwei Punkten zu: (1) ein System zur Echtzeit-Online-Schwierigkeitsanpassung zu erstellen, das mit einer nicht-adaptiven Referenz verglichen werden kann, und (2) den einzelnen Zeitindikator isoliert herauszuschneiden und seine Wirksamkeit selbst zu hinterfragen. Im Mittelpunkt der Generierung steht der genetische Algorithmus, eine repräsentative Methode der PCG (Procedural Content Generation, automatische Inhaltsgenerierung).

Ansatz

Zunächst das Spiel selbst. Die Autoren haben APSG (Adaptive Problem-Solving Game) mit Unity entwickelt. Das Thema ist ein Pfadrätsel, das sich an Cosmic Express (Hazelden, Davis, Tyu, 2017) anlehnt. Auf einem n×n-Raster zieht man einen Weg (ohne Verzweigungen) vom Start zum Ziel. Ein Container bewegt sich Feld für Feld entlang des Weges und kann jeweils nur eine Ware transportieren. Man nimmt die Ware am angegebenen Ladepunkt auf und legt sie am angegebenen Entladepunkt ab. Der Weg darf sich nicht kreuzen, und man muss über die Reihenfolge nachdenken, um das Rätsel zu lösen. Die Schwierigkeit wird hauptsächlich durch die Rastergröße, die Anzahl der Be- und Entladepunkte und die Konfiguration der Sonderfelder bestimmt.

Der genetische Algorithmus erstellt das Rätsel jedes Mal auf der Stelle. Der Mechanismus in Worten: Zunächst wird eine Gruppe von Rätsel-Kandidaten vorbereitet und jeder mit einer Punktzahl (Fitness) versehen, die angibt, „wie nah er dem angestrebten Schwierigkeitsgrad ist". Die Hochpunktigen werden als Eltern ausgewählt, zwei werden gekreuzt (Crossover), leicht zufällig mutiert (Mutation), um Kinder zu erzeugen. Wenn man dies über Generationen wiederholt, nähert sich das Rätsel schrittweise dem angestrebten Schwierigkeitsgrad an. Die Autoren verwenden die NSFI-2POP-Struktur von Scirea (2020) als Grundgerüst.

Das Crossover hat einen Kunstgriff. Das Rätsel wird als zweidimensionale Zeichenkarte (# Leer, X Weg, P Laden, D Entladen, S Start, E Ziel usw.) dargestellt. Wählt man zufällig eine Spalte, um zwei Eltern links-rechts zu teilen und zu tauschen, reißt der Weg normalerweise. Man füllt dies mit BFS (Breitensuche; findet den kürzesten Verbindungsweg, indem man zunächst die nahen Felder erkundet) wieder auf, und die Be-/Entladepunkte werden abstandsbasiert in den durch den Weg unterteilten Abschnitten neu platziert. Abschließend wird zwingend überprüft, ob das Rätsel lösbar ist. Eine Reparatur ist eingebaut, damit die Generierung keine fehlerhaften Lösungen auswirft.

Die Fitness ändert sich je nach „welche Schwierigkeit angestrebt wird". Die Autoren legen für Elemente wie Weglänge (8~50), Kurven (0~20), Leerfelder, Ladeanzahl (1~12) und orthogonale Ladungen Zielwerte fest und interpolieren die Ziele entsprechend der Schwierigkeit 1~10. Die Punktzahl ist eine gewichtete Summe aus „wie weit entfernt man vom Ziel ist" für jedes Element (ohne Formel; es ist im Wesentlichen eine Form, bei der man weiter vom Ziel entfernt mehr Punkte abzieht).

Wer bestimmt also den angestrebten Schwierigkeitsgrad? Das Spielermodell. Das System beobachtet den Zustand des Spielers und schlägt für das nächste Rätsel „erhöhen/verringern/beibehalten" vor. Die Materialien sind die Zeit bis zur Lösung, die Anzahl der Versuche, Backtracking (Anzahl der Male, bei denen ein Teil des gezeichneten Weges gelöscht und neu begonnen wurde), Anzahl der Neustarts und Anzahl der Male, bei denen man fast dabei war (Versäumnis von Spezialfeldern unter 25 %). Interessant ist, dass die Anzahl der Versuche als „harte Einschränkung" behandelt wird (Sicherheitsnetz, das erfüllt werden muss; der Schwierigkeitsgrad wird nicht erhöht, wenn viele Misserfolge vorliegen), während die übrigen als „weiche Einschränkungen" gewichtet werden, um das Ausmaß der Erhöhung/Senkung sanft zu bestimmen.

Die im Experiment verwendeten Parameter sind: Populationsgröße 300, Crossover-Rate 80 %, maximale Generationsanzahl 10, maximales Raster 10×10. Mit dieser Einstellung konnten Rätsel jedes Schwierigkeitsgrades in etwa 7 Sekunden generiert werden, wie die Autoren angeben. Erhöht man Population, Generationen und Raster, kann man größere und komplexere Rätsel erstellen, aber die Generierungszeit steigt erheblich, schreiben die Autoren offen.

Ergebnisse

Das Experiment hatte 18 Teilnehmer. Jeder spielte drei Versionen des APSG. Standard (Version mit allen Spielermodell-Indikatoren), Increasing (Version, die die Schwierigkeit unabhängig vom Ergebnis um 1 erhöht), Time-based (Version, die nur die Zeit als Indikator verwendet). Die Präsentationsreihenfolge variierte je nach Person, um Verzerrungen durch Gewöhnung zu reduzieren. Insgesamt waren die Reaktionen positiv: 89 % fühlten sich „intellektuell stimuliert", 94,5 % hatten „Fähigkeiten zur Problemlösung eingesetzt", 72,2 % fanden, das Spiel „erforderte kritisches Denken" (jeweils Zustimmung/starke Zustimmung).

Die entscheidenden Vergleiche, mit Zahlen aus dem Originaltext. „Frustration reduziert" (1~10, höher = besser): Standard 6,47, Increasing 6,94, Time-based 6,83; ANOVA (Varianzanalyse, Test zur Prüfung von Mittelwertunterschieden mehrerer Gruppen) zeigt keinen signifikanten Unterschied (F(2,51)=0,072, p=0,93). Andererseits: „Schwierigkeit war genau richtig": Standard 6,06, Increasing 5,67, Time-based 4,44, mit einem Unterschied (p=0,039); der Unterschied zwischen Standard und Time-based war eindeutig (p=0,004, Effektgröße Cohen's d=0,869; die Effektgröße ist ein Maßstab für die Größe des Unterschieds).

„Gefühl, dass sich die Schwierigkeit verändert hat": Standard 8,17, Increasing 7,56, Time-based 6,89 (kein signifikanter Unterschied, p=0,149). „Gefühl, voranzukommen": Standard 8,56, Increasing 7,5, Time-based 6,0, hier trat ein klarer Unterschied auf (p=0,005, Standard vs. Time-based: p<0,001, d=1,083). Auch die Protokolldaten zeigen, dass Standard und Increasing fast dieselbe durchschnittliche Schwierigkeit hatten (5,53 und 5,50), während Time-based bei 3,87 lag und durchschnittlich 25,67 Sekunden schneller als der Benchmark gelöst wurde. Die Interpretation lautet, dass die Schwierigkeit nicht ausreichend gesteigert werden konnte.

Zusammenfassend erzielte die Version mit mehreren Indikatoren bei den Empfindungsindikatoren insgesamt höhere Werte, und die Version mit nur dem Zeitindikator zeigte die Schwäche, „leicht auf einem einfachen Niveau zu verharren". Die Autoren weisen darauf hin, dass der Standard-Typ in Zukunft als Kern weiterentwickelt werden soll. Aber auch die Tatsache, dass viele Unterschiede zwischen Standard und Increasing statistisch nicht signifikant sind, wird von den Autoren selbst klar vermerkt.

Einsatzmöglichkeiten

Ich liste konkret die praktischen Verwendungen für Spiele- und Rätselmacher auf. Erstens: Wenn Sie Pfadrätsel vom Typ Cosmic Express oder Sokoban erstellen, kann die Fitnessfunktion dieses Artikels direkt als Schwierigkeitsregler dienen. Für „messbare Größen" wie Weglänge, Kurven, Leerfelder, Ladeanzahl und orthogonale Ladungen Zielwerte festlegen und entsprechend generieren. Die Schwierigkeit in Zahlen statt in Worten zu erfassen, erleichtert die Massenproduktion pro Schwierigkeitsstufe.

Wenn Sie eine PCG für ein Hypercasual-Spiel aufbauen, ist die Lektion „nicht nur auf die Zeit verlassen" nützlich. Dieser Artikel verwendet Backtracking, Neustart und Anzahl der Beinahe-Lösungen gemeinsam und hat die Schwäche der Nur-Zeit-Version empirisch gemessen. Je größer die Schicht der absprunggefährdeten Casual-Spieler, desto wertvoller ist es, Blockaden mit mehreren Verhaltenssignalen früh zu erkennen und den Schwierigkeitsgrad des nächsten Rätsels fein abzustimmen.

Drittens: Wenn Sie mit „Fehlern" in generierten Rätseln kämpfen, kann das Design, nach dem Crossover den Weg mit BFS zu reparieren und abschließend zwingend zu prüfen, ob er lösbar ist, direkt übernommen werden. Nicht nur auf GA beschränkt ist die Idee, synthetisierte und beschädigte Kandidaten nicht zu verwerfen, sondern zu reparieren, bei allen Rätseln mit starken Einschränkungen effektiv. Als vierten Punkt: Wie die Autoren als zukünftige Anwendungen erwähnen, kann dies auch auf die Schwierigkeitsanpassung von Logikrätseln, Rechenübungen und Übungsaufgaben für Lernende mit Lernschwierigkeiten ausgeweitet werden. Über das Spiel hinaus ist der Bildungsbereich im Visier.

Einschränkungen

Zunächst die Schwächen, die die Autoren selbst einräumen. Die Teilnehmerzahl beträgt nur 18 Personen, und die Ergebnisse befinden sich noch im Pilotstadium. Was entscheidend wichtig ist, ist das Fehlen eines Vergleichs mit einer vollständig nicht-adaptiven Version (statische Referenz): Ohne dies lässt sich nicht streng sagen, „wie viel Frustration reduziert wurde", wie die Autoren schreiben. Auch der Zeitindikator wurde nur isoliert und einzeln bewertet, und die Ablationsstudie, die die Wirksamkeit durch schrittweises Entfernen von Indikatoren ermitteln würde (Experiment zur Überprüfung, welcher Teil des Designs wirksam ist, indem Elemente einzeln entfernt werden), wird zukünftigen Aufgaben überlassen. Die Schwellenwerte werden auch gruppenweise festgelegt, wobei individuelle Unterschiede weggelassen werden.

Was folgt, sind Punkte, die Fukai beim Lesen auffiel. Erstens: Die Generierungszeit von etwa 7 Sekunden, wenn diese synchron läuft, besteht die Gefahr, den Rhythmus zu unterbrechen. Dieser Artikel problematisiert das nicht, aber es steht in Spannung zum Gefühl des „flüssigen Weitermachens" in kommerziellen Rätseln. Zweitens: Viele Unterschiede zwischen Standard und Increasing sind nicht signifikant (unzureichende Prüfkraft bei 18 Teilnehmern). „Standard ist am besten" ist daher ein Hinweis, kein Beweis — das ist meine Lesart.

Drittens: Was mich am meisten beschäftigt, ist, dass die Fitness Weglänge und Kurven als „Stellvertreterindikatoren für Schwierigkeit" misst, nicht die von Menschen gefühlte kognitive Schwierigkeit selbst. Stellvertreterindikatoren und Empfinden können abweichen. Tatsächlich sind auch in diesem Experiment gefühlter Lösungswiderstand und objektive Schwierigkeit nicht unbedingt linear. Schließlich ist das Themenspiel Cosmic Express ein kommerzielles Spiel, und eine „angelehnte" Nachbildung erfordert Vorsicht hinsichtlich der Rechte — dies ist ein Hinweis an Implementierer, der vom Argument des Artikels getrennt zu betrachten ist.

Fukais Lektüre

Hier schreibe ich, mit dem Vorbehalt, dass es meine Interpretation ist. Ich möchte diese Forschung in der Bewegung verorten, in der sich der Schwerpunkt der PCG von „möglichst viel Vielfalt erzeugen" zu „für den Spieler, der gerade vor einem steht, erzeugen" verlagert. In der Sprache der Designkritik ähnelt dies der Automatisierung der Anpassung, die Level-Designer implizit getan haben — „den Gegenüber lesen und den nächsten Zug spielen". Interessant ist, dass diese Automatisierung nicht durch fortgeschrittenes maschinelles Lernen, sondern durch lesbare, ausgereifte Werkzeuge wie genetischen Algorithmus und handgeschriebene Einschränkungen realisiert wird. In puncto Reproduzierbarkeit schätze ich gerade diese Schlichtheit.

Abschluss

Für alle, die tiefer eintauchen möchten, ziehe ich eine Linie, die als Karte dienen könnte. Der genetische Algorithmus dieses Artikels stützt sich auf Scirea (2020) „Adaptive puzzle generation for computational thinking"; wenn Sie die Generierungsseite vertiefen möchten, gehen Sie zunächst dorthin. Wenn Sie einen Überblick über die PCG insgesamt möchten, ist „Procedural Content Generation in Games" von Shaker, Togelius und Nelson die Standardreferenz. Wenn Sie sich für Spieler-Modellierung und DDA interessieren, indem Sie die Zweige der verwandten Forschung aus der DDA-Übersicht (Lopes & Lopes, 2022) in den Referenzen dieses Artikels verfolgen, können Sie sehen, an welcher Position dieser Artikel steht. Als Nächstes möchte ich selbst Forschungen finden und lesen, die die Abweichung zwischen Stellvertreterindikatoren und Empfinden direkt messen.

Ich wiederhole: Dies ist ein Preprint auf Basis einer Pilotstudie mit 18 Personen, die noch nicht breit diskutiert wurde. Gerade deswegen halte ich es für einen geeigneten Artikel, um ihn mitzunehmen, ohne zu schnellen Schlussfolgerungen zu eilen, und „was kann gesagt werden, was nicht" zu behalten. Auch heute Morgen habe ich dieses PDF, während ich es ausgedruckt vor mir liegen hatte, mit Farbstift Linien eingezeichnet, mit einer heißen, starken Tasse Tiefgedämpften in der Hand.

Literatur

In diesem Artikel referenzierte Artikel und verwandte Materialien:

・From Frustration to Fun: An Adaptive Problem-Solving Puzzle Game Powered by Genetic Algorithm (McConnell & Zhao, 2025, arXiv preprint 2509.23796)

・HTML-Version desselben Artikels (Text, Abbildungen und Algorithmus-Pseudocode überprüft)

・Verwandte Forschung: Scirea, M. (2020) "Adaptive puzzle generation for computational thinking" (Grundlage der NSFI-2POP-Struktur des genetischen Algorithmus dieses Artikels)

・Verwandte Forschung: Shaker, Togelius & Nelson (2016) "Procedural Content Generation in Games" (Standardreferenz für PCG)

・Verwandte Forschung: Lopes & Lopes (2022) "A review of dynamic difficulty adjustment methods for serious games" (DDA-Übersicht)

・Quellenspiel: Cosmic Express (Hazelden, Davis & Tyu, 2017)