\documentclass[a4paper,titlepage, 10pt, fleqn]{article}

% Times-New-Roman font
\usepackage{times}
\usepackage{graphicx}

% german spelling and strings
\usepackage{german}
\selectlanguage{austrian}


% usage of umlauts without the crazy TeX escapes
\usepackage[latin1]{inputenc}


% use parskip instead of parindent
\setlength{\parskip}{5pt plus 2pt minus 1pt}

% set page parameters
\textheight	      680pt
\textwidth	      460pt
\topmargin	      -40pt
\oddsidemargin	   5pt
\evensidemargin	5pt
\parindent	      0pt



%
%
\begin{document}
%

%
%
% titlepage
%

\begin{titlepage}

\begin{center}
% universität
\vfill
{\Large Universität~Salzburg, Institut~für~Computerwissenschaften }

% lehrveranstaltung
\vfill
{\Large Proseminar Programmierpraktikum I \\ Sommersemester 1999}

% titel
\vfill
{\Huge Spiele mit Künstlichen Neuronalen Netzwerken (KNN)}

% autoren
\vfill
{\large \begin{tabular}{rl}
Wiesbauer~Gerald & \underline{gerald.wiesbauer@sbg.ac.at} \\
Stürzlinger~Manuela & \underline{mstuerz@cosy.sbg.ac.at} \\
Rettenbacher~Christopher & \underline{cretten@cosy.sbg.ac.at} \\
Mayer~August & \underline{ags@gmx.net}\\
 & \\
Projektbetreuer: \\ Dipl.Ing.~Mag.~Roland Schwaiger & \underline{rschwaiger@cosy.sbg.ac.at}
\end{tabular} }

% projektbetreuer
\vfill
{\large }

\vfill
{\Large Version vom \today }

\end{center}

\vfill
\end{titlepage}

%
%
% abstract
%

\begin{abstract}

Dieses Dokument beschreibt die Planung und Implementierung eines Back\-gammon-Spiels mit Java,
wobei der Computergegner durch ein neuronales Netzwerk möglichst spielstark sein soll.

\end{abstract}





\tableofcontents
\newpage




\section{Einleitung}
\subsection{Spielregeln Backgammon\cite{Heyken-96}}

