Super Mario

Ein Evolutionärer-Regel-Basierter Mario Agent

Super Mario

Super Mario's 2D-Plattformervariante, erstmals 1985 von Nintendo eingeführt, ist eine bahnbrechende Videospielreihe die Generationen geprägt hat. Dieser Artikel beleuchtet den Agenten der 2010 die Mario AI Competition gewinnen konnte.

Infinite Mario Bros

Für die Mario AI Competition wurde eine abgewandelte Variante von dem Original Super Mario Bros genutzt. Infinite Mario Bros enthält die gleichen Spiel Mechaniken, erlaubt aber die zufällige Generierung von Leveln. Diese Möglichkeit macht es einfach, KI's zu benchmarken und zu trainieren.

Level Generierung

Die Level Generierung basiert auf einem Seed System. Beim Betreten des Levels wird der Instanz ein Seed (eine ganze Zahl) zugewiesen. Mit diesen Seed kann die Anordnung von Hindernissen, Gegnern und Spielblöcken für ein Level abgeleitet werden. Dadurch besteht die Möglichkeit ein Level wiederholt zu spielen.
Desweiteren kann die Level Generierung parametrisiert werden, z.B. kann man die Schwierigkeit der generierten Level einstellen.
Zusammen ermöglicht das ein einfaches Erstellen von hochwertigen Test- und Trainingsdaten. ^[1]

Competition - API

Für die Implementation der Mario Agenten wurde Infinite Mario Bros noch einmal stark refactored. Dazu wurde eine API zur Verfügung gestellt, die die Implementation der Agenten deutlich vereinfachte. Die wichtigsten Änderungen dabei sind:

Das Spiel läuft nicht mehr in Echtzeit ab, jeder Frame muss manuell zum Nächsten gewechselt werden. Die Bildfrequenz bleibt bei 25 fps, jeder Frame muss nach 40ms zum Nächsten wechseln. ^[1:1]
Die Informationen der einzelnen Spielelemente können über Gitter ausgelesen werden. Die genaue größe des Gitters und Werte der Felder hängt von dem spezifischen API Call ab. ^[1:2]

Spiel- regeln und mechaniken

Das Ziel von Mario Bros ist es das Ende des Levels zu erreichen. Dabei muss er Hindernissen und Gegnern ausweichen. Ein Level zählt als erfolgreich beendet, wenn Mario die Zielflagge erreicht. Fällt Mario in ein Loch oder berührt als kleiner Mario einen Gegner, ist das Level verloren.

Steuerung

Es gibt 5 Input Möglichkeiten zum Steuern von Mario:

Rechte Pfeiltaste
Linke Pfeiltaste
Untere Pfeiltaste
A Taste
B Taste

Mit der rechten und linken Pfeiltaste kann Mario über den Bildschirm bewegt werden. Mit der Pfeiltaste nach unten kann Mario sich ducken, wenn er groß ist.

Die A-Taste ermöglicht Mario das Springen.

Mit der B-Taste kann Mario sprinten und in dem Zustand Feuer, Feuerbälle schießen.

Gegnertypen

In der Original Variante von Super Mario Bros gibt es 5 verschiedenen Gegner Typen.

Goomba Kann besiegt werden indem man auf ihn springt oder ihn mit einem Feuerball oder einem Panzer trifft. ^[2]
Koopa Es gibt 2 Varianten der Koopa. Die roten Koopa bleiben auf der Plattform, auf der sie sich bewegen. Die grünen können von ihrer Plattform runterfallen, was sie unberechenbarer macht. Sie nehmen unter den gleichen Bedingungen Schaden wie Goombas.^[2:1]
Spiky Er ist gegen Sprünge und Feuerbälle immun. Er nimmt nur Schaden durch geworfene Panzer.^[2:2]
Piranha Pflanze Springt periodisch aus grünen Röhren und kann mit Feuer und Panzern besiegt werden.^[2:3]
Bullet Bill Wird aus Kanonen innerhalb des Levels geschossen. Kann von Panzern und Sprüngen Schaden nehmen. ^[2:4]

Von allen Gegnern gibt es noch eine Variante mit Flügeln. Diese Varianten können fliegen, nehmen unter den gleichen Bedingungen Schaden und verwandeln sich in ihre Bodenform wenn sie Schaden genommen haben. ^[3]

Goomba — **Abb. 3** Darstellung von Marios Gegnern. ieee.org

Items

Mario kann in den Leveln auf vier verschiedene Items stoßen. Diese kann er einsammeln, um Vorteile im Spiel zu bekommen.^[2:5]

Pilze

Pilze verändern die Form von Mario von klein zu groß.^[2:6]

Abb. 4 Darstellung eines Pilz pinterest.de

Feuerblume

