\label{kapitelfuenf}


\emph{GeneticChess}\index{GeneticChess} ist kein allgemeines
GP System, sondern ein spezialisiertes System mit dem Ziel
Schach spielende Individuen zu generieren. Genauer definiert besteht
das Ziel darin, eine \emph{gute} Suchheuristik für das Schachspiel zu
finden. Denn die Suchheuristik ist das zentrale Modul eines
Schachprogramms, kann aber auch für viele andere
Probleme eingesetzt werden. Viele Problem können direkt durch Suchverfahren
gelöst werden, andere können durch eine entsprechende Tranformation 
 mittels Suchverfahren, auch \emph{State-Space Verfahren} genannt,
gelöst werden~\cite{problem71,Kaindl:89}. Die Ergebnisse dieser Arbeit können 
durch entsprechende Anpassungen auf andere Suchprobleme angewendet werden, um so
Problemstellungen zu lösen, die noch nicht durch GP-Programme gelöst werden.
Beispiele wären hier Optimierprobleme wie das TSP oder das Vehicle Routing Problem
und auch andere Probleme, die durch Suchverfahren gelöst werden können. 


Wenn man sich nun das Schachproblem genauer anschaut, stellt man fest, dass
man es in verschiedene Teilprobleme aufteilen kann, die sowohl durch
den zeitlichen Ablauf als auch durch den Aufbau des Spiels selber 
gegeben sind. Die wichtigsten Teilprobleme des Schachspiels, die von
Schachspielern und guten Schachprogrammen gelöst werden müssen, sind:
\begin{enumerate}
\item \label{it:openingTheory} Die \emph{Eröffnung}, sie umfasst den zeitlichen
		Bereich zu Beginn des Spiels, sie ist nicht genau definiert, normalerweise 
		umfasst sie die ersten 10 bis 15 Züge einer Partie. Im
        allgemeinen werden eine große Datenbasis von verschiedenen Eröffnungen und
        auch verschiedene Regelmäßigkeiten in den Stellungen untersucht um gute Eröffnungen 
        zu spielen.
\item \label{it:middleTheory} Das \emph{Mittelspiel} versucht
        ganze Stellungen, aber auch wichtige Konstellationen verschiedener
        Figuren zu erkennen, um so einen taktischen Vorteil in einer
        Situation erringen zu können. In dieser Phase des Spiels werden im Computerschach 	
        Suchalgorithmen wie die Alpha-Beta Suche verwendet.
\item \label{it:endingTheory} Das \emph{Endspiel} ist die
       Situation im Spiel, wenn nur noch wenige Figuren auf dem Brett
       stehen. Hierfür wurden verschiedene Regeln entwickelt, aber auch
       Datenbanken mit der vollständigen Lösung von verschiedenen
       Figurkombinationen aufgebaut.
%\end{enumerate}
%
%       
%\begin{enumerate}       
\item \label{it:positionEval} Die \emph{Materialbewertung} bewertet eine
        gegebene Schachstellung, dabei werden sowohl die Figuren als auch die
        Stellung der Figuren bewertet.
\item \label{it:variantsEval} Die \emph{Variantenberechnung} berechnet die
        möglichen Konsequenzen einer gegebenen Stellung und ermittelt daraus
        einen \emph{guten Zug}.
\item \label{it:planEval} Die \emph{Planung} definiert für eine gegebene
        Stellung ein langfristiges Ziel. Die Aufgabe der langfristigen Planung
        wird von Computerschach Programmen selten durchgeführt. Hier wird anders als
        bei menschlichen Spielern das Gewicht stärker auf die Variantenberechung gelegt.
\end{enumerate}


Alle folgenden GP Systeme haben nicht das Ziel die
Aspekte der \emph{Eröffnungstheorie}, der \emph{Theorie des Mittelspiels}
oder der \emph{Endspieltheorie} zu lösen. Es werden keine Module für diese
Aufgaben evolviert, da diese Aspekte immer auf einer Wissensbasis
und die Lösung auf Data Mining Verfahren beruhen. Die
Praxis zeigt, dass alle diese Verfahren die Spielstärke jedes
Programms um mehrere hundert Elopunkte steigern können, aber eine gute
Suchheuristik ist der Kernpunkt jedes Programms. In der Literatur und
in der Praxis findet man sehr viele verschiedene Varianten der
Suchheuristiken und immer noch werden Verbesserungen an bekannten
Verfahren vorgeschlagen. Daher konzentriert sich die Arbeit auf die
Suchheuristiken und nicht auf alle möglichen Elemente des Schachspiels.


Um dieses Ziel zu erreichen, wird den GP Systemen ein allgemeines Modul einer
Suchheuristik und deren Programmfluss vorgegeben. Das Programm und seine
Module sollen sich dann automatisch durch den evolutionären Prozess bilden.
Dieses Vorgehen führte letztlich dazu, dass das \emph{State-Space Individuum} entwickelt
wurde, welches einen festen Rahmen für ein Suchprogramm vorgibt (siehe
Kapitel~\ref{sec:stateSpaceGP}).
Diese Erweiterung der Genetischen Programmierung ist jedoch nicht ausreichend,
um ein Individuum zu generieren, das Schach spielt. Hierzu sind spezielle Elemente
notwendig, die auf das Schachproblem ausgerichtet sind. Darunter fallen insbesondere die
Fitnessfunktion, Funktionen und Terminale sowie zusätzliche Datenstrukturen,
welche die Problemlösung unterstützen.




%----------------------------------------------------------------------
\section{Vorarbeiten}
%----------------------------------------------------------------------

Das GeneticChess System, das in den folgenden Kapiteln vorgestellt
wird, hat sich aus verschiedenen Vorarbeiten der letzten
Jahre entwickelt. Die Ergebnisse, aber auch Fehlschläge dieser Systeme,
sind in das Design der verschiedenen Komponenten des Systems eingeflossen. Sie
motivierten aber auch die Suche nach flexibleren und angepassteren
Individuenstrukturen um ein gegebenes Problem zu lösen. Die
Reihenfolge der Kapitel geben die zeitliche Entwicklung der einzelnen
Projekte wieder.

Die Grundidee aller dieser Systeme war es, ein Schachprogramm zu entwickeln,
welches evolutionäre Verfahren verwendet. Daher stellten sich  zwei zentrale
Fragen: Erstens, wie evolviert man ein GP Programm, das Schach spielt und zweitens, wie kann 
man dies mit der aktuellen Rechenkraft in einer angemessenen Zeit tun. Diese Fragen werden in
den folgenden Kapiteln bearbeitet und mit verschiedenen Methoden gelöst.

%In den folgenden Kapiteln werden verschiedene Ansätze gezeigt, die diese
%Problemstellung lösen können. Dabei sind verschiedene herangehensweisen an die
%Probleme zu



%----------------------------------------------------------------------
\subsection{ChessGP}
%----------------------------------------------------------------------
\label{sec:ChessGP}

Im \emph{ChessGP}\index{ChessGP} System wird das Problem zur Evolution von Schachprogrammen
dadurch gelöst, dass man es in verschiedene Teilprobleme zerlegt.
Diese Teilprobleme werden dann in einer \emph{hierarchischen Evolution}
entwickelt, die letztlich in einem evolvierten Schachprogramm endet. Die Teilprobleme 
werden durch eigenständige Teilindividuen
gelöst und anschließend in einer \emph{hierarchischen
  Struktur}\index{hierarchische Struktur} zusammengefasst. Die
Teilindividuuen werden jeweils einzeln evolviert, dabei wird jedoch auf
den hierarchischen Aufbau des Gesamtindividuums geachtet. Dies bedeutet,
dass Teilindividuen, die einer höheren Hierarchieebene angehören, erst
evolviert werden können, wenn die Teilindividuen der tieferen Hierarchieebenen
fertig evolviert wurden. Diese  werden dann den Teilindividuen
der höheren Hierarchieebene als zusätzliche Terminale zur Verfügung gestellt
(siehe Abschnitt~\ref{sub:ChessInds}).

Eine wichtige Erweiterung des Systems, gegenüber bekannten Systemen der
Genetischen Programmierung, ist die Einführung von Datenstrukturen für die
Individuen. Die Individuen in GP Systemen arbeiten normalerweise mit einem
einfachen Datentyp, entweder Double oder Integer, jedoch nie mit einer
komplexen Datenstruktur. Es hat sich gezeigt, dass viele Funktionen und
Terminale für das Schachproblem komplexe Datenstrukturen benötigen. Somit ist
es sinnvoll den GP Individuen die Möglichkeit zu geben, direkt auf diesen
Datenstrukturen zu arbeiten und nicht diese Strukturen auf Double- oder
Integerwerte herunterbrechen zu müssen (mehr zu diesem Thema in
Kapitel~\ref{sec:ChessGPDatenstruktur}). 

Während der Implementierung stellte sich schnell die Frage, welche
GP Strukturen für die einzelnen Teilindividuen verwendet werden sollten. Zu
Beginn des Projektes gab es die neuen Individuentypen noch nicht, so fiel die
Wahl auf lineare GP Strukturen. Weiteres zu diesem Thema ist in
Kapitel~\ref{sec:ChessGPResults} zu finden.



%----------------------------------------------------------------------
\subsubsection{Die Fitnesscases}
%----------------------------------------------------------------------

Die Ergebnisse maschineller Lernverfahren hängen sehr stark von der
Beschaffenheit der Trainingsdaten ab. Für die gestellte Aufgabe sind es
Schachstellungen. Nun kann man nicht wie für andere Probleme alle 
möglichen Stellungen betrachten,
sondern muss eine Auswahl treffen. Daher haben wir folgende Anforderungen an
die Trainingsdaten gestellt:
\begin{itemize}
\item Die Anzahl der Beispiele sollte nicht zu klein sein.
\item Die Stellungen sollten realistische Stellungen sein.
\item Die Diversität der Trainingsdaten sollte möglichst hoch sein.
\end{itemize}

Die verwendete Trainingsmenge beruht auf 640 real gespielten Partien, ihre
Grundlage ist die Sonderausgabe~\cite{mat96} einer Schachzeitschrift, die in
Deutschland als der Schachinformator bekannt ist. Diese Partiensammlung wurde
in eine Menge von etwa 40.000 Schachstellungen transformiert. Es wurde dieser
Weg beschritten, da versucht werden sollte hochwertige Partien als Trainingsmenge zu
nutzen. Viele Partien in kommerziellen Datenbanken haben aber Fehler,
enthalten Partien doppelt oder sind wenig repräsentativ. Daher haben wir uns
entschieden einen eigenen Weg zu gehen und nicht auf kommerzielle Datenbanken
zurückzugreifen.
Durch das hohe Spielniveau der Partien ergab sich leider das Problem, dass
die Partien frühzeitig durch die Spieler abgebrochen wurden, dieses wurde schon oft nach einem
Materialverlust von nur einem Bauern getan. Daher wurden diese Partien von dem
Schachprogramm \emph{Crafty} zu Ende gespielt, um so auch Stellungen vom Ende
der Partien als Fitnesscases zu erhalten~\cite{hyatt97b}.

%----------------------------------------------------------------------
\subsubsection{Struktur der Schachindividuen}
%----------------------------------------------------------------------
\label{sub:ChessInds}




Die Struktur der Schachindividuen\index{ChessGP!Schachindividuen} ist einer
der zentralen Punkte, der die Möglichkeiten der GP Programme und somit auch
ihre Güte begrenzt. Das Hauptziel der Evolution ist es,
eine \emph{gute} Suchheuristik für das Schachspiel zu finden. Daher analysierten
wir verschiedene Heuristiken. Es zeigte sich, dass die wichtigsten Elemente in
den Heuristiken die \emph{Materialbewertung}, die \emph{Variantenberechnung} und
die \emph{Planung} sind. Auf diesen drei Elementen beruht der Aufbau des
Individuums, die Grafik~\ref{fig:chessIndStruct} verdeutlicht die interne
Struktur der Individuen. 
Es wurde eine hierarchische Struktur gewählt, da auch
die drei Heuristiken einer Hierarchie unterliegen. Auf der untersten Ebene der
Hierarchie liegt die Materialbewertung, auf der nächsten Ebene liegt das
Modul, das kurzfristige Pläne vorschlägt und auf der letzten Ebene das
Modul zur Variantenberechnung. 
\begin{wrapfigure}{r}{85mm}
%\begin{figure}
   \centerline{\epsfig{figure=Pictures/Graphik/chessGPInd.eps,width=8.5cm}}
   \caption{Die Struktur der Schachindividuen. Die Module der höheren Ebenen
     können die Module der tieferen Ebenen aufrufen.}
   \label{fig:chessIndStruct}
\end{wrapfigure}%{figure}
Durch diese Struktur können die Module einer
höheren Hierarchieebene jedes Modul der tieferen Hierarchieebenen
aufrufen. Die oberste Hierarchieebene entscheidet, welcher Zug für eine
gegebene Stellung gemacht wird, dazu kann und muss dieses Modul die
Ergebnisse der unteren Hierarchieebenen nutzen, indem es diese aufruft. Dabei
ist es wichtig zu erwähnen, dass jede Ebene wiederum aus mehreren GP
Programmen besteht, die wie bei der Materialbewertung und der Planung
gleichberechtigt nebeneinander stehen. Anders im Varianten Modul, hier stehen die Module
durch einen vorgegebenen Programmfluss miteinander in Verbindung.



Die Grafik~\ref{fig:chessIndStruct} zeigt den hierarchischen Aufbau des
Individuums und der einzelnen Ebenen, auf die Struktur
der einzelnen Ebenen  wird erst später eingegangen. Jedoch kann
man schon erkennen, dass die Materialbewertungsebene aus acht Modulen
besteht, die Planungsebene aus sieben und die Variantenebene aus vier
Modulen. Wichtig ist noch zu erwähnen, dass Module der Material- und 
Planungsebene sich nicht gegenseitig aufrufen können, nur in der Variantenebene
rufen sich die Module gegenseitig auf.





%----------------------------------------------------------------------
\subsubsection{Materialbewertungsebene}
%----------------------------------------------------------------------
\label{sub:MatChessGP}

Die \emph{Materialbewertungsebene}\index{ChessGP!Materialbewertungsebene} hat die
Aufgabe für eine gegebene Stellung eine Bewertung zu finden. Bei der Bewertung
handelt es sich um eine statische Bewertung, da nur von der gegebenen Stellung
ausgegangen wird und nicht von möglichen Zügen oder Entwicklungen der
Stellung. Die Bewertung ist somit eine Funktion, die eine Stellung auf eine
reelle Zahl abbildet. Diese wird dann als ein Gütemaß für die untersuchte Stellung
interpretiert. Die Ebene in der hierarchischen Struktur selbst besteht
aus mehreren Modulen, die die Aufgabe aus verschiedenen Blickwinkeln betrachten
sollen.


Die einfachste Funktion um eine Materialbewertung beim Schachspiel durchzuführen,
wurde von Shannon um 1950 vorgestellt. Hierzu gibt er jedem Figurtyp einen ganzzahligen
Materialwert zwischen 100 für einen Bauern und 900 für die Königin. 
Die Funktion summiert dann die Materialwerte der Figuren jeder Seite auf und bildet
anschließend die Differenz der beiden Summen. So kann man erkennen, welche Seite
ein Materialübergewicht hat und dies entsprechend positiv oder negativ bewerten.
Innerhalb der Computerschachwelt haben sich verschiedenste
Materialbewertungsfunktionen entwickelt, die meisten Funktionen wurden für genau 
ein Schachprogramm entwickelt und auch nur in ihm eingesetzt.

An dieser Stelle
wollten wir einen anderen Weg gehen, indem das Modul nicht nur aus einem GP
Programm für eine Materialbewertung besteht, sondern aus einer Menge von
verschiedenen Programmen. Jedes dieser Programme hat einen etwas anderen
Blickwinkel auf die Aufgabe, so dass dem Gesamtindividuum die Möglickeit
gegeben werden soll die passende Materialbewertung für die verschiedenen
Spielsituationen zu nutzen oder diese zu kombinieren.

Wir haben dazu acht verschiedene Fitnessfunktionen für Materialbewertungsfunktionen
entwickelt, wobei die ersten vier Materialbewertungen neutral sind, das heißt,
sie bewerten die Stellung unabhängig vom Spieler, der am Zug ist. Die letzten
vier Bewertungen bewerten die Stellung von der Seite der GP Individuen aus; da
die GP Individuen im ChessGP immer weiß spielen, sind die Bewertungen nur für
die weiße Seite sinnvoll. Wir wollen acht verschiedene Materialbewertungen
vom ChessGP-System entwickeln lassen. Dazu haben wir die folgenden Bewertungen entwickelt, 
die gleichzeitig die Zielfunktion der Module darstellen.

\begin{enumerate}

\item Die \emph{Komplexitätsbewertung} bestimmt für jede Figur die
  Anzahl der möglichen Züge. Züge, die zum Schlagen einer anderen Figur führen, 
  werden doppelt gewertet.
\begin{equation}
    \label{eq:MatKomp}
    \begin{split}
      komp &= \sum_{f\in\text{Figuren}} (\text{Anzahl der von f erreichbaren
        Felder} \\
      &+ \text{Anzahl der von f möglichen Schlagzüge} )
 \end{split}
  \end{equation}

\item Die \emph{Endspielbewertung} ist ein Maß für den
  Endspielcharakter der Stellung. Dabei wird eine Stellung mit 13
  Figuren als Endspiel betrachtet und erhält einen Wert von 100. Hat eine
  Stellung weniger Figuren, soll der Wert linear weiter ansteigen, bei weniger
  Figuren linear fallen, bis er für 32 Figuren den Wert null erreicht. Die
  folgende Funktion berechnet dieses Maß:
  \begin{equation}
    \label{eq:MatEnd}
    \begin{split}
      endIndex(\text{Anzahl der Figuren})= \frac{32 - \text{Anzahl der
          Figuren} } {32-13} * 100
    \end{split}
  \end{equation}

\item Die \emph{Aggressivitätsbewertung} ermittelt über die Anzahl der
  Gewinnschlagzüge\footnote{Dies sind Züge, bei denen die zu schlagende Figur
  höher- oder gleichwertig ist oder die zu schlagende Figur ungedeckt ist.}
  die Aggressivität der Stellung. Die Gewinnschlagzüge werden sowohl für die
  weißen als auch für die schwarzen Figuren ermittelt, der Wert für die
  Aggressivität ist dann:
  \begin{equation}
    \label{eq:MatAgg}
    \begin{split}
      agg= \sum_{f \in \text{Figuren}}  \text{Anzahl der von f ausführbaren
        Gewinnschlagzüge}
    \end{split}
  \end{equation}

\item Die \emph{Defensivitätsbewertung} ermittelt über die Anzahl der
  gedeckten Figuren einen Wert für die Defensivität der Stellung. Dazu wird die
  Anzahl der Figuren gezählt, die eine Figur decken, und dies dann über alle
  Figuren summiert. Der Wert für die Defensivität ist dann:
  \begin{equation}
    \label{eq:MatDef}
    \begin{split}
      def= \sum_{f \in \text{Figuren}}  \text{Anzahl der f deckenden Figuren}
    \end{split}
  \end{equation}

