HTW > KI
 

Rosenkönig

Einführung

Willkommen bei Rosenkönig

Rosenkönig entstand als Belegarbeit im Rahmen des Faches Neuroinformationsverarbeitung an der Hochschule für Technik und Wirtschaft Dresden (FH) im Fach Neuroinformationsverarbeitung bei Professor Iwe. Weil wir - das sind Thomas Egerer und Dominik Hölz - beide leidenschaftliche Spieler von Brettspielen sind, war für uns relativ schnell klar, dass unser Beleg ein Brettspiel werden sollte. In Anbetracht der Tatsache, dass wir zu zweit am Projekt arbeiteten, entschieden wir uns für einen komplexen Beleg - den Rosenkönig.

Rosenkönig ist ein Brettspiel, bei dem ein Neuronales Netz zeigen kann, was es drauf hat. Die mögliche Anzahl an Spielstellungen ist immens. 24 Richtungskarten, die für Spielzüge verwendet werden, 52 zweifarbige Spielsteine und 4 Ritterkarten für jeden der zwei Spieler, ermöglichen es, unglaublich viele verschiedene Spielsituationen zu erzeugen.

Spielregel von Rosenkönig

Das Spiel versetzt uns zurück in die Vergangenheit, in der zwei englische Köngigshäuser um die Vorherrschaft kämpfen. Die beiden gegenerischen Parteien werden durch die Spielerfarben Rot und Weiß repräsentiert. Um zu gewinnen muss der Spieler versuchen, eine möglichst große zusammenhängende Fläche von Spielsteinen der eigenen Farbe zu legen.

Nachdem zu Beginn des Spieles jeder Spieler fünf verschiedene Richtungskarten erhalten hat, wird abwechselnd gezogen. Das Spielen einer Richtungskarte erfolgt - ausgehend von der Krone auf dem Spielfeld - so weit und in die Richtung, wie auf der Karte durch das abgebildete Schwert angegeben. Ein Spieler muss, wenn er an der Reihe ist, einen der folgenden Züge ausführen:

  • Spielen einer Richtungskarte (mit oder ohne Ritterkarte)
  • Ziehen einer Richtungskarte vom Ziehstapel. Dies ist nicht möglich, wenn der Spieler bereits fünf Karten besitzt.

Neben den fünf Richtungskarten erhält jeder Spieler vier Ritterkarten. Diese können verwendet werden, um eine Richtungskarte selbst dann zu spielen, wenn das Zielfeld bereits durch einen gegnerischen Spielstein belegt ist. Jede der vier Ritterkarten darf nur einmal verwendet werden. Ein aktiver Spieler der bereits über fünf Richtungskarten verfügt und nur unter Zuhilfenahme einer Ritterkarte ziehen kann, ist gezwungen diesen Zug durchzuführen.

Sollte ein Spieler nicht in der Lage sein, eine Richtungskarte zu spielen und bereits fünf Richtungskarten besizten, so muss er aussetzen.

Zu Beginn des Spiels wird die Krone auf das mittlere Spielfeld gesetzt. Eine Richtungskarte kann nicht gespielt werden, wenn sie den Rand überschreiten würde. Endet der Spielzug auf einem Feld das bereits besetzt ist, so kann der Spielzug nicht durchgeführt werden, es sei denn, das Zielfeld ist durch einen gegnerischen Spielstein besetzt und eine Ritterkarte wird gespielt.

Das Spiel endet, wenn keiner der Spieler mehr eine seiner fünf Richtungskarten spielen kann, oder 52 Spielsteine auf das Feld gesetzt wurden.

Bedienung von Rosenkönig

Bedienung des Spiels

Dieser Teil der Dokumentation beschäftigt sich mit der Bedienung des Spieles. Dies ist insbesondere deshalb wichtig, weil nach dem Start von Rosenkönig nicht sofort das Spielfeld dargestellt wird. Vielmehr wird zunächst ein Konfigurationsdialog angezeigt, der es ermöglicht, einen Computerspieler zu trainieren (siehe Training) bzw. das Spiel so zu konfigurieren, dass Daten gesammelt werden können (siehe Konfigurationsdialog), um einen Computerspieler zu trainieren.

Konfigurationsdialog

Nach dem Ausführen von Rosenkönig startet der Konfigurationsdialog. Dieser ist in der folgenden Abbildung dargestellt.

Der Konfigurationsdialog

Beschreibung der dargestellten Elemente:

  1. Spieler 1

    Dieses Steuerelement wählt Spielertyp und Spielername des ersten Spielers aus.
    Als Spielertyp stehen menschlich oder künstlich zur Verfügung.

  2. Spieler 2

    Dieses Steuerelement wählt Spielertyp und Spielername des zweiten Spielers aus.
    Wie auch für Spieler 1 stehen hier menschliche bzw. künstliche Spieler zur Verfügung.

  3. Einstellungen

    Die Einstellungen regeln zwei Parameter die während des Spiels über dessen Ausgaben entscheiden: Spielaufzeichnung und Log-Ausgaben

    • Spielaufzeichnung

      Diese Einstellung ist unverzichtbar, wenn ein neuer künstlicher Spieler angelernt werden soll. Damit dieser das Verhalten eines bestimmten Menschenspielers "erlernen" kann, muss er mit Spieldatensätzen des entsprechenden Spielers "gefüttert" werden. Um Ausgaben zu erzeugen, die das Neuronale Netz zu verarbeiten in der Lage ist, muss die Spielaufzeichnung aktiviert werden. Diese erzeugt im Verzeichnis ${GAME_ROOT}/data/patterns Patterndateien nach folgendem Muster pattern_<Spielername>_<Zeitstempel>, also beispielsweise pattern_MojoJojo_19478260 für ein Spiel des Spielers MojoJojo vom 30.01.2007 14:40. Nähere Informationen zu diesen Patterndateien finden sich unter Funktionsweise des Neurospielers.

    • Log-Ausgaben

      Die Log-Ausgaben sind im Grunde genommen nur für die Entwickler des Spieles wichtig. Sie sorgen dafür, dass während des Spiels auf der Konsole zusätzliche Statusmeldungen ausgegeben werden, die über den Zustand des Systems Auskunft geben. Dem interessierten Nutzer sollen sie jedoch nicht vorenthalten werden.

  4. Die Buttons im unteren Bereich des Dialoges haben die folgenden Funktionen:

    • Spiel starten

      Startet das Spiel mit den in 1-3 getätigten Einstellungen.

    • Trainer starten

      Startet den Trainer für einen künstlichen Spieler (siehe Training).

    • Spiel beenden

      Beendet das Spiel.

Bei der Wahl der Spielernamen sollte darauf geachtet werden, dass beide Spieler nicht den selben Namen tragen und vom gleichen Spielertyp sind. Dies wird vom Spiel nicht zugelassen.
Wird als Spielername - unabhängig vom Spielertyp - ein Name gewählt, für den noch kein Spieler existiert, so legt das Spiel einen neuen Spieler an. Für jeden Spieler wird dessen höchster Spielstand (Highscore) gespeichert.

Elemente des Spiels
Die Krone Spielt ein Spieler eine Richtungskarte, so wird der Zug ausgehend von dem Feld, auf dem sich die Krone befindet begonnen.
Mit weißem/roten Spielstein belegtes Feld Hat ein Spieler ein Spielfeld erfolgreich erobert, so wird dies durch die Anzeige eines roten/weißen Steines zum Ausdruck gebracht.
Vorschau für Position des Spielsteines Wählt der Spieler eine seiner Richtungskarten, so wird der damit vorbereitete Zug mittels dieses abgeblendeten Spielsteines dargestellt.
Beispielkarte #1 Ein Spieler im Besitz dieser Karte kann, ausgehend von der Krone, 3 Felder nach links oben rücken.
Beispielkarte #2 Ein Spieler im Besitz dieser Karte kann, ausgehend von der Krone, 2 Felder nach rechts rücken.
Beispielkaret #4 (deaktiviert) Ein Spieler im Besitz dieser Karte kann, ausgehend von der Krone, 2 Felder nach links rücken. Da die Karte abgeblendet ist, ist der Zug dieser Richtungskarte nicht möglich. Dies ist der Fall, wenn ein Spielzug über den Rand des Spielfeldes hinaus gehen würde bzw. das Zielfeld bereits besetzt ist.
Ritter des roten Spielers
Ritter des weißen Spielers
Ein Spieler jeder Farbe erhält vier Ritterkarten. Sind diese noch spielbar, so sind die Karten mit der Vorderseite nach oben dargestellt. Hat ein Spieler einen Ritter verbraucht, wird dieser mit der Rückseite nach oben dargestellt.
Übersicht über das Spielfeld

