Künstliche Intelligenz rollt Stephens Würstchen

Lesedauer: 6 min　　　　　　　Alternativ: misie.ga/künstliche-intelligenz-rollt-stephens-würstchen

​

Die Weihnachtsfeiertage lohnten sich doch gut zum Spielen. Nur eigentlich will man wenigstens einmal im Jahr entspannen, also warum nicht jemandem anders den Aufwand überlassen! Menschen sind mir dabei nicht zuverlässig genug, vertrauen wir lieber auf künstliche Intelligenz. Natürlich wird sie von mir selbst erstellt, so kann nichts schief gehen und sie wird sich schon nicht gegen die Menschheit aufrichten… »Gespielt« wird ein kleines, kniffeliges Puzzle-Game namens Stephen's Sausage Roll. Ich kenne mich nicht wirklich mit (künstlicher) Intelligenz aus, eine effektive KI dafür zu entwerfen kann aber schon nicht so schwer sein.


Künstliche Intelligenz hier, da und überall

Der Begriff KI oder AI fürs englische Artificial Intelligence ist noch einmal ungenauer als die ebenfalls trendige Bezeichnung Raytracing. Neben dem Namen für eine fiktionale, digitale, unkontrollierte und normalerweise böse Entität wird KI häufig als scheinbares Synonym für Maschine oder Deep Learning in den Medien genutzt. Ohne genauer auf die Details eingehen zu wollen, ist dieser Ansatz allerdings unnötig umständlich zum Rollen von Stephens Würstchen – und nicht sehr spannend.

Stattdessen wird eine zu Stephen's Sausage Roll besser passende, systematische Art verwendet: AI Planning. Hierbei ist ein Startzustand gegeben (zum Beispiel rohe Würstchen an bestimmten Positionen) und mit Hilfe von Aktionen (Wurst mit Spieß auf Grill rollen) soll ein gewünschter Endzustand erreicht werden (alle Würste gebraten). Die Folge der gewählten Aktionen ergibt unseren Plan, welcher letztlich eine Reihe von Tastendrücken beschreibt.

Aufgabe der KI: Welcher Plan führt zum Erfolg?​

Wenn die Aktionen, der Startzustand und der Zielbereich definiert sind, haben wir im Prinzip eine leicht abstrakte Repräsentation des Spiels erzeugt. Das Lösen an sich übernimmt dann ein schon existierender, allgemeiner Planning-Problem-Solver, der anhand unserer geschriebenen Instanz die Aktionen in möglichst effizienter Reihenfolge ausprobiert, um hoffentlich schnell auf einen Plan zu kommen. Zum Abschluss verwende ich noch ein kurzes Script, dass den Lösungsplan in eine Zeichenkette aus W, A, S und D überführt, um zu sehen, ob es im richtigen Stephen's Sausage Roll tatsächlich klappt.

Man kann also sagen, dass bei AI Planning das Rätsel »im Kopf« des Solvers durchgegangen und nach Berechnungsende in einem Rutsch eine Lösung ausgespuckt wird. Daher ist es eben essentiell, dass das Spiel lückenlos definiert ist und vollkommen durch den Spieler gesteuert wird, sprich keine unvorhersehbaren (Zufalls-)Ereignisse eintreten. Selbstverständlich muss für die künstliche Intelligenz die Darstellung des Spiels korrekt umgesetzt sein. Schleicht sich ein Fehler bei der Programmierung ein, passt die Lösung nicht zum richtigen Sausage Roll. Leider kann die Fehlersuche beim Planning etwas umständlich werden, was ja glücklicherweise nicht eure Sorge sein muss.


Die Erschaffung von Yin und Yang

Einen minimal genaueren Blick auf den Kern der AI würde ich in diesem Abschnitt noch gerne werfen, für all diejenigen, die sich davon begeistern lassen. Notwendig für den Solver ist die Domäne (unsere Spielregeln) und das Problem (unser Levelaufbau). Nur zusammen vervollständigen sie sich und ergeben einen Sinn. Die Unterteilung wird vorgenommen, um möglichst einfach weitere passende Probleme (Level) für die Domäne zu schreiben. Bei beiden Dateien handelt es sich um reinen Text, der dem PDDL-Standard unterliegt. Im Folgenden sei beides aber zum vereinfachten Verständnis etwas umformuliert.

Den Hauptaspekt stellen Zustände dar, die durch eine Menge von unterschiedlichen Atomen bestimmt werden. Als Wert kommt für jedes Atom lediglich wahr oder falsch in Frage, sprich das Atom gilt oder gilt nicht im jeweiligen Zustand. Beispiel eines Startzustands wäre: { Spieler auf Position 0, nicht Spieler auf Position 1, nicht Spieler auf Position 2, nicht Wurst auf Position 0, Wurst auf Position 1, nicht Wurst auf Position 2 }. Spieler und Wurst können also drei Position haben, dass sich jedoch jeder immer nur an einer Stelle zugleich befinden darf, verbietet der Zustand alleine nicht. Das Ziel muss dagegen kein einzelner Zustand sein, so würde { Wurst auf Position 2 } alle jene abdecken, bei denen dieses Atom wahr ist. Mit Start und Ziel zusammen haben wir nun ein erstes Level.

Schema der KI: Welche Aktion ist vom aktuellen Zustand aus zielführend?​

Damit vom Startzustand überhaupt zu einem Zielzustand gekommen werden kann, braucht es die Aktionen der Domäne. Jede Aktion hat eine Vorbedingung – das ist eine Menge von Atomen, die momentan wahr oder falsch sein müssen, um vom Solver ausgewählt werden zu dürfen. Wird eine verfügbare Aktion genommen, verändert ihr Effekt die angegebenen Atome, was zu einem neuen Zustand führt. Eine dieser Aktionen könnte sein:

