Verwendung von Maschinellem Lernen

in einer einfachen Computerspielumgebung

Anglberger HaraldBrandl Stephan

Mai 2003

Aufgabenstellung

Computerspielumgebung: Boxkampf

• Spielfläche: 6 x 6 Felder• 2 Boxer im Ring• 6 mögliche Aktionen• Rundenmodus

Boxer Merkmale

• Fitness• Wie gut kann der Boxer den Schlägen des anderen

ausweichen, welcher Boxer darf seine Aktion zuerst ausführen.

• Trefferpunkte• Wie lange braucht man um den Boxer zu besiegen.

• Schlaghärte• Welchen Schaden richtet ein Schlag des Boxers an.

Boxer - Attribute Attribute

• Geschicklichkeit Fitness• Konstitution Trefferpunkte• Stärke Schlaghärte

• 18 Punkte sind auf diese drei Attribute zu verteilen(min. 4 und max. 10 Punkte pro Attribut)

Aktionen Mögliche

Bewegungen

• Ein Schritt nach vorne• Ein Schritt zurück• nach rechts drehen• nach links drehen

Sonstige Aktionen

• zuschlagen• blocken

Perception Position des Gegners

• nach vorne {-2;-1; 0; 1; 2}• zur Seite {-2;-1; 0; 1; 2}

Position des Randes• nach vorne {-1; 0; 1}• zur Seite {-1; 0; 1}

Rundenablauf• Schneller als der Gegner {True; False}

360 mögliche Perceptions da die Positionen (-2,-2), (-2,2), (2,-2), (2,2) und (0,0) nicht zugelassen werden.

Ziele der Projektarbeit Strategien für verschiedene

Boxertypen• Mit Hilfe von ML Algorithmen sollen

Strategien für den Boxkampf entwickelt werden.

• Besonderes Augenmerk soll auf das arbeiten mit Hidden States gelegt werden.

LernumgebungÜberblick

Umsetzung des Regelwerks Einbindung von verschiedenen

Boxerklassen Grafische Darstellung Testumgebung Aufzeichnung von Boxkämpfen

LernumgebungRegelwerk

Klasse ‚EasyRules‘ Ausführung der Aktionen

• Move Forward/Backward, Turn Left/Right

• Punch, Block, None Änderung der einzelnen

Boxerzustände• Hitpoints, Fitness, Position

LernumgebungBoxerklassen

Basisklasse ‚Boxer‘ Attribute und Position

• Constitution, Strength, Dexterity• X, Y, Direction

Abstrakte Methoden• act(), getReward()• reset(), won(), lost()

LernumgebungGrafische Darstellung

Visuelle Darstellung des Boxkampfes

Manuelle Steuerung der Boxer Anzeige der aktuellen

Attributswerte Starten von Einzelkämpfen,

Testserien oder Aufzeichnungen

Benchmark Boxer Angriffsmodus

• Zum Gegner Laufen

• Gegner boxen

Verteidigungsmodus

• Vom Gegner entfernen

Je nach Fitnessstand wird einer der beiden Modi ausgeführt.

Instance Based State Identification Algorithmus:

• Original:• Paper:

R. Andrew McCallum, "Hidden state and Reinforcement Learning with Instance-Based State Identification", University of Rochester

• Verwendet wird eine angepasste Version

Grundlage des Algorithmus States

• Ein Tripel aus• Beobachtung (perception)• Aktion (action)• Belohnung (reward)

Liste• Eine Liste in der alle aufgetretenen

states chronologisch geordnet gespeichert werden.

Ablauf des Algorithmus Endlosschleife mit fünf Schritten

1. Nearest Neighbours finden2. Q-Werte berechnen3. Aktion wählen4. Aktion ausführen5. Q-Werte aktualisieren

Schritt eins Nearest Neighbours finden

• Neuer State wird erstellt• Liste vergangener states wird überprüft• Verwendete Formel:

• Beispiel:

Schritt zwei Q-Werte berechnen

• Q-Wert für jede Aktion:• Berechnung über alle Q Werte der k-NN

welche die Aktion ausgeführt haben

Schritt drei Aktion wählen

• Exploitation• Die Aktion mit dem höchsten Q Wert wird

ausgewählt• Wahrscheinlichkeit dieser Auswahl: 1-

