
Im folgenden Kapitel werden nun die Ergebnisse und Analysen der drei GP-Systeme
vorgestellt. Wir folgen hierbei der Reihenfolge, wie sie durch das 
Kapitel~\ref{kapitelfuenf} vorgegeben wird. Da zwischen der Entwicklung und Analyse
der einzelnen Systeme mehrere Jahre liegen und die Systeme zusätzlich
 sehr unterschiedlich sind,
wurden hier verschiedene Schwerpunkte bei der Analyse gewählt oder durch die
Systeme ermöglicht. 


%----------------------------------------------------------------------
\section{Ergebnisse des ChessGP Systems}
%----------------------------------------------------------------------
\label{sec:ChessGPResults}

Das ChessGP-System war das erste System, das versucht hat schachspielende
GP-Individuen zu evolvieren. Da die Aufgabe komplex ist, haben wir die Evolution
des Schachindividuums in verschiedene einzelne Evolutionsvorgänge aufgeteilt. Diese Evolutionsprozesse
spiegeln die drei Bereiche wieder, die der Aufteilung des
Individuums in die drei Ebenen entspricht.
Im folgenden werden nun die Ergebnisse der einzelnen Ebenen vorgestellt und mit
der letzten Ebene auch das Ziel der Evolution, die schachspielenden Individuen,
vorgestellt.


%----------------------------------------------------------------------
\subsection{Materialbewertungsebene}
%----------------------------------------------------------------------
\label{sub:ChessGPMat}

Die Individuen für die Materialbewertung wurden durch lineare Strukturen gebildet. 
Die Funktionen, die von den Individuen zur Lösung der Aufgabe genutzt wurden, sind
im Abschnitt~\ref{sec:FunkMatChessGP} aufgeführt und näher erläutert,
die Parameter, die in allen Tests nicht verändert wurden, sind in der
Tabelle~\ref{tab:ChessGPMat} zusammengefasst.


\begin{table}
\begin{center}
\begin{tabular}{|p{3cm}|p{3cm}|p{6cm}|}
\hline
 Parameter & Wert & Beschreibung \\
\hline 
 Evaluationen & 1.000.000 & Anzahl der Fitnessauswertungen pro Lauf \\
\hline 
 Population & 1.000 & Größe der Population für einen
 Lauf \\
\hline 
 Crossover & 0,8 & Wahrscheinlichkeit, dass zwei Individuen an einem
 Crossover teilnehmen\\
\hline 
 Mutation & 0,3 & Wahrscheinlichkeit, dass ein Individuum mutiert wird\\
\hline 
 Selektion & Turnierselektion 2*2 & Turnierselektion aus zwei Zweier-Turnieren\\
\hline 
 Initialisierung & ramped half and half & Initialisierungsart der Population \\
\hline 
 Minimale Individuengröße & 10  & Anzahl der Knoten, die ein Individuum
 minimal haben durfte \\
\hline 
 Maximale Individuengröße & 50 & Anzahl der Knoten, die ein Individuum
 maximal haben durfte \\
\hline 
 Konstanten & [-1000,..,1000] & Wertebereich der Konstanten\\
\hline 
\end{tabular}
\end{center}
\caption{Diese Tabelle enthält alle Parameter, die für alle Tests
der Materialbewertung genutzt wurden. }
\label{tab:ChessGPMat}
\end{table}


Die ersten Evolutionsläufe der Materialbewertungsebene wurden mit einer
Populationsgröße von 100 Individuen durchgeführt. Jedoch traten über den gesamten
Evolutionszeitraum kaum Verbesserungen auf, wie man dies im direkten Vergleich der
Plots~\ref{fig:MatClever100} und~\ref{fig:MatClever1000} für die Clevere
Materialbewertung sehr gut sehen kann. Dieser Vergleich ist beispielhaft für das
Verhalten aller Evolutionsläufe mit 100 Individuen für die verschiedenen Aufgaben.
Daher wurden alle Läufe mit 1.000 Individuen durchgeführt. Auf den folgenden
Kurven ist jeweils die Fitness des besten Individuums abgebildet. Hierbei ist zu
beachten, dass die Fitnesswerte der verschiedenen Teilprobleme der Materialebene
nicht normiert sind und immer die Quadratsumme der Fehlerabweichungen über alle
Fitnesscases berechnet wird. Eine Ausnahme bilden hier die Bewertungen \emph{Angriff} und
\emph{Verteidigung}, hier wird die Wurzel der Quadratsumme der Fehlerabweichungen
dargestellt. Dies war sinnvoll, da sonst die Entwicklung der Fitness in der Endphase
der Evolution schlecht dargestellt worden wäre. Die genaue Beschreibung der
Fitnesswerte kann in Kapitel~\ref{sub:MatChessGP} genauer nachgelesen werden.

\begin{figure}
\begin{minipage}{7cm}
  \centerline{\epsfig{figure=Pictures/Results/bewertungClever100PG.eps,width=7cm}}
  \caption{Materialbewertung Clever mit einer Population von 100 Individuen.}
  \label{fig:MatClever100}
  \end{minipage}
\hfill
\begin{minipage}{7cm}
 \centerline{\epsfig{figure=Pictures/Results/bewertungCleverPG.eps,width=7cm}}
  \caption{Materialbewertung Clever mit einer Population von 1.000 Individuen.}
  \label{fig:MatClever1000}
\end{minipage}
\end{figure}



\begin{wrapfigure}{r}{60mm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungVerteidigungPG.eps,width=6cm}}
  \caption{Bewertung Verteidigung mit einer Population von 1.000 Individuen}
  \label{fig:CGVer}
 \end{wrapfigure}%{figure}
Da die Fitnesscases aus 40.000 transformierten Schachstellungen bestanden, die
aus  65.000 Schachstellungen ausgewählt wurden, konnten nicht
alle Fitnesscases zur Bestimmung der Güte eines Individuums herangezogen werden.
Daher wurde eine \emph{Random subset selection} durchgeführt, dabei wird in
jeder Generation eine Teilmenge aus alle Fitnesscases ausgewählt und diese
Teilmenge auf allen Individuen angewendet~\cite{ga94aGathercole}.
Wir haben auch das \emph{Stochastic sampling} getestet, indem für jedes Individuum
eine neue Teilmenge ausgewählt wurde~\cite{olmer96evolving}. Dies führte aber in unserem
Fall zu sehr schlechten Ergebnissen, so dass wir uns für das
\emph{Random subset selection}-Verfahren entschieden haben. 
 Nach verschiedenen Tests haben wir die Größe der Teilmenge auf 100 Fitnesscases festgelegt. Dies war ein
Kompromiss zwischen der Güte der Individuen und dem Rechenaufwand während der Evolution.
Für eine kurze Zusammenfassung weiterer Verfahren siehe auch~\cite{lasarDittBanz2004}.
Die restlichen 25.000 Schachstellungen, die nicht als Fitnesscases verwendet wurden,
 wurden anschließend zur Analyse der Individuen genutzt, hierzu später mehr.


 \begin{figure}
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungMatPG.eps,width=7cm}}
  \caption{Bewertung Material mit einer Population von 1000 Individuen.}
  \label{fig:CGMat}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungAggressivePG.eps,width=7cm}}
  \caption{Materialbewertung Aggressive mit einer Population von 1000 Individuen.}
  \label{fig:CGAgg}
%  \end{figure}
\end{minipage}
\hfill
%\begin{minipage}{7cm}
%% \begin{figure}
%  \centerline{\epsfig{figure=Pictures/Results/bewertungCleverPG.eps,width=7cm}}
%  \caption{Bewertung Clever mit einer Population von 1000 Individuen}
%  \label{fig:CGClever}
%%  \end{figure}
%\end{minipage}
%\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungDefensivePG.eps,width=7cm}}
  \caption{Bewertung Defensive mit einer Population von 1000 Individuen}
  \label{fig:CGDef}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungAngriffPG.eps,width=7cm}}
  \caption{Bewertung Angriff mit einer Population von 1000 Individuen}
  \label{fig:CGAng}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungEndspielPG.eps,width=7cm}}
  \caption{Bewertung Endspiel mit einer Population von 1000 Individuen}
  \label{fig:CGEnd}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungKomplexPG.eps,width=7cm}}
  \caption{Bewertung Komplex mit einer Population von 1000 Individuen}
  \label{fig:CGKomp}
%  \end{figure}
\end{minipage}
 \end{figure}



Die Plots \ref{fig:CGMat}, \ref{fig:CGAgg}, \ref{fig:CGDef}, \ref{fig:CGAng},
\ref{fig:CGEnd} und \ref{fig:CGKomp} zeigen ein typisches Verhalten für die
Entwicklung der Fitness während der Evolution. Die Verbesserung der Fitness
ist in den ersten Generationen dramatisch und mündet dann in eine Phase mit nur
noch kleinen Fitnessverbesserungen. Aufgrund der hohen Laufzeit für
eine Evolution wurden auch einige Evolutionsläufe vorzeitig beendet, wenn keine
signifikanten Verbesserungen mehr zu erwarten waren.
Eine Ausnahme ist die Fitnessentwicklung der Verteidigungsbewertung in
Plot~\ref{fig:CGVer}, hier scheint die Verbesserung über den gesamten Zeitraum
verteilt zu sein. Dies deutet darauf hin, dass noch weitere Verbesserungen durch
eine längere Evolution möglich gewesen wären. Die Evolution wurde jedoch trotzdem
abgebrochen, da erstens alle Individuen einer Ebene des Gesamtindividuums die gleichen
Parameter haben sollten und zweitens wurde die Evolution der Teilindividuen während
der Evolution des Gesamtindividuums wieder aufgenommen. Dadurch sollte den Teilindividuuen
eine Anpassung an das Gesamtindividuum ermöglicht werden. Aus diesen Gründen wäre
es vorteilhaft gewesen, wenn auch die Evolutionsläufe der anderen 
Materialbewertungen ebenfalls ein größeres Entwicklungspotenzial gezeigt hätten.
Alle Evolutionsläufe wurden mit dem vollständigen Funktionssatz für diese Ebene durchgeführt,
alle Funktionen sind im Kapitel~\ref{sec:FunkMatChessGP} beschrieben.


Da wir die Ergebnisse nicht befriedigend fanden, wurden anschließend Evolutionsläufe
mit eingeschränkten Funktionssätzen durchgeführt, die auf die einzelnen Problemstellungen
zugeschnitten waren. Hierzu wurde eine Menge von Funktionen verwendet, die allen
Bewertungen zu Verfügung gestellt wurden und eine Teilmenge, die auf die jeweilige
Aufgabe zugeschnitten war. Allen Bewertungsfunktionen gemeinsam waren die Operationen:
\emph{add, addEqual, sub, subEqual, mult, multEqual, div, divEqual, absolute} und
\emph{ifThen}.
Die eingeschränkten Funktionssätze für die einzelnen Bewertungen
sahen wie folgt aus.
\begin{itemize}
\item Material
        Operationen: boardLoop, whichPiece \newline
        Terminale: pieceValue
\item Clever
        Operationen: boardLoop, whichPiece, setRow, setLine \newline
        Terminale: pieceValue, legalMovesNumber
\item Angriff
        Operationen: boardLoop, rowLoop, whichPiece, setRow, swap \newline
        Terminale: pieceValue, attackedByNumber, attackedByValue
\item Verteidigung
        Operationen: boardLoop, rowLoop, whichPiece, setRow, swap \newline
        Terminale: pieceValue, attackedByNumber, attackedByValue
\item Aggressive
        Operationen: boardLoop, rowLoop, whichPiece, setRow \newline
        Terminale: pieceValue, attackedByNumber, attackedByValue
\item Defensive
        Operationen: boardLoop, rowLoop, whichPiece, setRow \newline
        Terminale: pieceValue, attackedByNumber, attackedByValue
\item Komplex
        Operationen: boardLoop, whichPiece \newline
        Terminale: pieceValue, legalMovesNumber, attackedByNumber
\item Endspiel
        Operationen: boardLoop, whichPiece       \newline
        Terminale: pieceValue
\end{itemize}

 
Durch eine Einschränkung des Funktionssatzes sollte es der Evolution ermöglicht
werden, einfacher Lösungen zu finden, da nun nur Operationen zur Verfügung stehen,
die eine Lösung des Problems ermöglichen. Die Evolution der Materialbewertung
erfüllte die Aufgabe, so konnte hier ein Individuum erzeugt werden, welches die
optimale Lösung bezogen auf die Fitnessfunktion liefert. Die Bewertung machte sowohl
auf der Trainings- als auch auf der Testmenge keine Fehler.
Die Evolution der Aggressiven und Komplexen Materialbewertung erreichten zwar nicht
die optimale Lösung, aber Verbesserungen gegenüber den Läufen mit den nicht
eingeschränkten Funktionsmengen, siehe hierzu die Plots~\ref{fig:CGAgg} und \ref{fig:CGKomp}.

\begin{wrapfigure}{r}{70mm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungVerteidigungPG.eps,width=7cm}}
  \caption{Materialbewertung Verteidigung mit einer Population von 1000 Individuen}
  \label{fig:CGVerPart}
 \end{wrapfigure}%{figure}
 
Die Plots  \ref{fig:CGDef}, \ref{fig:CGAng} und \ref{fig:CGEnd} zeigen die Ergebnisse für
die anderen Materialbewertungen, hier wurde keine Verbesserung der Ergebnisse erkennbar.
Zu beachten ist hier aber auch die kurze Laufzeit, die einerseits auf externe
Rechnerstörungen zurückzuführen war, aber auch durch Abbruch der Läufe zustande kam.
Aufgrund der benötigten Rechenleistung und den geringen Erfolgsaussichten, die auch
durch Vortests untermauert wurden, haben wir hier darauf verzichtet, die Läufe bis
zur letzten Generation durchzuführen.


 
 \begin{figure}
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungAggressivPartPG.eps,width=7cm}}
  \caption{Materialbewertung Aggressive mit einer Population von 1000 Individuen und
  eingeschränkter Funktionsmenge}
  \label{fig:CGAggPart}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungCleverPartPG.eps,width=7cm}}
  \caption{Materialbewertung Clever mit einer Population von 1000 Individuen und
  eingeschränkter Funktionsmenge}
  \label{fig:CGCleverPart}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungDefensivPartPG.eps,width=7cm}}
  \caption{Materialbewertung Defensive mit einer Population von 1000 Individuen und
  eingeschränkter Funktionsmenge}
  \label{fig:CGDefPart}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungAngriffPartPG.eps,width=7cm}}
  \caption{Materialbewertung Angriff mit einer Population von 1000 Individuen und
  eingeschränkter Funktionsmenge}
  \label{fig:CGAngPart}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungEndspielPartPG.eps,width=7cm}}
  \caption{Materialbewertung Endspiel mit einer Population von 1000 Individuen und
  eingeschränkter Funktionsmenge}
  \label{fig:CGEndPart}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/bewertungKomplexPartPG.eps,width=7cm}}
  \caption{Materialbewertung Komplex mit einer Population von 1000 Individuen und
  eingeschränkter Funktionsmenge}
  \label{fig:CGKompPart}
%  \end{figure}
\end{minipage}
 \end{figure}




Zum Abschluss der Evolution wurde das Verhalten der Individuen auf sämtlichen Schachstellungen
in der Datenbank untersucht. Zur Visualisierung wurden der Fehler des Individuums
bezüglich des Wertes in der Datenbank auf der Y-Achse eines Plots angegeben. Dabei
ergaben sich vier verschiedene Verhaltensweisen der Individuen auf allen Datensätzen.
Das Individuum der einfachen Materialbewertung erzeugte ein optimales Verhalten,
indem es für jede Schachstellung den Fehlerwert 0 erzeugte. 
Das Individuum mit der Aufgabe einer Aggressiven Materialbewertung, Plot~\ref{fig:DBErrorAgg},
zeigt auf allen Schachstellungen ähnlich gute Ergebnisse. Obwohl dieses Individuum
extreme Ausreißer gegenüber dem erwarteten Wert hat, zeigt sich aber, dass das
Individuum abstrahieren und ein allgemeines
Konzept für die Aufgabe entwickeln konnte. Das Individuum der
Cleveren Materialbewertung, Abbildung~\ref{fig:DBErrorClever}, zeigt dagegen ein Verhalten,
welches man zwar erwartet, jedoch eigentlich nicht erhalten möchte. Denn hier erzeugt das
Individuum auf den unbekannten Schachstellungen (ab Stellung 40000) einen höheren
Fehler, als auf den Stellungen, die als Fitnesscases genutzt wurden. Dieses
Verhalten ist zwar nicht wünschenswert, aber ein schlechteres Ergebnis auf einer
Validierungsmenge ist für evolutionäre Verfahren normal. Ein ähnliches Verhalten
ergab sich auch bei der Defensiven Materialbewertung, Plot~\ref{fig:DBErrorDef}, nur mit
dem Unterschied, dass der Fehler auf den unbekannten Datensätzen kleiner war, diese
Verhalten wurden auch von der Komplexen Materialbewertung gezeigt.
Die Materialbewertungen Angriff, Endspiel und Verteidigung zeigten das extremste
Verhalten auf den unbekannten Datensätzen. Die Abbildung~\ref{fig:DBErrorVer}
zeigt das Verhalten der Materialbewertung Verteidigung auf allen Datensätzen, hier
ist deutlich die Verschlechterung auf den unbekannten Daten zu erkennen. Der Evolution
ist es für diese Bewertungen nicht gelungen ein generelles Modell für die Aufgabenstellung
zu entwickeln.

 \begin{figure}
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/DBFehlerVerteidigungPartPG.eps,width=7cm}}
  \caption{Fehler des besten Individuums der Materialbewertung Verteidigung auf allen
        Schachstellungen der Datenbank. Der durchschnittliche Fehler beträgt 213685.}
  \label{fig:DBErrorVer}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/DBFehlerCleverPartPG.eps,width=7cm}}
  \caption{Fehler des besten Individuums der Materialbewertung Clever auf allen
        Schachstellungen der Datenbank. Der durchschnittliche Fehler beträgt 50,8.}
  \label{fig:DBErrorClever}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/DBFehlerDefensivPartPG.eps,width=7cm}}
  \caption{Fehler des besten Individuums der Materialbewertung Defensiv auf allen
        Schachstellungen der Datenbank. Der durchschnittliche Fehler beträgt 8,26.}
  \label{fig:DBErrorDef}
%  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/DBFehlerAggressivPartPG.eps,width=7cm}}
  \caption{Fehler des besten Individuums der Materialbewertung Aggressiv auf allen
        Schachstellungen der Datenbank. Der durchschnittliche Fehler beträgt 0,88.}
  \label{fig:DBErrorAgg}
%  \end{figure}
\end{minipage}
\end{figure}


% \begin{figure}
%  \centerline{\epsfig{figure=Pictures/Results/cleverDBErr.eps,width=12cm}}
%  \caption{Die Graphik zeigt einen Auschnitt des Verhaltens der Cleveren
%    Materialbewertung bezogen auf die Daten in der Datenbank unter Verwendung
%    der Linear-Tree Struktur. Die Ergebnisse mit linearen oder Baum Strukturen
%    führten zu Ergebnissen die nicht verwendet werden konnten.}
%  \label{fig:CleverDBError}
%  \end{figure}

%----------------------------------------------------------------------
\subsection{Planungsebene}
%----------------------------------------------------------------------
\label{sub:ChessGPPlan}

