Lincoln(Player2)
Neuro-TicTacToe
von Sven Kühne 2004
Gauß(Player1)


Aufgabe

Erstellen eines Beleges(Programm) im Rahmen der Lehrveranstaltung „Neuronale Netze(Prof. Iwe)“ unter Verwendung der behandelten Technik Neuronaler Netze. Ich habe mich entschieden das Netz als KI Gegner in dem bekannten Spiel TicTacToe einzusetzen.

Spiellogik

Es spielen stets zwei Spieler gegeneinander. Es wird abwechselnd ein Feld belegt. Es hat derjenige gewonnen welcher zuerst 3 Felder in einer Linie belegt hat( horizontal, vertikal oder diagonal == 8 Möglichkeiten ). Wenn beide Spieler perfekt spielen darf es keinen Gewinner geben.

Ablauf eines Beispiel-Spiels:
Bild G1 Spielfeld vor Beginn. Gauß ist als Ki-Spieler und Beginner gewählt, Lincoln als menschlicher Gegner. Gauß Beginnt sein durch das NeuronaleNetz gegeben Zug nachdem der Startbutton betätigt wurde.
Bild G2 Gauß(KI-Player) setzt seinen Stein an die linke untere Ecke.
Bild G2B Hier ist nun rechts die Bewertung für jeden der einzelnen moeglichen Zuege zu sehen. Dabei wird dem Netz der Inputvektor angelegt welcher entstuende bei all diesen Zuegen. In diesem Fall waren alle Felder Frei, so mußten hier also 9 Muster angelegt werden. Sind gleiche Bewertungen fuer verschiedene Felder(symetrie-effekt) vohanden wird per zufall eine gewaehlt.
Bild G3 Das ist die Situation nachdem ich als Human-Player(Lincoln) meinen Stein in die Mitte setzte und der KI-Gegener(Gauß) sich fuer das Feld rechts daneben entschieden hat.
Bild G4 Hier der Stand nachdem ich(als Lincoln) seine Dreier-Reihe verhindert habe(oben rechts) und der KI-Gegner wiederum meinen Diagonalen-Dreier verhinderte(links unten).
Bild G5 Anschließend habe ich nun wiederum seinen waagerechten-Dreier verhindert(Zug mittte unten) und der KI-Gegener meinen senkrechten mit seien Zug (mitte-oben).
Bild G6 Der zug von mir(oben rechts) unde rder KI-Gegener Zug darunter koennen nichts mehr bewirken ---> Unentschieden !! Keiner der Spieler konnte eine Dreier-Reihe plazieren.