Das Spielfeld

Das Spielfeld teilt sich in verschiedene Bereiche, die angeklickt werden können, um das Spiel zu steuern. Spielkarten, die nicht auswählbar sind, werden grau dargestellt. Jeweils links und rechts des Spielfeldes befinden sich die Namen der Spieler. Ist ein Spieler an der Reihe, so ist sein Name rot dargestellt. Der nicht aktive Spielername ist schwarz.

  1. Die Spielkarten von Spieler rot

    An dieser Stelle befinden sich die Spielkarten des weißen Spielers. In der oben abgebildeten Grafik ist keine der Karten von Spieler rot auswählbar, weil Spieler weiß an der Reihe ist.

  2. Die Spielkarten von Spieler weiß

    An diese Stelle befinden sich die Richtungskarten von Spieler weiß. Da Weiß an der Reihe ist, kann er durch anklicken der farbigen Karten diese zum Ziehen auswählen. Die Auswahl einer Richtungskarte wird durch das Rotieren des Schwertes dargestellt. In oben abgebildeter Grafik ist lediglich die fünfte Karte nicht spielbar, weil das Zielfeld bereits durch einen weißen Stein belegt ist. Weiß hat die Ritter aktiviert (4) und die hervorgehobene Karte ausgewählt. Das Ergebnis des Spielzuges ist durch den abgeblendeten Stein auf dem Spielfeld gekennzeichnet (Pfeil).

  3. Ritterkarten von Spieler weiß

    Diese Stelle des Spielfeldes bevorratet die Ritterkarten von Spieler weiß. Ebenso wie die Richtungskarten sind diese in der Abbildung grau dargestellt, weil Spieler rot an der Reihe ist. Spieler weiß hat bereits einen Ritter gespielt. Dies ist daran erkennbar, dass dieser - mit der Rückseite nach oben - neben dem Ritterkartenstapel abgelegt ist.

  4. Ritterkarten von Spieler rot

    Die Richtungskarten von Spieler rot sind hier untergebracht. Rot hat seine Ritter aktiviert, was an dem blauen Rahmen zu erkennen ist, der die Ritterkarten umgibt.

  5. Punktestand von Spieler weiß

    An dieser Stelle des Bildschirmes wird der aktuelle Punktestand des weißen Spielers angezeigt. Die Änderung des Spielstands, die sich durch den geplanten Zug von Weiß ergibt, ist in kleinen Ziffern unter dem aktuellen Spielstand dargestellt.

  6. Ablagestapel für gespielte Karten

    Hat ein Spieler eine Richtungskarte gewählt und den Spielzug bestätigt (7), so findet sich die soeben gespielte Karte auf dem Ablagestapel wieder. Erst wenn alle Karten aufgebraucht sind, und ein Spieler neu ziehen möchte, wir der Ablagestapel neu gemischt und als Ziehstapel (8) wieder ins Spiel eingebracht.

  7. Bestätigungshäkchen

    Das Grafikelement an dieser Stelle mit dem lustigen Namen dient dazu, einen Spielzug zu bestätigen. Hat der aktuell aktive Spieler einen gültigen Spielzug vorbereitet, kann er diesen mit dem Klick auf dieses Häkchen bestätigen. Durch eine rote bzw. grüne Färbung des Häkchens wird angezeigt, ob der Spielzug des aktuellen Spielers gültig ist, oder nicht.

  8. Ziehstapel

    Noch nicht gezogene oder gespielte Richtungskarten befinden sich an dieser Stelle des Bildschirms. Möchte der aktive Spieler ziehen, so klickt er einfach auf diesen Stapel. In der oben dargestellten Spielsituation ist dies nicht möglich, da Rot bereits fünf Richtungskarten besitzt und daher nicht vom Ziehstapel ziehen darf.

  9. Punktestand Spieler rot

    An dieser Stelle des Bildschirms wird der aktuelle Punktestand des roten Spielers angezeigt. Die Änderung des Spielstands die sich durch den geplanten Zug von Weiß ergibt, ist in klein unter dem aktuellen Spielstand dargestellt.

Export

Neuroinformatik

Motivation

Die Implementierung von Rosenkönig erfolgte in drei Stufen:

  1. Basispiel (Logik, Grafik, Nutzerschnittstelle)
  2. Neuronale Netze
  3. Genetische Algorithmen

Nachdem die erste Stufe implementiert worden war, und das Spiel somit von menschlichen Spielern gespielt werden konnte, ging es darum, mit Hilfe Neuronaler Netze einen künstlichen Spieler zu erstellen. Ziel dieser Entwicklung war nicht, einen möglichst perfekt spielenden Spieler zu schaffen. Vielmehr ging es darum, einen Spieler zu erzeugen, der die Spielweise seines "Trainers" möglichst genau nachahmt. Es sollte also möglich sein, die Spielzüge eines menschlichen Spielers aufzuzeichnen und später das Neuronale Netz eines künstlichen Spielers damit zu trainieren.

Zu diesem Zweck musste entschieden werden, welche Teile einer konkreten Spielsituation für eine Spielentscheidung relevant sein könnten, wie diese für ein Neuronales Netz aufbereitet werden könnten und wie Eingabe bzw. Ausgabe des Netzes zu kodieren wären. Details dazu finden sich im Abschnitt Funktionsweise des Neurospielers.

Auf der Basis dieser Daten musste ein (möglichst lern- und abstraktionsfähiges) Neuronales Netz entworfen werden, das die Grundlage für die Implementierung eines künstlichen Spielers darstellt.

Softwareevaluierung

Um unnötigen Programmieraufwand und ein "Neuerfinden des Rades" zu vermeiden, hatten wir uns entschieden, eine Bibliothek für Neuronale Netze zu nutzen. Diese sollte für unsere Zwecke folgende Kriterien erfüllen:

  • Um Performanceeinbußen zu vermeiden, sollte die Bilbiothek nach Möglichkeit (ebenso wie Rosenkönig) direkt in Java implementiert sein.
  • Da eine fehlerfreie Arbeitsweise nur schwer nachprüfbar ist, sollte die Bibliothek bereits in verschiedenen Projekten erfolgreich eingesetzt worden sein.
  • Die Bibliothek muss über eine umfangreiche und leicht verständliche Dokumentation verfügen, um unnötigen Einarbeitungsaufwand und Fehlbedienungen zu vermeiden.
  • Trainierte Netze müssen persistierbar sein.
  • Training und Propagieren müssen direkt in den Quellcode von Rosenkönig integriert werden können.
  • Da die Spielsituationen in Rosenkönig relativ komplex sind, sollte die Bibliothek in "erträglicher Geschwindigkeit" arbeiten.

Bibliotheken für Neuronale Netze

Im Bereich der Künstlichen Intelligenz sind Neuronale Netze inzwischen eine etablierte Technik, so dass diverse Implementierungen für verschiedenste Problembereiche existieren. Nach einigen Recherchen stellte sich allerdings heraus, dass die meisten Systeme für unsere Zwecke völlig ungeeignet waren: Sie waren entweder nicht in Java implementiert oder aber nur für sehr spezielle Probleme (z.B. Finanzanalyse) entworfen worden.

Folgende Systeme wurden von uns genauer untersucht:

SNNS

SNNS ist eine in C++ implementierte Softwaresuite für Neuronale Netze. Das System wurde an der Universität Stuttgart entwickelt und hat sich inzwischen zum Quasi-Standard entwickelt. SNNS ist enorm leistungsfähig, ermöglicht den Aufbau komplexer Netze und die Nutzung verschiedenster Trainingsstrategien. Es verfügt über eine grafische Oberfläche für Netzentwurf und Training, für andere Zwecke (z.B. Patternerstellung) existieren Erweiterungen.

SNNS verfügt zwar auch über eine Java-Schnittstelle, wurde von uns aber nicht genutzt, da es nicht nativ in Java implementiert und somit platformabhängig ist. Wir wollten darüber hinaus eine modernere Bibliothek mit einer einfacher zu bedienenden Oberfläche nutzen.

Belegarbeiten

Im Rahmen von Belegarbeiten sind eine große Anzahl von Systemen entstanden. Einige davon sind z.B. auf der Website von Prof. Iwe (HTW Dresden) zu finden, aber auch an anderen Universitäten sind diverse Systeme entstanden.