Die Individuen der Planungsebene sollen für eine gegebene Stellung eine
Zugliste generieren. Die Aufgabe bestand einerseits darin eine Zugliste
zu generieren und andererseits darin eine möglichst kleine Zugliste zu erzeugen.
Die Funktionen, die von den Individuen zur Lösung der Aufgabe genutzt wurden, sind
im Abschnitt~\ref{sec:FunkPlanChessGP} beschrieben.
Bei der Evolution hat sich jedoch gezeigt, dass die gestellte Aufgabe für die
Individuen zu schwierig war. Obwohl der Verlauf der Fitnesskurven dem anderer
Evolutionsläufe entsprach, zeigte sich bei der Analyse der Individuen, dass alle Individuen
extrem kurze Zuglisten berechneten. Wie im Kapitel~\ref{sec:PlanChessGP} beschrieben
ist, wurde die Länge der Zugliste mit einem Strafterm belegt, siehe hierzu
die Gleichungen~\ref{eq:ChessGPlang} und \ref{eq:ChessGPPlanFit}. Obwohl der Strafterm
sowohl für zu kurze, als auch zu lange Listen gilt, war es für die Individuen besser
oder einfacher kurze Listen zu erzeugen. Die besten Individuen der verschiedenen
Läufe gaben selten Zuglisten zurück, die mehr als fünf Züge beinhalteten. Eine
genaue Analyse der Zuglisten zeigte, dass die Individuen entweder einfache
Heuristiken entwickelt hatten oder aufgrund von Design- und Implementierungsentscheidungen
zu einem gewissen Verhalten tendierten. So lieferte zum Beispiel das Individuum
der Desperado Züge nur Züge, die auf der a-Linie des Schachbrettes lagen. Die a-Linie
wurde intern durch die Zahl eins dargestellt und alle Register wurden immer mit
der Zahl eins initialisiert. Das Individuum für die Gefährlichen Züge lieferte
immer eine Liste von Zügen, deren Zielfeld auf der gleichen Linie lag.

Im Hinblick auf die Wichtigkeit der Ebene für die Evolution der Varianten
mussten wir feststellen, dass alle evolvierten Module häufig Zuglisten mit weniger
als fünf Zügen aufstellten und eine so kleine Auswahl aufgrund der Güte der einzelnen
Züge nicht ausreichend war um ein spielstarkes Individuum zu erzeugen. Daher haben wir
uns dazu entschlossen den Strafterm für die Längenbeschränkung aus der Fitnessberechnung
zu entfernen, um somit größere Zuglisten zu erhalten. Wir erwarteten durch diese Veränderung
der Fitness, dass die Individuen im schlimmsten Fall Listen mit allen möglichen
Zügen in verschiedenen Permutationen erzeugten. Dies geschah dann auch in allen
durchgeführten Läufen. Eine Analyse der verschiedenen Zuglisten zeigte dabei keine
sinnvolle Umordung der Listen bezogen auf das Evolutionsziel. Es waren Zuglisten
mit allen möglichen Zügen einer Stellung, die in einer willkürlichen Reihenfolge
sortiert wurden. Da diese Ebene für das Gesamtindividuum eine große Bedeutung hat,
sich durch die Evolution aber keine Individuen gebildet hatten, die die Aufgabe
sinnvoll lösten, modellierten wir zwei Individuen \emph{von Hand}. Wir nutzten dafür
die der Evolution zur Verfügung gestellte Syntax und den Sprachumfang des Interpreters
mit allen erlaubten Operationen. Dies ermöglichte uns Individuen zu erzeugen,
die die gestellte Aufgabe hinreichend gut lösten. Erstaunlich ist hierbei, dass
die Evolution es nicht geschafft hat entsprechende Individuen zu erzeugen, obwohl
sie die gleichen Möglichkeiten hatte wie wir. Es ist möglich, dass dies durch größere
Populationen und längere Laufzeiten  möglich gewesen wäre, jedoch waren die
von uns gewählten Parameter bezogen auf die Laufzeit der Evolution und die Ressourcen,
die uns zur Verfügung gestanden haben, maximal gewählt.

Da wir uns bei der Erzeugung der Individuen auf die Ausdruckskraft der Sprache
beschränkten, die auch für die Evolution galt, zeigte sich, dass es auch uns
nicht möglich war Individuen für die Problemstellung \emph{Tauschzüge} und
\emph{Materialzüge} zu entwickeln. Für beide Aufgabenstellungen wäre es notwendig
gewesen probehalber Züge auszuführen, dies konnte aber von einem Individuum nicht
durchgeführt werden. Nach weiteren Versuchen wurden dann die Individuen für
\emph{Beste Züge} und \emph{Gefährliche Züge} als Individuen von Hand implementiert.







% \begin{figure}
%\begin{minipage}{6cm}
%% \begin{figure}
%  \centerline{\epsfig{figure=Pictures/Results/ZugTauschPG.eps,width=12cm}}
%  \caption{Die Fitness des Modules Tauschzüge ohne eine Beschränkung der
%    Listenlänge.}
%  \label{fig:CGZugTausch}
% %  \end{figure}
%\end{minipage}
%\hfill
%\begin{minipage}{6cm}
%% \begin{figure}
%  \centerline{\epsfig{figure=Pictures/Results/ZugMatPG.eps,width=12cm}}
%  \caption{Die Fitness des Modules Materialzüge ohne eine Beschränkung der
%    Listenlänge.}
%  \label{fig:CGZugMat}
%  \end{minipage}
%  \end{figure}

% \begin{figure}
%  \centerline{\epsfig{figure=Pictures/Results/ZugOpferPG.eps,width=12cm}}
%  \caption{Die Fitness des Modules Opferzüge ohne eine Beschränkung der
%    Listenlänge.}
%  \label{fig:}
%  \end{figure}


%----------------------------------------------------------------------
\subsection{Das Schachindividuum}
%----------------------------------------------------------------------
\label{sub:ChessGPVariant}

Ein Gesamtindividuum besteht aus vier Modulen, der Variantenebene und jeweils
acht Individuen der Material- und Planungsebene. Der Aufbau der Variantenebene ist
in Kapitel~\ref{sec:ChessGP-Variantenebene} genauer beschrieben. Nach den Problemen
der Planungsebene konnten dem Gesamtindividuum jedoch nur zwei verschiedene Module
zur Verfügung gestellt werden. Dies schränkt zwar die Variabilität des Individuums
ein, hinderte jedoch ein Individuum nicht, sinnvoll Schach zu spielen.

Im Unterschied zu den ersten beiden Ebenen des Individuums wurden nun zur Berechnung
der Fitness Schachspiele durchgeführt. Da ein Schachspiel zur Bewertung nicht ausreichend
ist, mussten die Individuen mindestens fünf Schachspiele durchgeführt haben, bevor
sie durch den Selektionsmechanismus ausgewählt werden konnten, um anschließend
rekombiniert oder mutiert zu werden. Spätestens nach zehn Spielen wurde ein Individuum
zur Rekombination oder Mutation ausgewählt. Individuen, die fünf Pflichtspiele noch nicht
durchgeführt hatten, wurden  als \emph{junge Individuen} bezeichnet.
Wenn nun ein Schachspiel durchgeführt wurde, wurde mit einer Wahrscheinlichkeit von
90\% ein Individuum aus der Menge der \emph{jungen Individuen} gewählt. Mit
einer Wahrscheinlichkeit von 10\% wurde ein beliebiges Individuum aus dem Pool
oder eines der zehn Schachprogrammen mit verschiedenen Spielstärken ausgewählt. Das zweite
Individuum wurde dann entsprechend der Fitness (Elo-Zahl) des Individuums ausgewählt,
dazu wurde der Durchschnitt aus der Fitness des Individuums und der
durchschnittlichen Fitness des Pools berechnet. Dann wurde dieser Wert genutzt um ein
Individuum im Pool zu finden, das etwa die gleiche Elo-Zahl hat.
Anschließend wurde die Farbe ausgewählt mit der das Individuen das Spiel bestreitet.

Die Population enthielt 100 Individuen und in jeder Generation wurden 100 Spiele gespielt,
durch die Parallelsierung des Systems wurden jeweils 20-30 Spiele gleichzeitig 
ausgeführt~\footnote{Die Anzahl der Spiele ist von der Anzahl freier Rechner abhängig.}.
Ein Spiel wurde nach spätestens 80 Halbzügen abgebrochen, der Sieger der Partie wurde dann
durch die Materialüberlegenheit bestimmt. Jedes Individuum durfte pro Zug im Suchbaum
maximal 20000 Knoten expandieren und bis zur Tiefe 6 vordringen. In jedem fünften
Spiel wurde versucht, ein schlechtes Individuum durch ein neues Individuum zu ersetzen.
Ein Individuum durfte aber erst nach sieben Spielen ersetzt werden und das neue Individuum
durfte nur durch Individuen erzeugt werden, die nicht mehr zu den jungen Individuen
zählten, also mehr als fünf Spiele durchgeführt hatten. Um nun ein Individuum
zu ersetzen wird ein Turnier mit zehn Individuen durchgeführt. Dann wurde das neue Individuum
mit je gleicher Wahrscheinlichkeit durch eine Mutation des besten Individuums des Turniers
oder durch eine Rekombination der besten beiden Individuen des Turniers erzeugt.

\begin{wrapfigure}{r}{70mm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/EloPG2.eps,width=7cm}}
  \caption{Die Entwicklung der Elowerte über die Zeit.}
  \label{fig:ChessGPElo}
  \end{wrapfigure}%{figure}
Die Abbildung~\ref{fig:ChessGPElo} zeigt nun den Verlauf der Elowerte über 160
Generationen. Wenn man diese Kurve betrachtet, scheint ab ungefähr der 75.ten
Generation ein starker Einbruch zu passieren, von dem sich die Evolution nicht
mehr vollständig erholt. Was man dort sieht, ist jedoch ein Artefakt der Elobewertung,
denn jedesmal, wenn ein Individuum gewinnt, wird die Elo-Zahl besser, wie von
der Elobewertung definiert. Erst wenn dieses Individuum gegen ein anderes verliert,
sinkt seine Bewertung wieder, das heißt, in der Phase des Anstiegs gibt es kein
Individuum im Pool, das besser ist, somit steigt seine Elobewertung immer weiter.
Wenn nun ein neues Individuum besser ist, sinkt die Bewertung des alten Individuums
immer dann, wenn es verliert. Gleichzeitig steigt die Bewertung des neuen Individuums.
Die Phasen der fallenden Bewertung zeigen somit immer das Erscheinen eines neuen,
besseren Individuums. Da die Elobewertung nur eine relative Güte der Individuen
im Pool angibt, heißt das aber auch, dass ein Individuum der Generation 30 mit
einer Elobewertung von 700 nicht besser sein muss als ein Individuum der
Generation 150 mit einer Bewertung von 650. 



 
Für eine genaue Beurteilung der Spielstärke des besten Individuums muss man die Ergebnisse
aus Spielen gegen die selbstgeschriebenen Schachprogramme untersuchen. Die
Tabelle~\ref{tab:ChessGPResult} listet die Ergebnisse des besten Individuums
der Evolution gegen fünf verschiedene Gegner auf. Der einfachste Gegner ist ein
Programm, das zufällig einen legalen Zug angibt. Die nächste Klasse sind zufällige
Individuen, denn durch die Struktur der Individuen und ihrer Funktionen sind
sie besser als zufällige Züge. Abschließend kommen die Klassen, die durch
Minimax-Programme der Suchtiefen 1-3 erzeugt werden. Für diese Tabelle wurden
100 Spiele pro Gegner durchgeführt. Während der Evolution wurden zur Analyse des
besten Individuums die gleichen Spiele durchgeführt, es wurden jedoch aus Zeitgründen
nur fünf Spiele pro Gegner durchgeführt. In den Plots~\ref{fig:CGMinMax1}
und~\ref{fig:CGMinMax2} sind die Ergebnisse für ein Minimax-Programm der Suchtiefe eins
und zwei zu sehen, diese zeigen am besten die Entwicklung innerhalb der Population.
So kann man in beiden Plots erkennen, dass die besten Programme während der Generation
100 und 150 in der Population existieren. Dies kann man gut an der geringen Varianz
der Ergebnisse in der Abbildung~\ref{fig:CGMinMax1} erkennen und an den Ergebnissen
in der Abbildung~\ref{fig:CGMinMax2}. Dabei würde ein Ergebnis von 1,0 bedeuten, dass das
Individuum fünf Mal gegen das Minimax-Programm gewonnen hat. Man kann aber in
beiden Abbildungen kaum eine Ähnlichkeit zum Plot der Elowerte in Abbildung~\ref{fig:ChessGPElo}
erkennen.


\begin{figure}
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/chessGPMinMax1.ps,width=7cm}}
  \caption{Der Plot zeigt das durchschnittliche Ergebnis von fünf Spielen des besten Individuums
        gegen einen MiniMax-Algorithmus der Tiefe 1. Die Rauten geben die Varianz der
        Ergebnisse an. Die Kurve gibt an, ob das Individuum gewonnen (1,0) oder verloren
        (0,0) hat.}
  \label{fig:CGMinMax1}
 %  \end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/chessGPMinMax2.ps,width=7cm}}
  \caption{Der Plot zeigt das durchschnittliche Ergebnis von fünf Spielen  des besten Individuums
        gegen einen MiniMax-Algorithmus der Tiefe 2. Die Rauten geben die Varianz der
        Ergebnisse an. Die Kurve gibt an ob, das Individuum gewonnen (1,0) oder verloren
        (0,0) hat.}
  \label{fig:CGMinMax2}
  \end{minipage}
  \end{figure}


Die Tabelle~\ref{tab:ChessGPResult} zeigt nun eine genauere Analyse der Spielstärke
des besten Individuums. Daraus kann man erkennen, dass das Individuum ungefähr die
Spielstärke eines Schachprogramms der Suchtiefe zwei hat. Das Individuum hätte zwar
20.000 Knoten im Suchbaum expandieren können, was ausgereicht hätte ein Programm
der Tiefe drei zu schlagen, denn ein effizienter Suchalgorithmus benötigt für diese
Suchtiefe etwa 10.000 Knoten. Ein normaler Minimax-Algorithmus benötigt jedoch 38.000 Knoten.
Das beste Individuum hat jedoch im Durchschnitt nur 531 Knoten pro Zug expandiert,
was dem Niveau eines Alpha-Beta Suchprogramms der Suchtiefe zwei entspricht. Somit
hat die Evolution zwar einen effizienten Algorithmus entwickelt, jedoch hat sie nicht
alle Möglichkeiten genutzt, die ihr zur Verfügung standen.
Hier muss man nun anmerken,
dass wir nur einen Pool mit 100 Individuen genutzt haben, die Evolution
nach 160 Generationen abgebrochen haben und nur eine Evolution
durchführen konnten. Jedoch waren wir nicht in der Lage weitere Läufe mit dieser
Größenordnung oder sogar mit mehr Individuen und einer längeren Evolution durchzuführen,
da selbst diese Evolution bei einer parallelen Berechnung auf 28 Rechnern mehr als
14 Wochen benötigte. Da uns auch Testläufe mit kleineren Populationen und
mit vorevolvierten Programmen keine Verbesserung zeigten, gehen wir davon aus,
dass die erzielten Ergebnisse den Möglichkeiten des Systems entsprechen.

 
\begin{table}
\begin{center}
\begin{tabular}{|p{2cm}|p{1,5cm}|p{1,5cm}|p{1,5cm}|p{1,5cm}|p{1,5cm}|}
\hline
\vspace{0.01mm} Gegner & \vspace{0.01mm} Zufall & \vspace{0.01mm} zufälliges Individuum & \vspace{0.01mm} Minimax (1) & \vspace{0.01mm} Minimax (2) & \vspace{0.01mm} Minimax (3)\\
\hline 
 \vspace{0.01mm}  Sieg (Individuum) & \vspace{0.01mm} 100 &  \vspace{0.01mm} 87 & \vspace{0.01mm} 95 &  \vspace{0.01mm} 38 &  \vspace{0.01mm} 0 \\
\hline 
\vspace{0.01mm}  Überlegen          &  \vspace{0.01mm}  0 & \vspace{0.01mm}   0 &  \vspace{0.01mm} 3 &  \vspace{0.01mm} 18 &  \vspace{0.01mm} 0 \\
\hline 
\vspace{0.01mm}   Remis             &  \vspace{0.01mm}  0 & \vspace{0.01mm}  13 &  \vspace{0.01mm} 0 &  \vspace{0.01mm} 13 &  \vspace{0.01mm} 5 \\
\hline 
\vspace{0.01mm}   Unterlegen        &  \vspace{0.01mm}  0 &  \vspace{0.01mm}  0 &  \vspace{0.01mm} 2 &  \vspace{0.01mm} 13 &  \vspace{0.01mm} 8 \\
\hline 
\vspace{0.01mm}   Niederlage        &  \vspace{0.01mm}  0 &  \vspace{0.01mm}  0 & \vspace{0.01mm}  0 &  \vspace{0.01mm} 18 & \vspace{0.01mm} 87 \\
\hline 
\end{tabular}
\end{center}
\caption{Diese Tabelle enthält die Spielausgänge der Spiele des besten Individuums
gegen verschiedene Gegner. Der Zufallsgegner ist ein Schachprogramm, das zufällige,
aber legale Züge liefert. Die Minimax(x) Gegner sind Minimax-Algorithmen mit den
Suchtiefen eins bis drei.}
\label{tab:ChessGPResult}
\end{table}

%----------------------------------------------------------------------
\subsection{Fazit ChessGP}
%----------------------------------------------------------------------
\label{sub:ChessGPFazit}


ChessGP ist ein Negativergebnis, das aber als Grundlage für die weiteren
Systeme wichtig war. Das System konnte Schachindividuen evolvieren, jedoch
war die Komplexität des Systems zu groß und die Aufgabenstellung einiger
Module zu schwer gewählt. So erreichte das beste Individuum nur eine Spielstärke,
die einem Alpha-Beta Algorithmus der Suchtiefe zwei entspricht.
Somit hat dieses System wichtige Ergebnisse und Impulse für die weitere Entwicklung geliefert
und durfte daher in dieser Diskussion nicht fehlen.

Ein positives Ergebnis sehen wir in der Hierachisierung des Gesamtindividuums, sie
ist eine Möglichkeit komplexe Aufgaben durch ein GP-Individuum evolvieren zu lassen.
Durch die Verwendung verschiedener Ebenen mit unterschiedlichen Funktionssets konnten
gezielt Teilprobleme gelöst werden, die dann zu einem Gesamtsystem zusammengefasst
werden konnten. Dies ermöglichte eine Reduktion der Komplexität der Gesamtaufgabe.
Das Problem der Komplexitätsreduktion wurde aber nicht vollständig gelöst, wie
wir am Verhalten der Variantenebene sehen konnten. Letztlich war es nicht möglich
Individuen zu evolvieren, die das zuerst formulierte Ziel erreichten. Die Gründe
sind hier in dem Ziel und den Möglichkeiten der Individuen zu sehen. So sollten
möglichst kurze Zuglisten mit verschiedenen Ausrichtungen erzeugt werden, die
von den Individuen ohne die Möglichkeit einen Suchbaum aufzubauen erzeugt werden sollten.
Motiviert wurde dies durch psychologische Untersuchungen menschlicher Schachexperten,
die Züge nicht durch die Abarbeitung eines Suchbaumes ermitteln, sondern indem sie 
die vorhanden Situation einschätzen. Dieses Verhalten sollte nachgeahmt werden,
die Evolutionsläufe haben aber gezeigt, dass das System mit den vorhandenen Mitteln nicht
in der Lage war die Aufgabe zu lösen. Auch eine Vereinfachung der Aufgabenstellung
brachte nur wenig Erfolg, so dass wir an dieser Stelle \emph{selbst} erzeugte
Individuen nutzen mussten um ein spielendes Individuum zu entwickeln. Da wir hier
nur Operationen aus dem Sprachumfang genutzt haben, spricht nichts gegen die prinzipielle
Möglichkeit, dass solche Individuen durch eine Evolution erzeugt werden können.

Wichtig war auch die Erfahrung, dass eine Elo-Bewertung als Fitness für die Individuen
nicht sinnvoll ist, da sie ein relatives Maß ist. Dies in Verbindung damit, dass
Individuen hauptsächlich gegeneinander gespielt haben um die Fitness zu berechnen,
führte dazu, dass die Elowerte kein objektives Maß der Spielstärke darstellten.
Denn wenn ein Individuum besser war als alle anderen, stieg seine Fitness (Elowert)
immer weiter, solange kein Individuum erzeugt wurde, was dieses Individuum schlagen
konnte. An der parallel durchgeführten Bewertung mittels verschieden starker Programme
konnte man auch erkennen, dass in der Population gute Individuen verloren gehen
können. Dies ist aber für eine Evolution von Schachprogrammen aufgrund der hohen
Rechenzeiten nicht praktikabel.