\item Die \emph{einfache Materialbewertung} bildet die Summe der Figurenwerte
  jeder Seite und anschließend die Differenz. Die Figuren werden für
  die Fitnessfunktion wie folgt bewertet:
  \begin{itemize}
  \item Bauer: 100
  \item Springer: 300
  \item Läufer: 300
  \item Turm: 500
  \item Dame: 900
  \end{itemize}
  Der Materialwert berechnet sich dann wie folgt:
  \begin{equation}
    \label{eq:MatSimp}
    \begin{split}
      simple &= \sum_{w \in \text{weiße Figuren}} \text{Materialwert von }  w \\
      &- \sum_{s \in \text{schwarze Figuren}} \text{Materialwert von }  s
    \end{split}
  \end{equation}

\item Die \emph{clevere Materialbewertung} setzt sich aus dem Wert der
  einfachen Materialbewertung, zusätzlichen positionellen Kriterien und einer
  variablen Wertung der Bauern während des Spielverlaufes zusammen.
  Die Berücksichtigung der Brettposition erfolgt mittels einer
  Positionsmatrix, die es für jeden Figurtyp gibt. Die Positionsmatrizen
  wurden in Anlehnung an die Matrizen von GnuChess~\cite{GnuChess} erstellt.
  Die höhere Gewichtung der Bauern wird mit Hilfe des Endspielindexes
  realisiert. Für die clevere Materialbewertung ergibt sich dann folgende
  Formel:
  \begin{equation}
    \label{eq:MatClever}
    \begin{split}
      clever &= \text{simple } + \sum_{w \in \text{weiße Figuren}}
      \text{Positionswert}(w) \\
      &- \sum_{s \in\text{schwarze Figuren}} \text{Positionswert}(s) \\
      &+ 0,5 * \text{Endspielindex} \\
      &* \text{Anzahl weiße Bauern} \\
      &-  0,5 * \text{Endspielindex}  \\
      &* \text{Anzahl schwarze Bauern}
    \end{split}
  \end{equation}

\item Die \emph{Angriffsbewertung} bewertet inwieweit die weißen Figuren eine
  angreifende Position einnehmen. Dabei wird jede angegriffene schwarze Figur
  in der Höhe ihres Materialwertes in die Bewertung einbezogen. Gefesselte
  Figuren werden mit einem Bonus von 300 Punkten bewertet. Der Angriff auf den
  König wird bei dieser Funktion stark gewichtet, so wird der Materialwert des
  Königs mit 3.000 und die benachbarten Felder des Königs mit 75 bewertet. Die
  Summe wird durch den Materialwert aller schwarzer Figuren ohne König
  geteilt, um so eine Relation der materiellen Stärke von Schwarz zu
  erhalten. Zur Normalisierung wird der Wert noch mit
  $\frac{10.000}{\sum_{s\in\text{schwarze Figuren}}}$ multipliziert und gerundet.
\begin{equation}
    \label{eq:MatAng}
    \begin{split}
      angriff &= (\sum_{f \in \text{angegriffene Figuren}} \text{Materialwert von}
      f \\
      &+ 300 * \text{Anzahl gefesselter Figuren} \\
      &+ 75 * \text{Anzahl bedrohter Königsfelder}) \\
      &* \frac{10.000}{\sum_{s\in\text{schwarze Figuren}} \text{Materialwert von }  s}
    \end{split}
  \end{equation}

\item Die \emph{Verteidigungsbewertung} bewertet die Stellung unter dem
  Aspekt, inwieweit die weißen Figuren eine verteidigende Stellung
  einnehmen. Die Bewertung wird analog zu der
  Angriffsbewertung durchgeführt. Hierzu wird aber von der Materialdifferenz der
  gedeckten und ungedeckten weißen Figuren ausgegangen und zusätzlich noch die
  Verteidigung des Königs in die Bewertung mit einbezogen. So werden die
  Felder, die an den König grenzen und von weißen Figuren besetzt sind, mit
  plus 100 gewertet, unbesetzte Felder mit minus 100 und Felder, die von
  schwarzen Figuren besetzt sind, mit minus 200.

 \begin{equation}
    \label{eq:MatVertei}
    \begin{split}
      verteidigung &= (\sum_{f \in \text{gedeckte wieße Figur}} \text{Materialwert
        von } f \\
      &- \sum_{f \in \text{ungedeckte wieße Figur}} \text{Materialwert von } f \\
      &+ 100 * \text{Anzahl weiß besetzter Königsfelder} \\
      &- 100 * \text{Anzahl unbesetzter Königsfelder} \\
      &- 200 * \text{Anzahl schwarz besetzter Königsfelder} ) \\
      &* \frac{10.000}{\sum_{s\in\text{schwarze Figuren}}  \text{Materialwert von }  s}
    \end{split}
  \end{equation}

\end{enumerate}

Jede dieser Bewertungen ist zu unterschiedlichen Zeiten im Schachspiel
sinnvoll und kann somit zu einer Verbesserung der Bewertung gegenüber einer
Standardbewertung führen. Durch den Aufbau des Individuums sollte die
Nutzung der verschiedenen Module verstärkt werden, denn sowohl die
Planungsebene als auch die Variantenebene konnten auf die einzelnen Module
zugreifen.
Inwieweit unsere Erwartungen erfüllt wurden, ist im
Abschnitt~\ref{sub:ChessGPFazit} beschrieben.
Die Ergebnisse der verschiedenen Materialbewertungsmodule sind in
Kapitel~\ref{sub:ChessGPMat} zusammengefasst.


%----------------------------------------------------------------------
\subsubsection{Planungsebene}
%----------------------------------------------------------------------
\label{sec:PlanChessGP}

Die \emph{Planungsebene}~\index{ChessGP!Planungsebene} des Individuums soll für eine
gegebene Stellung eine Zugliste generieren. Die einfachste aller Zuglisten ist
die Liste aller möglichen Züge. Werden aber alle Züge in jeder Stellung
expandiert, hat man ein exponentielles Wachstum des Suchraums, um dies zu verhindern,
werden in den klassischen Verfahren die Suchräume durch verschiedene Verfahren
beschnitten, siehe hierzu die Kapitel~\ref{sub:MiniMax}, \ref{sec:alphaBeta}
und~\ref{sub:SchachHeuristiken}.
%die Züge bewertet und zuerst werden
%die besten Züge für eine Stellung expandiert, um so durch die verwendeten
%Suchalgorithmen zu einem frühren schneiden im Suchraum zu kommen.
In unserem
Modell sollte es nun aber nicht zu einer Bewertung aller Züge kommen, sondern es
sollte ein kurzfristiger Plan für die aktuelle Stellung entwickelt
werden und entsprechend des Plans sinnvolle Züge zur Verfügung gestellt werden.
Dieses Modul enthält dafür sieben verschiedene Individuen, die Zuglisten
mit verschiedenen Ausrichtungen generieren sollen.

\begin{itemize}
\item \emph{Beste Züge} versucht eine qualitative Einschätzung der Situation
  zu treffen und ermittelt die Züge, die zu einer Verbesserung der Stellung
  führen.

\item \emph{Gefährliche Züge}, sind Züge, die zu einem Materialgewinn führen
  können, jedoch auch die Gefahr von Verlusten in sich tragen. So wurden die
  gefährlichen Züge für die Fitnesscases dadurch ermittelt, dass Weiß zwei
  Züge machen kann und Schwarz keinen. Wenn Weiß durch diesen Doppelzug eine
  signifikant bessere Stellung erreichen kann, so wird dieser Zug als
  \emph{gefährlich} gewertet. Eine Stellung wurde als signifikant besser
  gewertet, wenn sie 300 Punkte mehr hat als die Ausgangsstellung, 300 Punkte
  entspricht ungefähr einem Läufer oder Springer.

\item \emph{Desperado Züge} sind Züge, die eine für Weiß verlorene Stellung
  wieder öffnen können. Dabei wird versucht die geplante Taktik des Gegners zu
  durchbrechen, da er mit einem solchen Zug nicht gerechnet hat. Um diese Züge
  zu finden, wird ein Spielbaum der Tiefe eins aufgespannt, mit einer
  veränderten Materialbewertung bewertet und durch zusätzliche Merkmale
  erweitert. Der Materialwert für die weißen Figuren bei Desperado
  Zügen ist 75 für die Bauern, 320 für den Springer, 280 für den Läufer, 450 für
  den Turm und 950 für die Dame. Die Materialwerte für die schwarzen Figuren
  bleiben unverändert. Ein weiteres Kriterium ist die Stellung des schwarzen
  Königs, für jedes den König umgebenden Feld sowie das Königsfeld, wird der
  Materialwert um 30 verringert, wenn das Feld von einer weißen Figur
  angegriffen wird. Ist ein solches Feld von einem schwarzen Bauern besetzt,
  wird der Materialwert um 80 erhöht. Der Materialwert wird erhöht,
  wenn Weiß noch die Dame oder einen Springer besitzt, der Wert ist abhängig von
  der Entfernung (\emph{Nähe}) zwischen den Figuren und dem schwarzen
  König. Die \emph{Nähe} zweier Figuren wird auf einer Reihe, Spalte oder
  Diagonale bewertet. Benachbarte Felder haben einen Wert von 90 und mit jedem
  Feld zwischen den Figuren sinkt dieser Wert um 10. Als letzter Faktor geht
  die Anzahl der möglichen Spielzüge mit in die Bewertung ein. Jeder Zug von
  Weiß erhöht den Wert um 12 und jeder von Schwarz senkt ihn um 10.

  Zusammenfassend ergibt sich folgende Formel für die Bewertung:
  \begin{equation}
    \label{eq:Desp}
    \begin{split}
      desp &= \text{Material Weiß} - \text{Material Schwarz} \\
      &+ \sum_{f \in \text{weiße Dame/Springer}} \text{Nähe} (f, \text{schwarzer
        König} \\
      &+ 30 * \text{Anzahl angegriffener Königsfelder} \\
      &- 80 * \text{Anzahl mit schwarzen Bauern besetzte Königsfelder}) \\
      &+ 12 * \text{Anzahl weißer Spielzüge} \\
      &- 10 * \text{Anzahl schwarzer Spielzüge}.
    \end{split}
  \end{equation}
 

\item \emph{Angriffszüge} sind eine Fortführung der Angriffsbewertung aus
  Kapitel~\ref{sub:MatChessGP}. Hierbei wird ein Spielbaum mit der
  Angriffsbewertung aufgespannt. Die Bewertung eines Zuges ist dann die
  Differenz der Ausgangsstellung und des kleinsten Materialwertes eines Blattes im
  Spielbaum.
 
\item \emph{Verteidigungszüge} werden analog zu Angriffszüge
  bewertet. Hierzu wird nur die Verteidigungsbewertung benutzt.

\item \emph{Tauschzüge} sind im Schach Zugfolgen, bei der beide Seiten
  Figuren schlagen, das Materialverhältnis jedoch gewahrt wird. Hier werden
  aber alle Schlagzüge als Tauschzüge gewertet, bei der es zu keiner
  Verschlechterung des Materialverhältnisses kommt.

\item \emph{Opferzüge} werden hier als Züge definiert, die dem Gegner das
  Schlagen einer Figur ermöglichen. Der Zug muss aber dann in maximal vier Halbzügen
  zu dem Gewinn der Partie führen, einen Materialgewinn von mindestens 400 Punkten nach
  der cleveren Materialbewertung  oder einen taktischen Vorteil
  ermöglichen. Als Vorteil wird dabei das Ansagen von Schach, das Schlagen
  eines Bauern zum Schutz des Königs und das Schlagen eines Königsbauern
  gewertet.

\end{itemize}

Die Aufgabe der Individuen ist es, eine Liste von Zügen zu erzeugen, neben
dieser Anforderung soll die Liste der Aufgabenstellung entsprechen. Die
Zugliste eines Individuums für Angriffszüge soll hauptsächlich Angriffszüge
enthalten und diese Liste soll auch nicht zu lang sein, da die Länge der Liste
dem Outgrad eines Knotes im Suchbaum entspricht und somit direkt die Laufzeit
der evolvierten Individuen beeinflusst. Ein weiteres Merkmal der Liste sollte
eine Sortierung der Liste sein, die besten Züge für die gestellte Aufgabe
sollten am Anfang der Liste stehen. Da man nicht für jede Stellung der
Datenbank alle Zuglisten generieren konnte, enthält die Datenbank nur die
Bewertung der einzelnen Züge, die in einer Stellung möglich sind.
Die Fitness einer Zugliste wird mit Hilfe der Daten aus der Datenbank über die
einzelnen Züge ermittelt. Die Funktion ist entsprechend der Kriterien
\emph{Qualität, Sortierung} und \emph{Länge} unterteilt.

Die \emph{Qualität der Zugliste} ist die Summe der Bewertung der einzelnen
Züge (im folgenden \emph{Zugwerte} genannt). Die Zugwerte wurden in der
Datenbank auf dem Intervall von $[0,1000]$ normiert. Der beste Zug hat dann
den Wert $1.000$ und der schlechteste den Wert $0$.
Für einige Bewertungskriterien wie die \emph{Gefährlichen Züge, Opferzüge}
oder \emph{Tauschzüge} werden nur Züge aufgenommen, die dem entsprechenden
Kriterium genügen. Daher sind einige legale Züge nicht in der Datenbank
enthalten, diese Züge enthalten den Zugwert $-250$, wenn sie vom Individuum
ausgewählt werden.

Die \emph{Sortierung der Liste} ist ein Strafterm in der Fitness, der sich aus der Summe der
Differenzen der Zugwerte zwischen der Zugliste des Individuum und der
Zugliste der Datenbank ergibt:
\begin{equation}
  \label{eq:ChessGPSort}
  \text{Sortierung} = \sum_{i \leq m} abs(\text{Zugwert}_i -\text{Zugwert}_{Pos_i} ) \text{
  für alle } i < Pos_i
\end{equation}

Wobei $m$ die Länge der Zugliste, $i$ die Position des Zuges in der
Zugliste und $Pos_i$ die Position des gleichen Zuges in der Datenbank sind.
Hat ein Zug also in der Zugliste die Position $1$ (mit dem Zugwert $1.000$)
inne und in  der Datenbank die Position $2$ (Zugwert $800$), so ergibt sich für
diesen Zug ein Strafwert von $200$.

Die \emph{Länge der Liste} ist ein weiterer Strafterm in der Fitness, dieser
ist wichtig, um die Listenlänge der Individuen sowohl nach oben als auch nach
unten zu beschränken. Als optimale Listenlänge wird die
Länge der Liste in der Datenbank für die betrachtete Brettstellung
genommen. Wird die optimale Listenlänge ($l_{opt}$) unter- oder überschritten,
so wird die Bewertung der Zugliste wie folgt bestraft:
\begin{equation}
  \label{eq:ChessGPlang}
  \text{Länge}=  abs(l_{opt} - m) * \text{Zugwert}_{l_{opt}}
\end{equation}

Zusammenfassend ergibt sich daraus folgende Fitness für die Bewertung der Zugliste:
\begin{equation}
  \label{eq:ChessGPPlanFit}
  fit= \text{Qualität} -  \text{Sortierung} - \text{Länge}
\end{equation}

Abschießend wird die Bewertung der Zuglisten noch auf das Intervall $[0,1000]$
normiert. Die beste Zugliste hat dann den Wert $1.000$ und die schlechteste den
Wert $0$. 

%----------------------------------------------------------------------
\subsubsection{Variantenebene}
%----------------------------------------------------------------------
\label{sec:ChessGP-Variantenebene}

Die evolvierten Programme der Bewertungsebene sollen statische Bewertungen
einer Brettstellung liefern. Die Planungsebene soll bezüglich einer Stellung
eine Zugliste berechnen, was eine semi-dynamische Aufgabe ist. Diese beiden
Ebenen sind aber nur Bausteine für die
\emph{Variantenebene}\index{ChessGP!Variantenebene}, sie stellt mit den Bausteinen das
Gesamtindividuum dar, welches Schach spielen soll. Der hierarchische Aufbau des
Individuums mit den verschiedenen Ebenen und den einzelnen Bausteinen ist in
der Abbildung~\ref{fig:chessIndStruct} dargestellt. Die Aufgabe des
Gesamtindividuums ist es nun zu einer Stellung einen \emph{Zug} zu berechnen.
Dazu werden in einer Baumsuche verschiedene Varianten für die Stellung
durchgerechnet und anschließend eine davon ausgewählt.

Um den GP-Programmen eine Baumsuche zu ermöglichen, wird das Programm rekursiv
ausgeführt. Die Eingabe für das Individuum ist eine Stellung, dann wird das
\emph{Entscheidungs-Modul} für die weiße oder schwarze Seite aufgerufen. Es
entscheidet darüber, ob die Stellung weiter expandiert wird oder nicht und
welches Programm für die Berechnung der Zugliste zuständig ist. Dann wird das
entsprechende Programm aufgerufen und eine Zugliste generiert. Für jede
Stellung in der Zugliste wird nun wieder das Individuum aufgerufen.
Das Entscheidungs-Modul der entsprechenden Seite wird aufgerufen, bis entweder das
Entscheidungs-Modul die Stellung nicht weiter expandiert oder die Zugliste,
die von dem Individuum der \emph{Planungsebene} zurückgegeben wird, leer ist.
Wenn dies der Fall ist, wird das \emph{Blatt-Modul} der entsprechenden
Seite aufgerufen, es entscheidet darüber, welches Programm der Bewertungebene
aufgerufen wird. Die Bewertungen der Blätter werden dann zurückgereicht. Dies wird für
alle Züge einer Zugliste durchgeführt und so entsprechend einer Baumsuche die Minima
oder Maxima der Blattbewertungen berechnet und an die nächste Ebene
weitergereicht.

Den GP-Programmen stehen verschiedenste Funktionen zur Verfügung um adequate
Programme für diese Ebene zu entwickeln, sie sind alle im
Abschnitt~\ref{sec:FunkVariantChessGP} zusammengefasst. Die zwei wichtigsten
Funktionen sind allerdings die \emph{exit}- und \emph{cut}-Funktion für das
Entscheidungs-Modul. Wenn  die \emph{exit}-Funktion ausgeführt wird, wird die
Rekursion abgebrochen und die Materialbewertung aufgerufen, weiterhin
erfolgt ein Abschneiden aller noch nicht bewerteten Züge in der Zugliste. Die
\emph{cut}-Funktion hat ein ähnliches Verhalten, jedoch ist die Auswirkung
 auf die Stellung beschränkt, alle weiteren Züge aus der Liste werden weiter
 bearbeitet.


Auch wenn zur Rückbewertung das Minimaxverfahren eingesetzt wird, so
unterscheidet sich die Suche von diesem Verfahren jedoch in den folgenden
Punkten:
\begin{itemize}
\item Es werden nicht alle legalen Züge betrachtet.
\item Das Entscheidungs-Modul bestimmt für jede Stellung einen eigenen
  Zuglistengenerator. Somit ändert sich das Verhalten der Suche in jeder Stellung.