Die Feuerblume verändert den großen Mario in den Feuer Zustand. In diesem Zustand kann Mario Feuerbälle schießen.^[2:7]

Fire Flower — **Abb. 5** Darstellung einer Feuerblume pixilart.com

Münze

Münzen werden zufällig im Level oder nach dem Zerstören von Spielblöcken generiert. Sie erhöhen den Spiele-Score von Mario.^[2:8]

Coin — **Abb. 6** Darstellung einer Münze pinterest.de

Koopa Panzer

Wenn Mario auf ein Koopa springt, hinterlässt dieser einen Koopa Panzer. Mario kann auf diesen Panzer springen und in so Bewegung versetzen oder ihn aufsammeln und auf Gegner werfen.^[2:9]

Mario's Zustände

Mario hat drei verschiedene Zustände. Klein, Groß und Feuer. Durch das Einsammeln von Pilzen und Feuerblumen kann Mario entsprechend seine Form ändern. Nimmt Mario Schaden, verwandelt er sich in seinen nächst schlechteren Zustand.

Mushroom — **Abb. 8** Darstellung von Mario's Power-Up Prozess. ieee.org

Realm v2. Ein Regel-Basierter-Evolutionärer Mario Agent

Realm v2 wurde für die Mario Competition 2010 von Slawomir Bojarski und Clare Bates Congdon entwickelt.
Realm nutzt Regeln zum Auswerten von Spielsituationen und leitet anhand der Erfüllbarkeit dieser Regeln Aktionen ab. Die Auswertung der Erfüllbarkeit wurde mit Hilfe eines evolutionären Prozesses gefunden.

Regeln

In jeder Spielsituation werden sieben verschiedene Regeln ausgewertet. Alle Regeln, bis auf Mario Size, werden binäre Werte zugewiesen.

Mario Size Mario wird abhängig von seinem Zustand, ein Wert zugewiesen.^[2:10]
Klein = 0
Groß = 1
Feuer = 2
Is_Enemy_Close_Upper_Left Überprüfe in einer gewissen Reichweite, ob in der oberen linken Hälfte von Mario Gegner sind.^[2:11]
Is_Enemy_Close_Upper_Right Überprüfe in einer gewissen Reichweite, ob in der oberen rechten Hälfte von Mario Gegner sind.^[2:12]
Is_Enemy_Close_Lower_Left Überprüfe in einer gewissen Reichweite, ob in der unteren linken Hälfte von Mario Gegner sind.^[2:13]
Is_Enemy_Close_Lower_Right Überprüfe in einer gewissen Reichweite, ob in der unteren rechten Hälfte von Mario Gegner sind.^[2:14]
Bricks_Present Überprüfe in einer gewissen Reichweite, ob Fragezeichen- oder zerstörbare Blöcke in der Nähe von Mario sind.^[2:15]
Power_Ups_Present Überprüfe in einer gewissen Reichweite, ob Power Ups (Pilz, Blume) in der Nähe von Mario sind.^[2:16]

Aktionen

Aktionen geben die nächste Zielposition für Mario an.Realm v2 nutzt vier abstrakte Aktionen dafür:

Progress: Mario versucht hier so schnell wie möglich im Level voranzukommen.^[2:17]
Attack: Mario versucht hier mit den gegebenen Mitteln seine Gegner anzugreifen. Dies variiert stark nach Gegnertyp und den Items, die Mario in dem Moment besitzt. ^[2:18]
Evade: Hier versucht Mario den Gegnern auszuweichen. Das kann heißen das Mario sich duckt, versteckt oder einfach einen Laufweg eines Gegners abwartet. Die Möglichkeiten sind hier wieder sehr groß.^[2:19]
Power UP: Mario versucht hier so schnell wie möglich an ein Power Up zu kommen. Entweder sammelt Mario ein Power Up in unmittelbarer Nähe ein, oder versucht Fragezeichenblöcke zu finden die ein Power Up generieren können. ^[2:20]

Ausführen der Aktionen

Zum Ausführen der Aktionen suchen wir einen Weg von der Startposition zum Ziel. Zuerst erstellt man zwei Gitter, eins für die Hindernisse und eins für die Gegner im aktuellen Frame. Jedem Feld wird ein Wert zugewiesen, je nachdem ob sich dort ein Gegner oder Hinderniss befindet.
Dann wird ein gerichteter Graph erstellt. Der Graph beginnt an Marios Start Position und endet an der Zielposition. Die Knoten sind aufeinanderfolgende Inputs. Finden wir einen Weg vom Start- zum Zielknoten, können wir die Inputs von diesen ableiten. Zum Finden des Weges wird der A* Algorithmus genutzt. Die Werte der einzelnen Postionen ergeben sich aus den Gegner- und Hindernissgitter.
Während der Weg von Mario berechnet wird, simulieren wir die Bewegungen der Gegner nicht. Deshalb werden Wege berechnet, die maximal so lang wie Mario's Sprungreichweite sind. Das Simulieren der Gegnerbewegungen benötigt deutlich mehr Rechenaufwand, als in kleinen Intervallen neue Aktionen auszuwählen und auszuführen.