Grundsätzlich muss man zum ChessGP-System sagen, dass sich viele Ideen des Systems
als zu komplex erwiesen haben. So waren die drei einzelnen Evolutionsprozesse zwar möglich,
jedoch schränkt man die Möglichkeiten der Ebenen, miteinander zu interagieren, ein,
da sie sich nur in den durch die Fitnessfunktion gegebenen Grenzen bewegen konnten. Auch einzelne
Aufgabenstellungen, wie die der Variantenebene, waren zu komplex um adequat gelöst zu werden.
Eine stärkere Anlehnung an Suchalgorithmen war somit ein Ergebnis des ChessGP-Systems,
ebenso eine Vereinfachung der Evolution selbst.

\vfill
\pagebreak

%----------------------------------------------------------------------
\section{qoopy}
%----------------------------------------------------------------------
\label{sec:qoopyResults}

Das qoopy-System hat verschiedene Probleme, die durch das ChessGP-System aufgezeigt wurden,
aufgegriffen und versucht diese zu beseitigen. Ein wichtiges Problem des ChessGP-System
war das Problem der Rechenzeit für eine Evolution. So konnte trotz einer
Parallelisierung nur eine kurze Evolution mit wenigen Individuen durchgeführt werden.
Daher wurde das qoopy-System als eine internetbasierte Evolution durchgeführt,
um hier die Vorteile des Peer-to-Peer Computing~\cite{AlbrechtAGW04} zu nutzen, siehe
Abschnitt~\ref{sec:EvoQoopy}. Dadurch konnte die Evolution mit sehr viel mehr
Individuen und Generationen durchgeführt werden, als es bei dem ChessGP-System möglich
war. Der Vorteil der großen Rechenkraft wurde durch den Nachteil erkauft, dass
man weniger Einfluss auf die Evolution hatte, da wir den einzelnen Nutzern die
Möglichkeit gegeben haben verschiedene Parameter der Evolution zu variieren,
um so eine stärkere Bindung der Nutzer an das System zu erzielen. Dies war auch
erfolgreich, so konnten über einen Zeitraum von mehr als drei Monaten über 1.300
Nutzer am Projekt gezählt werden. Zusätzlich wurden verschiedene Statistiken der
einzelnen Nutzer im Internet veröffentlicht, um jedem Nutzer zu zeigen, wie gut
\emph{seine Individuen} sind und wie viel Rechenzeit er zur Verfügung gestellt hat.
Die besten Individuen wurden in einer Top-100 Liste erfaßt.

Aufgrund der internetweiten Evolution wurden die besten Individuen zum Abschluss
noch einer Nachbewertung unterzogen, um eine genauere Bewertung der Individuen
zu erzielen. Die Nachbewertung wurde nicht im Internet durchgeführt, so dass mehr
Spiele und auch Spiele gegen stärkere Gegner durchgeführt werden konnten als während 
der internetweiten Evolution.


%----------------------------------------------------------------------
\subsection{Die Nachbewertung}
%----------------------------------------------------------------------

Die Fitness der Individuen wird durch die Ergebnisse der Partien gegen Programme
fester Suchtiefen bestimmt. Als Gegner standen den Individuen die Gegner
$G_1, G_2, \ldots , G_7$ zur Verfügung, wobei der Index die Suchtiefe des 
Programms angibt, siehe auch Abschnitt~\ref{sub:black}. Das Spielergebnis ist
ein Wert im Intervall von $[0, 1]$, wobei 0 einer Niederlage des Individuums 
entspricht, 0.5 einem Remis und 1.0 dem Gewinn der Partie für das Individuum.
Da Partien zwischen dem Individuum und dem Gegnerprogramm sehr lange dauern können,
gelten die gleichen Abbruchkriterien wie bei der Fitnessberechnung, so wurde nach maximal
50 Halbzügen eine Partie beendet. Dann erfolgte eine Materialbewertung der letzten
Stellung im Intervall von $[0, 1]$ und diese wurde als Ergebnis des Spiels gewertet.
Da die Individuen aufgrund der Blattbewertung nicht deterministisch spielten, ist war der 
Partieverlauf und somit das Ergebnis nicht sicher vorhersagbar. Somit musste jedes
Individuum gegen jeden Gegner $G_i$ mehrere Partien spielen um eine Aussage über die
Güte der Individuen zu erhalten. Da die Nachbewertung auf einem eigenen Rechner 
am Institut durchgeführt wurde, haben wir in interessanten oder kritischen Fällen 
maximal 100 Partien pro Gegner durchgeführt, im Normalfall 20 Partien. Eine
Nachbewertung mit je 20 Partien pro Gegner dauerte 1-2 Tage.
Die besten 200 Individuen der Evolution sollten nachbewertet werden, da dies jedoch
zu zeitaufwendig wäre, wurde eine Vorauswahl getroffen. Dabei wurde eine Nachbewertung
mit weniger Partien durchgeführt und überprüft, ob es zu einer starken Überbewertung
der Fitness während der Evolution gekommen war. Es hat sich gezeigt, dass die Fitness
der Individuen um eine bis drei Fitnessklassen während der Evolution besser bewertet
wurde als durch die Nachbewertung. Daher wurden am Ende 82 Individuen aus der Liste
der 200 besten Individuen nachbewertet. 


\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\vspace{0.01mm}  Fitness & \vspace{0.01mm} $G_3$ & \vspace{0.01mm} $G_4$ & \vspace{0.01mm} $G_5$  & \vspace{0.01mm} $G_6$  \\
\hline 
\vspace{0.01mm}  10,4816  & 1,0 & 0,8807 & 0,7528 & 0,10  \\
          & 100  &  50   & 50     &  50   \\
\hline 
\vspace{0.01mm}  10,3981  & 1,0 & 0,9803 & 0,5486 & 0,1652  \\
          & 100  &  50    & 50      &  50    \\
\hline 
\vspace{0.01mm} 10,3943  & 1,0 & 0,9218 & 0,6155 & 0,1809  \\
         & 100 &  100   & 100    &  93    \\
\hline 
\vspace{0.01mm}  10,3803  & 1,0 & 0,8898 & 0,6274 & 0,2065  \\
          & 100 &  100   & 100    &  100   \\
\hline 
\vspace{0.01mm}  10,3647  & 1,0 & 0,9318 & 0,5921 & 0,1717  \\
          & 100 &  50    & 50     &  50    \\
   \hline 
\vspace{0.01mm}  10,3572  & 1,0 & 1,0 & 0,4285 & 0,2072  \\
          & 100 &  20 & 20     &  20     \\
\hline 
\vspace{0.01mm}  10,3479  & 1,0 & 0,8841 & 0,7205 & 0,1397  \\
          & 100 &  20    & 20     &  20     \\
\hline 
\vspace{0.01mm} 10,3425   & 1,0 & 0,9431 & 0,4437 & 0,2503  \\
          & 100 &  20    & 20     &  20     \\
\hline 
\vspace{0.01mm}  10,3345  & 1,0 & 0,95 & 0,582 & 0,425  \\
          & 100 &  20  & 20    &  20  \\
\hline 
 10,331   & 1,0 & 0,95 & 0,6649 & 0,0748  \\
          & 100 &  20  & 20     &  20  \\
\hline 
\end{tabular}
\end{center}
\caption{Diese Tabelle zeigt die Fitness der besten Individuen, die durch die Nachbewertung
ermittelt wurden sowie das durchschnittliche Spielergebnis der Individuen gegen die
verschiedenen Gegnerprogramme $G_i$ und die Anzahl der Spiele gegen das entsprechende
Gegnerprogramm. Das durchschnittliche Spielergebnis liegt zwischen 0 und 1, wobei
0 den Verlust der Partie bedeutet und 1 den Gewinn.}
\label{tab:qoopyResult}
\end{table}

Die Tabelle~\ref{tab:qoopyResult} führt die Fitness und die durchschnittlichen 
Spielergebnisse der besten 10 Individuen nach der Nachbewertung auf. Gleichzeitig
wird das durchschnittliche Spielergebnis der Individuen gegen die verschiedenen 
Programme fester Suchtiefe mit der Anzahl der Spiele angegeben. Man kann an der
Tabelle sehr gut sehen, dass Programme der Suchtiefe fünf ($G_5$) noch geschlagen 
werden können, aber Programme der Suchtiefe sechs ($G_6$) nicht mehr. 

Wichtig ist hierbei, dass die Individuen im Durchschnitt 60.000 Knoten 
expandieren um diese Ergebnisse zu erreichen. Ein einfaches Alpha-Beta Schachprogramm
muss bei einer Suchtiefe von fünf Halbzügen 897.070 Knoten pro Zug expandieren und
ein F-Negascout Algorithums benötigt auch noch 120.000 Knoten bei dieser Suchtiefe.
Diese Programme würden einen Fitnesswert von 10 erreichen, die Individuen erreichen 
eine etwas bessere Fitness und nutzen dabei weniger Resourcen als die bekannten
Schachprogramme. Im Vergleich zu einem F-Negascout Algorithmus ist die Ersparnis
50\% und im Vergleich zu einem Alpha-Beta Algorithmus sogar 94\%. 

Die qoopy Individuen beruhen, wie im Kapitel~\ref{sec:qoopy-Ind} beschrieben,
auf einen Alpha-Beta Algorithmus und können diese an drei Punkten optimieren. 
Der Evolution ist es also gelungen einen bekannten Algorithmus zu verbessern,
denn wie man in der Tabelle erkennen kann, liegt das durchschnittliche Spielergebnis
nicht bei $0,5$, was einem Remi entsprechen würde und somit die gleiche Spielstärke
anzeigen würde, sondern in acht von zehn Fällen deutlich über $0,5$, das beste
Ergebnis war sogar $0,75$. Das Spielergebnis bezieht sich immer 
auf das Individuum und ist auf den maximalen Materialwert ohne die Könige normiert.
Das heißt, ein Ergebnis von eins für ein Individuum bedeutet, dass es keine
Figuren verloren hat, das Gegnerprogramm nur noch den König besitzt oder das
Gegnerprogramm schachmatt ist. 
Eine Figur hat einen Einfluss von $\frac{\text{Figurwert}}{4060}$
für einen Bauern, mit einem Figurwert von $100$ ergibt das $\frac{100}{4060} \approx 0,0246$.
Der Wert $0,75$ liegt um $0,25$ über dem Wert eines Remis, das heißt,
das Individuum hat einen Materialvorteil vom $0,25$, dies sind ungefähr
$\frac{1000}{4060}$ und entspricht bei den für qoopy gewählten Figurwerten 
einer Dame und einem Bauern oder zwei Türmen, andere Figurwerte können 
in Abschnitt~\ref{sub:black} nachgeschlagen werden.


%----------------------------------------------------------------------
\subsection{Analyse}
%----------------------------------------------------------------------



Ein Individuum des qoopy-Systems besteht wie ein ChessGP Individuum aus
drei Ebenen, jedoch bestehen die Ebenen im letzteren Individuum aus mehreren
Modulen. Im qoopy Individuum wird jede Ebene durch ein Modul dargestellt und die
Evolution eines qoopy Individuums wird in einem Schritt durchgeführt. Dadurch
erhält man, anders als im ChessGP-System, nur einen Fitnesswert, der die Gesamtleistung
des Individuums beschreibt. Somit kann eine Bewertung der einzelnen Module erst
durch eine anschließende Analyse erfolgen. Da es sich aber bei den Individuen um
ein Gesamtsystem handelt, kann auf der anderen Seite eine allgemein gültige
Bewertung der einzelnen Module nicht durchgeführt werden. Denn für sich alleine
betrachtet kann ein Modul ein schlechteres Ergebnis als das Modul eines anderen
Individuums haben, aber in der Kombination mit den anderen Modulen doch zu besseren
Ergebnissen führen als das \emph{bessere} Modul. 


%----------------------------------------------------------------------
\subsubsection{Tiefenmodul}
%----------------------------------------------------------------------


Das Tiefenmodul hat im Gesamtindividuum die Aufgabe die maximale Suchtiefe für jeden Pfad im
Suchbaum zu bestimmen, dadurch wird ein großer Einfluss auf die Spielstärke
des Individuums und die Anzahl der expandierten Knoten im Suchbaum ausgeübt.
Es hat sich gezeigt, dass zufällig initialisierte Individuen sehr spielschwach sind.
\begin{wrapfigure}{r}{70mm}
% \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/NodesSpielverlaufBIWK.eps,width=7cm}}
  \caption{Ein Boxplot Diagramm der durchschnittlich verbrauchten Knoten pro Zug
        über eine Spieldauer von 140 Halbzügen. Das Ergebnis wurde über 50 Spiele mit
        einem evolvierten Individuum ermittelt.}
  \label{fig:qoopyNodesInd}
  \end{wrapfigure}%{figure}
Dies liegt hauptsächlich an dem Tiefenmodul, denn die zufälligen Module beschränkten
die Tiefe entweder kaum oder sehr stark. Wenn ein Tiefenmodul die Suchtiefe extrem
beschränkt, werden durch den Rahmenalgorithmus mindestens zwei Halbzüge durchgeführt. 
Kommt es zu keiner Beschränkung, werden maximal zehn Halbzüge durchgeführt. 
Im ersten Fall erhält man
maximal ein Individuum, welches die Fitnessklasse vier erreicht und im zweiten Fall
kann nur ein sehr kleiner Teil des Suchbaums expandiert werden. Da die Suche erst
nach 10 Halbzügen abgebrochen wird und pro Zug maximal 100.000 Knoten expandiert 
werden (siehe hierzu Abschnitt~\ref{sec:qoopy-Ind}), wird ein extrem linkslastiger
Suchbaum erzeugt. 
Dies ist zwar immer das Ergebnis einer Alpha-Beta Suche, aber in
Verbindung mit einem zufälligen Zugsortierungs-
und Stellungmodul erreichen diese Individuen noch schlechtere Ergebnisse als ein 
Individuum mit einem restriktiven Tiefenmodul. Denn in diesem Fall könnten von
dem Individuum vielleicht nur die schlechten Züge expandiert werden, aber für ein
gutes Resultat braucht die Alpha-Beta Suche eine gute Zugsortierung und Stellungsbewertung.
Da dies für zufällige Individuen im allgemeinen nicht gilt, erreichen Individuen
mit einem restriktiven Tiefenmodul bessere Ergebnisse, da diese die gesamte Breite des 
Suchbaums bis zur Tiefe zwei explorieren und so trotz einer schlechten Zugsortierung
auch gute Züge expandieren können. 

Während der Evolution bildete sich schnell ein Modul, das 
die Suchtiefe auf fünf Halbzüge begrenzte. Wenn man sich vor Augen führt, dass dem
Individuum 100.000 Knoten pro Zug zur Verfügung stehen, ist dies eine gute Suchtiefe.
Denn ein guter Alpha-Beta Algorithmus benötigt 50.000 Knoten bei einer Suchtiefe von
fünf und 320.000 Knoten bei einer Suchtiefe von sechs. Somit könnte ein Individuum selbst
mit schlechter Zugsortierung noch einigermaßen gut spielen. Erst sehr spät entwickelten 
sich Individuen, die in den ersten Zügen nur zwei oder drei Halbzüge expandierten. Anschließend
expandierten die Individuen den Suchbaum wieder bis zur Tiefe fünf. Die durch das Individuum
eingesparten Knoten konnten so in der späteren Phase des Spiels genutzt werden. Jedoch
kam es während der gesamten Evolution nicht dazu, dass ein Tiefenmodul entwickelt wurde,
das mehr als fünf Halbzüge tief suchte. 
Die Abbildung~\ref{fig:qoopyNodesInd} zeigt das oben
beschriebene Verhalten, welches die Reduktion der Suchtiefe zum Beginn einer Partie
durchführt. Man kann gut erkennen, dass es ab dem fünften Halbzug zu einem Anstieg des
Knotenverbrauchs führt. Nach dem 20. Halbzug kommt es wieder zu einer Reduktion 
der expandierten Knoten, die mehr oder weniger bis zum 50. Halbzug konstant bleibt.
Anschließend kommt es kontinuierlich zu einer weiteren Reduktion des expandierten Knotens,
dies wird jedoch nicht durch das Individuum verursacht, sondern ergibt sich durch
die geringe Anzahl von Figuren auf dem Spielfeld zum Ende der Partie und die konstant
gehaltene Suchtiefe des Individuums.






%----------------------------------------------------------------------
\subsubsection{Zugsortierungsmodul}
%----------------------------------------------------------------------

Das Zugsortierungsmodul hat neben dem Tiefenmodul den größten Einfluss auf
die Anzahl der expandierten Knoten und die Spielstärke der Individuen. 
Denn das Alpha-Beta Verfahren (siehe Kapitel~\ref{sec:alphaBeta}) betrachtet für
jede Stellung des Spielbaums, in dem die Suche fortgesetzt werden soll, alle 
möglichen Stellungen, die von dieser Stellung aus durchgeführt werden können.
Eine gute Vorsortierung der Zugliste kann die Suche erheblich beschleunigen, denn wenn
dem Algorithmus vorzeitige gute Alternativen bekannt sind, verkleineren sie das 
$(\alpha, \beta)$ Suchfenster oder ermöglichen den Abbruch der Suche für diesen
Weg im Suchbaum durch einen Alpha- oder Beta-Schnitt. Wenn man den Worst Case annimmt 
und ein Zugsortierungsmodul die Züge immer in der falschen Reihenfolge ordnet, dann muss 
ein Alpha-Beta Algorithmus alle Züge expandieren, da keine
Verkleinerung des Suchfensters oder ein Schnitt im Suchbaum  möglich sind, 
siehe Abschnitt~\ref{sec:Zugbewertung}.  Dann würde der Algorithmus alle
Knoten expandieren und es würde zu keiner Einsparung kommen. Aber selbst die
besten Schachprogramme expandieren 20-30\% mehr Knoten, als in einem optimalen Suchbaum
expandiert würden. Eine Verbesserung der Zugsortierung führt somit zu einer starken
Reduktion der Größe des Suchbaums. 


Im Rahmen der Analyse des Zugsortierungsmoduls wurden spielstarke Individuen aus der
Top 200 Liste mit zufälligen Individuen und dem Algorithmus der Gegnerprogramme bezüglich
des Knotenverbrauchs bei einer konstanten Suchtiefe verglichen. Durch diesen Ansatz
wird die Güte der evolvierten Zugsortierungsmodule, bezüglich der Reduktion des
Suchraums zu den beiden Vergleichsalgorithmen, untersucht. Hierzu wurden  die Zugsortierungsmodule
in einen Alpha-Beta Algorithmus eingesetzt, so dass die Ergebnisse unabhängig von dem
Rest des Individuums waren. Das Gegnerprogramm ist jedoch weiterhin das Programm,
welches auch während der Evolution verwendet wurde (siehe Abschnitt~\ref{sub:black}).
Die Stellungsbewertung des Apha-Beta Algorithmus entspricht der des Gegnerprogramms.
Die Programme wurden auf 4.500 Brettstellungen getestet, die aus 50 Partien stammen,
die der Gegneralgorithmus gegen sich selbst gespielt hat. Damit wird jede 
Zugsortierungsstrategie auf identischen Situationen getestet und die Ergebnisse sind
somit direkt vergleichbar.
\begin{wrapfigure}{r}{70mm}
%  \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/NodesTiefenAnstiegWK.eps,width=5.5cm}}
  \caption{Durchschnittliche Anzahl verbrauchter Knoten im Suchbaum für
        verschiedene Suchtiefen. Den größten Unterschied beim Knotenverbrauch
        erkennt man für die Suchtiefe 6. Die Daten wurden über 50 Spiele gemittelt.}
  \label{fig:qoopyNodesDepth}
  \end{wrapfigure}%{figure}
  