\item Es findet keine konventionelle Stellungsbewertung statt, die für
  jedes Blatt dieselbe ist, sondern das Blatt-Modul entscheidet für jede
  Stellung, welche Bewertung sinnvoller ist.
\item Eine maximal erlaubte Suchtiefe wird nicht vorgegeben, es ist ein
  Attribut des Individuums, welches durch Mutation geändert werden kann.
\end{itemize}

%\begin{figure}
%   \centerline{\epsfig{figure=Pictures/Graphik/testBild.eps,width=11cm}}
%   \caption{Structure of a chess individual.}
%   \label{fig:chessIndLevelC}
%\end{figure}


Die Fitness der Individuen wurde mit Hilfe des Elo-Verfahrens bestimmt (siehe
Kapitel~\ref{sec:Elo}). Im Elo-System können Partien nur mit den Werten $0,
0,5$ und $1$ bewertet werden, also \emph{Verlust, Remis} und \emph{Gewinn}. Im
Gegensatz zur realen Schachpraxis, können im ChessGP-System aber alle Werte im
Intervall von $[0,1]$ angenommen werden. Dadurch wird die Bewertung
der Individuen beschleunigt, denn nun muss nicht bis zum Gewinn einer Seite
gespielt werden, sondern die Partie kann nach einer maximalen Anzahl von Zügen
beendet werden. Der Maximalwert für die Partielänge wurde auf 70 Halbzüge
festgelegt; falls zu diesem Zeitpunkt noch kein Gewinner feststeht, wird der
Materialwert als Bewertung genutzt. Eine Partie wird aber auch dann
abgebrochen, wenn eine Seite über mindestens vier Halbzüge eine \emph{große}
Materialüberlegenheit hat. Eine  \emph{große} Materialüberlegenheit von
Individuum $A$ zu Indivdium $B$ ist dann erreicht, wenn der Materialwert von
Individuum $A$ größer als zweimal dem Materialwert von Individuum $B$ ist und der
Materialwert von $A$ mindestens neun Bauerneinheiten entspricht, oder wenn der
Materialvorteil von $A$ größer als neun Bauerneinheiten ist. Dieses
Abbruchkriterium ist ausreichend, da Schachgroßmeister teilweise bei einem
Materialnachteil von einem Bauern kapitulieren.

%----------------------------------------------------------------------
\subsubsection{Datenstruktur}
%----------------------------------------------------------------------
\label{sec:ChessGPDatenstruktur}

Die Entwicklung einer \emph{Datenstruktur}\index{ChessGP!Datenstruktur} für die GP
Individuen war eines der wichtigsten Elemente  zur Lösung des
Schachproblems. Viele der Funktionen, die für die Schachindividuen entwickelt
wurden, haben verschiedene Eingabe- und Ausgabetypen, so brauchen einige
Funktionen eine Position des Bretts und andere Funktionen einer Figur oder
eine Zugliste. Alle Funktionen mit einer genaueren Beschreibung für die
ChessGP Anwendung finden sich im Kapitel~\ref{sec:FunktionenChessGP}.

Wenn keine Datenstrukturen eingeführt worden wären, hätte man alle Funktionen
so implementieren müssen, dass die entsprechenden Eingabe- und Ausgabewerte der
Funktionen den gleichen Typ haben, da kein grammatikalisches GP
verwendet wurde~\cite{oneill99geneticCode,oneill01crossoverIn}. 
Jedoch würde dies auch nicht alle Probleme
lösen, da viele Werte zwar den gleichen Typ, jedoch verschiedene
Bedeutungen besitzen. Der Semantik der Ein- und Ausgabewerte der Funktionen
sollte durch die Verwendung einer Datenstruktur eine größere Bedeutung
beigemessen werden. Dadurch sollte für das System die Komplexität zur
Erzeugung sinnvoller Programme reduziert werden, da nun die
Wahrscheinlichkeit, dass semantisch falsche Werte von den Funktionen genutzt
werden, stark herabgesetzt wird.

Ein anderer Aspekt der Datenstrukturen ist, dass in einem linearen Genom nun
parallele Programmflüsse auftreten können, da der Datenfluss parallel über die verschiedenen
Elemente der Datenstruktur läuft. Verschiedene Funktionen lassen die parallelen
Programmflüsse zusammenlaufen und andere trennen sie auf, so dass es zu einem
komplexen Programmablauf kommen kann.

Die Abbildung~\ref{fig:dataStructChessGP} zeigt die verschiedenen
Datenstrukturen für die einzelnen Ebenen der GP Individuen. Deutlich ist
hierbei die Komplexität der Datenstruktur für die Planungsebene zu erkennen,
die innerhalb der Datenstruktur ganze Zuglisten verwalten kann. Dies war
notwendig, da das Ergebnis dieser Ebene eine Zugliste war.
Die einfachste Datenstruktur hat die Variantenebene, sie hat einen Wert und zwei
Indizes für die Programme der Material- und Planungsebene.

\begin{wrapfigure}{r}{85mm}
%\begin{figure}
   \centerline{\epsfig{figure=Pictures/Graphik/chessGPDatenstruktur.eps,width=8.5cm}}
   \caption{Die Datenstrukturen der einzelnen Ebenen des GP Systems.}
   \label{fig:dataStructChessGP}
\end{wrapfigure}%{figure}


Die Datenstruktur der Materialebene ist ein Dreier-Tupel und besteht aus einer
Feld-, Figur- und Zahlenkomponente. Wichtig an dieser Datenstruktur ist eine
Besonderheit der Feldkomponente, sie speichert zwar ein Feld des Brettes als
Zahl zwischen 0 und 63, jedoch können einige Funktionen der Individuen diese auch
nur bezüglich des Zeilen- oder Reihenwertes verändern.

Die Datenstruktur der Planungsebene besteht aus drei Hauptkomponenten, von denen
zwei wieder aus Datenstrukturen bestehen. Die Zahlkomponente ist einfach eine
reelle Zahl, die für Berechnungen verwendet wird. Die Suchmaskenkomponente ist
wiederum ein Siebener-Tupel, das einen Zug beschreibt. Es besteht aus einem Startfeld,
einen Zielfeld, einer Zahl, einer Richtung, dem Figurtyp, der Figurfarbe und dem
Typ der geschlagenen Figur. Die letzte Komponente der Datenstruktur ist eine Zugliste,
in der jedes Element der Liste dem Siebener-Tupel der Suchmaskenkomponente entspricht.

Die Datenstruktur der Variantenebene ist auch ein Dreier-Tupel und besteht aus
einer Zahlenkomponente und jeweils einem Index für die Programme der Material- und
Planungsebene.

%Die Datenstrukturen ermöglichen zwar  Funktionen, deren Eingabewerte einer
%Semantik unterliegen, jedoch erhöhen sie auch gleichzeitig die Komplexität der
%Programme sehr stark. So muss die Evolution Individuen erzeugen, die die
%parallelen Programmflüsse innerhalb der Individuen sinnvoll nutzen können. Dies
%führt besonders bei den komplexeren Datenstrukturen zu einer Verlängerung des
%Lernprozesses. Neben diesen Problemen haben die Datenstrukuren aber auch das
%Potential der Individuen vergrößert und somit die Lösung des angestrebten
%Zieles möglich gemacht.



%----------------------------------------------------------------------
\subsubsection{Evolution}
%----------------------------------------------------------------------

Die Evolution\index{ChessGP!Evolution} des Chess-GP Systems teilt sich in
drei Evolutionen auf. Jede
hierarchische Ebene des Individuums durchlief eine eigene Evolution mit
unterschiedlichen Fitnesscases und unterschiedlichen Fitnessfunktionen.
Durch den hierarchischen Aufbau der Individuen konnten die Evolutionen der
einzelnen Ebenen aber nicht parallel durchgeführt werden, da ja die
hierarchisch höhere Ebene immer die evolvierten Individuen der tieferen Ebene
benötigt. Die Materialbewertungs- und Planungsebene bestehen aus mehreren
Individuen, die verschiedene Zielsetzungen verfolgen. Diese Individuen sind
nicht voneinander abhängig und können somit parallel evolviert werden.
Die Variantenebene besteht zwar auch aus vier Individuen, diese sind jedoch
eine Einheit und müssen innerhalb einer Evolution evolviert werden.
Da das Gesamtindividuum hierarchisch aufgebaut ist, ergibt sich eine
natürliche Reihenfolge für die Evolutionen der Ebenen.

Die Evolution eines schachspielenden Individuums in ChessGP beginnt mit der
Evolution der Materialbewertungsebenen. Hierzu wurde ein Lineares GP-System
verwendet, wobei eine Tunierselektion verwendet wurde. Die Individuen wurden
mit Beispielen verschiedener Stellungen trainiert. Da die einzelnen Individuen
für die verschiedenen Aspekte der Materialbewertungsebenen unabhängig voneinander
sind, kann die Evolution der acht verschiedenen
Materialbewertungsindividuen parallel ablaufen. Nachdem die Evolution
dieser Individuen abgeschlossen ist, kann die Evolution der Planungsebene
beginnen.% sie kann nicht parallel mit der Materialbewertungsebene durchgeführt
%werden.  da die Individuen der Planungsebene die der Materialbewerungsebene
%aufrufen können. 
%Würde man die Evolution der Individuen der Planungsebene ohne die
%Individuen der Materialbewertungsebene durchführen, was möglich wäre, da man
%zu diesem Zeitpunkt  mit festen Programmen arbeiten könnte, würde sich das
%Verhalten der Individuen der Planungsebene aber später im Gesamtindividuum
%verändern, da die Ergebnisse der evolvierten Materialbewertungsindividuen
%nicht mit denen der vorgegebenen Funktionen übereinstimmen muss. Daher kann 
%hier wie auch bei der Evolution der dritten Ebene, der Variantenebene,
%keine Parallelsierung genutzt werden.

Vor der Evolution der sieben verschiedenen Individuen der Planungsebene,
werden die besten Individuen der Materialbewertungsebene ausgewählt und jeder
Evolution der Planungsebene zur Verfügung gestellt. Auch hier wurde ein
linearer Individuentyp verwendet und eine Turnierselektion verwendet die
genauen Parameter der Evolution können im Abschnitt~\ref{sub:ChessGPPlan}
nach gelesen werden. Nach Abschluss der Evolution der Planungsebne
kann die Evolution der Variantenebene durchgeführt werden.

Der Unterschied der Evolution der Variantenebene zu den Evolutionen der beiden
hierarchisch untergeordneten Ebenen liegt in der Fitnessberechnung. Hier
 werden keine Fitnesscases genutzt, an denen die Individuen trainiert
werden, sondern es werden vollständige Schachspiele durchgeführt um die Fitness
der Individiuen zu bestimmen. Die Schachspiele werden zwischen den Individuen
durchgeführt, die während der Selektion ausgewählt werden.
Ergebnisse und Probleme bei diesem Vorgehen sind in
Kapitel~\ref{sub:ChessGPVariant} ausführlich beschreiben.


Im Abschnitt~\ref{sec:ChessGPResults} und in~\cite{kantschik:2000:TechRep}
sind alle Ergebnisse des Systems und seine Probleme vollständig beschreiben.



%----------------------------------------------------------------------
\subsection{qoopy}
%----------------------------------------------------------------------



Das \emph{qoopy-System}\index{qoopy} baut auf den Erfahrungen auf, die wir mit
\emph{ChessGP} gesammelt haben. Das Ziel war es hier, spielstärkere
Individuen zu evolvieren, somit haben wir uns näher an einen Alpha-Beta
Algorithmus gehalten und den Individuen nicht so viele Freiheiten gelassen wie
im ChessGP-System. Denn viele der möglichen Freiheiten wurden vom System
nicht genutzt. Außerdem führten sie zu einer sehr langsamen Evolution, da das
System durch die vielen Freiheitsgrade sehr lange brauchte sinnvolle Kombinationen
für ein Individuum zu erzeugen.
Der Rahmen des Individuums sollte daher ein Alpha-Beta
Algorithmus sein, der durch evolutionäre Verfahren verbessert werden sollte.
Eine weitere Vereinfachung der Schachindividuen ist die Evolution der
Individuen, anders als im ChessGP-System werden die Individuen hier in einem
Schritt evolviert und nicht in drei aufeinander folgenden Evolutionen.
Um diese zu ermöglichen, wird
die Fitness der Individuen nicht durch Fitnesscases bestimmt, sondern durch
vollständige Schachspiele gegen feste Schachprogramme verschiedenster
Leistungsstufen, wodurch die Spielstärke der Individuen bestimmt werden konnte.
Ergebnisse zu diesem System
wurden in~\cite{kantschik:2002:gecco} veröffentlicht.


%----------------------------------------------------------------------
\subsubsection{Das Schachindividuum}
%----------------------------------------------------------------------
\label{sec:qoopy-Ind}

Im \emph{qoopy-System} wurde ein Alpha-Beta Algorithmus~\cite{schae89,iida95a} als
Kern eines Schachindividuums genutzt. Dieser Kernalgorithmus wurde durch GP-
und EA-Module erweitert. Der Alpha-Beta Algorithums ist eine Heuristik, die für
das Schachspiel erfolgreich im Mittelspiel verwendet wird. Der Algorithmus
kann drei verschiedene Module nutzen, die über schachspezifisches Wissen verfügen.
Das Stellungsbewertungsmodul wird genutzt, um eine erreichte
Stellung zu bewerten. Diese Bewertung geht dann in die Alpha- und Beta-Werte
ein und ermöglicht das Schneiden des Baumes.
Eine weiteres Modul vieler Schachprogramme ist die
Zugsortierung~\cite{greer99,grimbergen00e,althofer97b}, sie ermöglicht es dem Alpha-Beta
Algorithmus gute Züge zuerst zu expandieren, was zu einer Verkleinerung des
Suchbaumes führt (siehe auch Abschnitte~\ref{sec:alphaBeta} und~\ref{sec:Zugbewertung}).
Ein weiterer wichtiger Punkt für Schachprogramme ist die Beschränkung des
Suchhorizontes~\cite{beal99d,birmingham77}. Normalerweise werden Programme
dadurch beschränkt, dass ihnen eine maximale Suchtiefe erlaubt wird, die
Anzahl der Knoten im Suchbaum hängt dann von der Spielsituation und dem
Algorithum ab.

Im Fall des \emph{qoopy-Systems} wurde die Suchtiefe zwar
beschränkt, jedoch nur um es den Individuen während der Evolution unmöglich
zu machen, 50 oder mehr Züge in die Zukunft zu schauen, was auch keinen Sinn
macht, da eine Partie in der Regel dann schon beendet ist. Die Beschränkung
der Suchtiefe schränkt das Individuum nicht in der Rechenkraft ein, bei einer
maximale Suchtiefe von 10 kann das Individuum immer noch
10 Billiarden Knoten expandieren. Um die
Rechenkraft der Individuen im qoopy-System zu beschränkten, wurde die Anzahl der
im Suchbaum zu expandierenden Knoten für ein Individuum auf 100.000 Knoten im
Durchschnitt beschränkt. Für diese Entscheidung
sprachen die folgenden Gründe:
\begin{itemize}
\item Die Beschränkung ermöglicht eine akzeptable Evolutionsgeschwindigkeit, denn für die
  Fitnessberechnung eines Individuums müssen mehrere Spiele durchgeführt
  werden.
\item Programme, die 100.000 Knoten expandieren haben schon eine akzeptable Spielstärke.
\end{itemize}

%Der Alpha-Beta Algorithmus der auch eine Baumsuche~\cite{iida95a} ist stellt den
%Rahmen eines Individuum im qoopy-System dar.
%Dieser wird durch drei Module erweitert, so dass die Individuen analog zu
%einem Alpha-Beta Algorithmus arbeitet können. Das heißt es ist ihnen möglich
%den Suchbaum aufzubauen und zu beschneiden. Zur Erweiterung werden dem Individuum
%drei Module zur Verfügung gestellt die Mittels evolutionären Verfahren entwickelt werden.
%\begin{itemize}
%\item Das Tiefenmodul, es berechnete die verbleibende Suchtiefe für den
%  aktuellen Knoten.
%\item Das Zugsortierungsmodul, gewichtete die einzelnen Züge für die aktuelle
%  Stellung und sortiert sie entsprechend der Güte.
%\item Das Stellungsbewertungsmodul, berechnet die Güte einer gegebene Stellung.
%\end{itemize}

Die Evaluation des Schachindividuums erfolgt nach folgendem Schema.
Zuerst wird das Tiefenmodul für die aktuelle Stellung aufgerufen, es berechnet
die verbleibende Suchtiefe für die Stellung im Suchbaum. Wenn die Suchtiefe
Null ist, wird die Stellung als ein Blatt interpretiert und das
Stellungsbewertungsmodul wird aufgerufen. Der Wert der Berechnung wird nun der
Stellung zugeordnet und während der Ausführung des Rahmenprogrammes genutzt.
So wird dieser Wert für die $\alpha-$ und $\beta-$ Schnitte im Algorithmus
genutzt und ob ein Zug in der Killertabelle aufgenommen wird oder nicht.
(Zur Funktionsweise der Killertabellen siehe
Abschnitt~\ref{sub:KillerMove}.)
Wenn das Tiefenmodul eine Tiefe größer als Null berechnet hat,  wird die
nächste Ebene im Suchbaum geöffnet. Dazu werden durch das Rahmenprogramm alle
Züge der aktuellen Stellung zur Verfügung gestellt, dann wird jeder
mögliche Zug durch das Zugsortierungsmodul bewertet und anschließend 
die Zugliste nach ihrer Güte durch das Rahmenprogramm sortiert.

Für jede Stellung der Zugliste wird das Programm rekursiv wieder aufgerufen.
Wenn die maximale Anzahl von Knoten erreicht wurde, wird für die noch nicht
ausgewerteten Stellungen jeweils das Positionsmodul aufgerufen,  die Bewertung durch
den Spielbaum an die Wurzel propagiert und dort der \emph{Beste Zug}
zurückgegeben. Der Pseudocode~\ref{tab:qoopyRahmen} verdeutlicht noch einmal
das Vorgehen des Rahmenprogrammes, hier wurde der \emph{Max}-Teil des
Algorithmus aufgeschrieben, der \emph{Min}-Teil des Schachindividuums
funktioniert analog (Zur Aufteilung eines Schachalgorithmuses in Max- und
Min-Algorithmen siehe Abschnitte~\ref{sub:MiniMax} und  \ref{sec:alphaBeta}).