Ableiten von Aktionen

Der Realm v2 Agent nutzt 20 verschiedene Regeln, um jede Spielsituation zu bewerten und eine Aktion abzuleiten. Analysieren wir eine Spielsituation versuchen wir die Regel zu finden die am ehesten erfüllt wird. Werden mehrere Regeln gleich stark erfüllt, wird die höher priorisierte gewählt. Man kann die 20 Regeln durch eine Tabelle visualisieren (siehe Abb. 13). Die Tabelle wurde mit Hilfe eines Genetischen Algorithmus erstellt. Dabei hatte jede Generation eine Evaluations - und Mutationsphase. Dies wurde für 1000 Generationen wiederholt. Jede Generation hat 12 verschiedene Level gespielt.

Evaluations Phase

Nach jeden abgeschlossenen Level wird ein Fitness Score berechnet:

 fitness = distance * 1
						 + win * 1024
             + marioMode * 32
             + timeLeft * 8
- died * (distance * 0.5)

distance gibt an wie weit Mario im Level gekommen ist; win ist 1 wenn Mario das Ziel erreicht, sonst 0 ; marioMode ist 0,1 oder 2, äquivalent zu Mario_Size; timeLeft ist die übrige Spielzeit nach einem Level; died ist 1 wenn Mario verloren hat, sonst 0.^[2:21]

Die Fitnessfunktion ist hier auch spezifisch für den Wettbewerb angepasst. Sollten im Wettbewerb zwei Agenten alle Level erfolgreich beenden, gibt es drei Kategorien nach denen der Sieg entschieden wird:

Game-Time Die Zeit die Mario nach der spielinternen Uhr für alle Level benötigt hat^[1:3]
Number of total Kills Die Anzahl an Gegnern, die Mario ausschalten konnte. ^[1:4]
Mode Sum Die Summe aller Mario Zustände am Ende eines Levels. Klein = 0, Groß = 1, Feuer = 2^[1:5]

Mutations Phase

Der Genetische-Algorithmus nutzte \lambda + \mu als Evolutionsstrategie. \mu hatte den Wert 5 und \lambda den Wert 45.
Während der Mutationsphase wurden drei Operationen durchgeführt.

Mutation Die Belegung einer Regel verändert sich zufällig.^[2:22]
Crossover Eine Regel wird mit der Regel eines anderen Kinds zufällig getauscht^[2:23]
Rule Reordering Die Prioritätsreihenfolge der Regeln wird zufällig angepasst^[2:24]

Diese Regeln werden pro Mutation mit einer Wahrscheinlichkeit von 10%, 10% und 20% ausgeführt.

Resultate des Evolutionären Prozess

Realm v2 verbesserte sich in seinen ersten Generationen drastisch. Danach war nur noch eine minimale Verbesserung pro Generation zu sehen. Weitere Optimierungsversuche im evolutionären Prozess haben keine merkbaren Verbesserungen gezeigt, sodass am Ende das Optimieren der hard-gecodeten Aktionen einen Großteil der Spielleistung von Realm v2 ausmacht.

Resultate der Mario AI Competition 2010

Das besondere am Wettbewerb in 2010, war die Einführung von "Backtracking Elementen" (Sackgassen) in den Leveln. In den eigenen Tests der Realm Entwickler, hatte der A*-Agent noch deutlich besser gespielt, da gab es diese Level aber noch nicht. Die deutliche Vergrößerung des Suchbaums sorgte dafür, dass der A*-Agent nicht schnell genug den optimalen Weg finden konnte. Realm v2 war zwar etwas fehleranfälliger und passte nicht jeden Sprung pixelperfekt ab, konnte aber durch seine Mischung aus Effizienz und Spielstärke den Wettbewerb für sich entscheiden.^[1:6]

Quellen

J. Togelius, S. Karakovskiy und R. Baumgarten The 2009 Mario AI Competition IEEE Congress on Evolutionary Computation Barcelona, Spain, 2010. IEEE ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
S. Bojarski und C. B. Congdon "REALM: A rule-based evolutionary computation agent that learns to play Mario," Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games Copenhagen, Denmark, 2010,. IEEE ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
J. -J. Tsay, C. -C. Chen and J. -J. Hsu, "Evolving Intelligent Mario Controller by Reinforcement Learning," 2011 International Conference on Technologies and Applications of Artificial Intelligence, Chung Li, Taiwan, 2011. IEEE ↩︎