Zur Analyse wurden Module aus drei Individuen der Top 200 Liste ausgewählt und drei
zufällige Module erzeugt. Bei der Analyse hat sich gezeigt, dass sich während der
Evolution Zugsortierungsmodule entwickelt haben, die bei einer Suchtiefe von fünf 
Halbzügen einer zufälligen Sortierung bezüglich des Knotenverbrauchs um den Faktor 7,8
und bei einer Suchtiefe von sechs Halbzügen um einen Faktor von 16,7 überlegen sind.
Gleichzeitig ziegte sich, dass die evolvierten Module den Gegnerprogrammen bei einer
Suchtiefe von fünf um den Faktor 1,8 und bei einer Suchtiefe von sechs sogar um
7,8 überlegen waren. Dies ist besonders erstaunlich, da die Gegnerprogramme im Gegensatz
zu dem Alpha-Beta Algorithmus, der als Testumgebung für die zufälligen und 
evolvierten Module diente, ein Scout-Algorithmus mit der F-Verbesserung kombiniert mit
den Techniken des Iterative Deepening und den Killer-moves nutzten, was gegenüber einem
einfachen Alpha-Beta Algorithmus eine erhebliche Einsparung von Knoten im Suchbaum
zur Folge hat. Trotzdem konnten die durch die Evolution erzeugten Module die Gegnerprogramme
bezogen auf den Knotenverbrauch im Suchbaum schlagen. Die Abbildung~\ref{fig:qoopyNodesDepth}
zeigt den Knotenverbrauch der drei Gruppen für drei, vier, fünf und sechs Halbzüge.
Deutlich kann man erkennen, dass die Unterschiede in der Zugsortierung erst ab einer
Suchtiefe von fünf richtig erkennbar werden. Dies liegt einerseits an der Skalierung
der y-Achse, jedoch lagen die Ergebnisse aller drei Klassen sehr eng zusammen, so dass
man nicht sagen konnte, ein Modul ist deutlich besser oder schlechter als ein 
anderes. Dies liegt daran, dass die zufälligen Module durch die Einschränkungen der
Parameter, die vorgegeben sind, schon sinnvolle Lösungen für die Problemstellung sind.
Jedoch konnte die Evolution die Parametereinstellung so weit verbessern, dass es dem Modul
sogar möglich war das Gegnerprogramm in Bezug auf die Anzahl der expandierten Knoten
zu unterbieten.





 

%  \begin{figure}
%  \centerline{\epsfig{figure=Pictures/Results/NodesSpielverlaufBRWK.eps,width=10cm}}
%  \caption{Box plot diagram of average number of
%  used nodes during a game with a random individual, average over 50
%  games. The plot shows that the most nodes will be used between ply
%  10 and 60. }
%  \label{fig:qoopyGameRunRand}
%  \end{figure}

 


%----------------------------------------------------------------------
\subsubsection{Stellungsmodul}
%----------------------------------------------------------------------


Das Stellungsmodul hat die Aufgabe materielle und positionelle Merkmale einer
Stellung zu bewerten. Die Stellungsmodule der Individuen sind von der Struktur her 
identisch zu denen der Gegnerprogramme, nur die Werte der einzelnen Merkmale
des Algorithmus unterscheiden sich. Eine genaue Beschreibung des Stellungsmoduls
und seiner Merkmale findet man in Abschnitt~\ref{sec:qoopySellung}. Um das Modul
zu analysieren sind wir ähnlich vorgegangen wie für das Zugsortierungsmodul, hierzu
wurde das Modul in ein Alpha-Beta Programm integriert.
Dann wurden für die Suchtiefen
eins bis fünf 500 Partien gegen das Gegnerprogramm aus der Evolution mit der entsprechenden
Suchtiefe gespielt.
Es wurden drei Module aus Individuen der Top 200 Liste ausgewählt und fünf zufällig
erzeugte Module verwendet. Die zufälligen Module wurden wie bei der Initialisierung
der Evolution erzeugt, also durch die Berechnung einer normal verteilten Zufallsvariable
im zulässigen Intervall für das entsprechende Merkmal.

 \begin{wrapfigure}{r}{70mm}
%  \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/leafbarplotD5WK.eps,width=5.5cm}}
  \caption{Das Balkendiagramm zeigt die Ergebnisse der Suchtiefe fünf für
        die fünf zufälligen Module und die drei evolvierten Stellungsmodule. Sie wurden
        in 500 Partien getestet. Das beste evolvierte Modul konnte 70 \% der
        Partieen gegen das Standardmodul gewinnen, aber auch das beste zufällige Individuum
        konnte 61 \% der Partien für sich entscheiden. }
  \label{fig:qoopyLeafModul}
  \end{wrapfigure}%{figure}
   
Das Balkendiagramm~\ref{fig:qoopyLeafModul} zeigt, wieviele
Partien die verschiedenen Module gegen das Gegnerprogramm, bei einer Suchtiefe von fünf, 
gewonnen haben. Man sieht, dass die zufälligen Module im Bereich von 44 und 61 \% 
liegen und die evolvierten im Bereich von 58 und 70 \%. Dies zeigt zuerst einmal,
dass alle getesten evolvierten Stellungsmodule dem Standardmodul überlegen waren.
Denn wären sie gleich stark, müssten die Ergebnisse in einem kleinen Bereich um 
50 \% liegen, denn in Experimenten mit dem Stellungsmodul des Gegnerprogramms
lagen die Ergebnisse im Bereich von 48 bis 53 \%. 
Da alle Programme die gleiche Suchtiefe benutzen und somit eine ähnliche
Anzahl von Knoten expandieren, liegt der Vorteil der evolvierten Stellungsmodule in 
einer besseren Bewertung der positionellen Kriterien. Dieser Vorteil wird aber erst
mit den größeren Suchtiefen sichtbar. Denn für diese Analyse wurden auch die Suchtiefen
eins bis vier untersucht, jedoch zeigten sich hier nicht so große Unterschiede 
zwischen den Ergebnissen wie in dem Experiment mit Suchtiefe fünf. Grundsätzlich
waren die evolvierten Module immer etwas besser als die zufälligen, jedoch lag der
maximale Unterschied bei diesen Versuchen bei 16 \% und im Fall der Suchtiefe fünf
26 \%.




%Das Balkendiagramm~\ref{fig:qoopyLeafModul} zeigt aber auch deutlich die Stärke
%zufälliger Modul, so war das beste zufällige Modul besser als das schlechteste
%evolvierte. Obwohl auch dieses Modul aus einem der besten 200 Individuen
%entnommen wurde. Das schon zufällige Module relativ stark sind, war von uns auch
%beabsichtigt, um hier die Evolution der einzelnen Internetclients auf einem ähnlichen
%und guten Niveau starten zu lassen. 

Erstaunlich an diesen Ergebnissen sind jedoch auch die großen Unterschiede in 
den evolvierten Modulen, denn die Module wurden aus Individuen entnommen, die eine
ähnliche und sehr gute Fitness hatten. Daraus folgt, dass man über die Güte eines
Moduls, bezogen auf diese Testumgebung, eigentlich keine zuverlässige Aussage 
treffen kann. Das Ergebnis legt die Vermutung nahe, dass die Aufgabe des Moduls 
von der Umgebung abhängig ist, in der es arbeitet. Dadurch ist es nicht möglich
eine objektive Güte der Module untereinander zu erhalten.


%----------------------------------------------------------------------
\subsection{Fazit qoopy}
%----------------------------------------------------------------------
\label{sub:qoopyFazit}


Das qoopy-System zeigte im Gegensatz zum ChessGP-System sehr gute Ergebnisse, so 
konnte das System spielstarke Schachprogramme evolvieren, die im Vergleich mit
bekannten Algorithmen sogar sehr gut abschneiden. Der Ansatz, einen Alpha-Beta Algorithmus
zu nehmen und ihn durch evolutionäre Verfahren zu verbessern, ist somit insgesamt
betrachtet ein großer Erfolg. Das beste Individuum aus der Evolution erreichte
eine Fitness von 10,48 und ist somit besser als ein Schachprogarmm mit einer
festen Suchtiefe von fünf, dies entspricht einem Elowert von 1.400, siehe
Abbildung~\ref{fig:eloEntwicklung}. Dies entspricht einem Vereinsspieler der letzten bis
vorletzten Klasse. Bezogen auf bekannte Schachprogramme sind die Individuen
zwar immer noch sehr schwach, jedoch muss man hier den Rechenaufwand der Programme
bezogen auf ihre Spielstärke vergleichen.
Dabei zeigte sich während der Nachbewertung in 60 Spielen, dass ein Individuum
im Durchschnitt 58.410 Stellungen pro Zug expandiert. Ein einfacher Alpha-Beta
Algorithmus expandiert bei einer festen Suchtiefe von fünf im Durchschnitt
897.070 Stellungen pro Zug. Der von uns als Gegnerprogramm verwendete
F-Negascout Algorithmus expandiert 120.000 Stellungen pro Zug bei dieser
Suchtiefe. Das heißt, die Evolution hat einen Alpha-Beta Algorithmus so
optimiert, dass er nur 6 \% der Ressourcen eines einfachen Alpha-Beta Algorithmus
benötigt und bezogen zum F-Negascout Algorithmus nur 50 \% der Stellungen
betrachten muss, um diesen zu besiegen. Durch den einfachen Aufbau der Individuen
konnte eine Analyse der Individuen durchgeführt werden. Diese zeigte, dass die Zugsortierung
die größte Auswirkung auf die Spielstärke der Individuen hat. Gleichzeitig müssten
bessere Tiefen- und Stellungsmodule die Spielstärke der Individuen noch weiter
steigern, jedoch war das im Rahmen von qoopy nicht so einfach, da wir uns
durch die Internetevolution zwar den Vorteil der großen Rechenkraft gesichert haben.
Gleichzeitig haben wir aber auch einige Nachteile dadurch eingekauft, wie eine
sehr geringe Kontrolle über die einzelnen Evolutionsläufe, \emph{Manipulationen} einiger
User bei der Evolution und ein Geschwindigkeitsnachteil der Java Implementierung.

Das Problem der geringen Kontrolle über die Gesamtevolution war zwar am Anfang
von uns gewollt, damit  eine höhere Bindung der User zu \emph{ihren Individuen}
entstand und sie somit mehr Rechenzeit zur Verfügung stellten. Jedoch war dies aus der
jetzigen Sicht betrachtet ein Fehler. So konnte nur ein Evolutionslauf durchgeführt
werden, der zwar mit verschiedenen Einstellungen in den verschiedenen Demes durchgeführt
wurde, jedoch war es nun nicht mehr möglich eine Verbindung zwischen der Güte einer Evolution
zu ihren Einstellungen herzustellen. Es war auch kaum möglich Evolutionsläufe mit neuen
Individuentypen durchzuführen, da die User lieber die \emph{alte Evolution}
weiter laufen ließen. Der Versuch eine zweite Evolution mit veränderten Individuen
durchzuführen, scheiterte an der geringen Resonanz. 
Die Bindung der User zu der Evolution führte auch dazu, dass einige User die
Fitnessbewertung manipuliert haben, indem sie das Feature \emph{Spielabbruch} genutzt
hatten. Durch den Spielabbruch konnte eine Auswertung zu jedem Zeitpunkt abgebrochen
werden, dies war notwendig, da wir den Rechner nicht immer blockieren konnten.
Wurde die Auswertung dann später wieder gestartet, wurde die Auswertung 
normalerweise beim letzten Zug der Partie wieder gestartet. Jedoch konnte man
auch von Neuem beginnen, indem man das Individuum vorher gespeichert hatte. 
Dies nutzten einige User aus und brachen Spiele ab, wenn ihre guten Individuen
Gefahr liefen ein Spiel zu verlieren und starteten es dann neu. So konnte man
bessere Fitnessbewertungen erreichen, da die Individuen nicht ganz deterministisch
spielten. Als dies im Forum bekannt wurde, haben wir die Nachbewertung der besten
Individuen eingeführt, was zu einer Reduktion vieler Fitnesswerte führte.


Bei der Evolution wäre es daher besser gewesen, so vorzugehen, dass die User nicht eingreifen
können und nur Rechenzeit zur Verfügung stellen, wie dies bei Seti-At-Home
gemacht wird. Dadurch hätte man die ganze Kontrolle über die Evolution erhalten. Jedoch
wäre der Implementationsaufwand für das System viel größer, da man dann nicht
ganze Spiele auf einem Client durchführen könnte, denn ein Spiel kann mehrere Stunden dauern.
Hier müsste man eine Lösung finden, welche die Bewertung der Individuen in
kleinere Pakete aufteilt, damit eine Berechnung auf einem Client maximal ein paar
Minuten dauert, so dass der Verlust einer Berechnung nicht groß ist.




%----------------------------------------------------------------------
\section{GeneticChess System}
%----------------------------------------------------------------------
\label{sec:State-Space:Run}

In diesem Kapitel werden die Ergebnisse des GeneticChess Schachsystems vorgestellt,
es ist das letzte System, welches entwickelt wurde, und versucht somit alle Ergebnisse
der Vorgängersysteme in sich zu vereinen. Genau wie das qoopy System besteht es
aus den drei Modulen Materialbewertung, Zugbewertung und  Tiefenmodul.
Jedoch sind diese Module in ihrem Aufbau und in ihrem Verhalten komplexer,
dadurch ist eine Analyse der einzelnen Module nicht so einfach möglich, wie es
für das qoopy System war. So konnte im qoopy System für das Tiefenmodul nach 
einer Analyse das Verhalten des Moduls erklärt werden, dies ist hier durch
die Menge verschiedener Verhaltensweisen nicht möglich. Man kann zum Beispiel sehen, dass
einige Individuen die maximale Anzahl von Knoten immer ausnutzen, andere jedoch
in jedem Spiel variabel reagieren. Auch die Material- und Zugbewertung kann nicht
wie im qoopy System in ein Standard Alpha-Beta Programm eingesetzt und
getestet werden, da ihr Verhalten im GeneticChess System nicht so eng begrenzt
ist. Tests haben gezeigt, dass Module als schlecht bewertet wurden, obwohl sie aus
sehr guten Individuen stammen. Daher kann man an dieser Stelle keine objektive
Aussage über die Leistungsstärke der Module als solches machen. Dies konnte schon im qoopy System
gezeigt werden. Dies zeigt aber auch, dass sich die Module während der Evolution
gegenseitig beeinflusst haben und somit besser als Gesamtindividuum bewertet
werden sollten. 

Zur Evolution der Individuen wurden Läufe mit einer Knotenbeschränkung von $100.000$ und $250.000$ 
Knoten durchgeführt. Zu Testzwecken wurden
auch Läufe mit nur $10.000$ Knoten durchgeführt, diese Ergebnisse werden hier jedoch
nicht vorgestellt, da sie hauptsächlich genutzt wurden, um Parameter und Funktionsmengen
zu testen. Die meisten Läufe wurden mit $100.000$ Knoten durchgeführt, da eine 
Evolution mit einer Knotenbegrenzung von $250.000$ bis zu einer Woche dauern konnte.
Für diese Läufe war das Ziel, ein Individuum zu evolvieren,
welches ein Programm der Tiefe acht schlägt. Bei den Evolutionsläufen mit $100.000$ Knoten
dagegen war das Ziel, ein Programm der Tiefe sechs zu schlagen, daher ist die durchschnittliche
Zeit für eine Evolution vier bis sechs Stunden.

Für alle Läufe waren die Parameter für die Anzahl der Generationen, die Größe
der Demes und weitere Parameter unverändert. Diese Parameter sind durch die Testläufe
mit $10.000$ Knoten evaluiert worden und in der Tabelle~\ref{tab:GeneticChessPara} 
zusammengefasst. Was einem bei den Parametern sofort auffällt, ist die kleine Population
von nur 20 Individuen, was für GP-Läufe ungewöhnlich ist. In Abschnitt~\ref{sec:GPResult}
konnte aber schon gezeigt werden, dass diese Poolgröße für die Linear-Graph Struktur
ausreichend ist um gute Ergebnisse zu erzeugen. Dies hatte ja auch zur Wahl dieser
Struktur innerhalb der State-Space Struktur der Schachindividuen geführt.
Ein zweiter Parameter, der auffällig ist, ist die geringe Anzahl von Evaluationen.
So werden maximal $4.000$ Evaluationen durchgeführt, danach wird die Evolution
abgebrochen. Die Evolution kann aber auch abgebrochen werden, wenn ein Individuum
eine vorgegebene Güte erreicht. Für die Evolutionsläufe mit $100.000$ Knoten
war diese der Gewinn einer Partie gegen Programme der Suchtiefe sechs und bei 
$250.000$ Knoten der Gewinn einer Partie gegen Programme der Suchtiefe acht.


\begin{table}
\begin{center}
\begin{tabular}{|p{3cm}|p{3cm}|p{6cm}|}
\hline
 Parameter & Wert & Beschreibung \\
\hline 
 Evaluationen & 4000 & Maximale Anzahl der Fitnessauswertungen pro Lauf \\
\hline 
 Population & 20 & Die Größe der Population für einen
 Lauf \\
\hline 
 Crossover & 0,2 & Wahrscheinlichkeit, dass zwei Individuen an einem
 Crossover teilnehmen\\
\hline 
 Mutation & 1,0 & Wahrscheinlichkeit, dass ein Individuum mutiert wird\\
\hline 
 Selektion & Turnierselektion 2*2 & Turnierselektion aus zwei Zweier-Turnieren\\
\hline 
 Minimale Individuengröße & 20  & Anzahl der Knoten, die ein Individuum
 minimal haben durfte \\
\hline 
 Maximale Individuengröße & 60 & Anzahl der Knoten, die ein Individuum
 maximal haben durfte \\
\hline 
 Maximale Individuen Tiefe & 10  & Die maximale Tiefe der Graphen in den einzelnen
        Modulen \\
\hline 
\end{tabular}
\end{center}
\caption{Diese Tabelle enthält alle Parameter, die für alle Tests
der Materialbewertung genutzt wurden. }
\label{tab:GeneticChessPara}
\end{table}

Für die Läufe mit $100.000$ Knoten wurden die Parameter für den Programmflussabschnitt,
siehe auch Kapitel~\ref{sec:StateSpaceStrukt}, variiert. Der Programmflussabschnitt
bestimmt, ob die Materialbewertung oder die Zugbewertung aufgerufen
wird und damit eine Rekursion durchgeführt wird. Vor dem Aufruf der Zugbewertung
müssen jedoch die möglichen Züge für die Stellung generiert werden. Neben der
Entscheidungsfunkton bestimmt der Programmflussabschnitt noch, welche Züge generiert
werden. Hierzu stehen vier Funktionen zur Verfügung, eine Funktion generiert alle 
legalen Züge für die aktuelle Stellung. Die zweite Funktion generiert aggressive
Züge, die dritte defensive Züge und die letzte Funktion ermöglicht dem Individuum
einen Nullzug durchzuführen. Um den Einfluss der verschiedenen Funktionen auf die
Fähigkeiten des Individuums zur Entwicklung eines Algorithmus zu bestimmen,
wurden Evolutionsläufe mit folgenden Funktionskombinationen durchgeführt:
\begin{itemize}
\item 1. alle legalen Züge,
\item 2. alle legalen und aggressive Züge,
\item 3. alle legalen,  aggressive  und defensive Züge,
\item 4. alle legalen, aggressive, defensive  und Nullzüge.
\end{itemize}
Die letzteren Funktionsmengen  ermöglichen der Evolution
Programme zu entwickeln, die immer komplexere Suchbäume erzeugen. Alle Funktionsmengen
enthalten die Funktion \emph{alle legalen Züge}, dies ist notwendig, da sonst
Programme entstehen würden, die nicht die Möglichkeit hätten 
den Suchraum ausreichend aufzuspannen. Die Philosophie bei der Auswahl der Funktionsmengen 
ist es, der Evolution
immer weitere Möglichkeiten zu geben, ohne ihr die Möglichkeit der vorherigen Stufe
zu nehmen. Für jede dieser Funktionsmengen wurden Läufe mit
der $100.000$ Knoten Grenze durchgeführt, die Ergebnisse werden im folgenden
dargestellt.