\begin{table}
\begin{center}
\begin{tabular}{rp{12cm}}
  1 & $ind_{MAX}$ (position $K$; integer$\alpha, \beta$)  \\
  2 & \texttt{BEGIN}  \\
  3 & \hspace{0.2cm} integer $i, j, value$ ;\\
  4 & \hspace{0.2cm} $nodes= nodes + 1;$ \\
  5 & \hspace{0.2cm} \texttt{IF} \textbf{Positionsmodue}($K$) \texttt{THEN} \\
    & \hspace{0.3cm} \texttt{RETURN} \textbf{Positionsmodul}($K$); \\
  6 & \hspace{0.2cm} \texttt{IF} $(depth$ == $maxdepth)$ \texttt{THEN} \\
    & \hspace{0.3cm} \texttt{RETURN} \textbf{Positionsmodul}($K$);  \\
  7 & \hspace{0.2cm} \textbf{Tiefenmodul} restdepth;\\
  8 & \hspace{0.2cm} \texttt{IF} $(((restdepth$ == $0)$ OR \\
    & \hspace{0.3cm} $(nodes$ $>$ $maxnodes))$ \\
    & \hspace{0.3cm} AND $depth >$= $mindepth$)  \texttt{THEN}\\
  9 & \hspace{0.4cm} \texttt{RETURN} \textbf{Positionsmodul}($K$); \\
 10 & \hspace{0.2cm} determine successor positions $K.1, \ldots, K.w$;\\
 11 & \hspace{0.2cm} \textbf{Zugsortireungsmodul}($K.1, \ldots, K.w$);\\
 12 & \hspace{0.2cm} $value= \alpha$;\\
 13 & \hspace{0.2cm} \texttt{FOR} $j= 1$ \texttt{TO} $w$ \texttt{DO}\\
 14 & \hspace{0.2cm} \texttt{BEGIN}\\
 15 & \hspace{0.2cm} \hspace{0.2cm}  $restdepthBackup$ = $restdepth$;
  \\
    & \hspace{0.2cm} \hspace{0.2cm} $restdepth$--;\\
 16 & \hspace{0.2cm} \hspace{0.2cm} $value$= $\max(value, inf_{MIN}(K.j,value,\beta))$;\\
 17 & \hspace{0.2cm} \hspace{0.2cm}  $restdepth$= $restdepthBackup$\\
 18 & \hspace{0.2cm} \hspace{0.2cm}  \texttt{IF} $value \geq \beta$ \texttt{THEN} \\
    & \hspace{0.2cm} \hspace{0.3cm} \{ ADJUST KILLERTABLE; \\
    & \hspace{0.2cm} \hspace{0.3cm} \texttt{RETURN} $value$\}; \\
 19 & \hspace{0.2cm}  \texttt{END} \\
 20 & \hspace{0.2cm}  \texttt{RETURN} $value$ \\
 21 & \texttt{END}    \\
\end{tabular}
\end{center}
\caption{Der Pseudocode beschreibt den Rahmenalgorithmus für das
  Schachindividuum. Es ist der Max-Teil des Algorithumses, die evolutionären
  Module im Algorithmus sind fett gedruckt.}
\label{tab:qoopyRahmen}
\end{table}


%----------------------------------------------------------------------
\subsubsection{Das Stellungsmodul}
%----------------------------------------------------------------------
\label{sec:qoopySellung}

Das \emph{Stellungsmodul}\index{qoopy!Stellungsmodul} bewertet eine gegebene
Stellung, es handelt sich
dabei um eine Materialbewertung, wie sie auch in
Kapitel~\ref{sec:MaterialBewertung} beschrieben wird.
Die Aufgabe dieses Moduls ist es, einen besseren Parametersatz für den
Stellungsbewertungsalgorithmus zu finden. Die Werte, die normalerweise in
solchen Algorithmen verwendet werden, gehen auf die Erfahrung des
Programmierers oder auf die Literatur zurück, wobei hier immer noch Werte zu
finden sind, die schon Shannon\footnote{Shannon hat schon 1950 einen Artikel
über den Aufbau von Schachprogrammen geschrieben, seine
Vorstellungen sind bis heute in fast allen Programmen wiederzufinden.} für die
Bewertung von Schachpositionen eingeführt hat.

Das Stellungsmodul im qoopy System ist kein GP-Individuum, sondern ein fest
vorgegebener Algorithmus, der die Stellung anhand von evolvierten Werten für
die verschiedenen Figuren und strukturellen Elemente bewertet. Hierzu wird eine
einfache $(\mu+\lambda)$ Evolutionsstrategie mit fester Mutationsschrittweite
verwendet~\cite{schwefel1}. Die Initialisierung der Vektoren war zufällig,
jedoch wurden die Werte durch Intervalle begrenzt, die den einzelnen
Merkmalen entsprachen, die Zuordnung der Intervalle zu den einzelnen Merkmalen
werden weiter unten beschrieben. Bei der Rekombination wurden zwei Techniken genutzt.
 Zum einen
die intermediäre Rekombination, bei der die reellen Zahlen, die zu denselbem
Merkmalen gehören, gemittelt werden. Dabei ist die Wahrscheinlichkeit, dass
ein bestimmtes Merkmal variiert wird, vom Benutzer einstellbar. Die zweite
Möglichkeit ist die diskrete Rekombination, bei der sich eine Ausprägung des
Merkmals durchsetzt.


Die Evolutionsstrategie soll Werte für die folgenden Merkmale der
Stellungsbewertung optimieren:
\begin{enumerate}
\item  die Werte für die einzelnen Figurtypen [0-1000]
\item  einen Bestrafungswert für einen Läufer in der Anfangsposition [0-30]
\item  ein Bonus für einen Bauern, der das Zentrum des Schachbrettes erreicht hat [0-30]
\item  eine Bestrafung, wenn zwei Bauern auf der gleichen Linie stehen [0-30]
\item  ein Bonus für einen Bauern, der auf beiden Nachbarlinien keinen
        gegnerischen Bauern hat [0-40]
\item  eine Bestrafung für einen Bauern, der keinen Bauern auf den Nachbarlinien
        hat, der näher an der ersten Reihe des Gegners ist [0-30]
\item  ein Bonus für einen Freibauern, der durch einen Turm beschützt wird [0-30]
\item  ein Bonus für einen Bauern, wenn er in der Nähe der ersten Reihe des Gegners
        ist (Promotionsmöglichkeit) [100-500]
\item  ein Bonus, wenn beide Läufer vorhanden sind [0-40]
\item  eine Bestrafung für einen Läufer, der sich in der Startposition aufhält
  [0-30]
\item  eine Bestrafung für Läufer in einer blockierten Stellung. Eine blockierte
  Stellung ist in diesem Zusammenhang eine Stellung, in der drei eigene Bauern
  sich im Bereich des erweiterten Zentrums befinden und Felder besetzen, die
  die gleiche Farbe haben wie die Felder auf denen sich der Läufer bewegt
  [0-40]
\item  ein Bonus für den Springer, wenn es sich um eine blockierte Stellung
  handelt. Für einen Springer handelt es sich um eine blockierte Stellung,
  wenn sich mehr als sechs Bauern im erweiterten Zentrum aufhalten. Durch die
  Fortbewegungsweise des Springers wird er aufgewertet [0-50]
\item  ein Bonus für den Springer, wenn er mehr als sechs Felder erreichen kann [0-30]
\item  ein Bonus für den Springer in einer geschlossenen Position [0-40]
\item  eine Bestrafung, wenn auf jeder Seite des Springers ein generischer Bauer steht
  [0-50]
\item  ein Bonus für den Turm, falls er von dem anderen Turm gedeckt wird [0-20]
\item  ein Bonus für den Turm, wenn er auf einer halboffenen Linie steht [0-30]
\item  ein Bonus für den Turm, wenn er auf einer offenen Linie steht [0-30]
\item  ein Bonus für den Turm für andere Vorteile [0-20]
\item  eine Bestrafung für den König, wenn er die erste Reihe während des
        Eröffnungs- oder Mittelspiels verlässt [0-20]
\item  ein Bonus, nachdem eine Rochade ausgeführt wurde [0-40]
\item  eine Bestrafung für die Rochade, wenn es eine Schwäche in der Bauernstruktur
        vor dem König gibt [0-30]
\item  eine Bestrafung, wenn die Möglichkeit einer Rochade vergeben wurde [0-50]
\item  ein Zufallswert, der zum Wert der Stellung addiert oder subtrahiert wird [0-30]
\end{enumerate} 

Die Werte in den Klammern geben die Intervalle an, in denen sich die Werte
für die Merkmale bewegen können. Diese Intervalle wurden vorgegeben, damit der 
Stellungsbewertungsalgorithmus schon mit zufälligen Werten noch relativ
sinnvolle Bewertungen errechnet. Denn durch die verteilte Evolution, wie sie
in Abschnitt~\ref{sec:EvoQoopy} beschrieben wird, werden viele kleine Demes
verwendet, so dass es sehr lange dauern würde, bis sich gute Parameter in der
gesamten Population durchgesetzt hätten. Dies würde die Attraktivität des
Systems für die Nutzer, die uns ihre Rechenkraft zur Verfügung stellen, senken.
Daher sahen wir darin eine Gefahr wieder schnell einige Nutzer zu verlieren, wenn
\emph{ihre} Evolutionen geringere Fortschritte machen würden als die der anderen
Nutzer.

Der Algorithmus summiert alle Figurwerte und die Boni, die für die
Stellung zutreffend sind auf, anschließend werden alle Bestrafungswerte subtrahiert, die
durch die Stellung erfüllt werden. Die Bonuswerte und die Bestrafungswerte
sind für die strukturelle Untersuchung der Stellung verantwortlich. Hier ist
auch die stärkste Einschränkung durch die vordefinierten Intervalle zu
erkennen, denn diese Werte können zwar den Wert der reinen Materialbewertung vergrößern
oder verringern, jedoch nicht den Verlust starker Materialwerte
ausgleichen. Dieses Vorgehen ist auch sinnvoll, denn selbst Großmeister bewerten den
Materialwert höher als die Struktur der Stellung (siehe auch~\cite{berliner:99}).

Dieser Algorithmus zur Stellungsbewertung wurde auch von den Gegnerprogrammen
während der Fitnessevaluation genutzt, jedoch wurden bei diesen die Werte für
die Gewichtung vorher festgelegt und während der gesamten Auswertung nicht
verändert (siehe Abschnitt~\ref{sub:black}). Die Werte wurden hierbei mit Hilfe
von Schachexperten bestimmt und durch Tests überprüft.

%----------------------------------------------------------------------
\subsubsection{Das Zugsortierungsmodul}
%----------------------------------------------------------------------
\label{sub:QoopySortmodul}

Das \emph{Zugsortierungsmodul}\index{qoopy!Zugsortierungsmodul} hat die
Aufgabe die möglichen Züge der aktuell betrachteten Stellung so zu gewichten,
dass eine Sortierung der Züge nach ihrer Güte möglich ist (siehe
auch~\ref{sec:Zugbewertung}). Die Sortierung der Züge erfolgt nach der
Bewertung jedes Zugs durch einen Quicksort Algorithmus. Nachdem diese Schritte
durchgeführt wurden, werden die Züge in der neuen Reihenfolge
expandiert. Wenn der Algorithmus über eine gute Zugsortierung verfügt, ist es
möglich die Anzahl der Knoten, die bei der Suche expandiert werden, stark
einzuschränken. Denn werden bei der Alpha-Beta Suche zuerst die besten
Züge\footnote{beste Züge im Sinne des Minimax-Prinzips} betrachtet, können die
weiteren Züge mit einem stark eingeschränkten Suchfenster ohne qualitative
Einbuße bearbeitet werden, dies führt zu einer stärkeren Beschneidung des
Suchbaumes(siehe~\cite{heinz00,slag69,schae89}). So expandieren selbst die
spielstärksten Schachprogramme 20-30\% mehr Knoten, als der optimale Suchbaum
expandieren würde. Eine Verbesserung der Zugsortierung könnte somit eine starke
Reduktion in der Größe des Suchbaums bedeuten.

Die Bewertung des Zugsortierungsmoduls ist unabhängig davon, ob ein Zug von der
schwarzen oder weißen Seite durchgeführt wird. Jedem Zug wird eine reelle Zahl 
zugewiesen und
anschließend absteigend sortiert. Die Güte des Zuges ergibt sich aus der Summe der
Merkmale, die der Zug erfüllt. Der Algorithmus untersucht die folgenden
Merkmale für jeden Zug:
\begin{itemize}
\item Werte, die den einzelnen Schachfiguren während der Eröffnungsphase
  zugeordnet werden
\item Werte, die den einzelnen Schachfiguren während des Mittelspiels
  zugeordnet werden
\item Werte, die den einzelnen Schachfiguren während des Endspiels
  zugeordnet werden
\item Schlagzüge versus nicht schlagende Züge:\\
  Schlagzüge bekommen ein
  anderes Gewicht beigemessen als solche Züge, die keine Figur schlagen.
\item Schachzüge:\\
  Züge, die den gegnerischen König ins Schach stellen,
  bekommen einen extra Bonus zugestanden.
\item MVV/LVA (Most valuable victim/Least valuable aggressor):\\
  Dieser Wert ist das Verhältnis der Materialwerte der geschlagenen Figuren zu
  den schlagenden Figuren.
\item Promotion: \\
	 Züge, die einen Bauern umwandeln, bekommen einen Bonus,
  jedoch nur, wenn zu einer Dame gewandelt wird. Dies wird gemacht, da es sich
  hier nur um eine Zugsortierung handelt, so kann sich in der Suche noch
  herausstellen, dass die Umwandlung in eine andere Figur ratsamer ist.
\item Zentrumsaktivität:\\
  Durch diese Merkmale wird dem Zug direkt ein Bonus zugesprochen, dabei hängt
  dieser nur vom Start- und Zielfeld des Zuges ab. Der Bonus ist die Summe des
  Bonus für das Zielfeld und der Hälfte des Bonus des Startfeldes. Die Boni
  der Felder ergeben sich durch die folgende Matrix:
  \newpage
  \centerline{ 0 0 0 0 0 0 0 0 }
  \centerline{ 0 1 1 1 1 1 1 0 }
  \centerline{ 0 1 2 2 2 2 1 0 }
  \centerline{ 0 1 2 3 3 2 1 0 }
  \centerline{ 0 1 2 3 3 2 1 0 }
  \centerline{ 0 1 2 2 2 2 1 0 }
  \centerline{ 0 1 1 1 1 1 1 0 }
  \centerline{ 0 0 0 0 0 0 0 0 }
\item Bauernzüge:\\
  Bauernzüge, die eine gegnerische Figur bedrohen, erhalten einen Bonus.
\item Killermoves\index{Killermove}:\\
  Killermoves sind Züge, die in einer früheren Situation zu einem Abschneiden
  eines Teiles des Suchbaumes geführt haben. Sie sind oft auch in anderen
  Situationen vorteilhaft, daher werden sie in einer sogenannten \emph{Killer 
  Table} gespeichert. Es werden maximal 4 Züge pro Ebene des Suchbaumes gespeichert.
\end{itemize}

Der Zusortierungsalgorithmus untersucht sowohl statische Elemente der Stellung
als auch, durch die Killermoves und die Art des Zuges, dynamische Aspekte des
Zuges. Die Bewertung des Zuges hängt aber kaum von der vorherigen Suche ab,
dies kann nur durch die Killermoves geschehen, somit kann sich der Wert des
gleichen Zuges in verschiedenen Spielen leicht unterscheiden, dies ist jedoch
kein Problem, da die Zugsortierung nur zur Unterstützung beim Aufbau des
Suchbaumes genutzt wird.

Um die Werte für die einzelnen Merkmale zu erhalten, wird ein
 $(\mu+\lambda)$ Evolutionsstrategie mit fester
Mutationsschrittweite benutzt, wie sie auch schon beim Stellungsmodul verwendet wird. 
Es wurde keine ES mit einer Anpassung der Mutationsschrittweite genutzt, da man im allgemeinen
nicht von der Spielstärke eines Individuums auf die Güte des
Zugsortierungsmoduls oder des Stellungsmoduls schließen kann (siehe~\cite{schwefel1}).
Daher ist eine Anpassung der Mutation durch die Fitness des Gesamtindividuums, als
problematisch anzusehen und wurde daher nicht verwendet.

Bei der Mutation und der Rekombination kommen die gleichen Techniken zum
Einsatz, wie sie für das Stellungsmodul eingesetzt wurden, also die
intermediäre und die diskrete Rekombination. Bei der Mutation wird jedes
Merkmal mit einer Wahrscheinlichkeit mutiert, die durch den Benutzer vorgebenen wurde.



%---------------------------------------------------------------------- 
\subsubsection{Das Tiefenmodul}
%----------------------------------------------------------------------
\label{sub:QoopyTiefenmodul}

Das \emph{Tiefenmodul}\index{qoopy!Tiefenmodul} entscheidet für jede Position,
ob die verbleibende Suchtiefe
verringert, vergrößert oder nicht verändert wird. Diese Entscheidung wird
nicht direkt getroffen, sondern indirekt über die \emph{Restsuchtiefe} für jeden Knoten
bestimmt. Die
Restsuchtiefe wird im Pseudocode durch die Variable $restdepth$ bezeichnet,
dort erkennt man auch, dass sie automatisch für jede Ebene des Suchbaumes um
eins reduziert wird. Die Restsuchtiefe wird zu Beginn mit zwei initialisiert, dies soll
die Evolution vereinfachen, denn dadurch werden auch Schachindividuen, die das
Tiefenmodul nicht verwenden, mindestens einen Suchbaum der Tiefe zwei aufbauen
können. Dies wurde aus zwei Gründen gemacht, der erste liegt in der
internetbasierten Evolution begründet (siehe hierzu
Abschnitt~\ref{sec:EvoQoopy}). Der zweite Grund bezieht sich auf das Stellungsmodul und
das Zugsortierungsmodul, die sich so auch bei einem nicht aktiven Tiefenmodul in
der Evolution weiterentwickeln können, da das Individuum mindestens die Suchtiefe
zwei erreicht. Dies ist besonders zu Beginn der Evolution hilfreich, da so die
Diversität des Demes nicht so schnell erodiert.

Das Tiefenmodul hat die Aufgabe dem Schachindividuum die Möglichkeit zu
geben einen variablen Suchhorizont zu erzeugen. Normalerweise haben
Schachprogramme einen festen Suchhorizont~\cite{plaat96research}. Das heißt, ein
Programm darf maximal eine vorgegebene Anzahl von Ebenen im Suchbaum
expandieren; wenn die maximale Tiefe erreicht wird, wird die Suche beendet und
alle Knoten wie Blätter behandelt. Hierdurch ergeben sich Probleme, die auch
als Horizonteffekt\index{Horizonteffekt} bekannt sind~\cite{Kaindl:89,berliner:74}.

Da das Tiefenmodul durch einen evolutionären Prozess entwickelt wird, gibt es
zwei Parameter um die Rechenzeit eines Individuums zu beschränken. Die erste
Schranke ist die Suchtiefe, die Maximaltiefe für die Individuen ist zehn.
Diese sind ungefähr  $10^{14}$ Knoten im Suchbaum, der expandierte
Suchbaums der Tiefe zehn, mit einen guten Alpha-Beta Algorithmus, hätte immer noch 512
Millionen Knoten. Dies ist für einen evolutionären Prozeß zu viel, denn bis
die Fitness eines Individuums feststeht, müssen mehrere Spiele durchgeführt
werden, hierbei würde die Auswertung eines Spiels aber im Stundenbereich
liegen. Daher wurde noch eine zweite Beschränkung eingefügt, sie beschränkt die
Anzahl der Knoten im Suchbaum auf 100.000. Ein Individuum darf im
Durchschnitt 100.000 Knoten pro Zug verwenden, das heißt, wenn es im x-ten Zug
50.000 Knoten verwendet hat, so darf es im nächsten Zug 150.000 Knoten
verwenden. Dadurch kann die vollständige Fitnessauswertung eines Individuums
innerhalb einiger Stunden durchgeführt werden.