Muster- Bewertungsstrategie

  • Fuer jeden moeglichen Zug(freies Feld) des KI-Spielers wird ein Netz-Eingabevektor generiert und dem Netz angelegt.
  • Das Ergebnis was dann am Ausgabeneuron anliegt ist die Bewertung für diesen Zug.
  • Die hoechste Bewertung gewinnt und wird ausgefuehrt, bei gleicher Bewertung entscheidet der Zufall.

      Am Beispiel KI-Zug von Bild G4 (spiellogik):
  • 4 Felder sind besetzt und 5 sind noch frei.
  • Fuer diese 5 Moeglichen wird der Eingabevektor generiert und angelegt.
  • Ein- und Ausgabevektor fuer gewinner Zug aus Bild G4(links-unten) : Input( 1 |0 |0 |2 |1 |0 |0,1 |0,1 |0,1 |0 |-1 |0,5 ) Output(0,8425599)
  • Als Ergebnis aller moglichen Zuege erhaelt man hier zB. folgende Bewertungen:
    gehoerig zu Entscheidung Bild G4 (s.o.)
  • Hier ist zu sehen das alle Bewertungen bis auf unten rechts negativ sind.
  • So wird dieser Zug(in diesem Fall vom KI-Spiler Gauß links-unten) schliesslich gesetzt.
      Gewinnung der MusterListen:
    Es gibt mehrere Moeglichkeiten Muster fuer das Training der Netzes zu gewinnen.
  • manuell, nach einem Spielzug gibt man in Seite "Netsettings 2" eine Bewertung ein und fuegt diesen Zug zu einer Liste hinzu.
  • teilautomatisch, waerend des Spielens werden stets die Muster gespeichert und am ende des Spiels wird die Bewertung dieser vorgenommen.
  • automatisch, waerend der Computer automatisch gegen sich selbst spielt(SingleNet oder DoubleNet Trainig) werden die Muster gesammelt und bewertet.

    Da bei den automatischen Varianten einige Eingabevektoren doppelt oder haeufiger vorkommen koennen(bedinngt durch symetrie) gibt es die Moeglichkeit die ueberzaehligen zu entfernen( Button "Sym" siehe GUI --> Man.Pattern(NetSettings 2) ). Weiterhin koennen Listern natuerlich geladen, gespeichert und verschmolzen(Button "++") werden. Sollte man die Anzahl der In- bzw Outputneuronen geaendert haben muß man auch darauf achten entsprechende Musterlisten zu waehlen ansonsten kann es zum Anwendungsfehler kommen.

      Symetrien:
    Symetrische Muster sind Muster mit gleichen Inputvektor aber unterschiedlichen Spielfeldaufstellungen. Zum Beispiel wenn das Spielfeld leer ist, ist es egal in welcher Ecke der Stein sich befindet, die Inputvektoren sind gleich.
    Moechte man das das Netz effektiv und schnell lernt so sollten die symetrischen Muster entfernt werden( Button "Sym" in Man.Pattern-Page(NetSettings2) ). Allerdings ist bei dieser Variante darauf zu achten das die Bewertung auch zu 100% stimmt. Das Bedeuted manuelle Mustergenerierung und ein mehr an Arbeitsaufwand. Laesst man hingegen Symetrische Muster zu, heben sich gegensaetzliche Bewertungen zum Teil wieder auf, natuerlich wird der Netz-Fehler dabei nicht so gering ausfallen. Dafuer ist es bei weitem benutzerfreundlicher, da Muster automatisch generiert werden koennen.
      Aufbau des Eingabe-Vektors:
  • 1 .. Player 1 Einer
  • 2 .. Player 1 Zweier
  • 3 .. Player 1 Dreier
  • 4 .. Player 2 Einer
  • 5 .. Player 2 Zweier
  • 6 .. leer
  • 7 .. mixed Zweier / 10
  • 8 .. mixed Dreier / 10
  • 9 .. free Lines / 10
  • 10 .. free Corners / 2 - 1
  • 11 .. free Center * 2 - 1
  • 12 .. free Fields / 10

      Ausgabe-Vektors:
  • 1 .. Bewertung des durch die Input-Neuronen repräsentierten Spielzugs

    • Neuronales Netz

      Zum erlernen der Spielzuege verwende ich ein Neuronales Netz(31 Neuronen) mit :
  • 12 Eingangsneuronen,
  • 12 Neuronen im 1. HiddenLayer,
  • 6 Neuron im 2. Hidden Layer und
  • einem Ausgabeneuron.

    Es hat sich gezeigt das mit diesem Aufbau relativ gute Ergebnisse zu erziehlen sind im Gegensatz zu Architekturen mit weniger(8 Eingabeneuronen) oder mehr(28 Eingabeneuronen) Neuronen.
    Verschieden Parameter des Netzes und der Lernstrategie sind vom Nuter veraenderbar. So sind einige Netztopologien unter "Net Settings/Teach Properties/NeuroNetInputType" einstellbar. Zum Beispiel: Gesamt-Neuronenanzahl 31, 25, 51, 69, 47, 55

      Als Standart Parameter verwende ich folgende Werte:
  • Aktivierungsfunktion :   ArcTanH
  • TeachingFactor :   0,07
  • AlphaFaktor :   0,5  (in diese Konfiguration nicht wichtig, nur bei MomentumUpdate)
  • BatchCycles :   2   (in diese Konfiguration nicht wichtig, nur bei Batchlearning)
  • MaxError(Cancel Threshold) :   0,10
  • TechCycles :   20000
  • UseBias :   True
  • NeuronsPerLayer :   12/12/6/1
  • NetType :   Standart Backpropagation

      Standart Backpropagation Lernalgorithmus


    Fuer weitere Informationen sieh Uebungs-Skript von Prof. Iwe.

      TanH Activierungsfunktion:
    Diese Activierungsfunktion habe ich hauptsaechlich verwendet, da ich schon mit dem XOR Beispiel sehr gute Ergebnisse damit erziehlte. Zudem ist der Wertebereich für die Activierung von -1 bis 1.


      Logistische Activierungsfunktion:
    Wird noch nicht vollständig unterstuetzt, da in der Anwendung automatisch Muster erzeugt werden mit Bewertungen zwischen -1 und 1. Dies muesste noch geaendert werden um diese Funktion voll einzusetzen. Aber bei der Manuellen Mustergenerierung ist dies schon moeglich.


      Fehlerbestimmung:
    Ich summiere die Fehler stets über alle Ausgabeneuronen und alle Muster und Dividiere anschließen durch die Ausgabeneuronenanzahl und Musteranzahl. So erhalte ich einen Durchschnittlichen Fehler, den ich fuer ueberschaubarer halte.

      Lernvorgaenge:
    Je nach Qualitaet der Muster und der Initialisierten Gewichte kann es zu unterschieden in der Lerngeschwindigkeit, Errorentwicklung kommen. Man sollte den Maximalen-Error nicht zu niedrig waehlem da sich einige Muster(speziel die automatisch generierten) evtl. wiedersprechen.

    Ausser dem Lernen durch anlegen einer festen Musterliste an das Netz gibt es noch die Moeglichkeiten waerend des Spiels automtisch weiter zu lernen oder das Netz gegen sich oder ein zweites Netz spielen und lernen zu lassen.

    • Implementierung

  • 2 Hauptklassen tragen den groessten Teil der Funktionalitaet, NN(fuer das Netz) und GameTTT(fuer das Spiel)
  • es gib noch einige kleinerer Hilfsklassen zur serialisierung, zum Daten halten oder Edit-Forms(Hilfsfenster) die hier nicht weiter interresieren.

    In dieser Klasse ist der Hauptteil der Funktionalität eines Neuronalen Netzes implementiert. Wobei nicht alle features in dieser TicTacToe-Anwendung genutzt wird.
    Mit Hilfe diser Klasse kann ein beliebig großes Feed-Forward Netz verwaltet werden,also mindestens einem Input- und Output-Layer und beliebig vielen Hidden-Layer(0-n). Es besteht aber auch die möglichkeit jedes Neuron mit jedem zu verbinden, worauf ich bei dieser Anwendung aber nicht zurueckgegriffen habe. Es wir das standart-Backprpagation sowie die Techniken des Batchlearning und Momentumupdates unterstützt. Als Aktivierungsfunktionen stehen "TanH" und "Sigmoid-Logistic" zur verfügung. Die Muster könne sowohl Gleichverteilt als auch Linear waerend des Lernprozesses angelegt werden. Über einen Maximalen Fehler oder "cancelThreshold" kann festgelegt werden bis zu welcher Genauigkeit das Netz lernen soll, wenn die Anzahl der Durchlaeufe(Cycles) gross genug gewaehlt wurde.

    Die Klasse enthaelt mehrere ein- und zweidimensionale Arrays um die Daten zu halten und effektiv die Berechnungen durchfuehren zu koennen.
  • w[von][zu] ... Gewichtsmatrix
  • d[von][zu] ... Delta Gewichte
  • tw[von][zu] ... Gewichtsmatrix für Batchlearning
  • pw[von][zu] ... letzen Gewichte fuer MomentumUpdate
  • connest[von][zu] ... Verbindungsmatrix
  • a[neuron] ... Aktivation
    und noch ein paar mehr.

    Fuer das Forward-propagation wird nun Layer fuer Layer die Neuronaktivation berechnet beginnen mit dem Inputlayer.
    Fuer das Back-propagation wird nun der Fehler einfach zurueckverteilt, beginnend mit den Neuronen des Outputlayer.

      Class GameTTT
    Diese Klasse ist fuer das Spielmanagement verantwortlich. Das Bedeutet:
  • Verwaltung der Spieloptionen und der Spielvisualisierung(GUI)
  • Umwandlung des Spielfelds in einen Eingabevektor fuer das Netz und auswerten der Ergebnisse
  • Pruefen der menschlichen Zuege und ob das Spiel endete und wer gewonnen hat.
  • Verwaltung und Bearbeitung der Musterlisten(zB. Entfernen Symetrischer Muster)
  • Steuerung des Lernprozesses, was und wie soll gelernt werden.
  • Hier wird auch versucht zum Spielbeginn ein gutes Netz(AGoodNet_12_1.tnet)
  • Und die zwei Musterlisten AGoodPatternList_12_1.tpat(enthaelt symetrische Muster, ueber 600 Muster) und PatListWithoutSym_12_1.tpat(vorherige Musterliste symetrie bereinigt, 123 Muster) zu laden.

    • GUI(Bedienoberflaeche)

    GameSettings (GameControl) :
    Hier sind die einfachen Spieloptionen untergebracht. Wie etwa, wer soll beginnen und übernimmt der Computer(NeuroNetz) oder der Mensch den jeweiligen Spieler. Sollte der Computer(KI bzw. NeuroNetz) beginne muss zum Spielstart der „Start-button“ unten rechts betätigt werden. Links befindet sich immer das Spielfeld.

    TeachControl (NetSettings 1):
    Auf dieser Seite sowie über das Datei-Menü kann ein Netz geladen, gespeichert oder reinitialisiert werden. Weiterhin erfolgt hier die Kontrolle über das Lernen. Es kann eine Pattern-Liste ausgewählt werden und diese dem Netz übergeben werden.

    Man. Pattern (NetSettings 2):
    Hier erfolgt im wesentlichen die Verwaltung der Musterlisten(laden, speichern, leeren, löschen, addieren oder symetrie-entfernen). Zusätzlich wird festgelegt wie und womit die Listen gefüllt werden, manuell oder automatisch bei verschiednen Spielvarianten. Unten besteht die Moeglichkeit manuell ein Zug hinzuzufuegen, wobei es moeglich ist symetrien zu ueberschreiben oder auch nicht.

    Teach Properties (NetSettings 3):
    Eine handvoll weiterer Optionen zum sammeln der Muster und Steuern des Lernvorgangs. Ueber NeuroNetInputType koennen vordeffinierte Netztopologien gewaehlt werden(mit Neuronenanzahl 31, 25, 51, 69, 47, 55).

    Net Properties (NetSettings 4):
    Hier können die Parameter des Netzes kontrolliert oder verändert werden, wie Lernfaktor, Lernduchgaenge(Cycles) oder der maximal tollerierte Fehler. Allerding kann die Netztopologie hier nur gering manipuliert werden, zB: keine Layer hinzufuegbar, Aenderung Input-Output Neuronenanzahl kann zu Problemen fuehren.

    ErrorGraph:
    ErrorGraph Nach abgeschlossenen „Pattern Training“ kann man sich hier die Entwicklung des Fehlers anschauen.

    Bewertung:
    Hier kann man waehrend des Spiels verfolgen wie die KI die einzelnen Zuege(Moeglichkeiten) bewertet.


    Download

    Die Anwendung incl. Dokumentation leigt    HIER    gepackt(.zip) breit. Die Gesamtgroesse betraegt ca. 2 MB
    Um die Anwendung zu starten muss diese einfach wieder entpackt werden und anschließend die "GameTTT.exe" ausgeführt werden.

    Entwicklungsumgebung

    Diese Programm wurde in Programmiersprache C# mit dem Visual Studio 2003 erstellt. Die verwendeten Bilder wurden eingescannt und mit Adobe Photoshop bearbeitet. Mit einem einfachem Editor wurde die Dokumentation erstellt.

    Systemvorraussetzungen

    Die Anwendung benötigt die 1.1. DotNet Runtime zur Ausführung. Weiterhin wird empfohlen ein PC mit mind. 1Ghz und 128 MB RAM plus Betriebssystem ab Win95.

    Fazit

    Es erforderte eine Ganze Menge an Aufwand gute Muster- und Bewertungsstartegien zu finden und sich fuer eine optimale zu entscheiden. Wohingegen das Netz an sich weniger ein Problem darstellte. Der aktuelle Stand des Netzes(welches defaultmaessig geladen wird) ist soweit ich getestet habe optimal, d.h. Man kann nicht als Sieger hervorgehen in einem Match Mensch gegen KI. Auch KI gegen KI laesst kein Gewinner/Verlierer zu, wie es bei perfekten Spielern sein musss.

    Von den Musterstrategien bleibt nur die Entscheidung zwischen
  • Effektiven-Lernen(ohne Symetrische Muster) + Mehrauffwand in der Mustergenerierung da moeglichst manuell
  • oder Langwierigeres Lernen + einfache, automatische Mustergenerierung(symetrische Muster moeglich).

    • Quellen

  • Main_Doc Java classes by Tsvi Dvorkind.( Wurde von mir nicht weiter beachted aufgrund zu schlechter Ergebnisse seiner Anwendung )


    • Umfeld

    Author:
    Sven Kühne
    svenk7@web.de
    Fachbereich :
    Informatik an der HTW-Dresden
    ia99 041/02
    Lehrveranstaltung :
    Neuronale Netze (Prof. Iwe )
    Datum :
    13.01.2004