Wie man anhand der Fitnessfunktion in Kapitel~\ref{sec:SchachFit} sehen kann,
war die Evolution darauf ausgelegt, Programme zu entwickeln, die sowohl \emph{weiß}
als auch \emph{schwarz} spielen sollten. Jedoch hat sich bei den Testläufen sehr
schnell gezeigt, dass die Evolution in der vorgegebenen Zeit keine Individuen
entwickeln konnte, die diese Aufgabe mit einer zufrieden stellenden Güte
lösen konnten. In den Läufen mit $10.000$ Knoten konnte keine Evolution Individuen
generieren, die ein Programm der Suchtiefe eins mit beiden Farben schlagen konnte.
Obwohl Programme, die nur weiß oder schwarz spielten, in der Lage waren Programme der Suchtiefe
drei zu schlagen. Daher wurden die Läufe so gestartet, dass die Individuen nur
weiß oder nur schwarz spielten. 


Im Anhang im Abschnitt~\ref{sec:FunktionenGeneticChess} sind alle Funktionen
aufgelistet, die für das GeneticChess-System entwickelt wurden. Jedoch wurden
für die Tests des GeneticChess-Systems nur eingeschränkte Operations-, Terminal- und 
Branchingmengen benutzt. Es wurden auch Tests mit dem kompletten Satz von Funktionen
durchgeführt, jedoch sind die Ergebnise relativ schlecht, näheres dazu später.
Diese Funktionsmengen wurden anhand verschiedener Testläufe entwickelt, dabei haben
sich diese Funktionsmengen als gut erwiesen. Problematisch ist hier, dass aus 
Gründen der Kombinatorik keine vollständigen Tests durchgeführt werden konnten,
um die optimalen Funktionsmengen zu finden. 

Für das Tiefenmodul wurden folgende Funktionssätze verwendet:
Die Operationsmenge bestand aus den Funktionen:  $+, -, *, /$, ifCurrentDepthIsBigger, ifCurrentDepthIsSmaller,
isBiggerThanAlpha, isSmallerThanBeta, isIndKingUnderAttack, isIndKingUnderCover,
isIndQueenUnderAttack, isIndQueenUnderCover, isOppoKingUnderAttack, isOppoKingUnderCover,
isOppoQueenUnderAttack und isOppoQueenUnderCover.  

%Die Operationsmenge bestand aus den Funktionen:
%\begin{itemize}
%\item mathematische Operationen: $+, -, *, /$
%\item Vergleiche mit der aktuellen Tiefe im Suchbaum: ifCurrentDepthIsBigger, ifCurrentDepthIsSmaller
%\item Vergleiche mit den Alpha- und Betawerten der Stellungen: isBiggerThanAlpha, isSmallerThanBeta
%\item Abfragen, ob der eigene König geschützt oder bedroht wird: isIndKingUnderAttack, isIndKingUnderCover
%\item Abfragen, ob die eigene Königin geschützt oder bedroht wird: isIndQueenUnderAttack, isIndQueenUnderCover 
%\item Abfragen, ob der gegnerische König geschützt oder bedroht wird: isOppoKingUnderAttack, isOppoKingUnderCover 
%\item Abfragen, ob die gegnerische Königin geschützt oder bedroht wird: isOppoQueenUnderAttack, isOppoQueenUnderCover 
%\end{itemize}

Die Terminalmenge setzt sich aus den folgenden Funktionen zusammen:
numOfExpandedMoves, numOfMoves, numOfKingMoves, numOfQueenMoves, numOfPawnMoves, numOfBishopMoves,
numOfKnightMoves, numOfRookMoves, bestMoveValue, worstMoveValue, currentMoveValue,
numOfThreatsOfInd, numOfThreatsOfOppo,  numOfCoversOfInd, numOfCoversOfOppo, 
endgameIndex, getBoardSimpleVal, getBoardAdvancedVal, numOfAttacksBefore, numOfDefensedBefore, attackDefenseDiffBefore,
 numOfAttacksAfter, numOfDefensedAfter, attackDefenseDiffAfter, captureValueOfMove, captureFigureOfMove,
 looseValueOfMove, maxLooseValueAfterMove, maxLooseValueBeforeMove, 
 maxCaptureValueAfterMove, maxCaptureValueBeforeMove, moveFigureValue und getHistoryOfMove. 
%\begin{itemize}
%\item Abfrage bezüglich der Anzahl von Zügen: numOfExpandedMoves, numOfMoves, 
%        numOfKingMoves, numOfQueenMoves, numOfPawnMoves, numOfBishopMoves, 
%        numOfKnightMoves, numOfRookMoves 
%\item Abfrage bezüglich des Zugwertes: bestMoveValue, worstMoveValue, currentMoveValue 
%\item Abfrage zur Anzahl der Bedrohungen: numOfThreatsOfInd, numOfThreatsOfOppo 
%\item Abfrage zur Anzahl der gedeckten Figuren: numOfCoversOfInd, numOfCoversOfOppo 
%\item der Endspielindex: endgameIndex 
%\item Berechnung des Materialwertes mittels einfacher Funktionen: getBoardSimpleVal, getBoardAdvancedVal 
%\item Berechnung der angegriffenen bzw. verteidigten Figuren vor dem aktuellen Zug: 
%        numOfAttacksBefore, numOfDefensedBefore, attackDefenseDiffBefore 
%\item Berechnung der angegriffenen bzw. verteidigten Figuren nach dem aktuellen Zug:
%        numOfAttacksAfter, numOfDefensedAfter, attackDefenseDiffAfter 
%\item Parameter geschlagener Figuren: captureValueOfMove, captureFigureOfMove 
%\item Werte des möglichen Figurverlustes: looseValueOfMove, maxLooseValueAfterMove, maxLooseValueBeforeMove 
%\item Werte des möglichen Figurgewinns: maxCaptureValueAfterMove, maxCaptureValueBeforeMove, moveFigureValue 
%\item getHistoryOfMove 
%\end{itemize}



Die Branchingmenge besteht aus den Funktionen:
R0$<$, R0$>$, currentDepthIsBigger, currentDepthIsSmaller, biggerThanAlpha, smallerThanBeta,
ifOppoOfQueens, ifOppoTwoBishops, ifIndTwoKnights, ifIndMoreKnights, ifIndMoreBishops, ifIndMove, 
ifIndTwoBishops und  ifIndOfQueens. 
%\begin{itemize}
%\item Vergleich, ob Register null größer oder kleiner einem Wert ist: R0$<$, R0$>$ 
%\item Vergleich, ob die aktuelle Tiefe größer oder kleiner einem Wert ist: 
%        currentDepthIsBigger, currentDepthIsSmaller 
%\item Vergleich, ob der Alphawert größer oder der Betawert kleiner einem Wert ist:
%         biggerThanAlpha, smallerThanBeta
%\item Abfrage bezüglich der Figuren des Gegners:  ifOppoOfQueens, ifOppoTwoBishops
%\item Abfrage bezüglich der eigenen Figuren
%: ifIndTwoKnights, ifIndMoreKnights, ifIndMoreBishops, ifIndMove, ifIndTwoBishops,  ifIndOfQueens 
%\end{itemize}

Für das Zugsortierungsmodul wurden folgende Funktionssätze verwendet:

Die Operationsmenge besteht aus den mathematischen Operationen $+, -, *, /$.

Die Terminalmenge setzt sich aus den folgenden Funktionen zusammen:
umOfAttacksBefore, numOfDefensedBefore, attackDefenseDiffBefore, 
numOfAttacksAfter, numOfDefensedAfter, attackDefenseDiffAfter,  
captureValueOfMove, captureFigureOfMove, looseValueOfMove, maxLooseValueAfterMove, 
maxLooseValueBeforeMove, maxCaptureValueAfterMove, maxCaptureValueBeforeMove, moveFigureValue,
 getHistoryOfMove, numOfThreatsOfInd, numOfThreatsOfOppo, numOfCoversOfInd, numOfCoversOfOppo,
 getAllOppoValue, getAllIndValue, endgameIndex, getBoardAdvancedVal, getBoardSimpleVal,
 getSumOfIndPawns, getSumOfIndKnigths, getSumOfIndBishops, getSumOfIndRooks, 
 getSumOfIndQueens, getSumOfIndKing getSumOfOppoPawns, getSumOfOppoKnigths, 
 getSumOfOppoBishops, getSumOfOppoRooks, getSumOfOppoQueens, getSumOfOppoKing, 
getNumOfIndPawns, getNumOfIndKnigths, getNumOfIndBishops, getNumOfIndRooks, 
getNumOfIndQueens, getNumOfIndKing, getNumOfOppoPawns, getNumOfOppoKnigths, 
getNumOfOppoBishops, getNumOfOppoRooks, getNumOfOppoQueens und getNumOfOppoKing. 

 
%\begin{itemize}
%\item Abfrage bezüglich Angriff und Verteidigung vor einem Zug: numOfAttacksBefore, numOfDefensedBefore, attackDefenseDiffBefore 
%\item Abfrage bezüglich Angriff und Verteidigung nach einem Zug: numOfAttacksAfter, numOfDefensedAfter, attackDefenseDiffAfter 
%\item Werte des möglichen Materialgewinns: captureValueOfMove, captureFigureOfMove 
%\item Werte des möglichen Figurverlustes: looseValueOfMove, maxLooseValueAfterMove, maxLooseValueBeforeMove 
%\item maxCaptureValueAfterMove, maxCaptureValueBeforeMove, moveFigureValue 
%\item getHistoryOfMove 
%\item Abfrage zur Anzahl der Bedrohungen: numOfThreatsOfInd, numOfThreatsOfOppo 
%\item Abfrage zur Anzahl der gedeckten Figuren: numOfCoversOfInd, numOfCoversOfOppo 
%\item Berechnung der Materialwerte einer Seite: getAllOppoValue, getAllIndValue 
%\item der Endspielindex: endgameIndex 
%\item Berechnung des Materialwertes mittels einfacher Funktionen: getBoardAdvancedVal, getBoardSimpleVal 
%\item Materialwerte einzelner Figurentypen des Individuums: getSumOfIndPawns, getSumOfIndKnigths, getSumOfIndBishops, getSumOfIndRooks, getSumOfIndQueens, getSumOfIndKing 
%\item Materialwerte einzelner Figurentypen des Gegners: getSumOfOppoPawns, getSumOfOppoKnigths, getSumOfOppoBishops, getSumOfOppoRooks, getSumOfOppoQueens, getSumOfOppoKing 
%\item Anzahl einzelner Figurentypen des Individuums: getNumOfIndPawns, getNumOfIndKnigths, getNumOfIndBishops, getNumOfIndRooks, getNumOfIndQueens, getNumOfIndKing 
%\item Anzahl einzelner Figurentypen des Gegners: getNumOfOppoPawns, getNumOfOppoKnigths, getNumOfOppoBishops, getNumOfOppoRooks, getNumOfOppoQueens, getNumOfOppoKing 
%\end{itemize}

Für das Stellungsbewertungsmodul wurden folgenden Funktionssätze verwendet:

Die Operationsmenge besteht aus den mathematischen Operationen $+, -, *, /$.

Die Terminalmenge setzt sich aus den folgenden Funktionen zusammen:
getNumOfIndPawns, getNumOfIndKnigths, getNumOfIndBishops, getNumOfIndRooks, 
getNumOfIndQueens, getNumOfIndKing, getPawnValue, getKnigthValue, getBishopValue, 
getRookValue, getQueenValue, getKingValue, getNumOfOppoPawns, getNumOfOppoKnigths, 
getNumOfOppoBishops, getNumOfOppoRooks, getNumOfOppoQueens, getNumOfOppoKing, 
numOfIndFiguresInOppoCenter, numOfOppoFiguresInOppoCenter, numOfIndFiguresInIndCenter, 
numOfOppoFiguresInIndCenter, advancedPawnValueInd, advancedKnightValueInd, 
advancedBishopValueInd, advancedRookValueInd, advancedPawnValueOppo, 
advancedKnightValueOppo, advancedBishopValueOppo und advancedRookValueOppo. 

%\begin{itemize}
%\item Anzahl einzelner Figurentypen des Individuums: getNumOfIndPawns, getNumOfIndKnigths, getNumOfIndBishops, getNumOfIndRooks, getNumOfIndQueens, getNumOfIndKing 
%\item Werte einzelner Figurentypen: getPawnValue, getKnigthValue, getBishopValue, getRookValue, getQueenValue, getKingValue 
%\item Anzahl einzelner Figurentypen des Gegners: getNumOfOppoPawns, getNumOfOppoKnigths, getNumOfOppoBishops, getNumOfOppoRooks, getNumOfOppoQueens, getNumOfOppoKing 
%\item Anzahl der Figuren in verschiedenen Brettzentren: numOfIndFiguresInOppoCenter, numOfOppoFiguresInOppoCenter, numOfIndFiguresInIndCenter, numOfOppoFiguresInIndCenter 
%\item Werte einzelner Figuren inklusive Positionswerten: advancedPawnValueInd, advancedKnightValueInd, advancedBishopValueInd, advancedRookValueInd 
%\item Werte einzelner Figuren inklusive Positionswerten: advancedPawnValueOppo, advancedKnightValueOppo, advancedBishopValueOppo, advancedRookValueOppo 
%\end{itemize}


Die Branchingmenge des Zugsortierungs- und Stellungsbewertungsmoduls
bestand aus den Funktionen $R0<$ und $R0>$.



%----------------------------------------------------------------------
\subsection{Ergebnisse der Evolution}
%----------------------------------------------------------------------
\label{sec:ErgEvo}

Die größte Anzahl von Evolutionsläufen wurde mit einem Knotenlimit von $100.000$ durchgeführt,
dies ermöglichte es, eine große Menge von Evolutionsläufen durchzuführen mit den Kapizitäten,
die zur Verfügung standen. Es wurden jeweils 100 Evolutionsläufe, in denen das Individuum
die weiße oder die schwarze Seite spielte, und acht Evolutionsläufe mit einem 
Knotenlimit von $250.000$ durchgeführt, hiervon konnten nur so wenige Evolutionsläufe durchgeführt
werden, da eine Evolution bis zu zwei Wochen auf einem Rechner dauern konnte. 
Plot~\ref{fig:GCFitAll} zeigt die durchschnittliche Fitness der Evolutionsläufe,
hier sind deutlich die Unterschiede im Ergebnis der verschiedenen Aufgaben
und Parameter zu sehen. So konnte die Evolution der weißen Individuen
eine Fitness von 4.800 erreichen, mit gleichen Parametern konnte die Evolutionsläufe 
für schwarze Individuen nur eine Fitness von 2700 erreichen. 
Bei einem Knotenlimit von $250.000$ erreichten die Individuen eine durchschnittliche
Fitness von 6.700. 
Das Verhalten der Evolution für die weißen Individuen mit 
einem Knotenlimit von $100.000$ zeigt einen typischen Verlauf der Fitnesskurve, mit einem
starken Anstieg am Beginn der Evolution und einen geringeren oder fast keinem
Anstieg zum Ende der Evolution. Daher kann man davon ausgehen, dass für diese
Einstellungen keine großen Verbesserungen durch längere Evolutionszeiträume
möglich sind. Der Fitnessverlauf für die schwarzen Individuen zeigt ein anderes
Verhalten, hier kann man deutlich erkennen, dass der Anstieg der Fitness gleichmäßig 
über den gesamten Evolutionszeitraum geschieht. Das deutet darauf hin, dass bei
einem längeren Evolutionzeitraum noch bessere Ergebnisse zuerreichen wären.
Es zeigt uns aber auch, dass es für die Individuen schwerer ist, die schwarze Seite 
zu spielen als die weiße Seite. Dies hat sich auch bei den Versuchen gezeigt,
bei dem die Individuen beide Seiten während der Evolution spielen mussten.
Bei keinem dieser Versuche ist es der Evolution gelungen ein Gegnerprogramm der Tiefe
zwei zu schlagen. Neben den Problemen mit der Farbe Schwarz, hatten die Individuen
massive Probleme Algorithmen zu entwickeln, die unabhängig  von der
Farbe sind, für die gezogen werden musste. Wobei hier während der Evolution immer
die Spiele gegen Programme der Farbe Weiß ein Problem für die Individuen darstellte.
Wir haben keine weitere Analyse durchgeführt, warum es den Individuen schwerfällt
Programme für die Farbe Schwarz zu entwicklen.

Die Evolutionsläufe mit dem Knotenlimit von $250.000$, die rote Kurve in der 
Abbildung~\ref{fig:GCFitAll}, zeigen ein stufigeres Verhalten als die anderen
Evolutionsläufe, dies liegt jedoch an der geringen Anzahl der Evolutionsläufe, die durchgeführt
wurden. 
%Jedoch konnten wir wegen des hohen Rechenzeitaufwandes nicht ausreichend Evolutionsläufe
%durchführen, um einen glatten Verlauf der durchschnittlichen Fitness zu erreichen.
%Bei diesen Evolutionsläufen ging es jedoch nicht darum das System zu analysieren, sondern 
%darum ein gutes Individuum zu evolvieren. 
Das Ziel war dabei, ein Individuum mit einer 
Fitness von 8000 zu erzeugen, hierzu jedoch mehr in Kapitel~\ref{sub:Ind250}.
 

  \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/GC-FitAll6.eps,width=10cm}}
  \caption{Der Plot zeigt die durchschnittliche Fitness der Individuen mit
  einem Knotenlimit von $100.000$ für die Seite Weiß und Schwarz, sowie mit einem
  Knotenlimit von $250.000$. Die Daten wurden über 
  der die weißen und schwarzen Individuen wurden über 100 Läufe gemittelt. Die
  Fitness für Individuen mit einer Knotengrenze von 250000 wurde über 11 Läufe gemittelt.}
  \label{fig:GCFitAll}
  \end{figure}

Die Tabelle~\ref{tab:GeneticChessLastGen} zeigt die Fitnessverteilung für die 
Evolution der weißen und schwarzen Individuen aus Abbildung~\ref{fig:GCFitAll}
und die Evolution mit maximalem Funktionssatz~\ref{fig:GCAllFunc}. Man erkennt
an der Tabelle viel besser, warum die Evolutionsläufe der schwarzen Individuen im 
Durchschnitt soviel schlechter ausfallen als die der weißen Individuen. Der wichtigste
Unterschied der Evolutionsläufe liegt in den Fitnessbereichen von 1000-1999 und ab 6000.
 Nur 1,9 \% der weißen Evolutionsläufe beenden den Lauf im Fitnessbereich von
1000-1999, aber 38,5 \% der schwarzen Evolutionsläufe. Dagegen erreichen 68,9 \%
der weißen Evolutionsläufe eine Fitness von 6000 und mehr, aber nur 26,9 \% der schwarzen
Evolutionsläufe. Evolutionsläufe der schwarzen Individuen können die gleiche maximale Fitness
erreichen wie die der weißen Individuen, jedoch ist die Erfolgswahrscheinlichkeit
viel kleiner als die der weißen Individuen, so können mehr als doppelt so viele
weiße Individuen diese Fitness erreichen. Für den Fitnessbereich von 1000-1999 
beträgt der Unterschied sogar das 20 fache. Sehr viele Evolutionsläufe scheitern schon
bei dem Versuch ein Programm der Suchtiefe 2 zu schlagen. Für die weißen Evolutionsläufe
gibt es erst ab Programmen der Suchtiefe 3 (Fitness 2000-2999) einen größeren
Widerstand, erstaunlich ist hier, dass der Widerstand für beide Fälle ungefähr
gleich ist. Für die Evolutionsläufe der schwarzen Individuen scheint der Schritt, einen Algorithmus
zu entwickeln, der auf eine Stellung reagiert, schwerer zu sein, als einen Algorithmus
zu evolvieren, der agiert. Ist diese Hürde überwunden, können die Evolutionsläufe
der schwarzen Individuen ungefähr die gleichen Leistungen erreichen wie für die
weißen Individuen. Für die Evolutionsläufe mit dem maximalen Funktionssatz sieht 
das Ergebnis ganz anders aus, hier erreicht die beste Evolution eine Fitness
im Bereich von 4.000-4.999 und 80 \% der Evolutionsläufe erreichen keine Fitness,
die besser ist als 1999. Durch die geringe Laufzeit der Evolutionsläufe von
nur 200 Generationen und der kleinen Demegröße von nur 20 Individuen
interpretieren wir das Ergebnis dahingehend, dass die Evolutionsläufe
bei dem maximalen Funktionensatz größere Demes und längere Laufzeiten benötigen
würde, um zu besseren Ergebnissen zu gelangen, eine weitere Möglichkeit
stellen wir in Kapitel~\ref{sub:GCAna} vor.

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
Fitness         &       Weiß    &       Schwarz         & Maximaler Funktionssatz \\
\hline
0-999           &       2,91    &       8,97            &       59,09 \\
\hline
1.000-1.999       &       1,94    &       38,46           &       22,73 \\
\hline
2.000-2.999       &       16,50   &       11,54           &       9,09 \\
\hline
3.000-3.999       &       0,97    &       8,97            &       4,55 \\
\hline
4.000-4.999       &       8,74    &       0,00            &       4,55 \\
\hline
5.000-5.999       &       0,00    &       5,13            &       0,00 \\
\hline
6.000-6.100       &       68,93   &       26,92           &       0,00 \\
\hline 
\end{tabular}
\end{center}
\caption{Diese Tabelle zeigt, wieviel Prozent der verschiedenen Läufe besser oder gleich
gut waren wie die angegebene Fitness. }
\label{tab:GeneticChessLastGen}
\end{table}