Die Aufgabe des Tiefenmoduls ist es, anhand der gegebenen Stellung zu
entscheiden, ob der mögliche Teilbaum genauer untersucht werden soll oder
nicht. Diese Aufgabe kann man nicht durch einen evolutionären Algorithmus
lösen, daher wurde an dieser Stelle ein GP-Programm verwendet.
Als Struktur für das GP-Programm wurde die Linear-Graph Struktur verwendet
(siehe~\ref{sub:LinGraph}). Das Funktionsset für dieses Modul wurde sehr
einfach gehalten, die schachspezifischen Funktionen sind in das Terminalset
eingegangen, eine genaue Auflistung ist im Anhang~\ref{sec:FunktionenQoopy}.

Das Tiefenmodul definiert die Suchtiefe für einen Knoten nicht direkt,
sondern verändert wie schon gesagt eine Variable (\emph{Resttiefe}), die angibt, 
wieweit die Suche für diesen
Ast noch weitergeführt werden soll. Um die Variable, welche die Suchtiefe
enthält, verändern zu können stehen dem GP-Individuum zwei Terminalfunktionen
zur Verfügung. Die Funktion \emph{incHorizon} erhöht den Wert der Resttiefe um
eins und die Funktion \emph{decHorizon} verringert den Wert um eins.
Die Funktionen können im Individuum mehrfach ausgeführt werden und sie können
auch beide nacheinander ausgeführt werden. Letzteres hat den Effekt, dass
diese Befehlsfolge ein sematisches Intron ist, da der Wert der Variable
Resttiefe sowohl mit als auch ohne diese Befehlsfolge die gleiche ist.
Eine Einschränkung dieser Funktionen gibt es, die Resttiefe kann durch die
Funktion \emph{decHorizon} nicht kleiner null werden. Durch die Funktion
\emph{incHorizon} kann der Wert von der Resttiefe aber auch nicht zu groß werden,
diese Einschränkung wurde gemacht, damit ein Individuum gezwungen wird nicht
nur in der Tiefe zu suchen, sondern auch in der Breite. Werden diese beiden
Funktionen im Tiefenmodul nicht aufgerufen, wird der Wert der Variable
Resttiefe automatisch um eins reduziert. Der Wert der Variable Resttiefe wird
zu Beginn der Auswertung des Tiefenmoduls mit zwei initialisiert. Dadurch
wird erreicht, dass das Gesamtindividuum mindestens einen Suchbaum der Tiefe
zwei aufspannt, selbst wenn das Tiefenmodul die Variable Resttiefe nicht
verändert. 
%Dies wird gemacht, da die Schachindividuen aus drei Modulen
%bestehen und somit die anderen beiden Module noch eine Möglichkeit haben ihr
%Genetisches Material weiterzugeben.


Wie schon oben erwähnt, besteht das GP-Programms aus der
Linear-Graph Struktur (siehe~\ref{sub:LinGraph}). Die
Branchingfunktionen in der Graphstruktur wurden durch schachspezifische
Funktionen ersetzt und sie überwachen nicht das Ausgaberegister wie bei den Tests
mit den Benchmarks. Dies würde für das Tiefenmodul auch wenig Sinn machen, da
es kein Ausgaberegister im engeren Sinn gibt, denn die Ausgabe des Moduls ist
die Veränderung oder Nichtveränderung der Resttiefe. Die Variable wird aber
nicht durch ein Ausgaberegister verändert, sondern durch den Seiteneffekt
zweier Terminalfunktionen.

Eine weitere Änderung für diese Anwendung war ein vermehrter Einsatz von
\emph{if-then} oder \emph{if-then-else} Funktionen. Normalerwiese werden
\emph{if-then} Funktionen in linearen Individuen wie normale Funktionen
behandelt, hier wurde aber eine erhöhte Wahrscheinlichkeit für diese Funktionen
verwendet. Dies führt somit auch zum Einsatz spezieller Terminalfunktionen, die
für die Bedingung in den \emph{if-then} Funktionen entwickelt wurden.
Im Abschnitt~\ref{sec:FunktionenQoopy} sind die verschiedenen Funktionen und
ihre Funktion genauer beschrieben, grundsätzlich handelt es sich aber um
Funktionen mit Schachwissen.


Zur Mutation wurde im Unterschied zu den im Abschnitt~\ref{sub:LinGraphMut}
beschriebenen Verfahren noch eine weitere Methode eingesetzt. Dabei wurde ein
Crossover mit einem Zufallsindividuum durchgeführt. Jedoch ist diese Methode
vergleichbar mit der Mutation einer ganzen Sequenz von Knoten im
Individuum. Daher wurde diese Methode auch nicht in diesem Kapitel
beschreiben. Ein  Nachteil dieser Methode ist, dass ein sehr großer
Anteil des Individuums verändert wird und sie somit besonders in späteren
Generationen hauptsächlich destruktiver Natur ist. Es wurde jedoch wegen 
der kleinen Populationen genutzt, die während der Evolution
verwendet wurden. Somit soll einem zu schnellen Absinken der Diversität entgegengewirkt
werden (hierzu siehe Abschnitt~\ref{sec:EvoQoopy}).



%----------------------------------------------------------------------
\subsubsection{Evolution}
%----------------------------------------------------------------------
\label{sec:EvoQoopy}

Die Evolution\index{qoopy!Evolution} des qoopy-Systems ist parallelisiert, da
durch den großen Rechenzeitbedarf während der Evolution eine Auswertung mit
nur einem Rechnern zu lange dauern würde. Die Parallelisierung ist jedoch
nicht auf eine Auslagerung der Fitnessberechnung auf weitere Computer
beschränkt, wie sie im ChessGP-System durchgeführt wurde. Im
qoopy-System wird sie durch eine Aufteilung in Teilpopulationen erreicht.

Für das \emph{qoopy-System} wurde der Ansatz des \emph{verteilten
 Rechnens}\index{verteiltes Rechenen} verwendet, um die Parallelisierung zu
erreichen (siehe~\cite{book:disComp1,book:disComp2}). Im Fall des
qoopy-Systems kann man das verteilte Rechnen als ein zentralisiertes
P2P-System betrachten, bei dem ein zentraler Server \emph{Aufgaben} an
registrierte \emph{Clients} verteilt und die Ergebnisse der dort erfolgten
Berechnung zu einem späteren Zeitpunkt wieder erfasst und weiterverwendet.
Der Server speichert unter anderem eine Liste der besten Individuen der gesamten
 Evolution, damit sie später von uns genauer analysiert werden können.
Durch diesen Ansatz ist es möglich die Aufgabe auf verschiedenste Rechner im
Internet zu verteilen und somit sehr viel Rechenkraft zur Verfügung gestellt
zu bekommen. Ein sehr bekannter Ansatz für das verteilte Rechnen ist das
\emph{SETI@home} Projekt, bei dem Radiosignale nach Mustern  außerirdischen
Ursprungs durchsucht werden.
Um den Teilnehmern an dem qoopy-System einen Anreiz zu bieten bei der
Evolution mitzumachen, wurde wie schon oben gesagt nicht nur eine
Fitnessberechnung an die \emph{Clients} weitergegeben, sondern eine gesamte
Teilpopulation. Die Tielnehmer konnten verschiedene Parameter der Evolution
\emph{ihrer} Teilpopulation verändern, so sollte eine Bindung zu dem Ergebnis
ihrer Evolution  aufgebaut werden. Die Teilnehmer der
internetweiten Evolution konnten
neben der Populationsgröße auch die Größe der Individuen und verschiedene
Einstellungen zur Evolution wie Crossover, Mutation, Migrationsraten und
andere Parameter einstellen. 

Die besten Individuen der Populationen wurden dann zum
Server geschickt und an andere Subpopulationen weitergegeben, um so eine Migration
der besten Gene durch die Gesamtpopulation zu ermöglichen. Gleichzeitig wurden beim
Server Information über die besten Individuen jedes Clients und der zur
Verfügung gestellten Rechenzeit erfasst und auf Internetseiten für alle
transparent dargestellt.

Dieses Vorgehen erreichte, wie von uns erhofft, eine starke Bindung der Teilnehmer an
das Projekt und eine große und stabile Anzahl von Teilnehmern (mehr als 1600). Ein großer
Nachteil war jedoch der geringe Einfluss, den wir auf die Evolution hatten.
So konnten wir nicht mehrere Läufe durchführen, um so die Auswirkung verschiedener
Parameter zu erkennen.

Die Defaultgröße einer Teilpopulation beträgt 20 Individuen, der Teilnehmer
hat zwei Möglichkeiten eine Population zu initialisieren. Er konnte alle
Individuen zufällig initialisieren oder Individuen aus anderen Populationen
zu Initialisierung nutzen. Anschließend beginnt die Berechnung der Fitness der
Individuen, die Fitness ist dabei in fünfzehn disjunkte Fitnessklassen
eingeteilt, allerdings ist als Fitness jeder Wert von $0,0$ bis $15,0$
möglich. In Abschnitt~\ref{sec:qoopyFit} wird die Fitness der Individuen
genauer beschrieben. Einem neuen Individuum wird die Fitness $1,0$ zugewiesen,
der beste Fitnesswert im System ist $15,0$. Um die exakte Fitness eines
Individuums zu bestimmen müssen eine gewisse Anzahl von Spielen gegen
Schachalgorithmen bekannter Stärke durchgeführt werden. Dadurch benötigt die
Fitnessberechnung für ein Individuum sehr lange, damit es aber schon während
der Fitnessberechnung zur Evolution neuer Individuen kommen kann, werden die
Individuen in drei Reifeklassen eingeteilt.
\begin{itemize}
\item Individuen werden als \emph{normal} bezeichnet, wenn die Bewertung der
  Individuen noch nicht abgeschlossen ist. Individuen dieser Klasse können
  nicht ersetzt werden, aber auch nicht bei der Mutation und Rekombination
  herangezogen werden.
\item Individuen werden als \emph{reif} bezeichnet, wenn sie bei der Mutation
  und Rekombination als Eltern herangezogen werden dürfen. Sie können aber
  nicht überschrieben werden, da die Fitness noch nicht endgültig bewertet
  ist. Wann ein Individuum als reif bezeichnet wird, kann vom Benutzer
  eingestellt werden, als Defaultwert wurde die Fitness $5,0$ verwendet.
\item Die letzte Klasse ist \emph{fertig}, ab dieser Stufe ist die
  Fitnessbewertung des Individuums abgeschlossen und die Fitness ist bekannt.
\end{itemize}
Bis zum Zeitpunkt, da die Fitness eines Individuum als \emph{fertig} bezeichnet
wird, kann man den Fitnesswert als untere Schranke sehen, d.h. die Fitness des
Individuums hat mindestens diesen Wert, kann aber auch höher sein.
Eine weitere Reifeklasse eines Indivduums ist die Klasse \emph{Spielschwach},
diese Klasse hat einer Sonderstellung, da sie nur für neue Individuen
zutreffen kann. Ein Individuum wird als \emph{Spielschwach} klassifizeirt,
wenn für ein Individuum während des ersten Spiels weniger als 50\% der Züge
als \emph{gut} betrachtet werden. Wenn dies geschieht, wird die Partie sofort
abgebrochen und das Individuum aus der Population entfernt. Dies wird gemacht
um die eingesetzten Ressourcen auf gute Individuen zu konzentrieren.

Als Selektion wird eine Tunierselektion zwischen \emph{reifen} Individuen
durchgeführt, anschließend kommt es dann zur Rekombination, Mutation oder
Erzeugung neuer Individuen. Die Wahrscheinlichkeiten für die Auswahl der
Methoden kann durch den Benutzer gewählt und auch während der Evolution
verändert werden. Die Erzeugung neuer Individuen wurde als eine weitere
Möglichkeit der Evolution hinzugefügt, da man durch die sehr kleinen
Populationen einer zu geringen Diversität entgegenwirken wollte.

Die Migration von Individuen ist ein weiterer wichtiger Punkt für die
internetweite Evolution, hierbei gibt es zwei Möglichkeiten der Migration, die
automatische Migration von Individuen zwischen Populationen und die durch den
Teilnehmer initiierte Migration, die durch eine Anfrage an den Server gestartet
wird. Beiden Methoden ist gemeinsam, dass lediglich Kopien der Populationsmitglieder
versendet werden, dadurch bleibt die Population des Senders
unverändert. Da die Evolution der Clients auch dann weiter läuft, wenn der
Client nicht mit dem Internet verbunden ist, werden die Individuen, die als
Migranten ausgewählt wurden, in einer Queue gespeichert. Die Queue hat eine
Länge von zehn, wenn sie vollständig gefüllt ist, wird immer das älteste
Individuum aus der Queue gelöscht, wenn ein neues Individuum als Migrant in die
Queue gestellt wird. Somit ist die Queue immer mit aktuellen Individuen
gefüllt, wenn ein Versenden der Individuen möglich ist. Dem Anwender ist es
nicht möglich das Versenden von Individuen zu unterbinden, jedoch kann er die
Migration neuer Individuen in die Population unterbinden, um so eine isolierte
Evolution durchzuführen. Da der Anwender das Versenden von Individuen nicht
unterbinden kann, ist es den anderen Teilpopulation weiter möglich an den
Ergebnissen, die von diesem Client erzeugt werden, zu partizipieren.

Die Evolution des Gesamtsystems hat ein offenes Ende, sie wird nicht nach
einer festen Anzahl von Generationen abgebrochen.


%----------------------------------------------------------------------
\subsubsection{Fitnessberechnung}
%----------------------------------------------------------------------
\label{sec:qoopyFit}

Der Fitnesswert eines Individuums ist eine reelle Zahl zwischen $0,0$ und
$15,0$, wobei höhere Werte mit besseren Individuen korrespondieren. Jede ganze
Zahl zwischen 0 und 15 steht für eine disjunkte
Fitnessklasse\index{qoopy!Fitnessklasse} und die
Nachkommastellen bestimmen die Güte des Individuums in der Fitnessklasse,
wobei auch hier ein größerer Wert eine bessere Güte bezeichnet.

Die Fitnessklasse wird durch die Algorithmen bekannter Stärke gebildet, diese
Algorithmen liegen in den Fitnessklassen 2, 4, 6, 8, 10, 12 und 14. Alle
ungeraden Fitnessklassen entsprechen einer Stärke, die zwischen den Spielstärken
der festen Algorithmen liegen. Die Fitnessklassen der festen
Algorithmen werden durch die maximale Suchtiefe des Algorithmuses gebildet. So
wird die Fitnessklasse 2 durch den Algorithmus mit der Suchtiefe 1 gebildet
und die Fitnessklasse 4 durch den Algorithmus mit der Suchtiefe 2. Die
Fitnessklasse ist also Suchtiefe des festen Algorithmus mal zwei. Der
Schachalgorithmus zur Fitnessberechnung wird in Abschnitt~\ref{sub:black}
genauer beschrieben.

Das Ergebnis eines Spiels wird durch eine reelle Zahl zwischen -1 und 1
beschrieben, wobei -1 anzeigt, dass das Individuum verloren hat und der
Standard Algorithmus gewonnen hat. Ein Remis wird durch eine 0
beschrieben. Da ein Spiel nach maximal 50 Halbzügen abgebrochen wird, kann es
vorkommen, dass der Sieger der Partie noch nicht feststeht. In diesem Fall
wird die Stellung mittels einer Materialbewertung bewertet und dieser Wert als
Ergebnis der Partie zurückgegeben. Der Wert der Materialbewertung liegt immer
zwischen $[-1.0, \ldots,1.0]$ und gibt das Verhältnis des Materialvorteils des 
Individuums zum
maximalen Materialwert ohne den König an, wobei ein Materialvorteil für den
weißen Spieler durch positive Werte dargestellt wird und für den schwarzen
Spieler mit negativen Werten.

Die Fitness eines Individuums wird mit eins initialisiert und dann wie folgt berechnet:
\[
 fitness= \frac{\sum_{j \in \mathcal{C}}^{m} \sum_{i=1}^{n}
        \text{class}_{j}^{\text{of
        result$_{i}$}}+\text{result}_{i}}{n*m}
\]


Die Klassen $\mathcal{C}$ teilen sich wiederum in zwei Klassen auf, die erste Klasse
enthält alle gewonnenen Spiele und die zweite Klasse die Remis und verlorenen
Spiele. Ein Spiel wird für weiß als gewonnen betrachtet, wenn die Bewertung
der Partie einen Wert größer als $0,3$ ergibt und als Remis, wenn der Wert
zwischen $0,3$ und $-0,3$ liegt, alle anderen Bewertungen werden als verlorene
Spiele gedeutet. Der Wert $0,3$ entspricht einen Materialvorteil von ungefähr
3 Bauern oder einer schweren Figur\footnote{Schwere Figuren entsprechen hier
  einem Läufer, Pferd und Turm.}. Dies ist ein sehr hoher Materialvorteil, da
bei guten Spielern schon ein Materialvorteil von einem Bauern oft zur Aufgabe
der Partie reicht. Die Klassen eines Individuums, die zur Fitnessberechnung
herangezogen werden, werden durch die folgenden zwei Regeln bestimmt:
\begin{itemize}
\item  Wenn ein Individuum alle Spiele bis zur Klasse $k$ gewonnen hat,
  werden die Ergebnisse der Klasse $k-1$ ignoriert.
\item Wenn ein Individuum alle Spiele ab der Klasse $k$ verliert, werden diese
  Ergebnisse ignoriert.
\end{itemize}

Um die Berechnung der Fitness zu verdeutlichen, hier zwei Beispiele.
Das erste Beispiel zeigt die Berechnung der Fitness in einer Klasse, wenn ein
Individuum  gegen einen Gegner der Klasse $6$ zweimal verliert und einmal
gewinnt $(-1, -1, 1)$, dann ergeben sich daraus für das Individuum folgende Werte
$(5,0, 5,0, 7,0)$, diese ergeben dann den Fitnesswert  $5,667$.

Wenn man das Beispiel nun auf mehrere Klasse erweitert, ergibt sich folgendes
Bild. Ein Individuum $i$ gewinnt alle Spiele der Klassen 2, 4 und 8, weiterhin
erspielt es Gewinne, Remis und Niederlagen in den Klassen 6 und 10. In den
Klassen 12 und 14 verliert es alle Spiele, dann enthält $\mathcal{C}_i$ die
Klassen 6, 8 und 10. Die erste Regel definiert eine untere Grenze, welche
Klasse noch zur Fitnessberechnung genutzt wird, in diesem Fall ist es die
Klasse 4, die zweite Regel ist eine obere Grenze und definiert in diesem
Beispiel die Klasse 12 als Grenze. Anschließend kann die Fitness des
Individuums mit der oben vorgestellten Formel berechnet werden.