\subsubsection{Spielidee}
Backgammon ist ein Spiel, bei dem zwei Spieler mit jeweils 15 Steinen auf einem
Brett mit 24 Feldern spielen.Ziel des Spieles ist es, alle Steine vom Brett ins
Aus zu spielen. Die Spielsteine haben eine bestimmte Startposition und m"ussen von dort aus alle in das Heimfeld gezogen werden. Das sind bei Wei"s die Felder 1 bis 6, bei Schwarz die Felder 19 bis 24. Die Spieler ziehen deshalb immer in entgegengesetzte Richtung (Wei"s von 24 nach 1; Schwarz von 1 nach 24), wobei sie auf ihrem Weg durch Blockaden des Gegners behindert werden k"onnen.
Sind alle Steine im Heimfeld versammelt, dann k"onnen sie ausgespielt, das hei"st durch w"urfeln aus dem Spiel genommen werden. Wer zuerst keine Steine mehr auf dem Brett hat, hat gewonnen.


\subsubsection{Würfeln und Ziehen}

Jeder Spieler würfelt vor seinem Zug mit zwei W"urfeln und zieht die geworfene Augenzahl vorw"arts (niemals r"uckw"arts!).Als Beispiel nehmen wir an, Wei"s hat in der Ausgangsstellung 6+5 geworfen. Er kann jetzt entweder zwei Steine mit jeweils einer Zahl (13 auf 7 und 13 auf 8) oder nur einen Stein mit beiden Zahlen spielen(24 auf 13). Welche der beiden Zahlen der Spieler dabei zuerst zieht, kann er sich aussuchen. Der Wurf mu"s aber immer vollst"andig ausgef"uhrt werden, wenn das nicht durch eine Blockade des Gegners verhindert wird. Dabei darf man beliebig viele Steine seiner Farbe auf ein Feld stellen.\\
W"urfelt man zwei gleiche Zahlen, so nennt man dies einen 'Pasch'. Wird ein Pasch geworfen, gilt folgende Sonderregel: Die Augenzahl ist viermal auszuf"uhren- mit einem, zwei, drei, oder vier Steinen.

\subsubsection{Blockierte Felder}
Ein Feld ist blockiert, wenn dort zwei oder mehr Steine des Gegners stehen. Auf ein blockiertes Feld kann nicht gezogen werden, man darf es jedoch "uberspringen. Kann nur eine der beiden gew"urfelten Zahlen ausgef"uhrt werden, mu"s die h"ohere Zahl ziehen.


\subsubsection{Schlagen}
Steine k"onnen nur geschlagen werden, wenn sie einzeln auf einem Feld stehen. Ein geschlagener Stein wird auf die Bar gestellt, das ist der Balken zwischen den Bretth"alften. Im n"achsten Zug mu"s er -wenn m"oglich- wieder ins Spiel gebracht werden.

\subsubsection{Wiedereinbringen geschlagener Steine}
Wenn ein geschlagener Stein auf der Bar steht, mu"s er zun"achst wieder ins Spiel gebracht werden, bevor man mit einem anderen ziehen darf. Geschlagene Steine m"ussen von der Bar ins Heimfeld des Gegners gespielt werden. Hierbei landet ein Stein bei einer 1 auf dem 1er(24er) Punkt, usw. Auf vom Gegner blockierte Felder darf nicht gezogen werden.
\subsubsection{Ausspielen}
Mit dem Ausspielen darf erst begonnen werden, wenn alle 15 Steine im eigenen Heimfeld sind. Man spielt dabei so als g"abe es ein Feld 0, auf das alle Steine ziehen m"ussen. Sind von den h"oheren Punkten alle Steine ausgespielt,so m"ussen die entsprechenden Zahlen vom n"achst niedrigeren Punkt ins Aus gespielt werden.
\subsubsection{Gammon und Backgammon}
Ein Spiel ist Gammon gewonnen, wenn eine Partei alle 15 Steine, der Gegner aber noch keinen Stein ausgespielt hat. Ein mit Gammon gewonnenes Spiel z"ahlt doppelt.\\
Hat der Sieger alle 15 Steine abgetragen, w"ahrend er Gegner noch einen Stein auf der Bar, oder im Heimfeld des Siegers hat, dann z"ahlt das Spiel dreifach, er hat Backgammon gewonnen.
\subsubsection{Spielbeginn}
Zu Beginn der Partie w"urfeln beide Spieler jeweils mit einem W"urfel. Der Spieler der die h"ohere Zahl hat beginnt die Partie mit dem sich ergebenden Wurf.
\subsubsection{Dopplerw"urfel}
Zu jedem Spiel geh"ort ein W"urfel, der auf seinen Seiten die Zahlen 2, 4, 8, 16, 32 und 64 hat. Glaubt ein Spieler einen klaren Vorteil zu haben, nimmt er den W"urfel und legt ihn mit der 2 oben auf die Spielfl"ache. Sein Gegner kann nun aufgeben, dies w"urde ihn einen Punkt kosten. Nimmt er die Herausforderung an, erh"alt er das alleinige Recht, bei einer Wende im weiteren Spielverlauf, ebenfalls zu verdoppeln. Auch diese Herausforderung kann angenommen, oder abgelehnt werden. Der Spielwert verdoppelt sich jedes mal.


\subsection{Neuronale Netze\cite{Hoffmann-93}}

\subsubsection{Biologische Grundlagen}

NN k"onnen als technische Umsetzung der Gehirnfunktionen verstanden werden.
Der Aufbau der Nervenzellen in Gehirn weicht in auff"alliger Weise von
dem aller anderen Zellen des K"orpers ab. Sie besitzen sogenannte
Dendriten und Axone, die durch Synapsen verbunden sind. Dadurch entsteht
zwischen den verschiedenen Neuronen eine hochgradige Vernetzung. Die synaptischen Verbindungen "andern sich im Laufe der Zeit, d.h. neue Synapsen entstehen
und alte verk"ummern. Wenn ein Neuron aktiv ist, so feuert es kurze Spannungsspitzen, sog. Aktionspotentiale, die sich "uber das Axon zu den Synapsen fortpflanzen,ab. \\
Zum Begriff des KNN gelangt man, wenn man die beschriebenen Vorg"angen zu einem
stark vereinfachten, abstrakten Modell zusammenfa"st:
\begin{enumerate}
\item Aufbau einer Nervenzelle: Eine Nervenzelle besitzt viele Eing"ange, n"amlich die synaptischen Verbindungen, und einen Ausgang, n"amlich das Axon.
\item Zust"ande einer Nervenzelle: Eine Nervenzelle kann zwei Zust"ande annnehmen: den Ruhezustand und den Erregungszustand.
\item Verbindungen der Nervenzellen untereinander: der Ausgang einer Nervenzelle f"uhrt zu den Eing"angen anderer Nervenzellen.
\item Eing"ange des Nervensystems: Einige Nervenzellen (z.B. Sinneszellen) k"onnen durch Umweltreize erregt werden.
\item Ausg"ange des Nervensystems: Einige Ausg"ange von Nervenzellen wirken("uber Muskelzellen) auf die Umwelt ein.
\item Erregungsbedingung. Eine Nervenzelle geht in den Erregungszustand "uber,
wenn gen"ugend viele ihrer Eing"ange mit erregten Nervenzellen verbunden sind.
\item Unabh"angigkeit der Nervenzellen: Der Zustand einer Nervenzelle ist allein durch die Verh"altnisse an ihren Eing"angen bestimmt. Die einzelnen Zellen arbeiten also unabh"angig voneinander.

\end {enumerate}

\subsubsection{K"unstliche neuronale Netze}
\begin{enumerate}
   \item Aufbau neuronaler Netze\\
    
         Die Nachahmungen von biologischen Neuronen-Netzen werden künstliche neuronale Netze (KNN) oder
         vereinfacht neuronale Netze (NN) genannt. Dabei werden in Anlehnung an die Natur die Dendriten, der
         Zellkern, das Axon und die Synapsen nachempfunden.\\

         Der künstliche Zellkern, auch Neuron, Element oder Unit genannt, besteht aus einem zeitabhängigen
         Aktivierungszustand $a_i(t)$ , der den Grad der Zellaktivierung mit einem reellwertigen, skalaren Wert angibt.
         Diese Zahl läßt sich über die Aktivierungsfunktion $f_a$ berechnen mit: \\
         
         \begin{displaymath}
         a_i(t+1)=f_a(a_i(t),net_i(t),O_i)
         \end{displaymath}

                                                                                        


         Wobei $a_i(t)$ die ursprüngliche Aktivierung des Neurons ist, $net_i(t)$ der Netzeingabe von anderen Neuronen
         und i dem Schwellenwert entspricht, bei dem das Neuron aktiv wird. Die Ausgabe O des Neurons i wird über
         die Ausgabefunktion $f_o$ mit dem Parameter Aktivität bestimmt: \\
         
         Ein neuronales Netz besteht aus verschiedensten Verknüpfungen zwischen den einzelnen Neuronen und
         kann als ein gewichteter, gerichteter Graph angesehen werden, da er einen Eingabevektor auf einen
         Ausgabevektor abbildet.\\

         Die Verknüpfung von oben beschriebenen Neuronen mittels Verbindungen nennt man Netzwerkarchitektur,
         -struktur oder -topologie. Zur Beschreibung einer bestimmten Architektur gehören nicht nur die Neuronen
         und ihre Verbindungen, sondern auch das Gruppieren einer Anzahl von Neuronen innerhalb eines
         Netzwerkes. Diese Gruppierungen werden Schichten (engl. layers) oder Ebenen genannt. \\

   \item Netzwerktypen\\

         Die unterschiedlichen Netzwerktopologien lassen sich in zwei Kategorien einteilen: 
     \begin {enumerate}
        \item Netzwerke ohne Rückkopplung \\

          Bei dieser Architektur werden die Informationen von der ersten Schicht
          (Eingabeschicht) über die zweite Ebene (verdeckte Schicht, engl. hidden
          layer) zur Ausgabeschicht geleitet (siehe Abb. 2.2.3). Die Anzahl der
          verdeckten Schichten, deren Aktivität im Allgemeinen versteckt bleibt,
          kann dabei variieren und auch Null betragen. Es gibt jedoch keine
          Verbindung von einer höheren zu einer der vorgelagerten Ebenen, sowie
          keine in sich rückgekoppelten Informationsflüsse eines einzelnen
          Neurons. Solch ein Netzwerk wird als feedforward-Netz bezeichnet und kann auch Verknüpfungen besitzen,
          die eine Schicht überspringen. Diese Verbindungen werden shortcut connections bezeichnet. \\



          Ein vollständig ebenenweise verbundenes,vorwärtsgerichtetes, neuronales Netz (feedforward) \\

        \item  Netzwerke mit Rückkopplung \\

           Das abgebildete neuronale Netz besitzt im Gegensatz zum feedforward-Netz auch
           Verbindungen, die einen rückwärts gerichteten Informationsfluß zulassen. Sie werden auch Hopfield- oder
           feedback-Netze genannt und besitzen nur eine Ebene, die sowohl als Eingabe- als auch als Ausgabeschicht
           dient. Desweiteren existieren Netzwerke mit speziellen Rückkopplungen zwischen den einzelnen Neuronen
           einer Ebene (lateral feedback), nur zwischen nebeneinanderliegenden Schichten (indirect feedback) und
           einzelner Neuronen mit sich selbst (direct feedback). \\

           Ein vollständig verbundenes, neuronales Netz (feedback); \\
     \end{enumerate}
  \item Lernverfahren \\

         Wählt man eine bestimmte Netzwerkarchitektur aus, so muß dem neuronalen Netz mitgeteilt werden, wie es
         die Eingabeparameter behandeln soll und wie das Ergebnis an der Ausgabeschicht auszusehen hat. Das
         Angehen und Lösen dieser Aufgabenstellung wird, wie beim Menschen, durch eine Lernphase vollzogen. Die
         Trainingsphase eines neuronalen Netzes zur Bestimmung der Eingabe-Ausgabe-Beziehung läßt sich in drei
         Verfahren unterteilen:\\ 
    \begin{itemize}
  
      \item Überwachtes Lernen (engl. supervised learning) 

         Dies ist die schnellste Lernmethode, bei der man dem neuronalen Netz Eingaben und die zugehörigen,
         gewünschten Ausgaben präsentiert. Durch die Minimierung des Fehlers zwischen berechneter und
         angegebener Ausgabe lernt es Ein- und Ausgabe aufeinander abzubilden und auf unbekannte, aber ähnliche
         Eingabemuster mit richtigen Ausgaben zu antworten (Generalisierung)\\
      \item Bestärkendes Lernen (engl. reinforcement learning) \\

         Bei diesem Verfahren wird dem neuronalen Netz nicht die exakte, zu erwartende Ausgabe mitgeteilt, sondern
         nur, ob die berechnete Lösung richtig oder falsch ist. Dies ist aus biologischer Sicht sicherlich eine plausible
         Methode, die jedoch mit sehr viel Zeitaufwand verbunden ist, da die zu trainierenden Netze weniger
         Informationen zur Änderung ihrer Parameter besitzen. In Zukunft sollen Untersuchungen durchgeführt
         werden, die dieses Lernverfahren auf Netze mit a priori Wissen anwenden, um die Trainingsphase zu verkürzen;\\
      \item Unüberwachtes Lernen (engl. unsupervised learning) 
         
         Hier werden dem Netz nur die zu berechnenden Eingaben zugeführt. Ohne das Wissen einer gewünschten
         Ausgabe findet es selbständig Zusammenhänge zwischen den einzelnen Eingaben und entwickelt
         entsprechende Ausgaben. Das neuronale Netz versucht, Gruppen ähnlicher Eingabevektoren zu
         identifizieren und sie dann auf Gruppen ähnlicher oder benachbarter Zellen abzubilden. Ähnliche
         Strukturen, auch topologieerhaltende Karten genannte, Netzwerke sind schon biologisch bei
         Säuglingsgehirnen im visuellen Kortex nachgewiesen worden.\\      
         
         Während des Lernvorgangs verändern sich interne Parameter des neuronalen Netzes, durch die die
         Erfahrungen, wie das Wissen beim biologischen Vorbild, gespeichert werden. Das anzulernende Netz ist also
         in der Trainingsphase ein dynamisches System, bei dem die Konvergenz auf ein gewünschtes Netzverhalten,
         also eine bestimmten Ausgabe, angestrebt wird. Um dies zu erreichen, können verschiedene Parameter eines
         Netzes angepaßt werden: \\
           \begin{enumerate}
             \item Modifikation der Verbindungsstärken 
             \item Änderung der Schwellenwerte und internen Funktionen 
             \item Hinzufügen oder Löschen von Neuronen 
           \end{enumerate}
    \end{itemize}

\item Einsatzmöglichkeiten u.  Problematik \\

         Der entscheidende Schritt ist, die Anzahl der Zellen und der Verknüpfungen festzulegen. Dies ist im allgemeinen
         der schwierigste und wichtigste Prozeß beim Aufbau eines neuronalen Netzes, da mit ihm festgelegt wird, wie
         viele unterschiedliche Klassen vom Netz separiert werden können. Es gibt leider nur empirische Studien über
         die notwendige Anzahl von Verknüpfungen und Neuronen, so daß es bislang nicht möglich ist, die exakte
         Anzahl der Elemente vorauszuberechnen.\\     

         Da neuronale Netze auf Grund ihres Generalisierungsvermögens immer eine gewisse Ungenauigkeit in ihren
         Ausgaben besitzen, werden sie im allgemeinen nicht für Probleme, die exakte Lösungen benötigen, eingesetzt.
         Vielmehr haben sie gegenüber gewöhnlich programmierten Programmen den Vorteil, hochdimensionale
         Aufgabenstellungen klassifizieren zu können. Dies betrifft Anwendungen, in denen der Zusammenhang der
         einfließenden Parameter schwer zu beschreiben oder gar nicht zu bestimmen ist. Zudem sind sie durch ihre
         Generalisierung in der Lage, zwischen den bekannten Daten zu interpolieren und bedingt zu extrapolieren. \\

\end{enumerate}

\newpage
\section{OO-Design und Analyse}

\subsection{Use-Case-Diagramm}

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=14cm]{usec1.eps.gz}
\end{center}
\caption{Use-Case-Analyse des Problems.}
\label{fig:usec1}
\end{figure}

\newpage
\subsection{Klassendiagramm}

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=14cm]{class1.eps.gz}
\end{center}
\caption{Klassendiagramm von GammonApp.}
\label{fig:class1}
\end{figure}

\newpage
\appendix


%
%
% Glossar
%

\section{Glossar}

\begin{description}

\item ["'abfeuern"':] ~ \\
Das Umschalten des Ausgangs der Neuronen von 0 auf 1 wird als "'feuern"'
bezeichnet. 

\item [Algorithmus:] ~ \\
Eine Rechenvorschrift.

\item [Back-Propagation Networks:] ~ \\
Neuronale Netze die das Fehlersignal speziell auf die einzelnen Neuronen 
aufteilen.

\item [Exzitatorisches Signal:]~\\
von lat. excitare=anregen; Signal, das ein Neuron anregt, zu feuern. Siehe auch
Inhibitorisches Signal.

\item [Fehlersignal:] ~ \\
Ein Signal das den Neuronen anzeigt ob sie etwas falsch machen. Auch als 
Residualvektor bezeichnet.

\item[Gewicht (weight)] ~ \\
   Parameter, der die Stärke der Verbindung zweier Neuronen beschreibt.
\item [GUI:] ~ \\
Graphical User Interface, die von Benutzer sichtbare Oberfla"che des Programmes.

\item [Hopfield-Netz:] ~ \\
Neuronales Netz mit bidirektionalen Verbindungen zwischen den Neuronen.

\item [Inhibitorisches Signal:] ~ \\
inhibit = hemmen, ein Signal welches ein Neuron vom "'feuern"' abha"lt. Gegensatz
dazu: Exzitatorisches Signal.

\item [JAVA:] ~ \\
Eine objektorientierte Programmiersprache.

\item [Künstliche neuronale Netze:] ~ \\
Ein auf den Computer simuliertes neuronales Netz.
   
\item[Neuron] ~ \\
   Biologie: signalverarbeitende Nervenzelle, besteht aus Dendriten (Eingangsfasern), Axonen (Ausgangsfasern)
   und Zellkörper.

\item [Rückkopplung:] ~ \\
Speziell bei den KNN eine Rückverbindung vom Ausgang eines oder mehrerer Neuronen
zurück zu den Eingängen derselben. Rückgekoppelte Netze können nicht mehr seriell durchgerechnet
werden, sondern müssen iteriert werden, d.h. es müssen alle Neuronen mehrfach mit den aktuellen
Eingangswerten berechnet werden, bis eine definierte Endsituation eintritt (z.B. keine Änderung
der Aktivierungszustände mehr).

\item [TD-Gammon:] ~ \\
Implementierung des TD-Algorithmus in ein Backgammon Spiel, durchgeführt von Gerald Tesauro für IBM.


\end{description}


\section{Protokolle}



\subsection{Protokoll vom 10. März 1999}


\begin{itemize}
\item {\bf Projekt:} ~Backgammon mittels Artificial Neural Networks
\item {\bf Ort:} ~Hr. Schwaigers Büro
\item {\bf Zeit:} ~$18^{00}$
\item {\bf Anwesende:}
 
     \begin{itemize}
     \item DI Mag.Roland Schwaiger
     \item August Mayer
     \item Gerald Wiesbauer
     \item Christopher Rettenbacher
     \item Manuela St"urzlinger
     \end{itemize}

\item {\bf Protokollf"uhrerin:} ~Manuela St"urzlinger
\item {\bf Themen:}
     \begin{itemize}
     \item Wiederholung des administrativen Teils
     \item Quellen fuer Lehrmaterial(Java,UML,HTML,Latex)
     \item Pr"asentation der Web-Site unserer Projektgruppe
     
     \item Informationsmaterial\\
     \mbox{\glqq Temporal Difference Learning  and TD-Gammon\grqq}\\
     \glqq Neural Networks \grqq (s.S. 66) by M"uller, Reinhardt
     
     \item Besprechung des Dokumentaufbaus bis Punkt Protokolle
     \end{itemize}

\item {\bf Aufgaben}
     \begin{itemize}
     \item Fotos der Projektmitarbeiter (fur Web-Site)
     \item Auseinandersetzen mit den Zeitungsartikel\\
     ev. auftauchende Fragen in Punkt Literaturuebersicht des Dokumentes vermerken
     \item Ausarbeitung des Dokuments bis Punkt Einleitung
     konkret:
          \begin{itemize}
          \item Titelseite\\
          Name des Projekts\\
          Name der Projektmitarbeiter\\
          \item Abstract\\
          kurze und pr"agnante Beschreibung des Projekts\\
          \item Einleitung\\
          Was ist Backgammon?\\
          Wie lauten die Spielregeln?\\
          Erscheinungsbild des Spielbrettes\\
          \end{itemize}
     \end{itemize}

\item Ziele bis n"achste Woche

    \begin{itemize}
    \item Gestaltung der Web-Site(Fotos)
    \item Lesen des Zeitungsartikels
    \item Ausarbeitung des Dokuments bis Dienstag, den 16.03.99\\
    Abgabe per E-Mail(.dvi-File)an DI~Mag.~Schwaiger
    \end {itemize}

\end{itemize}


\subsection{Protokoll vom 17. März 1999}


\begin{itemize}
\item {\bf Ort:} ~Hr. Schwaigers Büro
\item {\bf Zeit:} ~$18^{00}$
\item {\bf Anwesende:}
 
     \begin{itemize}
     \item DI Mag.Roland Schwaiger
     \item August Mayer
     \item Gerald Wiesbauer
     \item Christopher Rettenbacher
     \item Manuela Stürzlinger
     \end{itemize}

\item {\bf Protokollführer:} ~August Mayer
\item {\bf Themen:}
     \begin{itemize}
      \item Administrative Themen
         \begin{itemize}
            \item Fotos für Webseite sind noch nicht eingetroffen. Vorschlag eines
               Gruppenfotos für die Projekt-Homepage.
            \item Bei Mail an Hr. Schwaiger im Subject "`PPKT 8: "' voranstellen
            \item Bilder als GIF oder JPEG in Dokument einbinden bzw. als GZIPte
               Postscript-Datei schicken
         \end{itemize}
      \item Diskussion der Gestaltung des Papers
         \begin{itemize}
            \item Titelseite sollte eine separate Seite sein
            \item Inhaltsverzeichnis ist sehr gut
            \item Quellenangabe bei der Einleitung hinzufügen (\verb|\cite{...}|)
            \item Bilder für Spielfelder fehlen; es gibt auf einer Seite im Internet
               geeignete Illustrationen $\rightarrow$ Webmaster dieser Seite muß
               informiert werden, Referenz auf diese Seite
            \item Literaturverweise auf Bücher zu Backgammon-Taktiken hinzufügen;
               evtl. einige Taktiken selber lernen $\rightarrow$ Taktik-Spiel
               gegen Computer wäre vielleicht interessant
            \item Inhaltsangabe TD-Gammon: Was sind diese "`hand-crafted features"'?
         \end{itemize}
      \item Viel Information im Internet zu TD-Gammon verfügbar
      \item SNNS arbeitet nur bei mehr als 256 Farben
      \item Fragen zum Text
         \begin{itemize}
            \item Neuronen -- verbundene Verarbeitungseinheiten
            \item TD($\lambda$) -- Formel, neuronales Netz als Minimumsuche, Attraktoren
            \item Diskussion der zwei "`concept features"'
         \end{itemize}
     \end{itemize}

\item {\bf Aufgaben}
     \begin{itemize}
      \item Gestaltung des Papers aktualisieren, notwendige Änderungen durchführen
      \item Einführung zu den Neuronalen Netzen (Oldstedt) auf der Projekt-Homepage durcharbeiten
      \item Glossar zu Begriffen wie Neuron, \dots anlegen
      \item Erste Überlegungen über die Umsetzung machen; GUI-Gestaltung (evt. Handzeichnungen);
         Repräsentation von Elementen, Zügen, Einstellungen (Gegner Mensch oder Computer) usw. \\
         Verwendete Umgebung: Java 1.2 / Swing / Java2D \\
         Aufteilung der Gruppe in GUI- und Engine-Team; 2 eigenständige Packages machen
      \item Literatur: Müller, Reinhardt: "`Neural Networks"'
     \end{itemize}

\end{itemize}
\subsection{Protokoll vom 24. März 1999}
\begin {itemize}
\item {\bf Ort:} ~Hr. Schwaigers Büro
\item {\bf Zeit:} ~$18^{00}$\ 
\item {\bf Anwesende:}
 
     \begin{itemize}
     \item DI Mag.Roland Schwaiger
     \item August Mayer
     \item Gerald Wiesbauer
     \item Christopher Rettenbacher
     \item Manuela Stürzlinger
     \end{itemize}
\item {\bf Protokollführer:} ~Christopher Rettenbacher
\item {\bf Themen:}
     \begin{itemize}
       \item Besprechung der Arbeit der letzten Woche
       \item Einleitung zu ANN
             sollte aus 2 Unterpunkten bestehen;
         \begin{enumerate}
            \item  biologische Motivation
            \item  künstl.neuronale Netze(technischer Ansatz)
              \begin{itemize}
                \item Elemente
                \item Funktionsweise der Neuronen
                \item Prozesse,Neuron,Gewichte,Lernprozesse
                \item Netztypen(TD,Hoppfield,...)
              \end{itemize}
         \end{enumerate}
             Einleitung sollte ohne Zusatzinformation verständlich sein;
       \item Protokolle sollen direkt vor Literatur gereiht werden
       \item Fragestellungen
         \begin{itemize}
            \item  Gibt es automatisch/evolutionär generierte Netze?
            \item  Wer soll gegen unser Netz spielen?
            \item  Design der Input Daten?
            \item  Sind für andere Spiele (Go+Schach) bereits Lösungen vorhanden ?
         \end{itemize}
       \item Ziele
         \begin {itemize}
           \item Objektorientierte Analyse u. Design\\
             basierend auf Anforderungsanalyse;Klassendiagramme der Packete (GUI,ANN,techn. Package) 
           \item graphische Oberfläche(Screenshot)\\
             basierend auf Kundenwünschen; Designansatz beim GUI;Kunde bestätigt Vorabentwurf mittels
             Unterschrift(bereits Vertragsbestandteil); 
           \item use case diagramm\\
             Interaktion user/GUI
         \end{itemize}
     \end{itemize}
\end{itemize}


%
%
% Bibliographie
%

\section{Bibliographie}

\subsection{Inhaltsangaben}

\subsubsection{Temporal Difference Learning and TD-Gammon \cite{Tesauro-1}}

Dieser Text behandelt das Programm TD-Gammon von Gerald Tesauro, ein "`Back\-gammon-Lern-System"', das den
TD($\lambda$)-Algorithmus zum Lernen verwendet. Dabei spielt das Programm mit sich selbst, bewertet bei
jedem Zug die aktuelle Spielsituation und modifiziert die Gewichte des Netzwerks zeitlich abgestuft
anhand dieses Fehlersignals. Als Input des Netzes verwendet er neben der Spielposition auch einige
"`handgemachte"' Werte.

 Im Vergleich zu Neurogammon, das ein von Experten mit menschlichen
Regeln trainiertes neuronales Netz realisiert, aber nur gute Fortgeschrittenen-Spielstärke erreicht,
erreicht das Programm Weltklasseniveau und findet sogar einige optimale Zü\-ge selb\-ständig. So hat
eine von TD-Gammon gefundene Zugkombination die alte, in dieser
Spielsituation verwendete bereits abgelöst. 

TD-Gammon scheint in diesem Zusammenhang tatsächlich
zu lernen, und der Autor beobachtet auch verschiedene Stufen der Wissensaneignung beim Lernvorgang, 
wie das Lernen von Grundzügen und einfachen Strategien (erste paar tausend Spiele), später 
von komplexeren Strategien (nach einigen zehntausend Spielen).

\par

Fragen zum Text:
\begin{itemize}
\item Was sagt die Gewichtung (weights) aus?
\item Wie funktioniert das neuronales Netz von TD-Gammon?
\item Wie wirken die -two concept features- zusammen?
\item Wie entscheidet TD-Gammon über seinen nächsten Zug?
\end{itemize}


\subsubsection{History and Principles of Neural Networks \cite{Olmsted-98}}

Die Theorie der KNN hat ihren Ursprung in einer Arbeit des amerikanischen Psychologen W.~James,
der Gedanken und Aktionen als Resultat von Spannungsverschiebungen im Gehirn interpretierte und
Lernen als Modifikation der Pfade dieser Verschiebungen. In den nächsten Jahren bis 1910 wurde diese Theorie
zum Standardmodell erweitert, das besagt, daß einzelne Gehirnzellen (Neuronen) Signale über Dendriten
("`Eingangsfasern"') sammeln und bei Überschreitung einer Schwelle ein Signal abfeuern.

Zwischen 1938 und 1943 entstanden erste neurale Logiksysteme (N.~Rashevsky -- binäre logische
Operationen im Gehirn; W.~McCulloch, W.~Pitts -- "`Schwellwert-Logik"', "`Mehrwertige Logik"';
Erfindung der sog. Gewichte, adaptierbare Parametersysteme und Trennung von der mathematischen Logik).
In weiterer Folge trennten sich die Neurowissenschaftler in Artificial-Intelligence- (AI-) und
KNN-Forscher (etwa 1963); die AI-Forscher erweiterten und abstrahierten die binäre zu pro- und
präpositionaler Logik (Entwicklung der Programmiersprache LISP), während die KNN-Forscher weiter
parameterbasierte Klassifizierungsmodelle entwickelten.

1949 formulierte Hebb eine Lernregel, die in etwa besagt, daß bei häufigerer Benutzung einer Verbindung
zwischen Neuronen die Effizienz der Verbindung zunimmt. Farley und Clark simulierten 1954 erstmals ein
solches Netz am M.I.T. auf einem frühen Elektronenrechner, wobei die Neuronen zufällig verbunden waren.
1956 bauten N.~Rochester im IBM-Forschungslabor Poughkeepsie, New York, ein rückgekoppeltes Netz,
indem sie die Ausgänge von Neuronen wieder zurück ins Netz führten; es zeigten sich hier erstmals
Formen von Selbstorganisation. 1958 baute F. Rosenblatt ein selbstlernendes Netz, das er Perceptron nannte
und das Regelmäßigkeiten im Eingangsmuster erkannte. Es benutzte Subnetze, die untereinander konkurrieren.
Allerdings bauten diese Netze alle auf einer zufälligen Verschaltung der Neuronen, die sich als zu aufwendig
und ressourcenverbrauchend herausstellte, sodaß eine natürliche Verwendung wenig wahrscheinlich ist.

B.~Widrow und M.~Hoff entwickelten 1960 das ADALINE-System, bei dem vor der Summation eine Gewichtung  erfolgt.
Sie stellten 1962 eine Lernregel auf, nach der aktive Verbindungen mehr zum Fehler beitragen. F.~Rosenblatt
kombinierte ebenfalls 1962 das ursprüngliche Perceptron mit dem ADALINE-System zum "`Klassischen Perceptron"'.
M.~Minsky und S.~Papert, Vertreter der AI-Richtung, schrieben schließlich 1969 ein Buch über die inhärenten
Grenzen der Perceptrons, das zu einer Stillegung der Forschung auf dem Gebiet der KNN in den USA für einige
Zeit führte.

J.~Anderson und T.~Kohonen veröffentlichten 1972 Schriften über assoziative Netze, die zur nächsten
Entwicklungsstufe führten. Dabei produzieren mehrere Eingangssignale mehrere analoge Ausgangssignale.
Weiter entwickelte K.~Fukushima 1975 das Cognitron, das ähnlich dem Perceptron funktionierte, aber
bei einigen Problemstellungen durch spezielle inhibitorische Signale besser funktioniert. Dieses Modell
erweiterte er 1980 zum Neocognitron, das auch Musterverschiebungen toleriert.

J.~Hopfield entwickelte 1982 in den USA einen neuen rückgekoppelten Netztyp, indem er bidirektionale
Verbindungen zwischen den Neuronen verwendete, und löste einen neuen Forschungsschub auf dem Gebiet aus.
D.~Reilly, L.~Cooper und Ch.~Elbaum entwickelten ebenfalls
1982 sog. hybride Netze, die mehrere Netzebenen kombinierten. Dabei bewirkt die erste Ebene eine
Verallgemeinerung der Informationen, die zweite eine Spezialisierung. 

Drei unabhängige
Forschergruppen entwickelten 1986 den Typ der assoziativen Backpropagation-Netzwerke, die Fehlerwerte
 auf spezielle Weise
im Netzwerk verteilen. Dabei wird angenommen, daß näher am Ausgang liegende Neuronen mehr für den Fehler
verantwortlich sind als näher am Eingang liegende. Dieser Typ von Netzen lernt relativ langsam.

1987 entwickelten S.~Grossberg und G.~Carpenter Netzwerke zur Erkennung von Regelmäßigkeiten, die sog.
Adaptive Resonance Networks (ART). Hier wurde versucht, zu erkennen, ob ein Netzteil ein Muster {\emph nicht}
erkennt, indem positive Rückkopplung verwendet wird.

1990 schließlich entwickelte D.~Olmsted das Mehrwertig-Logische Neurale Netzwerk, das nach dem Vorbild der
retikulären Strukturen im Gehirn arbeitet und später zur Mustererkennung verwendet wurde.


\subsection{A 'neuronal' Network that learns to play Backgammon\cite{Anderson-88}}

Backgammon ist ein komplexes Brettspiel, das besonders geeignet
f"ur die Anwendung Neuronale Netze scheint, da die Zugauswahl
in erster Linie auf Basis von Mustererkennung im Gegensatz zur
expliziten 'Look-ahead' Methode funktioniert. Dies folgt aus den
nicht vorhersehbaren W"urfelresultaten, die die Zugm"oglichkeiten
in einer typischen Spielsituation auf "uber 400 erh"ohen.

Der wichtigste Faktor, der die Effektivit"at des Netzes entscheidet,
war die Methode, die bei der Kodierung der Information angewandt 
wurde, wobei die Hinzunahme von 'precomputed features' eine
signifikante Leistungssteigerung zur Folge haben.

Das hier beschriebene Netz greift auf eine Datenbank zur"uck,
die ca. 3000 ,teilweise bewertete Brettsituationen sowie daraus
resultierende optimale Z"uge [-/+100] enth"alt. Da einige Spielprinzipien verh"altnism"a"sig oft zum Einsatz kommen, ben"otigt man einen
intelligenten Auswahlmechanismus, um ein 'overlearning' zu
verhindern.

Das verwendete NN besteht aus 459 Input-Neuronen(je 18 pro Feld+Bar, sowie einige f"ur pre-computed information)
Auf die Hinzunnahme von 'hand-crafted features' wurde bewu"st 
verzichtet, einige einfache Bewertungsmechanismen jedoch hinzugenommen, da es f"ur das Netz zu schwierig scheint in absehbarer Zeit aus
der reinen 'Spielsituation' einen Lerneffekt zu erzielen.
Der Lernproze"s unterscheidet sich hier jedoch insofern vom
'standard back-propagation learning algorithm', als dem Netz
auch nicht bewertete Spielz"uge vorgeschlagen werden. Dabei wird
-unter der Annahme, da"s i.A. ung"unstige Szenarien nicht bewertet
 wurden- ein zuf"alliges 'teacher signal' [-65/+35]erzeugt.

Das Netzwerk wurde nach 4 Kriterien bewertet:
\begin{enumerate}
\item Performance beim Lernproze"s
\item Performance bei dem Netz unbekannten Situationen
\item Performance bei einem Wettkampf gegen ein konventionelles
Programm
\item Performance bei einem Wettkampf gegen einen menschlichen
Gegner
\end{enumerate}
Das Netzwerk gewinnt in 60\% der F"alle gegen Gammontool, ein zu
Vergleichszwecken herangezogenes konventionelles Backgammonprogramm.
Beim Entfernen der 'precomputed features' f"allt die Erfolgsquote
auf 41\%, ohne die zuf"allig bewerteten Spielsituationen('noise') 
auf 45\% und ohne die 'hidden units'(Zwischenschichten im NN) auf
50\%. Im Gegensatz dazu beeinflu"st eine "Anderung etwa der Anzahl
von 'hidden units', Schichten im NN oder Gr"o"se der Datenbank
das Ergebnis kaum.

Verst"arkt man das NN durch die Bewertungsmechanismen von
Gammontool, so wird die Effizienz des Systems erh"oht. In der
Verbindung von digitaler Technologie und NN scheint die Zukunft
der AI zu liegen.

Momentan erreichen NN jedoch nur mittelm"a"siges Spielniveau
da nur einzelne Spielsituationen bewertet, der daraus entstehende
zuk"unftige Spielverlauf jedoch nicht ber"ucksichtigt wird.


\subsection{Bücherliste}

\bibliographystyle{alpha}
\bibliography{Backgammon}

\end{document}