In der Einleitung zu diesem Kapitel wurden die verschiedenen Operations- und Terminalmengen
für die Individuen vorgestellt. Die Auswahl ergab sich durch vorbereitende Tests
mit kleineren Knotenlimits, um so schneller die Ergebnisse der Evolution zu
erhalten. Wir haben aber auch Läufe mit der vollstandigen Funktions- und Terminalmenge 
und einem Knotenlimit von $100.000$ durchgeführt, das Ergebnis ist in der
Abbildung~\ref{fig:GCAllFunc} zusehen. Die Fitness der Läufe mit der eingeschränkten
Funktions- und Terminalmenge erreicht im Durchschnitt eine fünf mal höhere Fitness
als die Läufe mit der vollständigen Funktionsmenge. Man erkennt für diese Kurve
auch nicht den typischen starken Anstieg der Fitness zu Beginn der Evolution.
Man kann hier davon ausgehen, dass durch den viel höheren Freiheitsgrad der Evolution
eine viel größere Anzahl von Evolutionsläufen und auch mehr Individuen pro Deme notwendig
sind um bessere Ergebnisse zu erzielen. Durch den hohen Rechenaufwand für jede 
Fitnessauswertung war es jedoch nicht möglich dem System die erforderliche Zeit
zur Verfügung zu stellen. Im Kapitel~\ref{sub:GCAna} haben wir eine Analyse über
die Häufigkeit der benutzten Funktionen in den einzelnen Modulen der Individuen
durchgeführt. Auf dieser Grundlage könnte man wahrscheinlich eine bessere Auswahl 
der Funktions- und Terminalmengen durchführen, als sie in den Vortests durchgeführt
wurden. Erstaunlich ist aber die geringe Fitness der Individuen, die allein auf
den höherdimensionalen Konfigurationsraum der Individuen  zurückzuführen ist. 
Inwieweit der Rückstand bezüglich des Fitnesswertes durch einen längeren Evolutionszeitraum
aufzuholen ist, konnte im Zusammenhang mit dieser Arbeit nicht überprüft werden.
Durch die extrem langen Fitnessberechungen und den komplexen Aufbau der Individuen
sollte man dies besser in einem einfacheren Umfeld überprüfen.


  \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/GC-FitAllFunc1.eps,width=10cm}}
  \caption{Der Plot zeigt die durchschnittliche Fitness der Individuen mit der
        vollständigen Funktions- und Terminalmenge (rote Kurve) und bei gleicher Einstellung
        mit der eingeschränkten Funktionsmenge (blaue Kurve). Die Daten wurden über 25 Läufe gemittelt.}
  \label{fig:GCAllFunc}
  \end{figure}



Wie zu Beginn des Kapitels beschrieben, haben wir dem Individuum im Programmflussabschnitt 
die Möglichkeit gegeben zu bestimmen, welche Züge generiert werden sollen.
Hierzu stehen vier Funktionen zur Verfügung, die wir zu den folgenden vier
Mengen zusammengefasst haben.
\begin{itemize}
\item 1. alle legalen Züge,
\item 2. alle legalen Züge und aggressive Züge,
\item 3. alle legalen Züge, aggressive Züge und defensive Züge,
\item 4. alle legalen Züge, aggressive Züge, defensive Züge und Nullzüge.
\end{itemize}
Bei Evolutionprozessen mit der Menge 1 wurde im Inidividuum in jedem Programmflussabschnitt
die Funktion \emph{legale Züge} verwendet. Wurde die Menge 3 verwendet, konnte die
Funktion im Programmflussabschnitt entweder \emph{legale Züge, aggressive Züge}
oder \emph{defensive Züge} sein. Dadurch kann das Individuum den Suchraum der Schachzüge
freier gestalten und gewisse Aspekte des Spiels stärker betrachten als andere.
Durch diese Möglichkeit verliert man natürlich auf der anderen Seite die Gewissheit,
dass der beste Zug ermittelt wurde. Dieses Vorgehen ist durch menschliche Spieler
motiviert, die auch nicht alle legalen Züge betrachten, sondern gewissen Strategien, oder
Vorstellungen folgen um den nächsten Zug zu bestimmen.
In der Abbildung~\ref{fig:GCFit1-4} kann man nun das durchschnittliche Ergebnis von 
je 25 Evolutionsläufe für jede der vier Möglichkeiten sehen. Die blaue Kurve stellt die
Ergebnisse der Menge eins dar, die grüne der Menge zwei, die rote der Menge 3 und die
gelbe der Menge 4. Der Plot zeigt eine Zweiteilung der Ergebnisse, so erreichen
die Evolutionsläufe mit den Funktionsmengen 2 und 3 und die Evolutionsläufe mit den 
Funktionsmengen 1 und 4 ähnliche Fitnesswerte. Dies entspricht zum Teil unseren
Erwartungen, so sind wir davon ausgegangen, dass eine Evolution mit der Funktionsmenge
4 die im Durchschnitt schlechtesten Ergebnisse liefert, da der Aufbau des Suchbaumes durch die
\emph{Nullzüge}-Funktion sehr stark beschnitten werden kann. Wenn die
Funktion zu häufig aufgerufen wird, kann es somit zu falschen Bewertungen einer
Stellung kommen. Aus den Erfahrungen mit den anderen Systemen haben wir geschlossen,
dass die Evolutionsläufe mit der Funktionsmenge 1 im \emph{Durchschnitt} die besten Ergebnisse
liefern sollten. Denn  sie besteht nur aus der Funktion \emph{legale Züge} und
sichert so, dass das Individuum einen vollständigen Suchbaum aufbaut, der den
Zugsortierungs- und Stellungsalgorithmen eine gute Bewertung der Situation ermöglicht.
Alle anderen Funktionsmengen sollten im Durchschnitt schlechter sein, aber in Einzelfällen
sollten bessere Lösungen möglich sein, da die Evolution die zusätzlichen Freiheitsgrade
nutzen könnte um die Suche effizienter zu gestalten und somit bessere Lösungen
zu finden. Wie man aber am Plot sehen kann, erreichen die Evolutionsläufe mit den
Funktionsmengen 2 und 3 die besten Lösungen im Durchschnitt und die Funktionsmengen
1 und 4 scheinen gleich gut zu sein, obwohl der Konfigurationsraum der Individuen
gestiegen ist, wie dies auch der Fall ist, wenn die vollständige Funktionsmenge 
verwendet wird. In dem Fall der vollständigen Funktionsmenge ist die Konfiguration
natürlich stärker gewachsen als durch die Verwendung der Funktionsmenge 4 anstelle
der Funktionsmenge 1. Man kann jedoch erwarten, dass es zumindestens zu einer
leichten Verschlechterung der Ergebnisse im Durchschnitt kommen sollte. Für die
Funktionsmengen 2 und 3 kommt es dagegen sogar zu einer Verbesserung der durchschnittlichen
Fitness. Wir interpretieren dies als einen Hinweis darauf, dass diese zusätzliche
Freiheit für die Individuen wichtig ist, um die Möglichkeiten des Tiefenmoduls besser
zu nutzen.


  \begin{figure}
  \centerline{\epsfig{figure=Pictures/Results/GC-FitZuege.eps,width=11cm}}
  \caption{Der Plot zeigt die durchschnittliche Fitness der Individuen für die
  verschiedenen Programmflussfunktionen. Die Daten wurden jeweils über 25 Läufe gemittelt.}
  \label{fig:GCFit1-4}
  \end{figure}

Die Tabelle~\ref{tab:GeneticChessKlassen} bietet  einen anderen Blick auf die
Ergebnisse. Hier werden die Ergebnisse der Evolutionsläufe in der letzten Generation
als Prozentzahlen für das Erreichen einer Fitnessklasse angegeben. Wenn man diese
Ergebnisse für die verschiedenen Programmflussfunktionen vergleicht, sieht man eine
starke Ähnlichkeit der Ergebnisse für die Funktionsmengen 1 bis 3. Sie haben alle
eine Häufung in der Fitnessklasse ab 2.000, ab 4.000 und ab 6.000.  Die Evolutionsläufe
für die Funktionsmengen 2 und 3 haben sogar die gleiche Erfolgsrate für die 
Fitnessklasse 6.000. Die Evolution mit der Funktionsmenge 4 zeigt ein anderes Verhalten,
hier zeigen sich nur zwei Häufungspunkte, der eine liegt bei 2.000 und der zweite liegt
bei 6.000. Obwohl die durchschnittliche Fitness für die Evolution der Funktionsmenge 1 
und 4 fast gleich ist, zeigen sich hier jedoch große Unterschiede, so erreicht keine
Evolution die Fitnessklasse 4.000 im Gegensatz zu den anderen Evolutionsläufen. Auch
erreichen 15 \% mehr Individuen die höchste Fitness gegenüber den Evolutionsläufen
mit der Funktionsmenge 1 und ungefähr 9 \% weniger als die der Funktionsmengen
2 und 3. Für die Evolutionsläufe mit der Funktionsmenge 4 ist die Fitnessklasse 2.000-2.999
eine Hürde, wenn diese genommen werden kann, erreichen fast alle Evolutionsläufe die
höchste Fitnessklasse. Dieses Ergebnis war für uns wichtig bei der Auswahl der 
Funktionsmengen für die Evolutionsläufe mit einem Knotenlimit von $250.000$. Denn
Evolutionsläufe, in denen keine guten Individuen erzeugt werden, sind von der Rechenzeit
nicht sehr aufwendig. Die Rechenzeit  wird durch die Auswertung 
der Fitness bestimmt und Spiele gegen spielstarke Gegnerprogramme, also ab Suchtiefe
sieben (Fitness 7.000), werden zu rechenzeitaufwendig, um während einer Evolution
zu häufig aufgerufen zu werden. Die Hoffnung bestand, dass die Evolutionsläufe entweder
das Ziel nicht erreichen und damit wenig Rechenzeit verbrauchen, da die Fitness
im Bereich von unter 5.000 liegt, oder das Ziel einer Fitness von über 8.000 erreicht
wird.


\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Fitness         &  Züge 1 &     Züge 2 &        Züge 3  &       Züge 4   \\
\hline
0-999           &       3,85  & 0,00   &        3,85    &       4,00     \\
\hline
1.000-1.999       &       3,85  & 0,00   &        0,00    &       4,00     \\
\hline
2.000-2.999       &       23,08 & 15,38  &        7,69    &       20,00    \\
\hline
3.000-3.999       &       0,00  & 0,00   &        0,00    &       4,00     \\
\hline
4.000-4.999       &       15,38 & 7,69   &        11,54   &       0,00    \\
\hline
5.000-5.999       &       0,00  & 0,00   &        0,00    &       0,00     \\
\hline
6.000-6.100       &       53,85 & 76,92  &        76,92   &       68,00   \\
\hline 
\end{tabular}
\end{center}
\caption{Diese Tabelle zeigt, wieviel Prozent der verschiedenen Läufe besser oder gleich
gut waren wie die angegebene Fitness. }
\label{tab:GeneticChessKlassen}
\end{table}


Zuletzt haben wir den Knotenverbrauch der einzelnen Evolutionsläufe im Durchschnitt
betrachtet. Der Plot~\ref{fig:GCKnoten} zeigt den Verlauf der 
Evolutionsläufe mit den vier verschiedenen Funktionsmengen. Obwohl die Kurven den 
Durchschnittswert über 25 Evolutionsläufe darstellen, kann man deutlich die 
sprunghaften Veränderungen der Werte während der Evolution erkennen. Beim Vergleich
der Daten hat sich gezeigt, dass es eigentlich kein einheitliches Bild für die
Entwicklung des Knotenverbrauchs gibt. So gibt es Evolutionsläufe, in denen die 
besten Individuen über Generationen sehr nahe am Knotenlimit liegen und plötzlich 
einen starken Einbruch haben oder umgekehrt. Es zeigt sich aber kein einheitliches
Bild. Man kann vielleicht eine grundsätzlich Tendenz ableiten, dass die Individuen 
in den ersten Generationen weniger Knoten verbrauchen und in späteren Generationen
mehr Knoten verbrauchen. Jedoch zeigen einzelne Evolutionsläufe teilweise ein anderes
Bild, was man sogar im Plot erkennen kann, wenn man sich die Kurve (blau)
 für die Funktionsmenge 1 betrachtet. Hier sieht man in Generation 175 einen 
Rückgang von $10.000$ Knoten. Erstaunlich ist, dass man die Evolutionsläufe mit
den Funktionsmengen 3 und 4 kaum unterscheiden kann, obwohl sie in den Plots der
Fitnesswerte stark unterscheidbar waren. Auch hatten wir erwartet, dass die
Evolutionsläufe mit der Funktionsmenge 1 die meisten Knoten während einer Evolution
verbrauchen würden, was nicht der Fall ist. Zwar benötigen diese Individuen
am Anfang mehr Knoten als die der Funktionsmengen 3 und 4, erreichen aber
zum Schluss einen ähnlich hohen Knotenverbrauch wie mit den anderen beiden Funktionsmengen.
Den höchsten Knotenverbrauch haben aber die Evolutionsläufe mit der Funktionsmenge 2, also
eine Kombination aus \emph{allen legalen} und \emph{aggressiven Zügen}. 
Eine Erklärung, warum dies so ist, haben wir nicht gefunden, da auch die anderen
Funktionsmengen die Funktion \emph{aggressive Züge} beinhalten und es so eigentlich
keine Begründung dafür gibt, dass die Funktionsmenge 3 weniger Knoten verbraucht. Die
Funktionsmenge 4 hat noch die Funktion \emph{Nullzüge}, was die Anzahl der 
Knoten eigentlich stark reduzieren kann, dieser Vorteil wurde wahrscheinlich 
durch häufigere Explorationen des Suchraums in tiefere Ebenen aufgebraucht.

\begin{figure}
\centerline{\epsfig{figure=Pictures/Results/GC-NodesAll.eps,width=11cm}}
\caption{Der Plot zeigt den durchschnittliche Knotenverbrauch der Individuen für die
  verschiedenen Programmflussfunktionen. Die Daten wurden jeweils über 25 Läufe gemittelt. }
\label{fig:GCKnoten}
\end{figure}


%----------------------------------------------------------------------
\subsubsection{Analyse der Individuen mit einem 250.000 Knotenlimit}
%----------------------------------------------------------------------
\label{sub:Ind250}

Nachdem alle Evolutionsläufe beendet waren, stellte sich für uns die Frage, ob
es möglich ist Individuen zu evolvieren, die Programme der Suchtiefe 7 oder 8
schlagen können. Um die Schwere dieser Aufgabe zu erkennen, muss man sich verdeutlichen,
dass ein guter Alpha-Beta Algorithmus bei einer Suchtiefe von sieben 2 Millionen 
und bei einer Suchtiefe von acht 13 Millionen Knoten expandiert. Die Individuen
mit einem Knotenlimit von $100.000$ konnten Programme der Suchtiefe sechs schlagen,
gute Programme benötigen hier $320.000$ Knoten. Die Individuen, die Programme der Suchtiefe
sechs schlagen, benötigen im Durchschnitt $80.859$ Knoten, die besten 20 \% der
Individuen benötigen zwischen $14.821 - 49.884$ Knoten. Der Durchschnittswert
für die besten 20 \% liegt also bei $35.560$ Knoten.
Das Individuum, welches
den kleinsten Suchbaum aufspannt, benötigt nur $4,6$ \% der Knoten, den ein Alpha-Beta
Algorithmus benötigt. Die
besten Individuen des qoopy-Systems benötigten $50$ \% der Knoten eines guten
Schachalgorithmus um die gleiche Spielstärke zu haben, siehe 
Abschnitt~\ref{sub:qoopyFazit}.  Im Durchschnitt benutzen die
Individuen des GeneticChess-Systems zwar mehr Knoten als die 
des qoopy-Systems, jedoch sind auch die Ergebnisse um eine Suchtiefe besser als
die des qoopy-Systems.
Wenn man nun den Durchschnittswert der besten 20\% Programme nimmt, benötigten die
Individuen ungefähr $10$ \% der Knoten eines guten Alpha-Beta Algorithmus.
Daher kann man davon ausgehen, dass die Individuen $200.000$ Knoten benötigen
würden um ein Programm der Suchtiefe sieben zu schlagen und eine Millionen Knoten
für ein Programm der Suchtiefe acht. Tests mit Evolutionsläufen, die ein Knotenlimit
von einer Millionen hatten, hatten aber eine Rechenzeit, die viel zu hoch war. 
Daher mussten wir uns auf ein Knotenlimit von $250.000$ beschränken, selbst bei
diesem Knotenlimit benötigte eine Evolution zwischen 2 und 26 Tagen. 
Die Hoffnung war, dass dies ausreichen würde, mindestens ein Programm der 
Suchtiefe sieben zu schlagen.
In der Abbildung~\ref{fig:GCFitAll} zeigt die Durchschnittsfitness dieser Individuen
(die rote Kurve), man erkennt ein sehr stufigen Verlauf der Kurve, dies liegt and
der geringen Anzahl von Evolutionsläufen. Trotzdem erreichen sie schon im
Durchschnitt eine Fitness von 6.700. 
Jedoch konnten wir wegen des hohen Rechenzeitaufwandes nicht ausreichend Evolutionsläufe
durchführen, um einen glatten Verlauf der durchschnittlichen Fitness zu erreichen.
Die Fitness der Individuen in der letzten Generation ergibt folgendes Bild:
\begin{itemize}
\item Fitness von 4.000 erreicht eine Evolution
\item Fitness von 6.000 erreichen sieben Evolutionsläufe
\item Fitness von 7.000 erreicht eine Evolution
\item Fitness von 8.000 erreichen zwei Evolutionsläufe
\end{itemize}
Ungefähr 70 \% der Evolutionsläufe erreichten das Ziel nicht, ein Individuum mit einer Fitness 
von mindestens 7.000 zu evolvieren. Diese Individuen sind ungefähr so stark wie
die Individuen mit einen Knotenlimit von $100.000$, obwohl sie teilweise deutlich mehr
Knoten pro Zug aufspannen als die Individuen der anderen Evolutionsläufe. Man sieht 
auch hier, dass ein gewisser Selektionsdruck ausgeübt werden muss, um die gewünschten
Ergebnisse zu erzielen. Drei Evolutionsrozesse erreichten das gesteckte Ziel oder übertrafen
es sogar; wie wir oben dargestellt haben, untersucht ein guter Suchalgorithmus
bei einer Suchtiefe von acht 13 Millionen Knoten pro Zug. Die Individuen durften
aber nur circa 2 \% dieser Knoten pro Zug betrachten und konnten ein Programm
der Suchtiefe acht dennoch schlagen. Hier stellt sich sofort die Frage: Kann dies
überhaupt sein oder gab es hier einen Fehler in der Auswertung?

 Man muss das Ergebnis