Ein weiteres Merkmal der Fitnessberechnung im qoopy-System ist die
Unterteilung der Berechnung in vier Phasen, wobei jede Phase andere
Fitnessklassen enthält und bestimmt, wie oft die Individuen ausgewertet
werden. Diese Vorgehen wurde gewählt, da die Berechnung der Fitness oder
allgemeiner die Auswertung eines Schachspiels mit jeder Klasse immer
rechenintensiver wird und somit mehr und mehr Zeit verbraucht.

In der ersten Phase spielt ein Individuum zwei Spiele gegen Programme der
Klasse \emph{zwei}. Die Individuen dürfen kein Spiel in dieser Klasse
verlieren, da sie sonst direkt ersetzt werden. Durch diese Regel können schon
in einer sehr frühen Phase schwache Individuen herausgefiltert werden. Dadurch
kann das System die Rechenzeit für aufwendigere Fitnessberechnungen der
höheren Klassen einsparen.
In der zweiten Phase spielt das Individuum gegen Programme der Klassen 4, 6,
8 und 10. Wenn das Individuum am Ende dieser Phase mindestens eine Fitness
von $4,5$ hat, wird die Fitnessberechung für das Individuum in der dritten
Phase fortgesetzt, sonst wird die Fitnessberechung beendet und der erreichte
Wert wird als Fitness des Individuums betrachtet.
In der Phase drei spielen die Individuen 1-2 Spiele gegen Programme der
Klassen 2 bis 10. Starke Individuen, die schon in der zweiten Phase Spiele
gegen Programme der Klassen 6 bis 10 gewonnen haben, spielen nur gegen
Programme der Klassen 6 bis 10. Wenn in dieser Phase alle Spiele gewonnen
werden, wird die vierte Phase der Fitnessberechung begonnen, sonst wird die
aktuelle Fitness als endgültige Fitness betrachtet.
Die vierte Phase der Fitnessberechnung erreichen nur die stärksten Programme,
dies ist auch sehr wichtig, da die Spiele gegen die Programme der Klasse 12
und 14 sehr rechenzeitintensiv sind (siehe hierzu~\ref{tab:AlphaBeta}).
Die maximale Anzahl der Spiele in dieser Phase wird durch ein Punktesystem
bestimmt. Jedes Individuum hat 6 (5) Punkte für Spiele in der Klasse 12 (14)
zur Verfügung; wenn die Punktzahl erreicht wird oder je zwei Spiele in jeder
Klasse gewonnen werden, wird die Fitnessberechung beendet. Denn ein Individuum
erhält für jedes Remis einen Punkt und für jedes verlorene Spiel zwei Punkte.

Es werden immer mehrere Spiele in jeder Klasse gespielt, da die Individuen
durch verschiedene Funktionen nicht hundertprozentig deterministisch
agieren. Daher kann ein Individuum Spiele gegen das gleiche Programm einer
Klasse sowohl gewinnen als auch verlieren. Die Variation des Spielverhaltens
ist jedoch nicht so dramatisch, dass ein Individuum alle Spiele gegen
Programme der Klassen 2 - 8 verlieren kann und Spiele der höheren Klassen
gewinnt. Der Nicht-Determinismus kommt durch eine kleine Variation der
Materialbewertung im Stellungsmodul zustande (siehe
Abschnitt~\ref{sec:qoopySellung}).

Die Fitnessberechung wird nach den Spielen gegen Programme der Klasse 14
eingestellt, da schon sehr effiziente Schachprogramme der Klasse 14, also Suchtiefe
sieben, ungefähr 2 Millionen Knoten im Suchbaum expandieren. Programme der
nächsten Klasse würden 13 Millionen Knoten expandieren, den GP-Individuen ist
es aber nur erlaubt maximal 100.000 Knoten pro Zug zu expandieren, somit ist
es unwahrscheinlich, dass das System ein GP-Programm entwickeln kann, welches ein
Programm der Klasse 16 schlagen könnte. Denn bei den Individuen handelt es
sich auch um Baumsuchverfahren, somit werden Programme der gleichen Klasse von
dem System entwickelt und es ist dem System nur möglich eine Optimierung von
Baumsuchverfahren durchzuführen. Daher gehen wir davon aus, dass es dem System nicht
möglich ist ein Verfahren zu entwickeln, welches um den Faktor 130 besser ist als
die bekannten Verfahren.



%----------------------------------------------------------------------
\subsubsection{Der Gegner des Individuums}
%----------------------------------------------------------------------
\label{sub:black}

Wie schon im Kapitel~\ref{sec:qoopyFit} besprochen, werden zur
Fitnessberechnung  Programme verschiedener Stärken benötigt, die zur
Bestimmung der Fitness genutzt werden. Hierzu werden Schachprogramme genutzt,
die den Suchbaum bis zu einer festgelegten Tiefe aufspannen dürfen. Für die
Fitnessbestimmung haben wir die Suchtiefen 1 bis 7 festgelegt, wobei diese mit
den Fitnessklassen 2 bis 14 korrespondieren.

Die Schachprogramme zur Fitnessevaluation nutzen für die Materialbewertung und
die Zugsortierung die gleichen Funktionen wie die Individuen, jedoch wurden
die Gewichte für die einzelnen Parameter vorher festgelegt. Wir haben uns dabei an
Werte aus der Literatur und von guten Schachspielern orientiert. Ein
wichtiger Unterschied zu den Individuen besteht noch darin, dass die Programme
keine Zufallswerte nutzen.

Da diese Programme sehr oft aufgerufen werden, sollten sie sehr effizient sein,
d. h. eine sehr geringe Anzahl von Knoten im Suchbaum expandieren.
Daher wurde der \emph{F-Negascout} Algorithmus \index{F-Negascout Algorithmus}
verwendet, der mit einem \emph{iterative deepening} Ansatz kombiniert wurde
(siehe~\cite{rein89}).
Der \emph{F-Negascout} Algorithmus ist ein sehr effizienter Algorithmus, der
auf dem Alpha-Beta Verfahren basiert (siehe Abschnitt~\ref{sec:FNega}).
Jedoch wurde anstelle der Nullfenstersuche mit einem Fenster der Größe
$(\alpha, \alpha + 0,00001)$ eine Fenstergröße genutzt, die 20\% des Wertes
eines Bauern entspricht, somit erhält man ein Fenster $(\alpha, \alpha +
20)$. In Simulationen hat sich diese Einstellung gegenüber der
Nullfenstertechnik als überlegen erwiesen. Denn je größer das Suchfenster ist,
desto geringer ist die Wahrscheinlichkeit, dass eine Wiederholungssuche
erforderlich ist, da der ermittelte Wert öfter innerhalb des Suchfensters
liegt. Die Wiederholungssuche arbeitet mit einem einseitig beschränkten
Suchfenster und ist demnach meist sehr aufwendig. Der Nachteil des größeren
Suchfensters ist, dass die normale Suche etwas langsamer abläuft als mit einem
Nullfenster. Jedoch überwiegen hier die Vorteile die Nachteile klar.

Die Zugsortierung wird mittels der Technik des \emph{Iterative Deepening}
erreicht (vgl. Abschnitt~\ref{sec:iterDeep}). Zusätzlich werden noch die
\emph{killer moves} genutzt um eine weitere Einsparung von Zügen bei der Berechnung zu
erreichen (vgl. Abschnitt{sub:KillerMove}).

Die Materialbewertung nutzt die in Abschnitt~\ref{sec:qoopySellung} beschriebene
Funktion. Die Werte für die einzelnen Parameter der Funktion sind für den
Algorithmus vorgegeben und haben sich aus der Literatur, Erfahrungen von
Schachspielern und Tests ergeben.

\begin{enumerate}
\item  Bauer [100]
\item  Springer [340]
\item  Läufer [340]
\item  Turm [500]
\item  Dame [900]
\item  Bestrafung für einen Läufer in der Anfangsposition [15]
\item  Bonus für einen Bauern, der das Zentrum des Schachbrettes erreicht hat [15]
\item  Bestrafung, wenn zwei Bauern auf der gleichen Linie stehen [30]
\item  Bonus für einen Bauern, der auf beiden Nachbarlinien keinen
        gegnerischen Bauern hat [20]
\item  Bestrafung für einen Bauern der keinen Bauern auf den Nachbarlinien
        hat, der näher an der ersten Reihe des Gegners ist [15]
\item  Bonus für einen Freibauern, der durch einen Turm beschützt wird [20]
\item  Bonus für einen Bauern, wenn er in der Nähe der ersten Reihe des Gegners
        ist (Promotionsmöglichkeit) [300]
\item  Bonus, wenn beide Läufer vorhanden sind [20]
\item  Bestrafung für einen Läufer, der sich in der Startposition aufhält
  [15]
\item  Bestrafung für Läufer in einer blockierten Stellung. Eine blockierte
  Stellung ist in diesem Zusammenhang eine Stellung, in der drei eigene Bauern
  sich im Bereich des erweiterten Zentrums befinden und Felder besetzen, die
  die gleiche Farbe haben wie die Felder, auf denen sich der Läufer bewegt
  [20].
\item  Bonus für den Springer, wenn es sich um einen blockierte Stellung
  handelt. Für einen Springer handelt es sich um eine blockierte Stellung,
  wenn sich mehr als sechs Bauern im erweiterten Zentrum aufhalten. Durch die
  Fortbewegungsweise des Springers wird er aufgewertet [20].
\item  Bonus für den Springer, wenn er mehr als sechs Felder erreichen kann [15]
\item  Bonus für das Pferd in einer geschlossenen Position [20]
\item  Bestrafung, wenn auf jeder Seite des Pferdes ein generischer Bauer steht
  [25]
\item  Bonus für den Turm, falls er von dem anderen Turm gedeckt wird [15]
\item  Bonus für den Turm, wenn er auf einer halboffenen Linie steht [15]
\item  Bonus für den Turm, wenn er auf einer offenen Linie steht [15]
\item  Bonus für den Turm für andere Vorteile [10]
\item  Bestrafung für den König, wenn er die erste Reihe während des
        Eröffnungs- oder Mittelspiels verlässt [15]
\item  Bonus, nachdem eine Rochade ausgeführt wurde [20]
\item  Bestrafung für die Rochade, wenn es eine Schwäche in der Bauernstruktur
        vor dem König gibt [15]
\item  Bestrafung, wenn die Möglichkeit einer Rochade vergeben wurde [20]
\item  Zufallswert, der zum Wert der Stellung addiert oder subtrahiert wird [20]
\end{enumerate} 



%----------------------------------------------------------------------
\section{Das GeneticChess System}
%----------------------------------------------------------------------
\label{sec:GeneticChess}

Das \emph{GenticChess System}\index{GenticChess System} ist wie die Vorgängersysteme
ein spezialisiertes GP System mit
einem sehr engen Fokus, der auf die Aufgabenstellung ausgerichtet ist. Aus diesem
Grund wurden verschiedenste Techniken entwickelt, aus anderen
Bereichen übernommen und angepasst, um \emph{gut spielende}
Schachindividuen zu erzeugen. Auch hier wird der
Grundgedanke dieser Arbeit weiterverfolgt, der versucht evolutionäre
Verfahren soweit zu erweitern und unterstützen, dass sie auch komplexe
Probleme in einer \emph{annehmbaren Zeit} entwickeln und lösen können,
was mit den \emph{Standardverfahren} nicht möglich ist. 
Das System verwendet die \emph{State-Space} Struktur für die Individuen, die
Struktur wurde in Abschnitt~\ref{sec:stateSpaceGP} vorgestellt. Diese Struktur
zielt auf die Evolution von Problemen, die als Suchproblem dargestellt werden
können, im Fall des Schachproblems müssen dem Individuum aber noch zusätzliche
Funktionen und Datenstrukturen zur Verfügung gestellt werden, damit sie das
Problem lösen können.
In der Literatur und Praxis sind schon Verfahren
und Funktionen bekannt, die das Problem oder Teilprobleme lösen
können. Die Güte dieser Verfahren variiert stark und ist von den
eingesetzten Verfahren und ihrer Kombination abhängig. Diese Kombination sollen 
nun durch die Evolution erprobt werden.
%Dem GP System
%werden nun Funktionen, Prozeduren aber auch Datenstrukturen an die
%Hand gegeben, aus denen Schachprogramme aufgebaut werden können.

%----------------------------------------------------------------------
\subsection{Erweiterungen für das GeneticChess System}
%----------------------------------------------------------------------

Im folgenden werden nun die Erweiterungen des GP Systems und des Individuums
besprochen. Hierbei steht eine starke Spezialisierung auf das Schachproblem im
Vordergrund. Um das Problem adäquat zu lösen, benötigt man einige
Datenstrukturen, die normalerweise ein GP System nicht verwendet. Hierbei sind
neben schachtypisichen Datenstrukturen, wie das Schachbrett, ein Zug oder ein
Spielbaum, auch Elemente eingeführt worden, die eine Anpassung des GP Systems
an die Funktionen und Module darstellten, hier sind die Datenstruktur der
Register und das Individuen ROM zu erwähnen.


%----------------------------------------------------------------------
\subsubsection{Datenstrukturen}
%----------------------------------------------------------------------

Eine weitere Notwendigkeit ist die Einführung komplexerer schachspezifischer
Datenstrukturen, die durch verschiedene Funktionen und Terminale manipuliert
werden. Die wichtigsten Datenstrukturen sind hierbei der Suchbaum, ein Schachzug
und das Schachbrett. Der Suchbaum ist ein Bestandteil der State-Space Struktur
und wird während der Auswertung durch den Interpreter aufgebaut, siehe hierzu auch
Abschnitt~\ref{sec:StateSpaceStrukt}. Der Suchbaum besteht dann aus den Schachbrettern
als Knoten und den möglichen Zügen zwischen den Stellungen als Kanten.

Das Schachbrett ist eine Bitboard Implementierung, das heißt, ein Brett wird durch
mehrere 64-Bitzahlen im Speicher dargestellt. Dies ermöglicht es sehr schnell,
Züge durchzuführen und wieder zurückzunehmen, da diese durch xor-Verknüpfungen
erfolgen. Da man durch eine 64-Bitzahl nur die Positionen feststellen kann,
an denen sich die Figuren auf dem Schachbrett befinden, benötigt man mehrere 64-Bitzahlen
um ein ganzes Schachbrett abzubilden~\cite{bitboard:69,bitboard:2004}. Insgeamt
benötigt man neun 64-Bitzahlen, eine mit allen Figuren, eine nur mit den schwarzen
Figuren, eine nur mit den weißen Figuren und eine für jeden Figurtyp. Durch
und-Verknüpfungen der verschiedenen Zahlen kann man die Position einer Figur ermitteln.
Diese Implementierung ist sehr schnell und ermöglicht es viele Stellungen
pro Sekunde zu betrachten, besonders vorteilhaft ist das Verfahren bei der
Verwendung von 64-Bit Prozessoren.

Der Zug ist eine weitere wichtige Datenstruktur im Schachspiel, er besteht hier aus
dem Startfeld, dem Zielfeld und einem Gütewert. Das Startfeld und Zielfeld wird
durch eine Zahl zwichen 0 und 63 dargestellt und der Gütewerte ist eine reelle Zahl.
Der Gütewert ist grundsätzlich nicht für die Datenstruktur notwendig, da es
aber im System zu einer Zugbewertung kommt, ist es sinnvoll diesen Wert direkt im
Zug zu speichern um keine zusätzliche Struktur zu nutzen.

%----------------------------------------------------------------------
\subsubsection{Individuen ROM}
%----------------------------------------------------------------------

Der \emph{Individuen ROM}\index{Individuen ROM} ist eine Erweiterung
des Individuums, er besteht aus einem Array mit reellen Zahlen. Das Individuum
kann auf diese Werte nur lesend und nicht schreibend zugreifen.
Damit die Werte sich während der Evolution dennoch
verändern können, werden sie während der Crossover oder
der Mutation des Individuums mit verändert. Für das ROM gibt es keine
explizite Fitnessfunktion, die Fitness des ROM's ergibt sich implizit
aus der Fitness des Gesamtindividuums. Die Werte des ROM's werden als
Funktionsparameter interpretiert und sind somit für die Fitness des
Individuums für besondere Bedeutung. Hierbei handelt es sich um
Funktionen, die für die Materialbewertung eingesetzt
werden, siehe Abschnitt~\ref{sec:MaterialModulChessGP}.
So werden den Figuren Werte zugeordnet, mit deren Hilfe eine
Bewertung der Stellung durchgeführt wird. Dadurch ist die
Vorgehensweise die Fitness des ROM's an die Fitness des Individuums zu
koppeln zweckmäßig, denn ohne diese Funktionen wäre es dem Individuum
nicht möglich die Aufgabe zu erfüllen. Die Annahme ist, dass schlechte Parameter
auch zu schlechten Individuen führen.



%----------------------------------------------------------------------
\subsection{Das Schachindividuum}
%----------------------------------------------------------------------

Die \emph{State-Space} GP-Struktur ist der zentrale Motor des
GeneticChess-Systems, die durch verschiedene schachspezifische
Elemente erweitert wurde, damit das Individuum Schachprogramme evolvieren kann.
Diese Erweiterungen sind die spezialisierten Datenstrukturen wie das
Schachbrett, der Zug und der Individuen ROM, wie sie oben beschrieben
wurden. Weitere Spezialisierungen für das Problem sind die Schachfunktionen für
die einzelnen Module der State-Space Struktur.

Die \emph{Modularisierung} der GP Struktur~\index{Modulare GP Struktur} ist
ein wichtiger Punkt des GeneticChess Systems. Die Modularisierung soll
dem System die Möglichkeit geben das Zielproblem zu lösen, indem es Lösungen
für Teilprobleme sucht. Um die Suche nach einer Lösung zu
unterstützen wird die Aufteilung in die Teilprobleme nicht durch die Evolution
entwickelt, sondern von dem System vorgeben. Hierdurch wird dem System
einerseits die Möglichkeit genommen eigene Lösungswege zu finden, jedoch wird
den Individuen auch die Möglichkeit gegeben schneller Lösungen zu erreichen,
wie wir es aus den Erfahrungen des GeneticChess und qoopy-Systems erkannt haben.
%
%Hier stellt sich die Frage, ob man durch den Verlust der Freiheit in
%der Evolution mehr verliert als durch die Kanalisierung gewinnt.
%
Da Schach selbst ein komplexes Problem ist, kann man davon ausgehen, dass
man durch den Einsatz von einfachen GP Individuen nicht in annehmbarer
Zeit zu einem Ergebnis kommen kann oder vielleicht auch nie zu einem
annehmbaren Ergebnis kommt.
Für das Schachproblem sind die Teilprobleme und die Interaktion der
Teilprobleme  klar definiert, so dass die Aufgabenstellung der Module und
deren Interaktion in einem Gesamtindividuum klar definiert sind.
Diese Module sind untereinander durch eine hierarchische Beziehung
verbunden, das heißt, dass ein Modul einer höheren Hierarchieebene die
Ergebnisse der Module einer niedrigeren Hierarchieebene benötigt.