Viele dieser Systeme wurden in Java implementiert, allerdings zeichneten sich die meisten durch eine eher schlechte Architektur aus oder wiesen eine schlechte Performance (hoher Speicherbedarf, geringe Geschwindigkeit) auf. Bei vielen Belegen war auch nicht klar zu erkennen, ob sie tatsächlich die gewünschte Funktionalität zur Verfügung stellen. Die Dokumentation der meisten Belege ließ zu wünschen übrig.

Letztlich konnte keine dieser Bibliotheken wirklich überzeugen, das Risiko eines zeitaufwändigen Fehlschlags war zu groß.

Joone

Joone (Java Object Oriented Neural Engine) ist ein in Java implementiertes Framework zur Arbeit mit Neuronalen Netzen. Joone verfügt über einen grafischen Editor zum Erstellen und Trainieren von Neuronalen Netzen, der allerdings durch intuitive Bedienbarkeit glänzt. Das Framework unterstützt verschiedene Arten von Netzen und auch unterschiedliche Trainingsverfahren.

Nach langwierigen Recherchen schien Joone die für unsere Zwecke am besten geeignete Bibliothek zu sein: alle geforderten Kriterien wurden erfüllt, das Framework ließ sich auch in eigenen Quellcode einbinden und die Implementierung in Java versprach Plattformunabhängigkeit. Allerdings zeigten sich bei näherer Beschäfigung mit Joone einige Schwächen:

  • Die Dokumentation ist unvollständig und schlecht verständlich, Javadoc ist kaum vorhanden und teilweise in spanischer Sprache verfasst.
  • Der Mechanismus zum Speichern/Laden von Netzen
    • funktioniert nur unzuverlässig
    • basiert auf Objektserialisierung und ist damit von der verwendeten Java-Version abhängig
  • Das Verhalten der mit Joone implementierten Netze war teilwese nicht nachvollziehbar.

Diese Mängelliste disqualifizierte dann leider auch Joone für unsere Zwecke.

Eigenimplementierung

Trotz langer Recherche gelang es uns nicht, eine für unsere Zwecke geeignete Bibliothek zu finden. Um den Beleg nicht weiter zu verzögern, entschlossen wir uns schließlich, eine eigene Implementierung umzusetzen.

Wir beschränkten uns dabei auf die Umsetzung von Feed Forward Netzen und Self Organizing Maps. Das einzige implementierte Trainingsverfahren für Feed Forward Netze ist Backpropagation (mit einigen Varianten). Es wurde versucht, das System möglichst modular aufzubauen und somit erweiterbar zu gestalten, auch sollte die Implementierung problemneutral sein. Der Nutzung in eigenen Projekten und dem Ausbau unseres Systems sind also keine Schranken gesetzt.

Diese Eigenimplementierung wird auf der folgenden Seite Aufbau der Netze näher erläutert. Der in der finalen Version von Rosenkönig enthaltene künstliche Spieler enthält ein Neuronales Netz, das mit unserer Implementierung entworfen und trainiert wurde.

Aufbau der Eigenimplementierung

Nachdem wir uns entschlossen hatten, keine fertige Bibliothek für Neuronale Netze zu nutzen, sondern eine Eigenimplementierung durchzuführen, galt es, einige wichtige Entscheidungen zu treffen.

Um den Implementierungsaufwand möglichst im Rahmen zu halten, entschieden wir uns, nur Feed Forward Netze und Self Organizing Maps umzusetzen. Diese beiden Netztypen bilden eine gute Grundlage für die Arbeit mit Neuronale Netzen und sind für unseren Beleg ausreichend. Auch sind zu beiden Netztypen in der Literatur umfangreiche Abhandlungen zu finden, was die Implementierung erleichtert. Das einzige implementierte Trainingsverfahren für Feed Forward Netze ist Backpropagation Learning, Quickpropagation wurde aus Zeitgründen nicht umgesetzt.

Trotz dieses eingeschränkten Funktionsumfangs ist unsere "Bibliothek" für Neuronale Netze voll funktionsfähig, es liegen auch einige Beispiele zur Demonstration vor. Es wurde versucht, die Implementierung zwar auf hohe Geschwindigkeit auszurichten, aber trotzdem modular zu arbeiten. Dadurch sind die vorhandenen Klassen leicht um weitere Funktionalitäten (z.B. weitere Lernverfahren) erweiterbar.

Die folgenden Abschnitte geben einen Überblick über die Struktur unserer Implementierung, weitere Informationen lassen sich aus der Entwicklerdokumentation entnehmen.

Aufbau

Alle Klassen zum Aufbau Neuronaler Netze befinden sich im Paket de.htwdd.rosenkoenig.neuro.net. Die Basisklasse für alle Implementierungen Neuronaler Netze ist die abstrakte Klasse NeuralNet. NeuralNet bietet Funktionen zum Speichern/Laden eines Netzes als XML-Datei sowie mehrere abstrakte Methoden, die ableitende Klassen implementieren müssen. Diese Basisklasse ermöglicht es, verschiedene Typen von Netzen mit einer einheitlichen Schnittstelle zu versehen. Die konkreten Netztypen (z.B. SOM oder Feed Forward Netz) werden somit austauschbar. Neben den momentan vorliegenden Netztypen wären weitere Netzarten wie z.B. Hopfield Netze denkbar.

Das folgende Klassendiagramm gibt einen Überblick über den Aufbau des Paketes.

Klassendiagramm de.htwdd.rosenkoenig.neuro.net

Feed Forward Netze

Eine typische Modellierung eines künstlichen Neuronalen Netzes ist das Feed Forward Netz, dessen Struktur die folgende Grafik zeigt.

Neuronales Netz

Derartige Netze sind typischerweise in Schichten mit jeweils einer bestimmten Anzahl Neuronen organisiert:

  • Eingabeschicht (input layer): Die Neuronen dieser Schicht verarbeiten die Eingaben des Netzes.
  • verdeckte Schichten (hidden layer): Die Neuronen dieser Schichten sind meist jeweils mit allen Neuronen der vorhergehenden bzw. nachfolgenden Schicht verbunden.
  • Ausgabeschicht (output layer): Die Neuronen der Ausgabeschicht fassen die Ergebnisse der vorherigen Schicht zusammen und bilden daraus die Ausgabe des Netzes.

Die einzelnen Neuronen sind durch Synapsen verbunden, die jeweils mit einem Gewicht versehen sind. Nach Anlegen der Eingabe an eine Schicht werden mittels Aktivierungs- und Ausgabefunktion die Ausgaben der Schicht berechnet, die dann wiederum die Eingaben der nächsten Schicht bilden. Auf nähere theoretische Details wird hier verzichtet. Eine gute Einführung findet sich z.B. auf den Seiten der Uni Münster.

Um die Implementierung einfacher und vor allem performanter zu gestalten, haben wir folgende Einschränkungen festgelegt:

  • Es lassen sich keine einzelnen Neuronen erstellen, sondern nur Schichten von Neuronen mit einer festgelegten Neuronenanzahl. Diese Schichten werden durch die Klasse Layer und ihre Unterklassen modelliert. Eine Schicht kann wahlweise ein Bias-Neuron enthalten.

    Eine Besonderheit stellt die Klasse KohonenLayer dar: Diese Klasse ermöglicht es, eine Self Organizing Map als Eingabeschicht eines Feed Forward Net zu nutzen.

  • Es wird davon ausgegangen, dass zwei Schichten immer voll verbunden (jedes Neuron der einen Schicht mit jedem Neuron der andern Schicht) sind. Die Klasse Synapse bildet die Verbindung zwischen zwei Schichten mit individuellen Gewichten für jede "reale" Synapse. Durch diese Einschränkung ist kein echtes Pruning der Verbindungen möglich.
  • Es handelt sich um Feed Forward Netze: Rückkopplungen oder Short Cuts sind nicht vorgesehen.
  • Die Aktivierungsfunktion (ActivationFunction und ableitende Klassen) wird jeweils pro Schicht festgelegt.
  • Ein- und Ausgaben des Netzes sowie sämtliche Zwischenwerte werden als double Werte bearbeitet.