zuerst einmal an mehreren Stellen relativieren. So expandieren die Individuen nur 
2 \% der Knoten eines guten Algorithmus, jedoch stehen dem Individuum mehr Funktionen
zur Verfügung, als sie ein normaler Algorithmus hat. Sie können demnach eine Stellung viel
genauer bewerten, als es das Gegnerprogramm kann. Ein weiterer Vorteil liegt in
Funktionen, denen es möglich ist Auswirkungen eines Zuges zu betrachten, ohne
ihn zu machen.
So konnten die folgenden Funktionen Aspekte einer Stellung nach einem Zug
betrachten, \emph{numOfAttacksAfter, numOfDefensedAfter, attackDefenseDiffAfter,
 maxLooseValueAfterMove, maxCaptureValueAfterMove} und \emph{attackDefenseDiffAfter}.
Durch eine geschickte Kombination der Funktionen kann so das Tiefen- und 
Zugsortierungsmodul nicht nur die aktuelle Situation beurteilen, sondern auch
den Effekt eines Zuges. Da beide Module auch Elemente der Materialbewertung
haben, können sie schon vor der Berechnung des Materialwertes der Stellung
eine recht gute Bewertung der zukünfigen Stellung durchführen. Wichtig ist noch
zu wissen, dass das Tiefenmodul jeden Pfad im Suchbaum abschließt und somit
noch Wissen über die nächste Suchtiefe indirekt an die Suche weitergibt.
Fasst man dies zusammen, untersucht der Algorithmus in Wirklichkeit etwas mehr
Stellungen als die angegebenen. Dieser Wert ist vom Ausgrad der Blätter im Suchbaum
abhängig. Wenn man etwas konservativer davon ausgeht, dass zu den späteren Zeitpunkten
im Durchschnitt nur noch 20 legale Züge möglich sind, würden die Programme somit
ein Knotenlimit von 21 mal $250.000$ also $5.250.000$ Knoten haben. Somit
hätte man \emph{nur} eine Einsparung von 60\% bei einer Suchtiefe von acht.
Wir finden es aber bemerkenswert, dass es der Evolution möglich ist,
durch bessere Möglichkeiten im Tiefen- und Zugsortierungsmodul eine so massive
Einsparung in der Anzahl der betrachteten Stellungen zu machen, wie es hier
möglich gewesen ist. An dieser Stelle ist das Individuum bei der Bewertung der
Situation näher am Vorgehen eines Menschen als das mechanische Vorgehen der
bekannten Schachalgorithmen. Denn jeder Mensch überlegt sich schon bei der
Auswahl der Züge, die er näher betrachten möchte, welchen Einfluss der Zug
haben wird. 

Wenn man sich nun die einzelnen Spiele der Individuen gegen die verschiedenen
Gegnerprogramme genauer ansieht, erkennt man viel besser als an dem
Fitnesswert, wie die Individuen auf die einzelnen Gegnerprogramme
reagieren. In den Tabellen~\ref{tab:GeneticChessBestIndA} und~\ref{tab:GeneticChessBestIndB}
 zeigen wir drei, beziehungsweise
zwei Spiele der besten beiden Individuen, dort \emph{Ind A} und \emph{Ind B} genannt.
Für das Individuum A wurden zwei Nachbewertungen durchgeführt, also insgesamt
dreimal wurden Spiele gegen alle Gegnerprogramme durchgeführt. Dies wurde gemacht,
da hier zweimal Spiele gegen Gegnerprogramme der Tiefe fünf und sieben verloren
gegangen sind. Die Werte in der Tabelle geben neben den durchschnittlich benutzten
Knoten pro Zug auch den Materialwert am Ende des Spiels an. Der Wert ist der reine Materialwert
des Spiels ohne Bewertung von Stellungselementen, er bezieht sich immer
auf das Individuum und ist auf den maximalen Materialwert ohne die Könige normiert.
Das heißt, ein Ergebnis von eins für ein Individuum bedeutet, dass es keine
Figuren verloren hat und das Gegnerprogramm nur noch den König besitzt oder das 
Spiel gewonnen hat, indem es den König geschlagen hat. 
Ein Bauer hat somit einen Einfluss von $\frac{100}{4060} \approx 0,0246$ 
auf den Ergebniswert. Ein negativer Wert zeigt an, dass das Individuum
einen Materialverlust erlitten hat und der Wert null zeigt einen 
ausgeglichenen Materialwert an, siehe hierzu auch Kapitel~\ref{sec:SchachFit}.


\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
          & \multicolumn{6}{|c|}{Ind A}  \\
\hline
Suchtiefe & Mat. 1 & Knoten 1 & Mat. 2 & Knoten 2 & Mat. 3 & Knoten 3  \\   
\hline
   1      &  0,1823  & 264.928   & 0,3941   & 250.182   &  0,3941	  & 250.185    \\   
   2      &  0,3301  & 291.874   & 0,4138   & 285.881   &  0,7783  & 268.028    \\   
   3      &  0,1478  & 250.178   & 0,3103   & 250.186   &  0,3941  & 250.174    \\   
   4      &  0,5222  & 250.173   & 0,3793    & 275.159  &  0,5123  & 281.438    \\   
   5      &  0,1577  & 264.078   & \textbf{-0,0099} & 262.701   &  0,3054  & 250.185    \\   
   6      &  0,3547  & 250.171   & 0,6699   & 261.033   &  0,3300  & 291.846    \\               
   7      &  0,0493  & 250.172   & \textbf{-0.1724}  & 250.156   &  0,1084  & 263.350    \\   
   8      &  0,4877  & 275.167   & 0,5468   & 272.909   &  0,3300  & 268.045    \\ 
   \hline        
\end{tabular}
\end{center}
\caption{Diese Tabelle zeigt die Ergebnisse der Spiele gegen die verschieden
starken Gegnerprogramme des Individuums A und die im Durchschnitt verbrauchten Knoten pro Zug. }
\label{tab:GeneticChessBestIndA}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
          &  \multicolumn{4}{|c|}{Ind B} \\
\hline
Suchtiefe & Material 1 & Knoten 1 & Material 2& Knoten 2 \\   
\hline
   1      &   0,157635 &  210.267  &  0,05     &  80.529   \\   
   2      &   0,802956 &  100.480  &  0,477833 &  73.132   \\   
   3      &   0,0344828&  120.448  &  0,0591133& 220.251   \\   
   4      &   0,586207 &  117.491  &  0,187192 & 193.247   \\   
   5      &   0,172414 &  104.687  & \textbf{-0,0492611} & 132.642   \\   
   6      &   0,8867   &  172.808  &  0        & 182.915   \\               
   7      &   0,0246305&  40.602   &  0,231527 & 203.662   \\   
   8      &   0,586207 &  60.689   &  0,719212 & 200.291   \\         
   \hline
\end{tabular}
\end{center}
\caption{Diese Tabelle zeigt die Ergebnisse der Spiele gegen die verschieden
starken Gegnerprogramme des Individuums B und die im Durchschnitt verbrauchten Knoten pro Zug. }
\label{tab:GeneticChessBestIndB}
\end{table}

In der Tabelle~\ref{tab:GeneticChessBestIndA} fallen zwei Punkte sofort auf,
erstens zwei klar verlorene Spiele gegen Programme der Suchtiefe
fünf und sieben und zweitens, dass die Anzahl der durchschnittlichen 
Knoten immer dem Knotenlimit entspricht. Das Knotenlimit von $250.000$ wird hier 
zwar oft deutlich überschritten, jedoch ist dies ein Seiteneffekt der Evaluation
des Tiefenmoduls, siehe auch~\ref{sec:GenticChessTiefenmodul}. So wird dem Individuum
die Möglichkeit gegeben, alle noch nicht bewerteten Stellungen zu bewerten, nachdem
das Knotenlimit erreicht wurde, somit wird dem Individuum die Möglichkeit gegeben
die Suche nicht zu abrupt zu beenden. Das Individuum nutzt hier eine Möglichkeit 
des Rahmenalgorithmus um das Knotenlimit zu erhöhen und somit die Rechenkraft zu steigern.
Negativ ist aber, dass wir nun nicht genau erkennen können, wie das Tiefenmodul
arbeitet, da wir die Suchtiefe nicht exportiert haben.

% Wir hatte dies
%zu Beginn der Evolutionsläufe gemacht, dann jedoch gemerkt, dass es zu viele Daten sind,
%wenn wir alle Suchtiefen exportieren und die maximale, durchschnittliche oder
%minimale Suchtiefe hatten keine Aussagekraft für die ersten Ergebnisse. So hatte
%fast jedes Individuum mindestens einmal die maximale Suchtiefe erreicht, die durch den Rahmenalgorithmus
%vorgegeben wurde. Die minimale Suchtiefe war auch immer eins, da es immer einen Pfad
%gab, der immer abgebrochen wurde. Die durchschnittliche Suchtiefe war mehr von
%den Parametern wie maximale Suchtiefe und dem Knotenlimit abhängig, so dass wir
%auf die Berechnung verzichtet haben, da der Rechenaufwand bei den Evolutionsläufen
%spürbar war. 

Obwohl das Individuum \emph{Ind A} das Knotenlimit immer ausreizt, können wir aber sagen,
dass es sinnvoll den Suchbaum beschneiden muss, denn würde das Individuum dies
nicht machen, so könnte nur der erste Zug analysiert werden. Diese Analyse wäre
aber sehr schlecht, da nur die unteren 2 Ebenen des ersten Zuges ganz analysiert
werden könnten. 
%Dabei gehen wir davon aus, dass die maximale Suchtiefe 10 ist und
%im Durchschnitt 10 Züge pro Stellung möglich sind. Dieses Individuum könnte nur 
%dann erfolgreich sein, wenn die Zugsortierung  immer den besten Zug finden könnte. Dies
%ist zwar noch für eine Spielstärke der Suchtiefe eins oder zwei vorstellbar, aber 
%nicht für Programme mit einer Spielstärke von acht. 
Dieses Individuum nutzt zwar 
das Tiefenmodul um den Suchraum zu beschneiden, aber es nutzt auch einen Seiteneffekt
des Rahmenalgorithmus, um so viel Stellungen wie möglich zu expandieren.

Individuum \emph{Ind B} zeigt ein Verhalten, das von uns erhofft wurde
und auch durch die Fitnessfunktion unterstützt wurde, da bei der Selektion
die Anzahl der verbrauchten Stellungen mit berücksichtigt wurde (siehe~\ref{sec:SchachFit}).
Es geht sehr differenziert beim Aufbau des Suchraumes vor und stellt sich somit auf
die aktuelle Situation ein, siehe Tabelle~\ref{tab:GeneticChessBestIndB}.
 Erstaunlich ist jedoch, dass der Knotenverbrauch nicht
einfach mit der Stärke des Gegnerprogramms steigt, sondern sich, wie es die erste
Analyse zeigt, sogar umgekehrt verhält. Von dem geringen Knotenverbrauch gegen die
Programme der Suchtiefe sieben und acht bei der ersten Analyse darf man auch nicht
den Schluss ziehen, dass während des gesamten Spiels so wenig Stellungen pro Zug
verwendet wurden. Die Versuche haben gezeigt, dass es bei Individuen, die
ein ähnliches Verhalten wie das Individuum \emph{Ind B} haben, sehr große Schwankungen
von Stellung zu Stellung gibt. Dass das Verhalten auch nicht typisch ist, zeigt die
zweite Analyse, in der bei dem Gegnerprogramm der Suchtiefe sieben bis zu 
fünf mal mehr Stellungen untersucht wurden. Da die Individuen nicht vollständig
deterministisch arbeiten, zeigen sich  Veränderungen im Spielverlauf, so dass sich für beide
Seiten von einer Entscheidung Vorteile, aber auch Nachteile ergeben können.
Hier sollte erwähnt werden, dass auch die Gegnerprogramme nicht ganz deterministisch
agieren. Dies passiert aber nur an einer Stelle des Algorithmus, dies ist die
Zugsortierung. Für die Zugsortierung wird ein randomisiertes Quicksort
genutzt, dadurch ist die Reihenfolge der Züge bei einer gleichen Zugbewertung
unterschiedlich, was zu einem anderen Suchbaum und vielleicht auch zu einem 
anderen Ergebnis führen kann. Da aber die Bewertung der Züge identisch ist, spricht
nichts gegen das Vorgehen. Da die Zugbewertung aber auch eine Heuristik ist, können
an dieser Stelle Fehler gemacht werden, die einen Einfluss auf das Spiel haben können.
Daher kann man davon ausgehen, dass die Gegnerprogramm zwar immer eine
gewisse Durchschnittsstärke haben, diese aber in einem gewissen Intervall schwankt. Jedoch sind
die Schwankungen der Gegnerprogramme geringer als die einzelner Individuen, wie man
es beim Individuum \emph{Ind A} sieht, so verliert das Individuum während der
zweiten Analyse die Spiele gegen die Programme der Suchtiefe fünf und sieben
deutlich, gewinnt Spiele gegen diese Programme aber auch deutlich bei der
Analyse eins und drei. Dies erkennt man auch beim Individuum \emph{Ind B}, bei der
zweiten Analyse hier erzielt das Individuum gegen ein Programm der Suchtiefe fünf
nur um ein Remis und bei Suchtiefe sechs einen Materialverlust, der zwei Bauern entspricht.
Da nur ein Spiel verloren ging, haben wir jedoch auf einen weiteren Analyselauf verzichtet. 



Bei beiden Individuen kann man erkennen, dass sie immer schlechter abschneiden,
wenn sie gegen Individuen mit einer ungeraden Suchtiefe spielen müssen. Dies ist
ein Effekt, der leicht durch das Schachspiel selber und die Struktur der Gegnerprogramme
erklärt werden kann. Alle Gegnerprogramme spannen den Suchraum bis zu einer maximalen
Tiefe auf, dann wird spätestens die Bewertung durchgeführt. Wenn eine Stellung
nicht in Ruhe ist, kann die Bewertung für einen Zug falsch sein,
siehe hierzu auch Kapitel~\ref{sec:ruheSuche}. Man kann sich das sehr schnell am 
Beispiel des Figurentausches klar machen. Nehmen wir einen Damentausch an,
eine Suchtiefe von zwei und Schwarz ist am Zug. Schwarz macht also einen Zug mit
der Dame, diese kann von Weiß wieder mit der Dame geschlagen werden. Nun wurden
zwei Halbzüge gemacht und die Bewertung wird durchgeführt. Schwarz hat nun eine
Materialbewertung, die um eine Dame schlechter ist als die von Weiß. Würden jetzt aber
die nächsten Züge von Schwarz analysiert, könnte festgestellt werden, dass die weiße
Dame von Schwarz im nächsten Zug geschlagen wird und somit die Stellung nicht
um einen Damenwert schlechter ist. Das Problem der geraden Suchtiefen ist, dass 
der Algorithmus nicht die mögliche Antwort auf einen Zug des Gegners mit in die
Bewertung einbeziehen kann. Dies hat in vielen Situationen keinen Einfluss, jedoch
gibt es ausreichend Situationen, in denen die Algorithmen somit eine \emph{suboptimale}
Entscheidung treffen. Dies scheinen die Individuen ausnutzen zu können um
zu besseren Ergebnissen zu gelangen als gegen ungerade Suchtiefen. Um dies zu verhindern,
müsste man Gegnerprogramme entwickeln, die eine Ruhesuche durchführen. An diesem
Beispiel sieht man aber auch, wie flexibel Individuen sind, die durch einen Evolutionsprozess
entwickelt wurden.


Es wurden keine Spiele gegen Programme der Suchtiefe neun durchgeführt, da diese
wahrscheinlich nicht gewonnen werden könnten, so konnte auch nur ein Programm
mit einen Knotenlimit von $100.000$ gegen ein Programm der Suchtiefe sieben einen geringen
Materialvorteil erkämpfen. Der Hauptgrund lag in der langen Rechenzeit, die
für diese Analyse benötigt worden wäre. Da die Gegnerprogramme nicht die Güte der
bekannten Schachprogramme haben und selbst diese nur selten während eines Spiels eine
Suchtiefe größer als zehn betrachten, haben wir auf Spielen gegen Programme der
Suchtiefe neun verzichtet.


%----------------------------------------------------------------------
\subsubsection{Analyse der Funktionsverteilung}
%----------------------------------------------------------------------
\label{sub:GCAna}

Abschließend wurde die Struktur der Individuen selbst analysiert, dabei
handelt es sich um die Analyse des Individuen ROM's und die Verteilung der 
verschiedenen Funktionen in die einzelnen Module der Individuen. Bei der Analyse
handelt es sich um eine statische Analyse der Individuen, die natürlich nur
einen Hinweis auf die Wichtigkeit einzelner Funktionen aus den Funktionsmengen
zeigt.


\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
Wert                            & Weiß 100.000   & Schwarz 100.000        & Weiß 250.000 \\  
\hline
König                           & 2.028,5               & 1.840,0                        & 1.565,8 \\         
Dame                            & 891,3                 & 862,9                         & 934,5 \\ 
Läufer                          & 377,9                 & 431,9                         & 390,8 \\
Springer                        & 303,1                 & 319,9                         & 343,8 \\
Turm                            & 136,7                 & 113,3                         & 113,0 \\
Bauer                           & 274,9                 & 276,2                         & 256,8 \\
\hline
Zentrumsbauer                   & 25,0                  & 26,3                          & 26,6 \\
Doppelbauer                     & \textbf{24,2}   & \textbf{28,4}               & \textbf{26,7} \\
Freibauer                       & 32,1                  & 43,5                          & 55,7 \\
Rückständiger Bauer             & \textbf{40,9}   & \textbf{34,3}               & \textbf{42,1} \\
Bauernstruktur                  & \textbf{23,5}   & \textbf{22,3}               & \textbf{22,4} \\
\hline
Springermobilität               & 36,8                  & 48,9                          & 40,4 \\
Springerbonus                   & 32,1                  & 39,3                          & 43,6 \\
Springer Bauer                  & \textbf{61,6}   & \textbf{59,3}               & \textbf{52,8} \\   
\hline
Läuferpaar                      & 24,4                  & 25,7                          & 27,1 \\
Bauer Läufer Feldfarbe          & \textbf{21,2}   & \textbf{20,6}               & \textbf{25,5} \\
Blockierter Läufer              & \textbf{42,0}   & \textbf{37,7}               & \textbf{24,0} \\
Läufer Startposition            & \textbf{24,7}   & \textbf{23,2}               & \textbf{33,4} \\
\hline
Turm auf halboffener Linie      & 44,2                  & 49,3                          & 42,3 \\
Turm auf offener Linie          & 36,9                  & 29,9                          & 37,9 \\
Turm                            & 39,9                  & 40,9                          & 44,6 \\
Freibauer und Turm              & 26,2           & 21,7                              & 27,9 \\
\hline
Rochade verpasst                & \textbf{31,1}   & \textbf{26,1}               & \textbf{20,2} \\
Rochade durchgeführt            & 27,0              & 23,9                              & 25,5 \\
König Grundlinie                & \textbf{18,0}   & \textbf{17,4}               & \textbf{22,2} \\
Promotionschancen               & 22,9                  & 31,4                          & 14,6 \\  
\hline   
\end{tabular}
\end{center}
\caption{Diese Tabelle zeigt die durchschnittlichen Werte für Funktionen des
Stellungsbewertungsmoduls. Alle \emph{fett} geschriebenen Werte sind Mali, die
vom Materialwert abgezogen werden, wenn sie zutreffen. Im Kapitel~\ref{sec:MaterialModulChessGP} werden diese
Werte genauer beschrieben.}
\label{tab:GeneticChessFigurWerte}
\end{table}

Die Tabelle~\ref{tab:GeneticChessFigurWerte} zeigt die durchschnittlichen Werte 
für Funktionen des Stellungsbewertungsmoduls. Im Kapitel~\ref{sec:MaterialModulChessGP}
wird die Bedeutung dieser Werte genauer beschrieben, die ersten vier Werte 
beschreiben dabei die Figurwerte und alle anderen Werte beschäftigen sich mit
Stellungselementen. 