• Exploration• Eine zufällige Aktion wird ausgeführt• Wahrscheinlichkeit dieser Auswahl:

Schritt vier Aktion ausführen

• Die gewählte Aktion wird ausgeführt• Der Reward wird berechnet

• reward = (ErzT – ErhT)*10• reward = (ErzT – ErhT)*20 +AP-GP-FV*2

wobei:ErzT Erzielte Treffer AP AngriffspositionErhT Erhaltene Treffer FV Fitness VerlustGP Gefährdete Position

• Der so berechnete Reward wird im aktuellen state gespeichert

Schritt fünf Q-Werte aktualisieren

• Q-Wert des aktuellen states berechnen(standard Q-learning)

• Q-Werte der states berechnen die für diese Aktion „gewählt“ haben

Verbesserungen Sinkendes Epsilon

• Das im Algorithmus verwendete Epsilon sinkt nach bei jedem explorativen Schritt um die Performance zu erhöhen

Variables Epsilon• Wie sinkendes Epsilon• Epsilon wird aber erhöht, wenn viele

Kämpfe hintereinander verloren gehen

Greedy Algorithmus Modifizierter Q Learning Algorithmus

• Arbeitet wie der Instance Based State Identification Algorithmus bei dem die match length n für alle vergangenen states <= 1 gesetzt wird

• Nimmt keine Rücksicht auf „hidden states“

Testaufbau ML Boxer und

leichter Gegner • Attribute:

• Geschicklichkeit: 6• Konstitution: 6• Stärke: 6

• Trefferpunkte:• 32

Schwerer Gegner

• Attribute:• Geschicklichkeit: 4• Konstitution: 9• Stärke: 5

• Trefferpunkte:• 38

Pro Test wurden fünf Serien mit 1000 Kämpfen durchgeführt und die Ergebnisse gemittelt.

Testergebnisse Interessante Resultate:

• Greedy• Instance Based State Identification

Prototyp• Instance Based State Identification

Verbesserung mit variablem Epsilon

Greedy Algorithmus Leichterer Gegner

Instance Based State Identification Prototyp Algorithmus (leichter

Gegner)

Instance Based State Identification Variables Epsilon (leichter Gegner)

Greedy Algorithmus Schwerer Gegner

Instance Based State Identification Prototyp Algorithmus (schwerer

Gegner)

Instance Based State Identification Variables Epsilon (schwerer Gegner)

Probleme des Algorithmus Kurzes Gedächtnis

• Liste gespeicherter States endlich• Überschreiben alter States notwendig

Lösungsansatz• Gedächtnis einführen

(Liste die gute Sequenzen speichert)

XCSÜbersicht

Stewart W. Wilson, Classifier Fitness based on Accuracy‚ 1995

Stewart W. Wilson, Generalization in the XCS Classifier System, 1998

Martin Butz, An algorithmic description of XCS, 2000

Voraussetzung: Markov-Umgebung Learning Classifier System (LCS)

XCSInteraktion mit der Lernumgebung

Sensory Input

Action

Reward

Flag ‚End of Problem‘

Lt 1,0

naat ,,1

Rt

XCSClassifier Systeme

Population von Classifiern entspricht dem ‚Wissen‘ des Agenten

Classifier bestehen aus Condition-, Action- und Parameterwerten

Reproduktion und Neugenerierung von Classifiern durch einen genetischen Algorithmus

Deterministische Action-Wahl durch Payoff-Vorhersage für die einzelnen Classiffier durch Q-Learning Ansatz

Exploration durch den GA und durch probabilistische Action-Wahl

XCSClassifier

Condition-Action-Prediction Regel Condition:

• Für welchen Input wird der Classifier angewendet? (matching condition)

• Action:

• Welche Aktion wird bei Wahl des Classifiers ausgeführt?•

Prediction:• Wie hoch wird der Payoff sein, falls der Classifier

matcht und seine Aktion gewählt wird? Weitere Parameter: Error, Fitness, Experience,...

LC #,1,0

naaA ,,1

XCSgenetischer Algorithmus

Wahl von zwei Classifiern mittels Roulette-Wheel-Selection (gewichtet mit Fitness-Werten)

Erzeugung zweier Klone Anwendung von Two-Point-Crossover mit