Die Klasse FeedForwardNet modelliert ein derartiges Netz: Es besteht aus einer Ein- und einer Ausgabeschicht, deren Größe beim Erzeugen des Netzes festgelegt wird. Die Aktivierungsfunktion dieser Schichten ist die Identitätsfunktion. Mittels der Methode addHiddenLayer können beliebig viele verdeckte Schichten mit beliebigen Aktivierungsfunktionen hinzugefügt werden. Die Gewichte werden bei Erzeugung des Netzes zufällig initialisiert. Die Ein- und Ausgaben des Netzes werden jeweils durch Arrays von double Werten repräsentiert.

Self Organizing Maps

Self Organizing Maps (SOM) sind eine Spielart der sogenannten Kohonen Netze, die im Gegensatz zu Feed Forward Netzen durch unüberwachtes Lernen trainiert werden. Auch zu diesem Netztyp findet sich auf den Seiten der Uni Münster eine interessante Einführung.

Netze dieses Typs bestehen nur aus einer einzelnen Schicht Neuronen. Jedes dieser Neuronen hat einen Gewichtsvektor der Größe des Eingaberaums, man kann sich die einzelnen Neuronen also als Koordinaten auf einer (evtl. vieldimensionalen) Karte vorstellen. Die Neuronen werden z.B. rechteckig oder in einem hexagonalen Gitter angeordnet, so dass jedes Neuron eine Anzahl von Nachbarneuronen hat. Sobald ein Eingabevektor angelegt wird, bestimmt das Netz das Neuron, dessen Gewichtsvektor die größte Ähnlichkeit zum Eingabevektor aufweist. Dieses sogenannte "Gewinner-Neuron" bekommt eine Aktivierung von 1.0, durch eine Nachbarschaftsfunktion werden weitere Neuronen in seiner Umgebung angeregt, die ebenfalls eine (geringere) Aktivierung bekommen. Die Ausgabe des Netzes ist die "Karte" mit den "eingezeichneten" Aktivierungen der Neuronen.

Unsere Implementierung der SOM ist die Klasse KohonenNet. Beim Erzeugen einer Instanz dieser Klasse werden die Größe des Inputvektors sowie Höhe und Breite der Karte angegeben. Um den Rechenaufwand gering zu halten, haben wir uns auf eine rechteckige Karte beschränkt. Abstände und Ähnlichkeiten werden über den euklidischen Abstand ermittelt. Bei der Instanziierung der SOM werden die Gewichtsvektoren zufällig initialisiert.

Um das Verhalten der SOM flexibel zu gestalten, lässt sich die Nachbarschaftsfunktion austauschen: Die Klasse NeighbourhoodFunction stellt ein Attribut radius zur Verfügung, das den Nachbarschaftsradius repräsentiert. Alle ableitenden Klassen müssen die Methode computeActivation implementieren, die die Aktivierung für einen vorgegebenen Abstand zum Gewinner-Neuron berechnet. Mehrere Implementierungen sind bereits vorhanden.

Sobald ein Eingabevektor angelegt wird, bestimmt die SOM das Gewinner-Neuron und ermittelt für alle Neuronen die Aktivierung. Diese "Karte" wird dann zurückgegeben. Über die Attribute winnerX und winnerY lassen sich die Koordinaten des Gewinner-Neurons abfragen.

Training

Das Paket de.htwdd.rosenkoenig.neuro.net.training enthält Klassen, die zum Training von Neuronalen Netzen genutzt werden.

Klassendiagramm de.htwdd.rosenkoenig.neuro.net.training

Feed Forward Netze

Für das Training von Feed Forward Netzen existieren verschiedene (überwachte) Trainingsverfahren (z.B. Backpropagation, Quickpropagation, ...), von denen es teilweise noch unterschiedliche Varianten gibt. Um dieser Vielfalt gerecht zu werden, wurde ein modulares Trainingssystem entworfen, dass auf einfache Weise den Austausch des Trainingsverfahrens ermöglicht.

Bei überwachten Lernverfahren werden dem zu trainierenden Netz jeweils Paare von Ein- und Ausgabedaten präsentiert. Ein solcher Datensatz wird durch die Klasse Pattern repräsentiert. Die zentrale Klasse des Trainingsvorgangs ist die Klasse Trainer. Diese Klasse enthält verschiedene Attribute, die den Trainingsprozess beeinflussen, z.B. die Lernrate (learningRate), das Momentum (momentum) oder den Fehler, bei dessen Erreichen das Training beendet werden soll (maxError). Weiterhin kann vorgegeben werden, ob nach dem Training Pruning durchgeführt werden soll. Es handelt sich hier allerdings nicht um "echtes" Pruning, stattdessen werden alle Gewichte, die unterhalb einer bestimmten Schwelle liegen, auf 0 gesetzt. Die Angabe des Validierungskoeffizienten (validationCoeff) bestimmt das Verhältnis von Validierungs und Trainingsmenge. Ein Validierungskoeffizient von 0.1 würde bei einer Patternanzahl von 200 bedeuten, dass 180 Pattern für das Training und 20 Pattern für die Validierung genutzt werden.

Für den eigentlichen Trainingsvorgang nutzt der Trainer ein konkretes Lernverfahren, repräsentiert durch die abstrakte Klasse TeachingAlgorithm. Die Methode teachPatterns dieser Klasse wird zyklisch aufgerufen, sie bekommt die Trainingsmenge als Parameter. teachPatterns führt also einen Lernzyklus über der gesamten Trainingsmenge durch. Von TeachingAlgorithm ableitende Klassen können über das Attribut trainer auf die Trainingsparameter (Lernrate, ...) zugreifen.

Aus Zeitgründen wurde nur das Verfahren Backpropagation implementiert, weitere Verfahren lassen sich durch Ableiten der Klasse TeachingAlgorithm leicht hinzufügen. Die Klasse Backpropagation kann sowohl für Online- als auch für Offline-Training verwendet werden (Trainingsparameter batchsize) und implementiert außerdem die Varianten Momentum und Flatspot. Die Nutzung von Backpropagation lässt sich in den Beispielklassen BankExample und XORExample nachvollziehen, die beide im Package de.htwdd.rosenkoenig.neuro.net.examples enthalten sind.

Self Organizing Maps

Der Lernalgorithmus für Kohonen Netze wurde in der Klasse KohonenTrainer implementiert.

Da es sich hierbei um unüberwachte Lernverfahren handelt, bestehen die Pattern im Gegensatz zum überwachten Lernen nur aus einem Eingabevektor. Der KohonenTrainer propagiert diesen Vektor und erhält so das Gewinner-Neuron. Die Gewichte dieses Neurons und seiner Nachbarn werden dann (abhängig von der Lernrate) an den Eingabevektor angeglichen. Welche benachbarten Neuronen wie stark angeglichen werden, hängt von der Nachbarschaftsfunktion und vom Nachbarschaftsradius ab. Um zu Beginn des Lernprozesses ein schnelles "Entfalten" der Kohonen-Karte zu verstärken, wird der Nachbarschaftsradius beim Start des Lernprozesses erhöht und nimmt mit der Zeit ab. So werden bei späteren Durchläufen nur noch "Feinjustierungen" vorgenommen.

Die Nutzung des KohonenTrainer ist in der Beispielklasse AnimalExample im Package de.htwdd.rosenkoenig.neuro.net.examples verdeutlicht.

Funktionsweise des Neurospielers

Überblick

Um zu verstehen, wie der Neurospieler funktioniert, muss zunächst einmal das beleuchtet werden, womit der Neurospieler gefüttert wird: Die Datenstrukturen. Erzeugt werden die Datenstrukturen, indem beim Start eines Spieles die Option Spiel aufzeichnen aktiviert wird. Dies wird näher bei den Erläuterungen zur Bedienung des Spiels beschreiben.

Beim Speichern der Daten für eine entsprechende Spielsituation ist darauf zu achten, dass dies immer aus der Sicht des aktuell aktiven Spieler geschieht, weil die Spielzüge beider Spieler in eine separate Datei gespeichert werden.

Aufbau der Datenstrukturen

Vorbetrachtung

Betrachtet man die Anzahl der Spielsituationen, die in diesem Spiel existieren, erkennet man schnell, dass deren Anzahl unglaublich hoch ist. 52 Spielsteine, 24 Richtungskarten, 81 Spielfelder. Dazu noch Ritterkarten und die Möglichkeit, jeden der 52 Spielsteine entweder als weißen oder als roten Stein zu setzen. Betrachtet man jedoch die verschiedenen Spielsituationen näher, so kommt man schnell zur Erkenntnis, dass diese sich wiederholen. Die nachfolgenden Abbildungen - bei der nur die Spielsteine, nicht aber die Richtungskarten betrachtet werden - sollen dies verdeutlichen:

Vier unterschiedliche Spielstellungen

Auf den ersten Blick erscheinen diese Spielsituationen absolut unterschiedlich. Führt man jedoch den einfachen Trick durch, und dreht die Spielsituationen so, dass sich die Krone im unteren rechten Bereich des Spielfeldes befindet, erkennt man, dass die vier Spielsituationen vollkommen identisch sind. An der nachfolgenden Abbildung wird dies deutlich:

Reduktion der Spielstellungen

Mit diesem Kniff - wir wollen ihn Normalisierung nennen - lässt sich die Anzahl der möglichen Spielsituationen um 75% reduzieren. Außerdem wird dadurch erreicht, dass sich die Anzahl der möglichen Positionen der Krone von 81 auf 21 verringert. Wichtig ist, dass festgelegt wird, an welcher Stelle des Spielfeldes sich die Krone befindet. Im Rosenkönig wird jede Spielsituation, bevor sie in eine entsprechende Patterndatei geschrieben wird, so normalisiert, dass sich die Krone im unteren rechten Bereich des Spielfeldes befindet.

Struktur der Eingabedaten

Durch den in der Vorbetrachtung erläuterten Schritt konnte die Anzahl der Eingänge für das Neuronale Netz bereits gesenkt werden. Es ist jedoch festzustellen, dass die Zahl der Eingänge für den Neurospieler trotzdem beträchtliche Ausmaße annimmt. Die folgende Tabelle soll verdeutlichen, welche Daten an den Eingängen des Neuronalen Netzes anliegen:

Anzahl der EingängeBedeutung/Darstellung der Werte
162Darstellung der Spielsteine auf dem Spielfeld, mit jeweils zwei Eingängen pro Spielfeld:
-1:-1 - leer
-1: 1 - eigene Farbe
 1:-1 - gegnerische Farbe
 1: 1 - nicht definiert
21Position der Krone. Durch die Normalisierung ist es nicht nötig, 81 Eingänge zu verwenden.
-1 - keine Krone auf dem Feld
 1 - Krone befindet sich auf dem Feld
12010 Richtungskarten, die jeweils mit 12 Eingängen pro Karte wie folgt kodiert werden:
xxxxxxxxxxxx
^       ^  ^
|       |  |
|       |  Spielbarkeit der Karte:
|       |                         -1 - nein
|       |                          1 - ja
|       |
|       Weite des Zuges:
|                       -1:-1: 1 - 1 Felder
|                       -1: 1:-1 - 2 Felder
|                        1:-1:-1 - 3 Felder
|                       -1:-1:-1 - keine Karte
|                       alle anderen Kombinationen sind ungültig
|
Richtung des Zuges:
                   -1:-1:-1:-1:-1:-1:-1:-1 - keine Karte
                   -1:-1:-1:-1:-1:-1:-1: 1 - Osten
                   -1:-1:-1:-1:-1:-1: 1:-1 - Südosten
                   -1:-1:-1:-1:-1: 1:-1:-1 - Süden
                   -1:-1:-1:-1: 1:-1:-1:-1 - Südwesten
                   -1:-1:-1: 1:-1:-1:-1:-1 - Westen
                   -1:-1: 1:-1:-1:-1:-1:-1 - Nordwesten
                   -1: 1:-1:-1:-1:-1:-1:-1 - Norden
                    1:-1:-1:-1:-1:-1:-1:-1 - Nordosten
10Kodierung der Ritterkarten:
xxxxxyyyyy
^    ^
|    |
|    gegnerische Ritter
|
eigene Ritter

-1 - Ritter nicht vorhanden (bereits gspielt)
 1 - Ritter vorhanden (noch nicht gespielt)

Zur Kodierung des vom Spieler vorgenommenen Spielzuges - den Ausgangsdaten - wird ein ähnliches Verfahren verwendet. Dabei werden 6 Ausgänge wie folgt interpretiert:

xxxxxd
^    ^
|    |
|    -1 - keine Karte gezogen
|     1 - Karte gezogen
|
 1:-1:-1:-1:-1 - Karte 1 gespielt
-1: 1:-1:-1:-1 - Karte 2 gespielt
-1:-1: 1:-1:-1 - Karte 3 gespielt
-1:-1:-1: 1:-1 - Karte 4 gespielt
-1:-1:-1:-1: 1 - Karte 5 gespielt

Zur Kodierung der Eingangsdaten des Netzes sind somit 313 Eingänge, für die Kodierung der Ausgangsdaten 6 Ausgänge notwendig. Beim Aufzeichnen eines Spieles wird bei jedem Spielzug ein solcher Datensatz generiert, der beim Trainieren des Netzes verwendet werden kann.

Funktionsweise des Neurospielers

Ist ein Neurospieler trainiert (siehe Trainieren), so wird ihm im Verlauf des Spieles ständig die aktuelle Spielsituation präsentiert. Aus dieser kann er durch Abstrahieren seinen nächsten Spielzug bestimmen. Dabei wird die aktuelle Spielsituation als Netzeingabe verwendet und die Netzausgabe ausgewertet: Der höchste der sechs Ausgabewerte des Neuronalen Netzes kennzeichnet die getroffene Entscheidung.

Die Entscheidung auf Basis des Neuronalen Netzes ist jedoch nicht in allen Situationen notwendig. Die Ausnahmefälle werden im nächsten Abschnitt besprochen.

Ausnahmen

Ist ein Neurospieler trainiert, so existieren Situationen im Spiel, bei denen dem Neuronalen Netz nicht die Spielsituation präsentiert wird, um eine Entscheidung durch das Netz zu erwarten. Dies ist beispielsweise der Fall, wenn der gegnerische Spieler bereits fünf Karten besitzt, sich aber trotzdem nicht bewegen kann. Dann wird dem Neuronalen Netz die Entscheidung abgenommen und automatisch gezogen.

Eine andere Situation tritt ein, wenn das Neuronale Netz sich für ein Ausgabemuster entscheidet, bei dem eine nicht vorhanden Karte gespielt werden müsste. Dann setzt ein Fallbackmechanismus ein, der dazu führt, das die am höchsten bewertete vorhandene Karte gespielt, bzw. ein Karte vom Ziehstapel gezogen wird.

Trainieren des Netzes

Einer der wichtigsten Schritte, um einen leitstungsfähigen Neurospieler zu erhalten, ist das Trainieren. Dazu müssen ausreichend viele Trainingsdatensätze vorhanden sein. Wie diese gewonnen werden können, ist in Allgemein - Bedienung ausführlich beschrieben. Ein Überblick über den Aufbau dieser Datensätze, findet sich in Aufbau der Datenstrukturen.

Um in den Trainingsdialog zu gelangen, muss im Konfigurationsdialog der Trainer starten-Button betätigt werden. Anschließend erscheint das folgende Menü:

Die Krone

