Der nachfolgende Text ist die Wettbewerbskonzeption einer Teilnehmerin des Wettbewerbs, Julia Dingert. Dieses Thema wurde von ihr außerdem als Schwerpunkt im Vertiefungsfach “Künstliche Intelligenz und Sprachanalyse” gewählt.
Künstliche Intelligenz und Sprachanalyse
Vertiefungsthema „Mario AI“ Sommersemester 2018
von Julia Dingert, Dozent: Prof. Adrian Müller (Webseite)
Inhalt
Aufgabenstellung
Die Aufgabe besteht darin, dass Mario mit höchstmöglicher Punktzahl das Ziel erreicht. Hierbei wird der Suchalgorithmus A* genutzt um den bestmöglichen Weg für Mario zu bestimmen.
Agent
Der Agent ist ein Nutzenbasierter Agent, da es nicht nur darum geht, das Ziel zu erreichen, sondern hierbei auch noch möglichst viele Punkte zu bekommen. Es wird eine Nutzenfunktion benötigt, die nicht nur die Schnelligkeit betrachtet, sondern auch die zu erreichenden Punkte. Die Welt des Mario Agenten beruht auf einem 2 dimensionalen Koordinatensystem. Die Weltsicht des Agenten ist nur teilweise beobachtbar, so kann er nicht das ganze Geschehen beobachten.
Ebenso ist die Welt stochastisch, da nicht vorhersehbar ist, z.B. wann der nächste Gegner kommt oder um welchen Gegner es sich handelt. Des Weiteren ist die Welt sequenziell, weil jeder Zug Auswirkungen auf den Folgezustand hat. Auch verändert sich die Welt dynamisch, da sich die Gegner bewegen. So ist Mario ein Einzelagent, der den Gegner ausweicht oder sie töten kann. Marios Interaktionen haben keine Auswirkungen auf die Gegner (außer er tötet sie). Auch sind die Auswirkungen des Handelns bekannt, d.h. wenn der Agent z.B. in ein Loch springen wird, weiß er, dass er stirbt.
Der Agent besitzt vier Eigenschaften, um ihn zu steuern: laufen, sprinten, springen und schießen. Die jeweilige Richtung kann mit links und rechts bestimmt werden. Die Runde ist zu Ende, wenn der Agent sich nicht bewegt, die Zeit abgelaufen ist oder er von einem Gegner getötet wurde.
Mögliche Steueralgorithmen
Neben dem A* Algorithmus gibt es noch andere Möglichkeiten, den Agenten zu steuern. Diese Alternativen sind z.B. ein Zustandsautomat, Regelsysteme oder hybride Systeme. Jedes dieser Systeme hat seine Stärken und Schwächen.
Eine große Schwäche des Zustandsautomaten ist die Schwierigkeit ein Ziel festzulegen und dieses mit bestem Nutzen zu erreichen. Aus diesem Grund wurde der Zustandsautomat nicht für die Implementierung des Mario Agenten gewählt.
Auch Regelsysteme sind mit einer bestimmten Ziel- bzw. Nutzenorientierung schwierig umzusetzen, da keine Funktionen für die Nutzenberechnung vorgesehen sind. Ebenso ist es in Marios Welt schwierig, jede Situation mit Regeln widerzuspiegeln, die vollständig einzuhalten sind.
Hybride Systeme haben ähnliche Schwächen, auch hier ist eine große Schwierigkeit die Komplexität der Regeln, die nur schwer jede Situation abbilden können.
Der A* Algorithmus hingegen ist darauf ausgelegt, einen Weg zum Ziel mit höchstmöglichen Nutzen zu finden und wurde deshalb für den Mario Agenten gewählt.
A* Algorithmus
Der A* Algorithmus ist eine Form der Bestensuche und besteht aus einer zweigeteilten Kostenfunktion. Diese berechnet zum einen die bisherigen Kosten zur Zielerreichung und addiert sie zu den noch geschätzten Kosten bis zum Ziel. Den geschätzten Kosten liegt eine Heuristik zugrunde, die beliebig komplex sein kann. In dieser Heuristik kann die Nutzenfunktion eingepflegt werden, um das Ziel möglichst effizient zu erreichen. Die Effizienz wird hierbei durch die Definition der Heuristik festgelegt. Bei der Erstellung der Heuristik muss darauf geachtet werden, dass die Heuristik abhängig vom Spielzustand ist. So macht es einen Unterschied, ob Mario kurz vor seinem Ziel ist und noch all seine Leben besitzt und somit bis zum Ziel sprinten kann, um wertvolle Zeitpunkte zu bekommen, oder ob er nur noch ein Leben in der gleichen Situation besitzt. Der A* Algorithmus ist auch an Randbedingungen gebunden, wobei die Wichtigste die Echtzeitbeschränkung ist, denn dadurch, dass es von jedem Ausgangszustand 9 Folgezustände gibt, wächst der Graph sehr stark exponentiell.
Mathematische Forderungen an die Heuristik
Um eine optimale Heuristik zu haben, muss sie mathematischen Anforderungen gerecht werden. So muss sie zulässig sein, d.h. sie darf die Kosten, um das Ziel zu erreichen niemals überschätzen. Eine weitere Anforderung ist die Konsistenz, die ausdrückt, dass für jeden Knoten n und jeden Nachfolger n‘ die geschätzten Kosten für die Zielerreichung von n aus nicht größer sind als die Summe der Schrittkosten, um nach n‘ zu gelangen, und der geschätzten Kosten, um von n‘ das Ziel zu erreichen (Dreiecksungleichung). Des Weiteren ist die Grundidee des A*, dass immer der kürzeste Weg gewählt wird. Dadurch ist aber nicht gewährleistet, dass damit auch der nützlichste Weg gewählt wurde. Um die Nützlichkeit gewährleisten zu können, wird die genutzte Heuristik die Entscheidung aufgrund der Entfernung übersteuern und den Nutzen mit einbringen.
Vorgehensweise zur Implementierung
1. Schritt: Knoten erzeugen
Der Algorithmus benötigt eine Grundlage, auf der er arbeiten kann, deshalb müssen zuerst die Knoten erzeugt werden.
2. Schritt: Graphen erzeugen
Aus den erzeugten Knoten muss ein Graph erzeugt werden, der als Grundlage für den Algorithmus dient.
3. Schritt: einfache Heuristik erstellen
Es wird zunächst eine einfache Heuristik erstellt, damit der Algorithmus mit etwas arbeiten kann. Das „Fine Tuning“ kommt zum Schluss.
4. Schritt: A* Algorithmus implementieren
5. Schritt: besten Pfad zurückgeben
Der vom Algorithmus errechnete Pfad muss so zurückgegeben werden, dass er in Befehle umgesetzt werden kann, die Mario versteht.
6. Schritt: Heuristik optimieren
Die Heuristik wird nun so angepasst, dass Mario das bestmögliche Ergebnis erzielt.
Heuristik
Idee: Eine Kombination aus Euklidischem Abstand im 2 dimensionalen Raum und einem Punktesystem bestehend aus „Bad Points“ und „Good Points“. Als Alternative zum Euklidischen Abstand könnte die Manhatten Distanz verwendet werden. Diese wurde jedoch nicht genutzt, da Mario nicht nur einfache Richtungsbefehle ausführen kann, sondern auch komplexe, wie z.B. „rechts – sprinten – springen“ und somit den (fast) kürzesten Weg nehmen kann. Es ist nur der fast kürzeste Weg, da bei manchen Sprungkombinationen eine Sprungkurve entsteht. Diese Abweichung ist aber im Verhältnis zur Distanz kleiner als die berechnete Distanz mittels Manhatten Metrik und deshalb zu vernachlässigen.
Definition Bad Points: Als Bad Point zählt jedes Ereignis, was Mario schaden kann, z.B. Gegner berühren und in Löcher fallen. Je höher die Gefahr, desto höher die Punkte.
Definition Good Points: Als Good Point zählt jedes Ereignis, für das man Punkte bekommt, z.B. Münzen aufsammeln.
Beschreibung der Heuristik: Die Basis bildet der Euklidische Abstand zwischen Ausgangspunkt und Zielpunkt. Hierzu werden die Bad Points addiert. Die Good Points werden diesem Ergebnis wieder gutgeschrieben.
Testen
Sobald der Agent implementiert und lauffähig ist, muss getestet werden, wie gut der Agent funktioniert. Der Test wird hierbei in verschiedene Phasen unterteilt, die sich in ihrer Schwierigkeit unterscheiden und aufsteigend schwieriger werden. So wird zuerst getestet, wie gut der Mario Agent durch die Welt kommt ohne Gegner (gemessen an der Geschwindigkeit).
In der nächsten Phase kommen nun Gegner hinzu. Hier werden die Eigenschaften getestet, wie Mario ausweicht oder Gegner eliminiert. In der letzten Phase kommen nun die Münzen hinzu und es soll getestet werden, wie Mario entscheidet.
Die Auswertung erfolgt auf Grundlage der erreichten Punkte nach jedem Durchgang im Verhältnis zur benötigten Zeit zum durchlaufen der Runde. Wenn Mario z.B. alle Gegner tötet, aber doppelt so viel Zeit benötigt und deshalb weniger Punkte im Gesamtergebnis erhält, wird die Heuristik dahingehend optimiert, dass der Agent sprintet, statt alle Gegner zu eliminieren.
Quellen
Unterlagen von Novatec Consulting GmbH
Skript
Grundkurs Künstliche Intelligenz – Eine praxisorientierte Einführung (3. Auflage), Wolfang Ertel, Kapitel 6 Suchen, Spielen und Probleme lösen
Künstliche Intelligenz – Ein moderner Ansatz (3. Aktualisierte Auflage), Stuart Russel, Peter
Norvig, Kapitel 3 Problemlösung durch Suchen
Kontakt
Julia Dingert cand. B. Sc. Medieninformatik