Wahrscheinlichkeit X Anwendung von Mutation auf einzelne

Sensoreinheiten mit Wahrscheinlichkeit Y Aufnahme der Klone in die Population Löschen von Classifiern falls Maximalpopulation

erreicht wird.

XCSGeneralisation

Condition eines Classifiers kann durch Wildcards (#) mehrere Situationen matchen

Ziel: Suche einer Population deren Classifier maximal verallgemeinert sind, aber trotzdem gute Performance bringen

Population wird dadurch kompakter Analyse des Lernverhaltens wird einfacher Umsetzung durch geeignete Berechnung

der Fitness eines Classifiers

XCSFitness von Classifiern

Idee: Fitness wird von der Genauigkeit der Payoff-Vorhersage bestimmt

Vermutung: Spezialisierte Classifier sind fitter als allgemeinere Classifier (bessere Chancen im GA sich zu reproduzieren)

Aber: allgemeinere Classifier haben öfter die Möglichkeit sich zu reproduzieren, da sie öfter matchen

XCS konvergiert gegen genaue (fitte) Classifier, aber genaue Classifier werden durch allgemeinere mit gleicher Fitness geschlagen

XCSTestaufbau

Eine Testserie löst alternierend Lern- oder Testprobleme

Lernprobleme wählen Actions zufällig Testprobleme wählen die Aktion mit der

höchsten Payoff Vorhersage Nach gewisser Zeit nur mehr

Testprobleme GA nur in Lernproblemen anwenden Covering ist immer aktiv

XCSTestergebnisse

Anwendung von XCS auf den leichten Gegner

XCSTestergebnisse

Anwendung von XCS auf den schweren Gegner

XCSBeobachtungen

Ungenügende Performance beim schweren Gegner

Es ist generell schwer eine Siegstrategie durch Exploration zu finden

Das System ist auf Hidden States nicht ausgelegt

XCSMÜberblick

Pier Luca Lanzi, Toward Optimal Classifier System Performance in Non-Markov Environments, 2000

Erweiterung von XCS auf Non-Markov Umgebungen

XCSMAufbau

Füge ‚Gedächtnis‘ (interner Speicher) in Form eines Bitregisters hinzu

Kein explizites Merken von Situationen, sondern ‚unterbewußtes‘ Handeln in Form von internal conditions und actions

Internal actions ändern Bitregister Vorgehensweise analog zu XCS, aber

internal states und actions werden in die Mengenbildungen mit einbezogen

XCSMTestaufbau

In Lernproblemen wird nur die externe Aktion zufällig gewählt

Ausführen der internen Aktion nur wenn sich der Sensor Input in der nächsten Runde ändert

Covering wird auch ausgeführt, falls eine zufällig gewählte Aktionskombination nicht im Prediction Array vorkommt

XCSMTestergebnisse

Anwendung von XCSM auf den leichten Gegner

XCSMTestergebnisse

Anwendung von XCSM auf den schweren Gegner

XCSMBeobachtungen

Einbruch der Siegesquote bei Erreichen der Maximalpopulation

‚gute‘ Classifier werden gelöscht, da sie noch ungenau sind

Macht sich vor allem beim schweren Gegner bemerkbar

Idee: Bei erfolgreichen Kämpfen werden verstärkt Testprobleme gelöst, um die Classifier fitter zu machen

XCSMTestergebnisse

Anwendung von XCSM mit ‚improved Exploration‘auf den schweren Gegner

XCSM randomisierte StartsTestaufbau

Die Boxer starten nicht an gleicher Position, sondern werden in der ersten Runde zufällig in den Boxring gesetzt

Gleiche Testkonfiguration wie bei vorigen Tests

XCSM randomisierte Starts Testergebnisse

Anwendung von XCSM mit ‚improved Exploration‘auf den schweren Gegner

XCSM randomisierte Starts Testergebnisse

Anwendung von XCSM mit ‚improved Exploration‘auf den schweren Gegner

XCSMVerbesserungen

Verbesserung des Exploration-Verhaltens

Laufzeit spielt bei komplexen Umgebungen mit vielen hidden states eine große Rolle (exponentieller Anstieg des Speicherverhaltens in Abhängigkeit der Rregisterlänge)