Code:

Aktion: Bewegung nach rechts
Vorbedingung: Spieler auf Position 0
Effekt: nicht Spieler auf Position 0 und Spieler auf Position 1
        und wenn Wurst auf Position 1 dann nicht Wurst auf Position 1 und Wurst auf Position 2

Damit wir nicht versehentlich auf unser dickes Würstchen treten, wird beim Effekt noch unterschieden, ob ein Wiener im Weg steht und verschoben werden muss. Solche Spezialbefehle sind allerdings nur eingeschränkt einsetzbar und idealerweise sollten Aktionen eigentlich bloß aus mit »und«-verknüpften Atomen bestehen.

Schon mit dieser einen Aktion käme man direkt vom Startzustand unseres ersten Levels zu einem Ziel. Doch was soll man bei Leveln machen, die aus vier, fünf oder hunderten Positionen bestehen? Hierfür lässt sich die Positionseigenschaft als Objekttyp verwenden, um etwas Flexibilität zu erhalten. Genaueres dazu sparen wir uns jedoch. Ihr solltet nur mitnehmen, dass es nicht selbstverständlich ist, ob Position i direkt links, rechts, über oder unter Position j liegt, oder doch ganz wo anders. Dabei ist das noch das einfachste an unserer Wurst-KI.


Die Schwierigkeit von Stephen's Sausage Roll

Ich hoffe jeder kennt dieses tolle Puzzle und so erwähne ich einzig aus reiner Formalität die grundlegenden Herausforderungen. Wie ihr euch erinnern könnt sind die Bewegungsmöglichkeiten abhängig von der Ausrichtung Stephens Würstchenpiksers im Verhältnis zum Spieler. Mit der Gabel in den Händen kann sich nicht seitwärts bewegt werden, stattdessen muss man sie rotieren, um in alle Himmelsrichtungen gehen zu können. Das wäre halb so wild, wenn dieses Monsterteil kein eigenes Feld einnehmen würde. Apropos große Dinger, die Wiener nehmen jeweils selbst zwei Felder ein und müssen exakt ein Mal von oben und ein Mal von unten gebraten werden. Ins Wasser darf uns auch nichts fallen und außerdem muss der Spieler zur Startposition zurückkehren.

Modellierung der KI: Boden | Wurst & Grill | Spieler & Startposition​

Zumindest für die erste Insel – auf welche wir uns beschränken – sind das die wichtigsten Hürden, welche viele Leute auf eine harte Probe stellen. In einem empfehlenswerten Video der GameStar zeigen zwei Schlawiner schön, wie man erfolglos mit Prengeln spielt. Problematisch für die KI ist zusätzlich der Umgang mit mehreren Würsten in einer Reihe. Verschiebt die Spielfigur während eines Zugs ein Würstchen, müssen sich alle Würste die dahinter im Weg liegen ebenfalls bewegen. Die unzähligen Kombinationsmöglichkeiten aus verschiedenen Orientierungen ließen sich nicht vernünftig niederschreiben, wenn man mehr als ein oder zwei Würste erlauben will. Somit muss eine andere Repräsentation verwendet werden, die dennoch zu einem logisch äquivalenten Zustand führt.

Im vorherigen Abschnitt versprach ich jedoch nicht tiefer auf die Implementierung einzugehen. Ihr könnt gerne überlegen, mit welchem Prinzip man das Problem umgehen könnte. Wenn das Interesse besteht, dass ich auf einen Punkt genauer eingehe, könnt ihr das ruhig als Kommentar äußern. Bei genug Leserinteresse findet das vielleicht Platz in einem zweiten Teil mit der zweiten Insel.


Die künstliche Intelligenz in Aktion

Da sich unsere erschaffene Intelligenz nicht durch Lernen verbessert und man meines Wissens nach auch nicht den »Gedankengang« des Solvers ausgeben kann, ist das Verhalten vermutlich nicht ganz so spannend wie bei Maschine Learning – aber ein begeisteter Freund meinte daraus müsste ich unbedingt ein YouTube-Video machen. Als Solver wird übrigens Fast Downward verwendet. Dieser stellt die Zustände des Planning-Problems als Graph dar und probiert mit einem Suchalgorithmus zu einem Zielzustand zu gelangen. Der Pfad dorthin sind die dafür auszuführenden Aktionen.

Da euch natürlich die Lösungen der gesamten ersten Insel gezeigt werden, seid ihr hier noch einmal gewarnt! Vor allem versteht man auch besser was vor sich geht, wenn man selbst Hand an Stephens Wiener gelegt hat. Und nur dass ihr euch nicht wundert, das nicht besonders schwere Laufen zwischen den Leveln übernehme ich – die KI ist sich dafür zu etepetete.

https://www.youtube.com/watch?v=IeYghl761k4​

Auch wenn es recht überschaubare Probleme sind, ist die immense Berechnungsgeschwindigkeit erstaunlich. Die meisten Rätsel sind in einem Sekundenbruchteil gelöst! Ein paar Sekunden länger benötigen lediglich zwei Level, bei denen man sich das Zurückgehen an die Startposition verbauen kann. Die Geschwindigkeit ist dabei maßgeblich beeinflusst durch die Qualität der Repräsentation, aber auch des Solvers, beziehungsweise dessen »Suchtaktik«.

Insofern bin ich mit dem Ergebnis durchweg zufrieden und ich hoffe es war für euch als Außenstehende interessant genug. Wenn euch etwas detaillierter anspricht, dann gebt wie gesagt gerne Feedback.