Wenn man sich die Werte für die verschiedenen Evolutionsläufe anschaut, sieht man
deutlich, dass sie ähnlich sind, dies stimmt sowohl bei den Figurwerten als auch bei Werten, 
welche Stellungselemente bewerten. Bei den Figurwerten sieht man drei große Unterschiede
zu den Werten, die man in der Literatur findet, die auf einen Artikel von 
Shannon~\cite{shannon50} zurückgehen. Dabei betragen die relativen Werte
für die Königin 900, den Turm 500, den Läufer und den Springer 300 und den Bauern 100, 
 siehe auch~\ref{sec:MaterialBewertung}. 
So werden bei Standardstellungsbewertungen der König nicht bewertet, dem 
GeneticChess-System wurde diese Möglichkeit gegeben, auch um zu überprüfen, ob
dies überhaupt genutzt wird. Im Histogramm~\ref{fig:GCHist-Stellung} kann man 
erkennen, dass die Funktion \emph{getKingValue}, welche den Wert des Königs ermittelt,
für Individuen mit einem Knotenlimit von $250.000$ war dies die viertwichtigste
Funktion in der Funktionsmenge, nach den Grundrechenarten. Auffällig bei den evolvierten
Werten ist aber der geringe Wert für den Turm, er liegt 400 Punkte unter den
Werten, die in der Literatur für den Turm angebeben werden. 
Am erstaunlichsten war für uns jedoch die Bewertung des Bauern, der einen Wert
von ca 260 Punkten bekam und damit um 150 Punkte höher bewertet wurden als ein Turm.
Dies ist ein Verhältnis, welches in der Literatur nicht zu finden ist.
Sehr erstaunlich ist auch der Unterschied von 50-100 Punkten 
zwischen Springer und Läufer, obwohl in der Literatur beide Figuren annähernd 
gleich bewertet werden, oder, wenn es einen Unterschied gibt, der Springer immer
besser bewertet wird als der Läufer. Die Bewertung muss aber in Verbindung mit
den Stellungskriterien gesehen werden, denn für den Springer gibt es drei
stellungsbezogene Kriterien, wobei zwei Boni sind und einer ein Malus. Für den
Läufer gibt es vier stellungsbezogene Kriterien, jedoch sind hier drei Mali und nur
einer ein Bonus. Der Bonus verfällt sofort, wenn nur noch ein Läufer auf dem Brett
steht, wodurch dieser Bonus nicht wie andere Boni bei einer Veränderung der Stellung
wieder gewährt werden kann. Wenn man die Boni des Springers und die Mali des Läufers
den Figuren hinzuzählt, kann man eine Bewertung erhalten, wie wir sie durch die
Literatur erwarten würden. 
Für den Turm kann man einen Wert, wie er in der Literatur zu finden ist nicht einmal
dadurch erreichen, indem man alle Boni zum Figurwert addiert. In den evolvierten
Individuen kann man dann maximal den Wert eines Bauern erreichen. Der Wert des Turms
ist für uns eines der erstaunlichsten Ergebnisse bei diesen Werten.

Die Gegnerprogramme arbeiten mit den bekannten Werten für die Figuren und obwohl wir
die Wahl der Figurwerte der Individuen als nicht gut empfinden, können diese
Individuen die Programme mit den Werten der Literatur schlagen. Dies war auch
das Ziel der Evolution, erstaunlich bleibt trotzdem die Wahl einiger Werte. Wir 
können jedoch nicht abschließend analysieren, warum diese Werte für die Individuen
von Vorteil sind, da sie innerhalb komplexer Programme verrechnet werden und
es dem Programm auch gestattet ist diese Werte intern noch zu verändern. Somit
sind die hier aufgezählten Werte nicht unbedingt die Werte, die auch bei einer
Bewertung innerhalb eines Spiels genutzt werden.



In den folgenden Abbildungen~\ref{fig:GCHist-Stellung} bis~\ref{fig:GCHist-AlphaBranch}
kann man die Verteilung der Funktionen in den einzelnen Modulen für die Evolution 
der weißen (gelbe Balken) und schwarzen Individuen (blaue Balken) mit einem  
Knotenlimit von $100.000$ sehen und die Evolutionsläufe mit einem Knotenlimit von $250.000$
(rote Balken). Hierzu wurden die besten Individuen der einzelnen Evolutionsläufe ausgewählt
und die prozentuale Häufigkeit der verwendeten Funktion bezogen auf die Anzahl aller verwendeten
Funktionen im Individuum berechnet.


\begin{figure}
\centerline{\epsfig{figure=Pictures/Results/GC-HistStellung.eps,width=10cm}}
\caption{Der Plot zeigt ein Histogramm aller genutzten Terminalfunktionen für das Stellungsmodul.
Die gelben Balken des Diagramms stellen die Evolutionsläufe der weißen Individuen mit
einem Knotenlimit von $100.000$ dar, die blauen die der schwarzen Individuen und die
roten die mit einem Knotenlimit von $250.000$, nach diesen sind Balken 
auch fallend sortiert. }
\label{fig:GCHist-Stellung}
\end{figure}


In der Abbildung~\ref{fig:GCHist-Stellung} kann man die Verteilung der Terminalfunktionen
des Stellungsmoduls, die Häufigkeit der Terminalfunktionen ist nach denen der Evolutionsläufe 
mit einem Knotenlimit von $250.000$ absteigend sortiert. Die Nicht-Terminalfunktionen
waren für das Stellungsmodul die Grundrechenarten, diese sind in der Graphik nicht
dargestellt, da sie für alle Evolutionsläufe einen Wert zwischen 12 und 18 \% erreichten.
Damit wären die kleinen Unterschiede bei der Verteilung der Terminalfunktionen
für die Individuen kaum zu erkennen gewesen. Auffällig an diesem Histogramm ist
die relative Homogenität in der Verteilung der einzelnen Funktionen. So kann man
nicht sagen, dass die Individuen die Gruppe von Funktionen der Figurwerte denen der
Stellungskriterien bevorzugen. Hier scheint die Kombination dieser Funktionen wichtig
zu sein. Diese kann leider durch diese Art der Analyse nicht erkannt werden.
Durch die genutzte Individuenstruktur kann aber die Kombination der Funktionen
untereinander durch eine statische Analyse des Individuums nicht herausgefunden
werden, da sich ja die aktiven Bereiche des Individuums durch den Programmfluss und
somit die Eingabe ergeben. Grundsätzlich zeigt uns das Histogramm aber, dass die
von uns gewählten Funktionen für das Individuum alle sinnvoll gewesen sind.


\begin{figure}
\centerline{\epsfig{figure=Pictures/Results/GC-HistZug.eps,width=11cm}}
\caption{Der Plot zeigt ein Histogramm aller genutzten Funktionen für das Zugsortierungsmodul. 
Die gelben Balken des Diagramms stellen die Evolutionsläufe der weißen Individuen mit
einem Knotenlimit von $100.000$ dar, die blauen die der schwarzen Individuen und die
roten die Evolutionsläufe mit einem Knotenlimit von $250.000$.}
\label{fig:GCHist-Zug}
\end{figure}


Das Histogramm~\ref{fig:GCHist-Zug} zeigt die Verteilung der Funktionen im Zugmodul,
hier sieht man ähnlich wie im Stellungsmodul eine relative Homogenität in der
Verteilung der Funktionen, sie ist jedoch nicht ganz so stark ausgeprägt wie
bei dem Stellungsmodul ist. In der Graphik sind ebenso wie für das Stellungsmodul
nur die Terminalfunktionen abgebildet, die Menge der Nicht-Terminalfunktionen wurde nur
durch die Grundrechenarten gebildet und sie haben ähnlich wie für das Stellungsmodul
Häufigkeiten im Bereich von 15\% ergeben. Einen geringen Unterschied zwischen der
Verteilung der Funktionen im Stellungsmodul und im Zugmodul gibt es allerdings doch.
Durch die Sortierung nach den Funktionsnamen wird dies etwas deutlicher, denn
hier kann man schon erkennen, dass besonders von den weißen und schwarzen Individuen
gleiche Funktionen gleich häufig in den Individuen genutzt werden. Die Häufigkeiten
für die Individuen mit einem Knotenlimit von $250.000$ unterscheiden sich für
einige der Funktionen deutlicher als die anderen beiden Evolutionsläufe. 
Dies ist auch beim Stellungsmodul zu beobachten, wenn auch nicht ganz so deutlich. 
Wir interpretieren diese Ähnlichkeit dahin, dass diese Funktionen für die Module
ähnlich wichtig sind und die Kombination dieser Funktionen wichtiger ist als
deren Häufigkeit.


\begin{figure}
\centerline{\epsfig{figure=Pictures/Results/GC-HistAlpha.eps,width=11cm}}
\caption{Der Plot zeigt ein Histogramm aller genutzten Funktionen für das Tiefenmodul. 
Die gelben Balken des Diagramms stellen die Evolutionsläufe der weißen Individuen mit
einem Knotenlimit von $100.000$ dar, die blauen die der schwarzen Individuen und die
roten die Evolutionsläufe mit einem Knotenlimit von $250.000$.}
\label{fig:GCHist-Alpha}
\end{figure}


Für das Histogramm des Tiefenmoduls~\ref{fig:GCHist-Alpha} ergibt sich ein
anderes Bild als für die beiden anderen Module. Hier kann man deutliche Unterschiede
zwischen den Häufigkeiten der einzelnen Funktionen sehen. So sind Funktionen, die
die Struktur des Suchbaumes beschreiben, wie die Tiefe des Suchbaumes oder die
Alpha- und Beta-Grenzen für dieses Modul genauso wichtig, wie Informationen
bezüglich des Königs und der Königin. Hierbei werden sowohl die eigenen Figuren
betrachtet, als auch die gegnerischen Figuren. Auch werden die Grundrechenarten
häufig genutzt, jedoch sind sie hier nicht so wichtig, wie sie es für die anderen
Module sind. Ebenfalls wichtig, jedoch nicht genauso wichtig wie die erste
Gruppe von Funktionen, sind die Funktionen, die die Anzahl der angegriffenen oder
gedeckten Figuren der eigenen Seite oder der gegnerischen Seite berechnen.
Die letzte Gruppe bilden die restlichen Funktionen, die für dieses Modul zugelassen
waren, hierunter befinden sich hauptsächlich Funktionen, die eine Bewertung
der möglichen Züge durchführen.


\begin{figure}
\centerline{\epsfig{figure=Pictures/Results/GC-HistAlphaBranch.eps,width=11cm}}
\caption{Der Plot zeigt ein Histogramm aller genutzten Branching-Funktionen für das Tiefenmodul. 
Die gelben Balken des Diagramms stellen die Evolutionsläufe der weißen Individuen mit
einem Knotenlimit von $100.000$ dar, die blauen die der schwarzen Individuen und die
roten die Evolutionsläufe mit einem Knotenlimit von $250.000$.}
\label{fig:GCHist-AlphaBranch}
\end{figure}


Eine deutliche Unterteilung der Häufigkeiten von Funktionen erkennt man auch
in der Abbildung~\ref{fig:GCHist-AlphaBranch}, hier werden die Branchingfunktionen
des Tiefenmoduls dargestellt. Die Histogramme für die Stellungs- und Zugmodule
für die Branchingfunktionen werden hier nicht gezeigt, da sie eine ähnliche
Homogenität aufweisen wie die Histogramme für die Funktionen. Auch für die Branchingfunktionen
sind Funktionen wichtiger, die die Struktur der Stellung analysieren, als die
Funktionen, die Bewertungen von Zügen vornehmen.


An diesen Beispielen kann man erkennen, dass die  verschiedenen Module doch 
sehr unterschiedlich mit den angebotenen Funktionsmengen umgehen. So gibt
es bei dem Tiefenmodul eine deutliche Strukturierung der Häufigkeiten, die es
für die anderen Module nicht gibt. Eine weitere Analyse der Funktionsmengen
für die Schachindividuen wäre sicherlich von Vorteil und könnte sehr wahrscheinlich
auch noch das Potential der Programme erhöhen. Problematisch ist jedoch der hohe
Zeitaufwand für solche Analysen, da wir nicht davon ausgehen können, dass Evolutionsläufe
mit geringerem Knotenlimit und damit schwächeren Individuen die gleichen Funktionsmengen
benötigen würden wie stärkere Individuen. Dies kann man schon an den Unterschieden
der Funktionshäufigkeiten für die Programme mit einer Fitness von 6.000 und der von
8.000 sehen. An dieser Stelle könnte der Einsatz von  Developmental Genetic 
Programming (DGP)~\cite{keller:1999:TEGCGP} vielleicht ein Ausweg sein, um trotz
des hohen Rechenaufwandes zu einer besseren Auswahl der Funktionsmengen zu kommen.
%besonders wenn man Evolutionsläufe mit dem vollständigen Funktionssatz starten würde.




%----------------------------------------------------------------------
\subsection{Fazit GeneticChess}
%----------------------------------------------------------------------
\label{sub:GeneticChessFazit}

Das GeneticChess-System hat unser Hauptziel, spielstarke Individuen zu evolvieren, die mindestens
Programme der Suchtiefe sieben schlagen können, erreicht. Weiterhin konnten wir
auch eine Steigerung der Spielstärke durch einen komplexeren Aufbau der
Individuen gegenüber dem qoopy-System erreichen. Dies konnte die Steigerung 
der Spielstärke gegenüber dem qoopy-System erreichen, ohne dass wir den Individuen
eine höhere Rechenleistung erlaubten. So hatten beide Systeme ein Limit von $100.000$
Knoten, die zur Analyse des nächsten Zuges genutzt werden konnten. Konnten die
Individuen des qoopy-Systems maximal ein Programm der Suchtiefe fünf schlagen,
so konnten die Individuen des GeneticChess-Systems Programme der Suchtiefe sechs schlagen.
Bei einem Knotenlimit von $250.000$ ist es dem GeneticChess-System sogar gelungen
zwei Individuen zu evolvieren, die Programme der Suchtiefe acht schlagen und ein
Individuum, das Programme der Schuchtiefe sieben schlägt.


Da die Stärke von Schachprogrammen eigentlich mittels des Elowertes ermittelt
wird, stellt sich für uns noch die Frage, wie stark  ein Programm der Suchtiefe
fünf oder sechs ist. Hierzu gibt es verschiedene Untersuchungen, die alle ungefähr zum
gleichen Ergebnis kommen. Wir haben in der Abbildung~\ref{fig:eloEntwicklung}
die Ergebnisse einer Untersuchung von Ernst Heinz dargestellt~\cite{heinz-new}.
Er konnte zeigen, dass zwischen dem dritten und neunten Halbzug die
Programme eine Steigerung von 200 Elopunkten erzielten, jenseits des neunten Halbzuges
sinkt die Steigerung der Spielstärke auf 70 Elo. 
Ein Programm der Suchtiefe fünf
hat einen Elowert von 1.600, da die Individuen des qoopy-Systems Programme der
Suchtiefe fünf schlagen können und gegen Programme der Suchtiefe sechs verlieren
liegt ihr Elowert bei ungefähr 1700.  Die Individuen des GeneticChess-Systems mit
einem Knotenlimit von $10.0000$ können Programme der Suchtiefe sechs schlagen und
erreichen somit ungefähr einen Elowert von 1.900. Die stärksten Individuen des
GeneticChess-Systems können Programme der Suchtiefe acht schlagen und hätten somit einen
Elowert von über 2.200. Da wir aber im Abschnitt~\ref{sub:Ind250} gesehen haben, dass
die Individuen gegen Programme mit einer geraden Suchtiefe weniger Probleme hatten, die
Spiele zu gewinnen, als gegen Programme mit einer ungerade Suchtiefe. Was durch
die Implementierung der Gegnerprogramme ohne Ruhesuche herrührt. Daher gehen wir davon
aus, dass die Individuen ungefähr eine Spielstärke von 2.000 Elo haben. Dies entspricht
einem Expertenlevel bei den Schachspielern.


\begin{wrapfigure}{r}{60mm}
%\begin{figure}
  \centerline{\epsfig{figure=Pictures/Graphik/eloEntwicklung2.eps,width=6cm}}
  \caption{Das Balkendiagramm zeigt die Entwicklung des Elowertes bezogen
        auf die Suchtiefe eine Schachprogramms. Die Werte sind aus~\cite{heinz-new} 
        entnommen. }
  \label{fig:eloEntwicklung}
\end{wrapfigure}%{figure}

Wenn man diese Ergebnisse mit anderen Ergebnissen vergleicht, die evolutionäre
oder lernende Verfahren verwendet haben, um schachspielende Programme zu entwickeln,
so haben wir einen sehr großen Fortschritt erzielt. Als Beispiele seien hier
die Arbeiten von Keller et al. in~\cite{keller:2002:bnaic}, sie konnten nur eine vereinfachte
Variante des  Schachproblem lösen; oder Hauptman und 
Sipper~\cite{eurogp:HauptmanS05,Hauptman:gecco05lbp}, die Programme zur Lösung von
Endspielproblemen evolvierten;  
und Kendall und Whitwell~\cite{kendall:2001}, die die Parameter für die Materialbewertung
evolvierten um so eine Verbesserung eines Alpha-Beta Algorithmus zu erhalten.
Als ein anderes Verfahren ist noch das SAL-System von Gherrity zu erwähnen~\cite{sal:93}.
Nach einer langen Lernphase konnte es acht Remis in 4.200 Spielen gegen Gnuchess erreichen,
bei der gewählten Einstellung für Gnuchess, erreichte es ein spielstärke von ungefähr 1.200 Elo.
Im Vergleich zu diesen Ergebnissen, haben wir einen großen Sprung bei der
Spielstärke und der Komplexität der Programme gemacht. 
So konnten zwei Individuen Programm der Suchtiefe acht schlagen und
haben somit die Spielstärke eines Schachexperten erreicht, dies entspricht einem
Elowert von ungefähr 2.200 Punkten.


Neben diesen Leistungen ist uns aber besonders wichtig, wie die Individuen
diese Ergebnisse erzielen konnten. Hier ist der geringe Knotenverbrauch der Individuen
beim Aufspannen des Suchraumes zu unterstreichen. So konnten die Programme diese
Leistungen mit nur 2\% des Suchraumes erreichen, den ein guter Alpha-Beta
Algorithmus für die gleiche Aufgabe benötigt hätte. Wie wir in Kapitel~\ref{sub:Ind250}
aber genauer untersucht haben, kommt man durch die komplexen Berechnungen, die wir
den einzelnen Modulen ermöglichen, nur zu einer Knotenersparnis von 60\%. Dies ist immer noch
ein sehr guter Wert und zeigt zudem, dass man durch Erweiterungen der Module eines
Standardalgorithmuses ein erhebliches Entwicklungspotential freisetzen kann.
Man müsste an dieser Stelle die Algorithmen genauer hinsichtlich der Laufzeit 
analysieren, ob der erhöhte Aufwand bei der Berechnung der Stellungen den Gewinn
in den Einsparungen im Suchraum ausgleicht. Bei Spielen gegen Programme der
Suchtiefe sieben und acht, können wir dies auf jedenfall bestätigen, denn hier
war die Berechung der Individuen um einen Faktor von bis zu 20 schneller als die der Gegnerprogramme. 
Da wir bei der Entwicklung dieses Systems, aber auch immer die Möglichkeit der 
Lösung anderer Probleme mit berücksichtigt haben. Glauben wir, dass dieses
System gut bei Problemen eingesetzt werden kann, bei denen die Auswertung eines
Punktes im Suchraum sehr aufwendig ist und eine starke Einsparung von Knoten
im Suchraum auch mit einer aufwendigeren Berechung zur Auswahl der Punkte im Raum sinnvoll ist.

Der Ansatz Module eines bekannten Suchalgorithmus durch die
Genetische Programmierung zu erweitern hat sich bewährt und erstaunliche
Ergebnisse hervorgebracht. Auch der Einsatz eines rekursiven Individuums kann als
Erfolg gewertet werden. So konnten die Individuen ohne Probleme die Rekursion
nutzen, um das gestellte Problem zu lösen.









%%% Local Variables:
%%% mode: latex
%%% TeX-master: "mainChessDiss"
%%% End:
%