Ein hierarchisches Modul unterscheidet sich von
\emph{ADF's}\index{ADF} (automatisch definierte Funktionen), wie sie
Koza in~\cite{koza2} eingeführt hat. Diese Module sind Teilfunktionen,
die sich während der Evolution herausbilden und über deren
Funktionalität zu Beginn der Evolution keine Informationen vorhanden
sind. Die Funktionalität dieser ADF's wird nur durch ihre Funktions-
und Terminalmenge vorgegeben. Meistens haben sie aber die gleichen
Funktions- und Terminalmengen wie das Hauptindividuum. Daher wird die
Funktion eines ADF's erst in dem Evolutionsprozess herausgebildet und
unterscheidet sich stark zwischen Individuen verschiedener
Evolutionsläufe. Eine weitere Methode Module in GP Systeme zu verwenden
wurden von Angeline in~\cite{angeline:94} vorgestellt. Dabei werden
während der Crossoveroperation Teilbäume gekapselt, vor weiterer
Veränderung geschützt und als \emph{Libraries} bezeichnet. Auch hier
werden die Module innerhalb der Evolution erzeugt und können von den
gegebenen Ressourcen nur eine Teilfunktion dieser Aufgabe sein.

Im GeneticChess System wird die Funktionalität eines
Moduls vorher festgelegt, so ist ein Modul nicht eine
zufällig entstandene Funktion sondern ein gezielt entwickeltes Modul
eines komplexeren Gesamtindividuums oder Gesamtprogramms.
Die Module unterscheiden sich nicht nur in ihrer
Aufgabenstellung sondern auch in ihren Funktions- und Terminalmengen.
Das GeneticChess System soll einen Alpha-Beta Algorithmus evolvieren, somit
braucht das Individuum drei Module:
\begin{itemize}
\item das Materialbewertungs Modul,
\item das Zugbewertungs Modul und
\item das Tiefen Modul.
\end{itemize}
%Die Abbildung~\ref{fig:modulGP} verdeutlicht den Aufbau des State-Space
%Individuums mit den verschiedenen Schachmodulen. 
Als GP-Struktur wird die State-Space Struktur verwendet, die in Kapitel~\ref{sec:stateSpaceGP}
vorgestellt wurde.% Jedes der Module nutzt die
%Linear-Graph Struktur, obwohl bis auf das Tiefen Modul jedes Modul die
%verschiedensten GP Strukturen verwenden könnte. Während der erstens Tests hatte
%sich aber gezeigt, dass die Linear-Graph Struktur zwei Vorteile besitzt. Diese
%haben sich schon bei der Analyse der GP Strukturen gezeigt, siehe Abschnitt~\ref{sec:GPResult}.
%Die Linear-Graph Struktur kann trotz kleiner Pools zu sehr guten
%Ergebnissen kommen und auch die Streuung bei den Ergebnissen ist viel kleiner
%als bei den anderen Strukturen. Diese Punkte sind für die Evolution der
%Schachprogramme sehr wichtig, da die Fitnessberechnung der Individuen sehr
%teuer ist (siehe hierzu Kapitel~\ref{sec:SchachFit}). Für jede
%Fitnessauswertung werden mehrere Spiele gegen verschieden starke Schachprogramme
% durchgeführt. Die Stärke des Gegnerprogramms wird über die maximale Suchtiefe
 %des Algorithums geregelt, hierzu mehr in Abschnitt~\ref{sub:ChessGP-Gegner}.

%\begin{wrapfigure}{r}{60mm}
%%\begin{figure}
%\centerline{\epsfig{figure=Pictures/Graphik/stateSpace.eps,width=6cm}}
%\caption{ Aufbau des State-Space Individuums mit den einzelnen Modulen. }
%\label{fig:modulGP}
%\end{wrapfigure}%{figure}





%----------------------------------------------------------------------
\subsubsection{Materialbewertungs Modul}
%----------------------------------------------------------------------
\label{sec:MaterialModulChessGP}

Das \emph{Materialbewertungs Modul}\index{Materialbewertungs Modul}
hat die Aufgabe, die Analyse einer
Schachposition durchzuführen. Dies ist im Schachspiel eine sehr
wichtige Aufgabe, da während der Suche eine Bewertung gebraucht wird,
um jede betrachtete Stellung im Spiel zu bewerten. Dies ist notwendig, da die
Berechnung eines Zuges nicht bis zum Remis oder Matt des Spielzuges
durchgeführt werden kann. Die
Suche muss mitten im Spiel abgebrochen werden und diese Situation muss
dann bewertet werden. Die Bewertung einer Stellung beruht somit auf
unvollständigen Informationen, denn eigentlich ist die Bewertung nicht
von der statischen Situation abhängig, sondern von dem dynamischen
Verhalten des Spiels der nächsten Züge. Da die Materialbewertung aber
sehr oft in den Algorithmen aufgerufen wird, muss sie auch schnell
sein und kann somit nur die statische Situation bewerten.
Die einfachste Variante ist die Differenz der Summe der Materialwerte
beider Seiten. In der Literatur findet man aber verschiedene
Verfahren, die wichtigsten davon werden in
Kapitel~\ref{sec:MaterialBewertung} genauer erklärt.

Eine einfache Materialbewertung bietet jedoch sehr viel Raum für
Verbesserungen, so können verschiedene positionelle Kriterien
berücksichtigt werden um eine Verbesserung der Bewertung zu erzeugen.
Die einfache Materialbewertung benutzt nur die reinen Materialwerte
der Figuren für die Bewertung. Dem GP Modul wird hier  die
Möglichkeit gegeben die Werte für die einzelnen Figuren selbst
anzupassen. Zu den reinen Materialwerten kann das Modul aber auch
positionelle Werte in die Materialbewertung einbeziehen. Dem Modul
stehen hierzu Funktionen zur Verfügung, die folgenden Kriterien in die
Materialbewertung mit einbeziehen können:




\begin{description}
\item [Zentrumsbauer] Ein Bonus, wenn Bauern die Zentrumsfelder der
        entsprechenden Seite besetzen. Die Zentrumsfelder sind d3-6
        und e3-6. Zusätzlich hat weiß noch die Felder c4-5 und schwarz
        f4-5. Die Idee der Zentrumsfelder ist, dass Figuren im
        Brettzentrum größeren Einfluss ausüben als am Rand.
\item [Doppelbauer] Ein Malus, wenn zwei gleichfarbige Bauern dieselbe
        Linie besetzen.
\item [Freibauer] Ein Bonus für Bauern, die an einer Umwandlung nicht
        mehr direkt von gegnerischen Bauern gehindert werden können.
\item [Rückständiger Bauer] Ein Malus für Bauern, die sich nicht mehr
        in der Grundstellung befinden und keinen gleichfarbigen Bauern
        auf den benachbarten Linien haben, die näher an der
        Grundstellung sind.
\item [Springermobilität] Ein Bonus, der die Mobilität des Springers
        berücksichtigt. Denn je nach Position kann ein Springer
        2,3,4,6, oder 8 Felder erreichen. Das Merkmal, wieviele Felder
        ein Springer erreichen kann, erhöht den Bonus für den Springer.
\item [Springerbonus] Dieser Bonus wird gewährt, wenn sich im
        erweiterten Zentrum bestehend aus 16 Feldern, mehr als 6 Bauern
        aufhalten, hat der Springer aufgrund seiner Fortbewegung
        im Gegensatz zu den Läufern einen Vorteil, der durch diesen Wert
        berücksichtigt wird.
\item [Blockierter Läufer] Ein Malus, wenn im erweiterten Zentrum
        (Quadrat aus 16 Feldern in der Mitte des Brettes) mindestens 3
        eigene Bauern mit der gleichen Feldfarbe wie der Läufer stehen.
        Diese Bauern beeinträchtigen die Mobilität des Läufers,
        gegnerische Bauern zählen nicht, da sie geschlagen werden können.
\item [Läuferpaar] Ein Bonus, der vergeben wird, solange beide Läufer
        vorhanden sind. Denn nur beide können alle Felder des
        Schachbrettes erreichen.
\item [Läufer Startposition] Ein Malus für einen Läufer, der in der
        Startposition verbleibt. Für den Springer wird dieses Kriterium
        über die Mobilität bewirkt und für den Turm über die Rochademöglichkeit.
\item [Turm auf halboffener Linie] Ein Bonus, wenn der Turm auf einer
        Linie steht, auf der sich kein eigener, sondern nur ein
        gegnerischer Bauer befindet.
\item [Turm auf offener Linie] Ein Bonus wenn der Turm auf einer
        Linie steht, auf der sich kein eigener und kein
        gegnerischer Bauer befindet.
\item [Freibauer und Turm] Ein Bonus für einen Freibauern, wenn er
        durch einen Turm geschützt wird, der auf der gleichen Linie
        steht und damit die Promotionschancen erhöht.
\item [Turm] Ein Bonus, falls sich Türme gegenseitig decken oder auf
        Reihe 1 oder 2 stehen.
\item [Rochade verpasst] Ein Malus, falls in einer Stellung eine lange
        oder kurze Rochade möglich war, diese aber nicht ausgeführt wurde.
\item [Rochade durchgeführt] Ein Bonus, falls eine Rochade
        durchgeführt wurde.
\item [Bauernstruktur] Ein Malus für eine Schwäche in der
        Bauernstruktur nach einer Rochade. Das heißt, die schützenden
        Bauern bleiben in der Grundstellung. Dieser Malus wird im
        Endspiel nicht mehr verwendet.
\item [König Grundlinie] Ein Malus, wenn der König die Grundlinie
        verlässt, dies gilt nicht für das Endspiel.

\end{description}


Zusätzlich werden noch verschiedene positionelle Kriterien nur im
Endspiel benutzt, diese sind:
\begin{description}
\item [Promotionschancen] Ein Bonus, der die Nähe des Bauern zur
        gegnerischen Grundlinie bewertet. Denn je näher ein Bauer ist,
        desto besser ist die Chance für eine Promotion. Dies ist
        besonders im Endspiel wichtig, da es in Endspielpositionen oft
        zu Promotionen kommt.
\item [Bauer Läufer Feldfarbe] Ein Malus, wenn ein Bauer auf einem
        Feld steht, welches die gleiche Farbe wie der Läufer
        hat. Dieser Wert wird dann interessant, wenn der Gegner im
        Endspiel nur noch einen Läufer hat und somit der Bauer auf
        den entsprechenden Felder nicht geschlagen werden kann.
\item [Springer Bauer] Ein Malus, falls sich gegnerische Bauern auf
        der Linie a oder b befinden oder auf der Linie g oder
        h. Wenn der Springer beide Bauern bedrohen möchte, braucht er
        viele Züge um die Seite zu wechseln. Dieses Kriterium gilt
        nicht für den Läufer.
\end{description}

In vielen Schachprogrammen werden diese oder ähnliche Merkmale
verwendet um eine Stellung zu bewerten. Dies geschieht aber immer
statisch, das heißt, den Merkmalen wird ein bestimmter Wert zugeordnet
und mittels einer Prozedur zu einem Wert für die Stellung
verarbeitet. Diese Werte werden entweder durch die Programmierer
vorgeben oder auch durch Methoden der CI gelernt
(siehe~\cite{tiggelen:91,tunstall:91} und
Kapitel~\ref{sec:MaterialBewertung}).

Das Bewertungsmodul soll nun die Möglichkeit erhalten nicht nur diese
Werte zu adaptieren, sondern auch die Kombination dieser Werte zu
einer Bewertung zu komponieren, ein ähnlicher Versuch wurde
in~\cite{kantschik:2000:TechRep} durchgeführt (siehe auch
Kapitel~\ref{sec:ChessGP}). Dort gab es eine feste Fitnessfunktion, so dass die
Individuen nur eine festgelegte Funktion lernen konnten. Durch den Ansatz der
impliziten Fitnessfunktion wird dem Modul die Möglichkeit gegeben die Bewertungsfunktion
frei zu erzeugen. Die Fitnessfunktion ist implizit, da als
Grundlage der Fitness nur der Sieg oder die Niederlage des
Gesamtindividuums betrachtet wird.

Das Modul nutzt die Linear-Graph Struktur um eine Blattbewertung zu
berechnen. Die Funktionen und Terminale, die verwendet wurden, sind in
Abschnitt~\ref{sub:FunkGCMat} genauer beschreiben. Wichtig an dem Funktionsset
ist, dass es an den Standardverfahren zur Materialbewertung angeleht ist, aber
auch Funktionen verwendet werden, die darüber hinausgehen. So werden hier wie auch
in den anderen Modulen Funktionen verwendet, die dem Algorithmus die Möglichkeit geben
potentielle Entwicklungen in die Bewertung mit einfließen zu lassen. Somit ermöglicht
man sowohl dem Modul als auch dem Individuum etwas über den aktuellen Suchhorizont hinaus
zu sehen um die Bewertung der aktuellen Position durchzuführen.


%----------------------------------------------------------------------
\subsubsection{Zugbewertungsmodul}
%----------------------------------------------------------------------

Die Aufgabe des \emph{Zugbewertungsmoduls}\index{GeneticChess!Zugbewertungsmodul}
ist es alle möglichen Züge einer Stellung zu bewerten und so eine
relative Sortierung der Züge untereinander erreichen zu können.
Zugsortierungen werden im Besonderen in Verfahren angewendet, die auf
den Alpha-Beta Verfahren beruhen. Denn dies basiert auf einer
Suchfenstertechnik, bei der stets die Werte der besten Alternativen des weißen 
und schwarzen Spielers im sogenannten Suchfenster ($\alpha, \beta$) gespeichert
werden. Je kleiner dieses Fenster ist, desto größer ist die Chance, dass
Teile des Suchbaums abgeschnitten werden können. Eine gute
Vorsortierung der Züge im Suchbaum ermöglicht es dem Alpha-Beta
Verfahren die guten Alternativen früh zu finden und somit das
Suchfenster schnell zu verkleinern.
Die Sortierung der Züge erfolgt nach der Bewertung jedes Zugs durch einen
Quicksortalgorithmus. Anschließend werden die Züge in der neuen Reihenfolge
expandiert. Wenn das Modul eine gute Zugsortierung evolviert hat, ist es also
möglich die Anzahl der Knoten, die bei der Suche expandiert werden, stark
einzuschränken. So expandieren selbst die
spielstärksten Schachprogramme $5*\sqrt(n)$ Knoten, wobei $n$ die Anzahl der
Knoten für eine feste Suchtiefe angibt, siehe Tabelle~\ref{tab:AlphaBeta} in
Kapitel~\ref{sec:alphaBeta}. Diese Werte liegen aber immer noch  20-30\%
über der Anzahl von Knoten den ein optimalen Suchbaum benötigen würde.

Gute Zugsortierungen berechnen im Allgemeinen eine gewichtete Summe über
verschiedene Merkmale des Zuges, ähnlich wie es im qoopy-System durchgeführt
wurde, siehe hierzu Abschnitt~\ref{sub:QoopySortmodul}. Da die Zugsortierung
ein sehr wichtiges Modul ist, um die Rechenkraft eines Algorithmus zu verbessern,
haben wir uns dazu entschlossen nicht eine festgelegte gewichtete Summe über eine Kombination
von Merkmalen des Zuges und der aktuellen Stellung zu berechnen, um die Parameter
zu optimieren, sondern durch den evolutionären Prozess einen ganzen Algorithmus
für diese Aufgabe zu evolvieren. Der Algorithmus hat dabei mehr Möglichkeiten einen
Wert für einen Zug zu bestimmen, als dies durch eine gewichtete Summe möglich ist.
Dies wird besonders durch die zur Verfügung gestellten Funktions- und Terminalmengen
ermöglicht, sie werden im Abschnitt~\ref{sub:FunkGCZug} genauer beschreiben. Sie
basieren  auf Techniken zur Zugbewertung, wie sie in Kapitel~\ref{sec:Zugbewertung}
vorgestellt wurden. Einige dieser Funktionen gehen jedoch darüber hinaus, eine
Gruppe dieser Funktionen bewertet dabei verschiedene Aspekte der aktuellen Stellung
und die andere Gruppe von Funktionen die gleichen Aspekte unter der Annahme,
dass der Zug schon durchgeführt wurde.
So ist es dem Zugbewertungsmodul möglich festzustellen, ob ein Zug kurzfristige positive
oder negative Eigenschaften hat. Keine dieser Funktionen führt eine vollständige
Materialbewertung der neuen Stellung durch, sondern betrachtet nur Teilaspekte davon
oder Aspekte, die nie für eine Materialbewertung herangezogen werden.
So kann die Differenz der angegriffenen/gedeckten Figuren durch einen Zug ermittelt
werden oder es kann ermittelt werden, wie hoch der maximale Gewinn oder Verlust
durch den Gegner nach diesem Zug ist. Dies soll es dem Modul ermöglichen die Güte
eines Zuges besser zu bestimmen als durch eine gewichtet Summe von Merkmalen.
Das Modul nutzt die Linear-Graph Struktur, um dem Algorithmus
eine einfache Möglichkeit zu geben auf verschiedene Eingaben mit verschiedenen
Berechnungen zu reagieren und somit eine größere Flexibilität zu gewährleisten,
als dies mit eine linearen oder Baumstruktur möglich wäre.

Mit diesen Möglichkeiten muss das Modul nun einen Algorithmus entwickeln, der
einen Gütewert für jeden Zug bestimmen kann. Die Randbedingungen sind dabei, dass
gute Züge einen höheren Wert bekommen als schlechte Züge und die Bewertung muss unabhängig
von der Seite mit dem Zugrecht berechnet werden. Das heißt, die Bewertung des Zuges muss
unabhängig von der Farbe der Figur sein, die zieht. Die zweite Bedingung ist zwar
einfach, jedoch kann durch die Wahl einer falschen Funktions- und Terminalmenge
diese Nebenbedingung durch ein Individuum nur schwer oder gar nicht zu erreichen
sein. Daher sind sie so gewählt, dass diese Nebenbedigung immer erfüllt ist. Somit
hat die Evolution nur die Aufgabe ein Gütemaß zu bestimmen.
Die Funktions- und Terminalmenge für dieses Modul besteht aus sehr vielen
schachspezifischen Methoden, eine genaue Auflistung kann im Anhang,
Abschnitt~\ref{sub:FunkGCZug} gefunden werden.



%----------------------------------------------------------------------
\subsubsection{Tiefenmodul}
%----------------------------------------------------------------------
\label{sec:GenticChessTiefenmodul}

Das \emph{Tiefenmodul}\index{GeneticChess!Tiefenmodul} entscheidet für jede Position,
ob diese expandiert werden soll oder nicht. Das Tiefenmodul unterscheidet sich
in der Aufgabenstellung stark von dem Tiefenmodul des qoopy-Systems, wie es
in Kapitel~\ref{sub:QoopyTiefenmodul} beschrieben wird. Im qoopy-System wird
durch das Tiefenmodul die Entscheidung nicht direkt getroffen. Im GenticChess
hat das Modul neben der direkten Entscheidung noch eine weitere Aufgabe,
es bestimmt die Funktion, welche die Züge erzeugt, die im nächsten Schritt
expandiert werden sollen.
Dem Modul stehen vier verschiedene Funktionen zur Verfügung, um die Struktur des
Suchbaumes zu beeinflussen.
Die Funktionen sind:
\begin{itemize}
\item Alle Züge: Es werden alle erlaubten Züge erzeugt.
\item Angriffszüge: Es werden nur Züge erzeugt, die eine Figur schlagen oder
	angreifen.
\item Verteidigungszüge: Es werden nur Züge erzeugt, die die Deckung der
	eigenen Figuren erhöhen.
\item Nullzüge: Es wird kein Zug durchgeführt, sondern das Zugrecht wird
	an den Gegner abgegeben, siehe~\ref{sec:NullMove}.
\end{itemize}

Um dem Modul diese Möglichkeit zu geben, wurde das Tiefenmodul der State-Space
Struktur entsprechend implementiert, so dass die Terminalknoten der Linear-Graph
Struktur eine dieser Funktionen enthalten. Diese Elemente der Struktur werden
Programmflussabschnitt genannt, weiteres findet man dazu in
Kapitel~\ref{sec:StateSpaceStrukt}.

Der Programmflussabschnitt besteht aus zwei Funktionen, die
miteinander kombiniert werden, einerseits hat man eine binäre
Entscheidungsfunktion, die Ergebnisse des Tiefenentscheidungsmoduls für die
Entscheidung nutzen, ob die Problembewertung oder die Blattbewertung
aufgerufen wird. Zusätzlich enthält der Abschnitt die Funktion,
die die möglichen Züge im Suchbaum für den nächsten Schritt erzeugen.
Durch den Programmflussabschnitt ermöglicht man den Individuen einen sehr variablen
Aufbau des Suchbaums und somit die Möglichkeit andere Wege im Suchraum zu finden.

Das Tiefenmodul hat somit auch die Möglichkeit einen variablen Suchhorizont zu erzeugen.
Dies wirkt dem Horizonteffekt entgegen, da nun die Suche nicht nach einer
festen Suchtiefe beendet wird, sondern situationsabhängig auf Grund der gegebenen
Stellung. Gleichzeitig geben wir dem Tiefenmodul die Möglichkeit heuristisch bei
der Wahl der nächsten
Züge vorzugehen, dies bewirkt eine heuristische Bewertung des gewählten Zuges
an der Wurzel, jedoch ist die Bewertung jedes Algorithmus im Schach heuristisch,
da die Bewertung nie bis zum Ende der Partie durchgespielt werden kann. Durch dieses
Vorgehen kann jedoch der Ausgrad des Baumes um viele Ebenen reduziert werden, was
zu einer genaueren Analyse der beobachteten Züge führt. Die Aufgabe des Moduls ist
es somit auch ein gutes Verhältnis zwischen der Auswahl der Züge und der Tiefe
der betrachteten Variante zu finden. Im optimalen Fall soll das Modul einen ungleichmäßigen
Suchbaum erzeugen, der jedoch alle wichtigen Varianten enthält um eine gute
Entscheidung treffen zu können.

Da das Tiefenmodul einen entscheidenden Einfluß auf die Rechenzeit des Individuums
hat, ist die Suchtiefe nicht unbeschränkt, so wird die Expansion des Baumes
maximal bis zur Tiefe zehn zugelassen. Diese sind ungefähr  $10^{14}$ Knoten im
Suchbaum, dies ist für einen evolutionären Prozess zu langsam, denn bis
die Fitness eines Individuums feststeht, müssen mehrere Spiele durchgeführt
werden, hierbei würde die Auswertung eines Spiels aber Tage benötigen.
Daher wurde noch eine zweite Beschränkung eingefügt, die nun die
Anzahl der Knoten im Suchbaum beschränkt. Ein Individuum darf eine maximale Anzahl
Knoten pro Zug verwenden, dadurch kann die vollständige Fitnessauswertung eines
Individuums innerhalb einiger Stunden durchgeführt werden. Der Wert für die maximale
Anzahl der Knoten wird als Parameter dem System übergeben, dieser Wert variierte
zwischen $10.000$ und $250.000$ Knoten. Wenn das Knotenlimit vom Individuum erreicht
wird, wird das Tiefenmodul nicht mehr ausgeführt, sondern die Rekursion wird für alle
noch folgenden Züge beendet. Da nun aber noch viele Bewertungen nicht durchgeführt 
sein können, da das Module immer sehr tief gesucht hat, erlauben wir dem Individuum,
für alle ausstehenden Stellungen noch die Materialbewertung durchzuführen. Dadurch
können von einem Indviduum etwas mehr Knoten ausgewertet werden als durch das
Knotenlimit vorgesehen. Wir haben uns für diese Vorgehen aber entschieden, da
wir hoffen gute Zugsortierungsmodule und Materailbewertungmodule nicht durch ein
schlechtes Tiefenmodule zu beginn der Evolution zuverlieren.


Die Aufgabe des Tiefenmoduls ist es, anhand der gegebenen Stellung zu
entscheiden, ob der mögliche Teilbaum genauer untersucht werden soll oder
nicht. Die Funktions- und Terminalmenge für diese Module besteht aus sehr vielen
schachspezifischen Methoden, eine genaue Auflistung kann im Anhang
Abschnitt~\ref{sub:FunkGCTief} gefunden werden.



%----------------------------------------------------------------------
\subsection{Fitness Funktion}
%----------------------------------------------------------------------
\label{sec:SchachFit}

Die Fitness eines Schachindividuums wird dadurch gemessen, dass es Spiele
gegen Schachprogramme fester Suchtiefe durchführen muss. 
%Ein Schachindividuum
%spielt jeweils in jeder Farbe gegen einen Gegner mit der gleichen
%Suchtiefe. 
Wenn das Individuum gewinnt, spielt es gegen ein Gegnerprogramm mit
einer Suchtiefe, die um eins größer ist. Die Fitnessberechnung hat zwei
Abbruchkriterien, das erste Abbruchkriterium ist die Anzahl der verlorenen
Spiele. Während der Evolution wird die Fitnessberechnung nach einem
verlorenen Spielen beendet, diese Grenze kann durch einen Parameter bestimmt
werden. Ein verlorenes Spiel ist zwar sehr restriktiv, so kann
aber die Fitnessbewertung für ein Individuum sehr schnell beendet werden.
Es hat sich gezeigt, dass es, wenn
man die Grenze der verlorenen Spiele erhöht, zu keinem Gewinn in der Evolution
für die verwendeten Parameter kommt. Die Anzahl der verlorenen Spiele ist auch ein
Parameter für den Selektionsdruck, somit haben wir hier einen sehr hohen
Selektionsdruck gewählt, der Grund hierfür ist der hohe Rechenaufwand, wenn ein 
geringerer Selektionsdruck verwendet wird.
 Sehr viele Individuen, die mehr als zwei Spiele verlieren, verlieren auch
Spiele gegen Gegnerprogramme mit einer größeren Rechentiefe, wodurch sehr
viel Rechenzeit aufgewendet wird. Die Tests haben für die verwendete Evolutionszeit
zu keinen Vorteilen geführt. Denn viele Individuen, die gegen leichte Gegnerprogramme
verlieren, verlieren auch gegen stärkere Programme und die
Individuen die auch gegen Gegnerprogramme mit größeren Rechentiefen gewinnen,
sind auf der anderen Seite zu unbeständig und dies ist nicht
das Ziel der Evolution. 
Das System soll Individuen generieren, die gute
Ergebnisse mit kleinen Spielbäumen erreichen, daher ist es nicht sinnvoll
Individuen zu erhalten, die unbeständig sind oder zuviel Rechenzeit benötigen.

Ein Spiel dauert maximal 50 Halbzüge, danach wird es abgebrochen, falls nicht
ein Programm vorher gewonnen hat. Als Ergebnis eines Spiels wird dann der reine Materialwert
des Spiels ohne Bewertung von Stellungselementen genutzt. Der Wert 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. Ein Bauer hat somit einen Einfluss
von $\frac{100}{4060} \approx 0,0246$ auf den Ergebniswert. Ein Spiel wird nun als
gewonnen betrachtet, wenn das Individuum mindestens einen Wert von $0,1/Tiefe$
hat. $Tiefe$ ist immer die Tiefe und somit die Spielstärke des Gegnerprogramms. Für
ein Individuum wird es immer schwieriger zu gewinnen und daher wird die Schwelle
für den Gewinn immer weiter gesenkt. Ab Gegnerprogramme der Tiefe fünf wird die
Schwelle auf einen Wert von $0,02$ gesenkt, was ungefähr einem Bauern
entspricht, d.h. ein Individuum muss während eines Spiels mindestens einen
Materialvorteil von einem Bauern erspielen, um weiter an der Fitnessbewertung
teilzunehmen.

Die Fitness selbst setzt sich aus vier Werten zusammen, zwei dieser Werte bewerten
die Ergebnisse der Individuen gegen die verschiedenen Gegnerprogramme. Diese Werte
werden durch die Funktionen~\ref{eq:fitWhite} und~\ref{eq:fitBlack} berechnet. Die Funktionen
summieren die Bewertung der Spiele für die jeweilige Farbe, dabei wird eine Gewichtung
durchgeführt die auch davon abhängig ist, ob ein Spiel gewonnen oder verloren
wurde. Gewonnene Spiele werden stärker gewichtet als verlorene Spiele und Spiele gegen
Gegnerprogramme mit größerer Suchtiefe werden auch stärker gewichtet. Die Gewichtung
erfolgt über die Gauss'sche Reihe\footnote{Im Jahr 1786 entwickelte Karl
  Friedrich Gauß eine
Funktion, wie die Summe der natürlichen Zahlen von 1 bis $n$ einfach berechnet werden
kann.}, deren Eingabeparameter die Spielstärke des Gegnerprogramms
ist. Durch dieses Vorgehen erreicht man, dass Spiele gegen spielstärkere Gegnerprogramme
stärker bewertet werden und somit der Verlust eines Spieles gegen einen
schwächeren Gegner
nicht so ins Gewicht fällt.
In der Fitnessfunktion
wird der Ergebniswert als positiv bewertet, wenn er größer Null ist und nicht mit einem
Schwellwert wie beim Abbruchkriterium. Das Ergebnis des Schwellwertes geht aber
in die Werte $BothWin$ und $LastWinDepth$ ein. $BothWin$ ist die Tiefe, in der
das Individuum sowohl das schwarze als auch das weiße Gegnerprogramm besiegt
hat, und $LastWinDepth$ ist die Tiefe, in der ein Individuum das letzte mal gegen
ein Gegnerprogramm gewonnen hat.  