Zum Trainieren eines Spieler sind die folgenden Schritte notwendig:

  1. Auswahl eines (vorhandenen) Spielers

    Die Auswahl des Spieler erfolgt über einen DropDown-Dialog, bei dem ein bereits vorhandener Spieler weiter trainiert werden kann. Alternativ dazu wird auch die Eingabe eines neuen Spielernamens akzeptiert. In diesem Falle erzeugt das System einen neuen, untrainierten Spieler

  2. Konfiguration der Netzstruktur

    Die Konfiguration der Netzstruktur ist mit Hilfe der Steuerelemente unter 2 möglich. Die Anzahl der Eingabeneuronen ist nicht veränderlich. Sie beträgt 314 (313 Neuronen und ein Bias-Neuron, siehe Struktur der Eingabedaten, wohl aber die Anzahl der verdeckten Schichten, deren Anzahl und Breite. Des weiteren besteht die Möglichkeit einer vorgeschalteten Kohonenschicht (auch wenn sich diese als wenig hilfreich erwies).

    Die Anzahl der Neuronen pro Schicht ist jeweils durch die entsprechenden SpinBoxen möglich. Es kann jeweils nur eine Kohonenschicht pro Netz vorhanden sein. Für die Anzahl der verdeckten Schichten gibt es keine Beschränkung. Ist eine verdeckte Schicht einmal dem Netz hinzugefügt, kann sie nicht mehr entfernt werden.

    Ebenfalls wieder fest vorgegeben ist die Anzahl der Ausgabeneuronen (siehe Struktur der Eingabedaten). Diese Wert muss - nicht veränderlich - 6 für jedes Netz betragen.

  3. Einstellung der Trainingsparameter

    Für das Trainieren des Spielers sind neben der Netzstruktur noch andere Parameter wählbar. Deren Bedeutung soll im folgenden kurz angesprochen werden.

    • Lernrate

      Die Lernrate ist der Einfluss der berechneten Gewichtsänderung auf das aktuelle Gewicht.

    • Momentum

      Das Momentum ist der Einfluss der vorangegangenen Gewichtsänderung auf die darauf folgende Gewichtsänderung.

    • Lernzyklen

      Anzahl der Lernzyklen legt fest, wie häufig die ausgewählten Trainingsdatensätze dem Neuronalen Netz präsentiert werden.

    • Batchsize

      Die Batchsize legt fest, nach wie vielen präsentierten Mustern eine Gewichtsänderung durchgeführt wird. Eine Batchsize von 1 wird als Onlinelernverfahren bezeichnet. Man spricht von einem Offline learning, wenn die Batchsize größer 1 ist.

    • max. Fehler

      Zahlenwert, bei dem das Training eines Spieler beendet wird und das Netz als trainiert gilt. Dieser Zahlenwert sollte bei <<1 liegen.

    • Val. Koeff. (Validierungskoeffizient)

      Prozentsatz der Trainingsdaten, der nicht zum Trainieren, sondern zum Validieren der Trainingsdaten verwendet wird.

  4. Auswahl der Trainingsdatensätze

    Zu guter letzt müssen die Datensätze ausgewählt werden, die dem zu trainierenden Spieler wiederholt präsentiert werden sollen. Hier empfiehlt es sich bei der Auswahl immer auf die Datensätze eines menschlichen Spieler zurückzugreifen, da dessen Spielmuster in der Regel wesentlich besser erlernbar sein sollten, als wirr durcheinandergewürfelte Trainingsdaten von mehreren Spielern.

Nach dem Treffen all dieser Einstellungen kann das Training des Spieler mit einem Klick auf den Button Spieler trainieren gestartet werden. Es ist jedoch darauf hinzuweisen, dass das Training aufgrund der Komplexität des Problems und der notwendigen Menge an Trainingsdatensätzen eine extrem zeitaufwendige Angelegenheit ist. Weiterhin sollte darauf acht gegeben werden, dass nach abosolviertem Training eines Spieler dieser gespeichert wird, damit die mühsam errungenen Trainingsfortschritte nicht verloren gehen.

Fazit

In den ersten Phasen des Projekts Rosenkönig sind mehrere Dinge entstanden:

  1. Eine Umsetzung des Brettspiels Rosenkönig als Computerspiel
  2. Eine erweiterbare Bibliothek für Neuronale Netze
  3. Ein lernfähiger KI-Spieler

Jeder dieser Punkte war auf seine Weise arbeitsintensiv und wir als Entwickler haben viel gelernt und Erfahrungen gesammelt.

Vom Brettspiel zum Computerspiel

Bei der Umsetzung des Brettspiels wurde vor allem Wert auf eine ansprechende Oberfläche und ein durchdachtes Bedienkonzept gelegt. So hat unsere Umsetzung von Rosenkönig auch für eingefleischte Brettspieler durchaus ihren Reiz, nicht nur durch die Möglichkeit des Spiels gegen einen virtuellen Gegner. Auch das Ausprobieren verschiedener Zugmöglichkeiten und die Berechnung der Punktdifferenzen im voraus ist so im reinen Brettspiel nicht möglich.

Neben diesen nach außen sichtbaren Eigenschaften war ebenfalls wichtig, das Spiel intern möglichst sinnvoll modular zu gliedern. Eine zentrale Klasse implementiert das Regelwerk und steuert den Spielablauf, alle weiteren Elemente sind austauschbar:

  • Verschiedene Spielertypen werden gleich behandelt. Dies sind im Moment menschliche und künstliche Spieler, denkbar wäre aber z.B. auch ein Netzwerkspieler zum Spiel mit einem entfernten Gegner.
  • Die GUI ist austauschbar. Momentan liegen eine Implementierung für die Sprite-Bibliothek Genuts und eine passive "Logger-GUI" vor, eine Umstellung auf eine andere Sprite-Bibliothek wäre leicht möglich. Vorstellbar wäre z.B. auch eine 3D-Oberfläche
  • Die Konfigurationsdialoge sind ebenfalls austauschbar.

Es ist also eine voll funktionsfähige und erweiterbare Brettspielumsetzung entstanden.

Neuronale Netze

Nach der enttäuschenden Evaluierung bestehender Systeme ist eine modulare und erweiterbare Eigenimplementierung einer Bibliothek für Neuronale Netze entstanden.

Diese Bibliothek ist trotz ihres momentan noch relativ geringen Funktionsumfangs für viele Projekte ausreichend und lässt sich an vielen Stellen einfach erweitern. Wünschenswert wären vor allem folgende Erweiterungen:

  • Implementierungen weiterer Lernverfahren, z.B. Quickpropagation oder Reinforcement Learning
  • Die Erweiterung der bestehenden Netztypen um Netze mit Rückkopplungen und Shortcuts
  • Um während des Trainingsprozesses vorhandene Rechenkapazitäten besser auszunutzen, wäre die Möglichkeit der Parallelisierung wünschenswert

Durch die Eigenimplementierung Neuronaler Netze ist unser Verständnis für diesen Bereich der Künstlichen Intelligenz enorm gestiegen, wir hoffen, dass spätere Projekte davon profitieren können.

Künstliche Spieler

Die Entwicklung des KI-Spielers hat trotz großen Aufwandes nicht zum ursprünglich erhofften Ergebnis geführt. Wir konnten einen Spieler entwickeln, der seine Entscheidungen auf Basis eines Neuronalen Netzes trifft, wir können die Spielzüge menschlicher Spieler aufzeichnen und den künstlichen Spieler mit diesen Daten trainieren. Allerdings ist das Training extrem zeitaufwändig und der trainierte Spieler trifft oftmals nicht nachvollziehbare Entscheidungen.

Eine Verbesserung dieses Verhaltens trat erst durch den Einsatz Genetischer Algorithmen ein.

Genetische Algorithmen

Motivation

Für Rosenkönig wurde ein künstlicher Spieler entworfen, der seine Entscheidungen auf Basis eines Neuronalen Netzes trifft. Dabei wird als Input des Netzes die aktuelle Spielsituation (siehe Funktionsweise des Neurospielers) kodiert, der Netzoutput bestimmt, welche Karte gespielt oder ob eine Karte gezogen wird. Trainingsdaten können durch menschliche Spieler erzeugt werden, indem jeweils die aktuelle Spielsituation gespeichert wird. Zu jeder Spielsituation wird außerdem die vom Spieler getroffene Entscheidung gespeichert (siehe auch Bedienung).

Ein neuer KI-Spieler kann nun mittels des Trainerdialogs erstellt, trainiert und gespeichert werden, er kann dann im Spiel eingesetzt werden.

Das Neuronale Netz ist ein Feed Forward Netz, das wahlweise eine SOM als Inputschicht enthalten kann. Die Anzahl der verdeckten Schichten ist beliebig, die Eingangsschicht enthält 313 Neuronen, das Netz hat 6 Ausgabeneuronen. Das eigentliche Problem besteht nun in der Ermittlung einer geeigneten Netzstruktur, so dass das Netz in der Lage ist, sinnvolle Spielentscheidungen zu treffen. Da das Training mittels Backpropagation erfolgt und die Komplexität des Spiels relativ große Trainingsdatensätze (mehrere hundert Pattern) erfordert, gestaltet sich die Findung einer Netzstruktur durch Ausprobieren als schwierig. Weiterhin ist das Training äußerst zeitaufwändig, ein Trainingsprozess mit 4000 Zyklen bei einem durchschnittlich großen Netz dauert ca. 6-8 Stunden.

Da für Rosenkönig, im Gegensatz zu anderen Spielen wie z.B. Schach, keine umfassenden spieltheoretischen (strategischen) Abhandlungen existieren und das Spiel (durch das Ziehen der verdeckten Karten) auch Zufallselemente enthält, ist es schwierig, eine Spielentscheidung zu "berechnen". Zu diesem Zweck wären umfangreiche Analysen nötig gewesen, außerdem handelt es sich bei Rosenkönig um einen Beleg im Bereich der Künstlichen Intelligenz, so dass nach anderen Möglichkeiten gesucht wurde.

Zur Ermittlung einer günstigen Netzstruktur bietet sich vor allem der Genetische Algorithmus als Lösungsmöglichkeit an.

Nutzung Genetischer Algorithmen

Genetische Algorithmen sind in der Lage, auch für hoch komplexe Probleme, die mit anderen Mitteln nicht oder nur extremem Rechenaufwand lösbar sind, sinnvolle Lösungsmöglichkeiten zu finden. Dabei werden in einem Prozess, der dem Evolutionsprozess der Biologie nachempfunden ist, Generationen von sich weiterentwickelnden und mutierenden Lösungsansätzen erzeugt. Durch Ausleseverfahren setzen sich auf lange Sicht die Ansätze durch, die das Problem am besten lösen: Die fittesten Lösungen.

Aus den in der Motivation genannten Gründen sollte mit Hilfe eines Genetischen Algorithmus eine Netzstruktur gefunden werden, die in der Lage ist, auf Grund einer vorgegebenen Spielsituation eine sinnvolle Spielentscheidung zu treffen (mehr zum Aufbau des KI-Spielers ist unter Funktionsweise des Neurospielers zu finden).

Als Basis für die Arbeit mit Genetischen Algorithmen wurde hier das im Rahmen eines weiteren Beleges entstandene Framework GaFrame genutzt. Eine ausführliche Dokumentation zu diesem Framework kann auf der Homepage des Projekts eingesehen werden, auf Details zur Bedienung von GaFrame wird deshalb hier nicht weiter eingegangen.

Chromosom

Der erste Schritt beim Einsatz eines Genetischen Algorithmus besteht in der Überlegung, wie das zu lösende Problem sinnvoll (binär) codiert werden könnte. Im Falle von Rosenkönig sind folgende Aspekte durch den Genetischen Algorithmus zu ermitteln:

  • Soll eine SOM genutzt werden? Wenn ja, wie groß soll sie sein?
  • Wie viele verdeckte Schichten soll das Netz enthalten?
  • Wie groß sollen die einzelnen verdeckten Schichten sein?

Prinzipiell ist die Größe der einzelnen Schichten unbegrenzt, durch Überlegungen bezüglich des Rechenaufwandes wurde die Größe der Schichten jedoch auf maximal 511 Neuronen begrenzt.

Um die genannten Aspekte zu codieren, wurde ein Chromsom der Länge 28 Bit gewählt. Das erste Bit bestimmt, ob als Eingabeschicht eine SOM genutzt werden soll, oder nicht. Die restlichen 27 Bit bestimmen die Größe der (maximal) drei Hiddenschichten, jeweils 9 Bit werden als eine Binärzahl interpretiert. Ist eine Zahl kleiner als 20, wird keine Schicht eingefügt, eine Zahlen n >= 20 wird als verdeckte Schicht mit n Neuronen interpretiert. Falls das erste Bit den Wert 1 hat und die erste 9-Bit-Zahl einem Wert >= 20 entspricht, wird als Eingangsschicht eine SOM der entsprechenden Größe genutzt.

Die Begrenzung auf drei verdeckte Schichten folgt der These, dass diese Schichtentiefe für Feedforward-Netze ausreichend ist, um n-dimensionale Zusammenhänge zu erlernen (siehe z.B. Lippe).

Beispiel
Beispielchromosom

Die nebenstehende Zahlenfolge würde als Netz mit einer SOM der Größe 324 sowie einer Hiddenschicht der Größe 47 interpretiert.

Die Neuronenzahl der dritten Schicht ist mit 10 angegeben, dies wird aber ignoriert, da die Mindestzahl von 20 Neuronen nicht erreicht ist. Es wird also keine weitere verdeckte Schicht hinzugefügt.

Fitnessfunktion

Die Fitness eines Individuums bestimmt, wie groß seine Chancen auf "Weiterleben" und "Vermehrung" sind.

Um im Falle von Rosenkönig die Fitness eines Individuums zu bestimmen, wird nach den im vorherigen Abschnitt genannten Regeln ein Neuronales Netz erzeugt und mit Zufallswerten initialisiert. Dieses Netz wird mit einem Patternsatz von ca. 400 Pattern über einen kurzen Zeitraum (30 Zyklen) mit konstanten Trainingsparametern nach der Backpropagation-Methode trainiert. Nach der Trainingsphase folgt eine Validierungsphase und ggf. ein Nachtrainieren. Wird eine SOM genutzt, so wird diese vorher über 500 Zyklen ebenfalls mit konstanten Trainingsparametern trainiert. Die konkreten Werte sind dem Quelltext der Klasse de.htwdd.rosenkoenig.ga.NetworkFitness zu entnehmen.

Die genannte Zahl an Trainingszyklen mag klein erscheinen, aber ein derartiger Durchlauf benötigt bereits (je nach Netztopologie) 10-30 Minuten, so dass eine weitere Erhöhung der Zyklen nicht sinnvoll erschien.

Nach einem Trainingsdurchlauf werden der Fehler über der Trainingsmenge sowie der Fehler über der Validierungsmenge bestimmt. Aus diesen beiden Werten wird die Fitness des Individuums nach folgender Formel bestimmt:

Fitnessfunktion

Aus der Formel wird klar, dass die Fitness gegen 1.0 läuft, je kleiner Trainings- bzw. Validierungsfehler sind. Weiterhin wird deutlich, dass der Validierungsfehler weniger stark gewichtet ist als der Trainingsfehler.

Ein Individuum mit einer Fitness nahe 1.0 sollte also ein Netz repräsentieren, dass die Trainingsdaten sehr schnell lernt und außerdem fähig ist, zu abstrahieren.

Nachdem die theoretischen Überlegungen abgeschlossen waren, wurde auf der Basis des entstandenen Vorgehensmodells die Klasse de.htwdd.rosenkoenig.ga.NetworkFitness entworfen, die dieses Vorgehen umsetzt und kompatibel zum Framework GaFrame (implementiert de.htwdd.ga.FitnessFunction) ist.

Genetischer Algorithmus (GeneticRosenkoenig)

Die in GaFrame enthaltene Klasse de.htwdd.ga.GeneticAlgorithm steuert den Ablauf eines Genetischen Algorithmus. de.htwdd.rosenkoenig.ga.GeneticRosenkoenig ist eine davon abgeleitete Klasse, die die ursprüngliche Klasse um Log-Ausgaben erweitert und außerdem jede Generation als XML-Datei speichert. Dies soll verhindern, dass bei eventuellen unvorhersehbaren Ereignissen (Rechnerdefekt, Rechner unerwartet von Dritten abgeschaltet) Datenverluste auftreten.

Es werden Zwei-Punkt-Kreuzung, fitnessproportionale Selektion und Elitismus bei einer Mutationsrate von 10% genutzt, die oben erläuterte Fitnessfunktion kommt zum Einsatz.

Da enorme Rechenzeiten zu erwarten waren, lief das Programm zuerst auf der ilux150, die über vier Kerne verfügt. Die Rechenzeit bei für 200 Generationen (Populationsgröße 20) betrug hier ca. 10 Tage. Ein weiterer Durchlauf erfolgte im Clusterbetrieb auf mehreren Rechnern des Labors Z146a (jeweils DualCore Prozessoren).

Auswertung der Ergebnisse

Um die anfallende enorme Datenmenge auswerten zu können, wurde die Klasse de.htwdd.rosenkoenig.ga.PopulationOutputter implementiert, die eine beliebig große Anzahl an XML-Dateien (die während des Evolutionsprozesses entstandenen Generationen) auswerten, nach Fitness sortieren und gut lesbar ausgeben und in ein Logfile schreiben kann.

Mit diesem Werkzeug lässt sich ein Überblick über die Ergebnisse eines Durchlaufs des Genetischen Algorithmus gewinnen und es werden die im Laufe des gesamten Evolutionsprozesses "fittesten" Lösungen zuerst präsentiert. So werden gute Lösungen, die evtl. durch Mutation bereits vor Ende des Durchlaufs ausgesondert wurden, hier trotzdem sichtbar. Individuen, die über mehrere Generationen hinweg überlebt haben, werden nur einmal dargestellt.

Der folgende Logfile-Auszug zeigt einen Teil der Ausgaben des PopulationOutputter (das Gesamtergebnis dieses Durchlaufs war über 1000 Zeilen lang):

2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 496 447 126 	fitness: 0.023848969206630922
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 256 126 	fitness: 0.02373320413969819
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 255 126 	fitness: 0.02358347941846832
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 416 126 	fitness: 0.02355794281414487
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 510 127 	fitness: 0.022940124951524414
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 255 134 	fitness: 0.02291398631241888
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 506 447 126 	fitness: 0.02287942602085891
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 446 125 	fitness: 0.02282521325765836
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 511 130 	fitness: 0.02280552263842655
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 256 127 	fitness: 0.022665045393661747
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 305 127 	fitness: 0.022588571552002053
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 223 127 	fitness: 0.022528424934089658
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 474 178 76 	fitness: 0.022486022127941572
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 181 120 	fitness: 0.022463114088692723
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 304 127 	fitness: 0.022433327808965127
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 185 126 	fitness: 0.022427906281637038
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 257 127 	fitness: 0.02240057013924276
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 317 127 	fitness: 0.022395264899376235
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 440 126 	fitness: 0.022376697025895006
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 508 415 126 	fitness: 0.02235259911845529
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 511 162 	fitness: 0.022349136870794803
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 445 127 	fitness: 0.022333433925070974
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 506 399 126 	fitness: 0.02233138538120193
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 256 94 	fitness: 0.022301239907678995
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 305 127 	fitness: 0.022282541546904414
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 478 261 127 	fitness: 0.022265267213501475
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 384 127 	fitness: 0.022220861769487024
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 384 127 	fitness: 0.022219680209971008
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 382 127 	fitness: 0.022196100546723985
2007-04-03 10:29:59             main INFO  - PopulationOutputter:78 - SOM: false	Netz: 510 387 127 	fitness: 0.02217103349544533
			

Bereits an diesem kurzen Auszug kann man mehrere interessante Dinge erkennen, die sich durch Auswertung des gesamten Durchlaufs (und auch bei weiteren Durchläufen) bestätigt haben:

Die Fitnesswerte sind sehr niedrig

Da die Fitnessfunktion bei geringen Fehlern gegen 1 läuft, liegen auch nach dem Training noch hohe Fehlerraten vor. Dies zeigt, dass die Anzahl der Trainingszyklen zu gering ist, um die angelegten Muster vollständig zu lernen. Es haben sich die Netze durchgesetzt, deren Fehler am schnellsten zurückgeht (die "lernfähigsten" Netze).

Unter den besten Individuen sind nur Netze ohne SOM

Entgegen vorherigen Erwartungen lassen sich die Spielsituationen anscheinend nicht eindeutig klassifizieren. Das deutet darauf hin, dass die auftretenden Situationen und das Verhalten des trainierenden Spielers zu komplex sind, um mittels einer SOM klassifizierbar zu sein.

Große trichterförmige Netze (3 Hiddenschichten, hohe Neuronenzahl) setzen sich durch

Auch dies deutet auf eine hohe Komplexität des vorliegenden Problems hin: Es werden viele Neuronen und eine enorme Anzahl Synapsen benötigt, um die vorhandenen Zusammenhänge zu erlernen.
Trotzdem bleibt die für derartige Neuronale Netze typische Trichterform zumindest teilweise erhalten: Die erste Hiddenschicht ist deutlich größer als die Eingabeschicht, die dritte Hiddenschicht wiederum ist im Vergleich dazu relativ klein.

Beispiel einer Netzstruktur: 313 510 256 126 6

Ein (r)evolutionärer KI-Spieler?

Bereits vor dem Einsatz Genetischer Algorithmen in Rosenkönig hatten wir "nach Augenmaß" Neuronale Netze für KI-Spieler entworfen und diese dann mit den vorhandenen Trainingsdaten trainiert. Dabei wurden verschiedene (meist trichterförmige) Netzstrukturen sowie diverse Kombinationen der Trainingsparameter ausprobiert.

Die Ergebnisse waren allerdings mehr als enttäuschend: Die so entstandenen Spieler ließen oft eine wenig nachvollziehbare Spielweise erkennen, so dass der menschliche Gegenspieler regelmäßig frustriert über die Dummheit seines "Blechgegners" war.

Die schlechten Leistungen der ersten KI-Spieler ließen dann die Idee des Einsatzes Genetischer Algorithmen aufkommen, was zu der auf der vorherigen Seite erläuterten Vorgehensweise führte.

Evolution des Spieler-Gehirns

Bereits die Auswertung der ersten Logfiles nach Durchlauf des Genetischen Algorithmus ließ erkennen, dass die durch künstliche Evolution entstandenen Netze deutlich schneller zu lernen schienen als unsere von Hand erstellten. Nach mehreren Feineinstellungen am Genetischen Algorithmus bestätigte sich diese Vermutung. Die durch Evolution entstandenen Netze hatten allerdings eine andere Struktur als ursprünglich von uns erwartet: Die Schichten waren deutlich größer und es wurde keine SOM als Eingabeschicht genutzt. Dadurch wurde dann auch sofort die miserable Leistung unserer "selbstgestrickten" KI-Spieler klar, die Komplexität des vorliegenden Problems machte eine andere Netzstruktur erforderlich.

Die Ergebnisse des Genetischen Algorithmus mussten nun noch in der Praxis umgesetzt werden: Wir erzeugten KI-Spieler mit den evolutionär entstandenen Netzstrukturen und trainierten diese mit unseren Trainingsdaten.

Dies brachte allerdings auch eine gewisse Ernüchterung: Die so entstandenen Spieler spielten zwar deutlich besser als ihre (quasi ausgestorbenen) Vorgänger, konnten aber mit einem menschlichen Spieler weiterhin nicht mithalten: Taktische Rafinesse und vor allem das Überraschungsmoment gaben den menschlichen Spielern meist einen Vorteil.

Dennoch: Der Einsatz Genetischer Algorithmen hat die KI-Spieler in Rosenkönig deutlich verbessert und sich somit als lohnenswert erwiesen.

Ressourcen

Quellenverzeichnis

Online-Quellen

Die folgenden online verfügbaren Quellen wurden von uns genutzt:

Literatur

Dieser Abschnitt enthält mehrere interessante Bücher, die zu Recherchezwecken herangezogen wurden.

  • Brause, R. Einführung in die Neuroinformatik, Teubner 1995
  • Kratzer, K. Neuronale Netze, Carl Hauser 1990
  • Heaton, J. Introduction to Neural Networks with Java, Heaton Research 2005

Technologien

Im Beleg kommen verschiedene APIs und Bibliothen zum Einsatz, die hier aufgeführt werden.

  • Rosenkönig ist in Java implementiert
  • Die Oberfläche basiert auf der Sprite-Bibliothek Genuts
  • Zur XML-Verarbeitung wird JDOM eingesetzt
  • Die Bibliothek log4j wird für Log-Ausgaben genutzt
  • Für Genetische Algorithmen kommt GaFrame zum Einsatz

Downloads

Note
Um Rosenkönig nutzen zu können, wird eine Java Virtual Machine 1.5.x (oder höher) benötigt. Zum Übersetzen der Quellen sind ein entsprechendes JDK sowie das Buildwerkzeug Ant notwendig.
JavaSE ist z.B. unter java.sun.com erhältlich.
Ant kann unter ant.apache.org heruntergeladen werden.

Binärdistribution

Die Binärdistribution von Rosenkönig steht fertig konfiguriert zum Download bereit. Nach dem Entpacken der ZIP-Datei kann im neu entstandenen Verzeichnis rosenkoenig das entsprechende Startskript run.bat (Windows) oder run.sh (Linux) ausgeführt werden.

Weitere Hinweise zur Bedienung von Rosenkönig finden sich im Benutzerhandbuch und in den Spielregeln.

Quelldistribution

Die Quelldistribution enthält neben den Java-Quellen und benötigten Bibliotheken die Entwicklerdokumentation (Javadoc), die auch UML-Klassendiagramme enthält.

Um Rosenkönig zu kompilieren, muss nach dem Entpacken der ZIP-Datei im Verzeichnis rosenkoenig der Befehl ant compile ausgeführt werden, ant run startet die Applikation.

Die ZIP-Datei enthält außerdem eine Eclipse-Projektdatei, so dass das Projekt auch direkt mit Eclipse bearbeitet werden kann.

Subversion-Repository

Das Projekt wird mittels des Versionsmanagementsystems Subversion verwaltet.

Das entsprechende Repository ist unter http://www.hoelzware.de/svn/rosenkoenig/ erreichbar, der Zugriff kann sowohl per Browser als auch über einen SVN-Client (anonymer Zugriff) erfolgen.

Javadoc

Javadoc wird durch ant erzeugt und ist im PDF nicht enthalten.