\begin{equation}
White(i)= \sum_{d= 0}^{MaxDepth}  \begin{cases}
                                  gauss(d+1)*resWhite(d) > 0 & resWhite(d) > 0 \\
                                  gauss(d)*resWhite(d) & resWhite(d) < 0 \\
                                \end{cases}
\label{eq:fitWhite}
\end{equation}


\begin{equation}
Black(i)= \sum_{d= 0}^{MaxDepth}  \begin{cases}
                                  gauss(d+1)*resBlack(d) > 0 & resBlack(d) > 0 \\
                                  gauss(d)*resBlack(d) & resBlack(d) < 0 \\
                                \end{cases}
\label{eq:fitBlack}
\end{equation}

Der Wert $LastWinDepth$ wird mit 1.000 multipliziert
und der Wert $BothWin$ mit 100. Die Fitnessfunktion hat somit drei Ebenen, auf denen
die Fitness steigen kann. Die Ebene mit den geringsten Einfluss ist der
gewichtete Materialgewinn
der Individuen, die zweite und dritte Ebene ist jeweils eine Treppenfunktion
und wird über die
Werte von $BothWin$ und $LastWinDepth$ gesteuert. Da diese Werte den höchsten Anstieg
in der Fitness bewirken, werden somit Individuen bevorzugt die gegen starke
Gegnerprogramme
gewinnen können und nicht Individuen, die mit einem möglichst hohen
Materialvorteil gewinnen.
Aus diesem Grund wird auch der Wert $LastWinDepth$ stärker gewichtet, denn
dadurch sollen
Programme bevorzugt werden die gegen spielstarke Gegner gewinnen können. Diese
Werte
wurden in den ersten Fitnessfunktionen nicht berücksichtigt und es führte
dazu, dass viele
Evolutionen an den Gegnerprogrammen ab der Tiefe drei scheiterten und nur den
Materialgewinn
gegen die leichte Gegnerprogramme erhöhten.



\begin{equation}
 \begin{split}
  BothWin &= BothWin*100; \\
  dFit  &= ((BothWin)+dWhiteVal+dBlackVal+ (LastWinDepth*1.000,0);\\
\end{split}
\label{eq:fitChess}
\end{equation}


Durch die Verbindung des gewichteten Materialgewinns und der Stufenfunktion in
der Fitnessfunktion~\ref{eq:fitChess} ermöglicht man es der Evolution, Programme
zu erzeugen, die gegen spielstarke Programme gewinnen können aber nicht den maximalen
Materialgewinn erzielen müssen um gegen den Gegner der nächsten Stufe zu spielen.

Die Rechenzeit ist ein weiterer wichtiger Punkt bei der Auswahl der Individuen, so wird,
neben der Fitness auch die Anzahl der betrachteten Stellungen, bei der Selektion der
Individuen mit berücksichtigt. Ein Ziel der Evolution ist es Programme zu entwickeln, die möglichst
kleine Suchbäume erzeugen, daher wird beim Vergleich der Fitness zweier Individuen nicht
nur der Fitnesswert betrachtet, sondern auch die durchschnittliche Anzahl der betrachteten
Stellungen pro Zug. Dieser Wert wird aber nur dann berücksichtigt, wenn die Fitnesswerte,
die durch die Funktion~\ref{eq:fitChess} berechnet wurden gleich sind. Dadurch erreicht man
in den Phase, in denen es zu keine Verbesserung der Fitness kommt, eine
 Verkleinerung des Suchraums.

Zu dieser Art der
Fitnessberechnung gibt es für Schach nur eine Alternativen. Ein Individuum
kann mit Hilfe von Schachstellungen trainiert werden. Diese Art der
Fitnessberechnung wurde für einige Module des \emph{ChessGP-Systems}
verwendet (siehe~\ref{sec:ChessGP}), diese Methode hat aber den Nachteil, dass
nicht alle Spielsituationen für ein Programm bereitstellt. So gab es bei der
Erstellung der Fitnesscases für das ChessGP-System das Problem, dass man kaum
Beispiele für Endspiel Stellungen hatte und diese erst erzeugen musste. Bei der
Analyse der Ergebnisse haben wir auch gesehen, dass es sehr oft zu nicht erwünschten
Verhalten der Individuen gekommen ist, da es ihnen nicht gelungen ist mit Hilfe der
gegebenen Fitnesscases die Problemstellung zu abstrahieren (siehe hierzu Abschnitt~\ref{sub:ChessGPMat}).
Wegen dieser Probleme haben wir in allen weiteren Evolutionen immer die zeitaufwändigere
Variante genutzt, die vollständige Spiele zur Berechnung der Fitness nutzt.



%%----------------------------------------------------------------------
\subsection{Evolution}
%%----------------------------------------------------------------------
%\label{sec:EvoInd}

Das GeneticChess System nutzt ein Standardverfahren zur Evolution der Schachindividuen.
Es wird ein Pool mit eine zweier Turnierselektion verwendet, die auf einem
Rechner läuft. Es wird keine Internet-Evolution wie in qoopy verwendet, da hier
mehrere Läufe mit verschiedenen Parametern durchgeführt werden sollten und dies
bei dem internetbasierten qoopy System schwierig ist. Da die Geschwindigkeit des GeneticChess
Systems gegenüber qoopy auch um einen Faktor von circa 50 besser ist, war auch eine
Parallelisierung für die durchgeführten Läufe nicht notwendig. Es hat sich zwar
später gezeigt,
dass eine Parallelisierung für die Evolution der stärksten Individuen vorteilhaft
gewesen wäre, jedoch war auch ohne Parallelisierung der Fitnessbewertung möglich,
 sehr gute Ergebnisse zu erzielen.

Da die Evolution von Schachindividuen sehr rechenzeitaufwendig ist, werden für
die Läufe maximale Fitnesswerte angegeben, die erzielt werden sollen. Wenn die
Zielfitness durch die Evolution erreicht wird, wird die Evolution abgebrochen.
Dies verhindert zwar eine weitere Verbesserung der Individuen, wenn das Abbruchkriterium,
die maximale Anzahl der Generationen, noch nicht erreicht wurde, jedoch wäre dies
bei den gewählten Einstellungen für die Individuen auch sehr unwahrscheinlich. 
Dies ermöglicht die Einsparung erheblicher Rechenzeiten, da die Fitnessberechung 
für das Individuum auch sehr aufwendig ist, wenn die Zielfitness
erreicht wurde.
Die Erfahrung mit evolutionären Verfahren zeigt auch, dass nach dem Auftreten eines
guten Individuum sehr viele Nachfahren entstehen, die ähnlich gut sind und
somit in unserem Fall die Zeit der Evolution erheblich erhöhen würden.


%----------------------------------------------------------------------
\subsection{Das ChessGP Gegnerprogramm}
%----------------------------------------------------------------------
\label{sub:ChessGP-Gegner}

Das \emph{Gegnerprogramm} zur Fitnessberechnung entspricht mit leichten Modifikationen
dem Gegnerprogramm, wie es im qoopy-System verwendet wird, siehe hierzu Abschnitt~\ref{sub:black}.
Eine Änderung zum Algorithmus im qoopy-System ist das Weglassen des Zufallswerts
bei der Materialbewertung. Dieser bewirkte, dass zu einer Stellung ein zufälliger
Wert in einem festgelegten Intervall von 0 bis 20 zum Materialwert
der Stellung hinzugezählt oder abgezogen werden kann. Damit wurde beabsichtigt,
das Spiel variabler zu gestalten, so dass die Gegnerprogramme nicht immer gleich
agieren. Da qoopy auf einer internetbasierten Evolution basierte, war ein variableres
Spiel bei der Auswertung wünschenswert. Dies führte jedoch dazu, dass der
Algorithmus besser, aber auch schlechter arbeiten kann und somit die Bewertung eines
Individuums auch vom Zufall abhing. Dies wurde durch die Fitnessbewertung gemildert,
die ein Individuum mehrmals gegen den Algorithmus mit gleicher Stärke spielen ließ.
In den Nachbewertungen hatte sich jedoch gezeigt, dass dies nicht ausreichend war.
Durch den Verzicht auf diesen Wert soll die Bewertung der Individuuen einheitlicher
sein, dies kann jedoch nicht ganz erreicht werden, da die Bewertung als solche dynamisch
ist und auch stark vom Verhalten des Individuums abhängt. 

Die weiteren Veränderungen betreffen nur Implementationsdetails, die keine Auswirkungen
auf das Verhalten des Algorithmus haben. Die stärkste Änderung ergibt sich durch
die Verwendung von C++ als Programmiersprache. Das qoopy-System ist in Java implementiert,
was für die Zielsetzung einer Internetevolution von Vorteil war, jedoch auch einen
stärkeren Verlust bei der Rechengeschwindigkeit bewirkte. Dies lag auch an der Bitboard
Programmierung, die in Java nicht so effizient zu programmieren ist wie in C++.
Jedoch wurden das Verhalten und der Aufbau des Gegnerprogramms nicht verändert, da
wir mit diesem Programm im qoopy System gute Erfahrungen gemacht haben.







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