 
\emph{GeneticChess}\index{GeneticChess} ist kein allgemeines optimier
GP System, sondern ein spezialisiertes System mit der Zielrichtung
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 der zentrale Motor der
Schachprogramme und kann verallgemeinert auch für viele anderen
Probleme eingesetzt werden (siehe
Kapitel~\ref{sec:State-SpaceReduktion,sec:Suchen}). Die entwickelten
Individuen werden nicht über Erweiterungen moderner Schachprogramme
verfügen, wie Eröffnungsbücher, Endspieldatenbanken, Hashtabellen, und
andere Verfahren, die die Spielstärke der Programme verbessern. Die
Praxis zeigt, dass alle diese Verfahren die Spielstärke jedes
Programms um mehrere hundert Elopunkte steigern kann, aber die
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 eine Komplettlösung des Schachproblems. 

Um diese Ziel zu erreichen wird im GP System ein allgemeines Modul einer
Suchheuristik und deren Programmfluss vorgegeben. Das Programm und seine
Module sollen sich dann automatisch innerhalb der Evolution bilden. Dazu wurde
das \emph{State-Space Individuum} entwickelt, welches einen festen Rahmen für
ein Suchprogramm vorgibt (siehe Kapitel~\ref{sec:state-space}). 
%zwei Wege verfolgt. Ein
%Weg versucht eine bekannte Heuristik durch GP Module zu
%verbessern. Als Heuristik wird der Alpha-Beta Algorithmus verwendet
%(siehe Kapitel~\ref{sec:alphaBeta}). Dieser Algorithmus ist einer der
%erfolgreichsten Algorithmen in Computerschachprogrammen und wurde in
%den letzten Jahren durch verschiedenste Heuristiken verbessert. Der
%Algorithmus lässt sich auch einfach in mehrere heuristische Module
%unterteilen, die durch das System evolviert werden. Die Wahl viel auf
%den Alpha-Beta Algorithmus einerseits weil er ein bekannter
%Algorithmus ist, der schon seit einigen Jahren analysiert
%wird. Dadurch können die Effekte und Verbesserungen der neuen Module
%leichter identifiziert und analysiert werden. 
%Der zweite Weg soll aber auch die direkte Evolution einer
%Suchheuristik für das Schachproblem sein. Dabei werden nur die

Hierzu reichen die Erweiterungen der Genetischen Programmierung, wie
sie in Kapitel~\ref{GP-Erweiterungen} eingeführt wurden jedoch auch nicht
aus. Diese Erweiterungen sind auf viele Problemstellung anwendbar. Die
Erweiterungen die aber nun vorgestellt werden sind  speziell auf
das Schachproblem ausgerichtet. Darunter fallen insbesondere die
Fitnessfunktion und viele Funktionen und Terminale. Aber auch der Aufbau
der Individuen und die Herangehensweise an die Problemlösung.
Das System wurde zwar mit dem Ziel entwickelt Schach zu spielen,
jedoch können diese Ansätze zur Lösung von Problemen auch auf andere
Probleme angewendet werden. Hierzu sind speziell Probleme gemeint wie
sie in Kapitel~\ref{sec:Problemloesung} beschrieben wurden.
Dabei handelt es sich um Probleme die mittels Suchverfahren gelöst
werden, diese werden auch \emph{State-Space Verfahren} genannt und
wie man aus Kapitel~\ref{sec:Problemloesung} ersehen kann,
können viel Probleme durch eine entsprechende Tranformation durch
\emph{State-Space Verfahren} bearbeitet werden. 



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

Das GeneticChess System, dass in den folgenden Kapitel vorgestellt
wird hat sich aus den Ergebnissen verschiedene Vorarbeiten der letzten
Jahre entwickelt. Die Ergebnisse aber auch Fehlschläge dieser System
sind in das Design und verschiedener Komponenten eingeflossen. Sie
motivierten aber auch die Suche flexiblerer und angepassterer
Individuenstrukturen um die gegebenen Probleme zu lösen. Die
Reihenfolge der Kapitel geben die zeitliche Entwicklung der einzelnen
Projekte wieder.





%----------------------------------------------------------------------
\subsection{ChessGP}
%----------------------------------------------------------------------
\label{sec:ChessGP}
normales GP und Hierarchie
~\cite{kantschik:2000:TechRep}

%----------------------------------------------------------------------
\subsection{Qoopy}
%----------------------------------------------------------------------
viel ea und wenig gp 
\cite{kantschik:2002:gecco}

%----------------------------------------------------------------------
\subsubsection{Zugbewertung}
%----------------------------------------------------------------------
\begin{description} 
\item [Spielphasenmodel] 
\item [Materialwert] 
\item [MVV/LVA] 
\item [Schlagzüge] 
\item [Schachzüge] 
\item [Promotion] 
\item [Zentrumsaktivität] 
\item [Bauernzüge] 
\item [killermoves] 
\item [Killertabelle] 
\end{description} 


%----------------------------------------------------------------------
\subsection{Villwock}
%----------------------------------------------------------------------
nur ea und auch recht schlecht




%----------------------------------------------------------------------
\section{Spezialisierte Erweiterungen für GeneticChess}
%----------------------------------------------------------------------

\emph{GenticChess} ist 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 das Ziel \emph{gut spielende}
Schach Individuen zu erzeugen zu erreichen. Auch hier wird der
Grundgedanke dieser Arbeit deutlich, in der versucht wird 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,
die mit den \emph{Standardverfahren} nicht möglich sind. So sind für
viele Problemstellungen in der Literatur und Praxis 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. Dem GP System
werden nun Funktionen, Prozeduren aber auch Datenstrukturen an die
Hand gegeben, aus denen Schachprogramme aufgebaut werden können. Im
folgenden werden nun die Erweiterungen des GP Systems besprochen
dessen Ausrichtung eine Spezialisierung und Modularisierung der GP
Individuen auf die Problemstellung bedeuten.


%----------------------------------------------------------------------
\subsection{Datenstrukturen}
%----------------------------------------------------------------------

%----------------------------------------------------------------------
\subsubsection{Brett}
%----------------------------------------------------------------------


%\begin{figure}
%\centerline{\epsfig{figure=Pictures/Graphik/tree.eps,width=12cm}}
%\caption{ Die Spielbaumdatenstruktur, auf die Individuen und Module
%des GeneticChess Systems zugreifen können.  } 
%\label{fig:spielbaum}
%\end{figure}

%----------------------------------------------------------------------
\subsubsection{Zug}
%----------------------------------------------------------------------

%%----------------------------------------------------------------------
%\subsubsection{Spielbaum}
%%----------------------------------------------------------------------
%
%
%\begin{figure}
%\centerline{\epsfig{figure=Pictures/Graphik/tree.eps,width=12cm}}
%\caption{ Die Spielbaumdatenstruktur, auf die Individuen und Module
%des GeneticChess Systems zugreifen können.  } 
%\label{fig:spielbaum}
%\end{figure}

%----------------------------------------------------------------------
\subsection{Individuen ROM}
%----------------------------------------------------------------------

Der \emph{Individuen ROM}\index{Individuen ROM} ist eine Erweiterung
des Individuums und ist ein 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
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. 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 das schlechte Werte
für die Werte auch zu schlechten Individuen führt. 




%----------------------------------------------------------------------
\subsection{Alpha-Beta Gegner}
%----------------------------------------------------------------------
\label{sub:AB-Gegner}

Der \emph{Alpha-Beta Gegner} ist ein Alpha-Beta Schachprogramm, welches als
Gegnerprogramm für die Schachindividuen genutzt wird um deren Fitness zu
bestimmen. Das Gegnerprogramm ist ein Standard Alpha-Beta Algorithmus mit
einer guten Materialbewertung und ein Zugsortierung


%----------------------------------------------------------------------
\subsubsection{Blattbewertung}
%----------------------------------------------------------------------



%----------------------------------------------------------------------
\subsubsection{Zugbewertung}
%----------------------------------------------------------------------



%----------------------------------------------------------------------
\section{Das Schachindividuum}
%----------------------------------------------------------------------

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

Die \emph{Modularisierung} einer GP Struktur~\index{Modulare GP Struktur} ist
einer wichtiger Punkt des GenticChess Systems. Die Modularisierung soll
dem System die Möglichkeit geben das Zielproblem zu lösen, indem es inLösungen
für Teilprobleme des Problems sucht. Um die Suche nach einer Lösung zu
unterstützen wird die Aufteilung in die Teilproblem nicht durch die Evolution
entwickelt, sondern wird dem System vorgeben. Hier durch wird dem System
einerseits die Möglichkeit genommen eigene Lösungswege zu finden, jedoch wird
den Individuen dadurch die Möglichkeit gegeben schneller zu Lösungen zu
kommen. 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
durch den Einsatz der Standardansätze 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.
Für das Schachproblem sind die
einzelnen Module untereinander durch eine hierarchische Beziehung
verbunden, dass heißt das ein Modul einer höheren Hierarchieebene die
Ergebnisse der Module einer niedrigeren Hierarchieebene benötigt. 

Ein hierarchisches Module 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 herrausbilden und über deren
Funktionalität zu Beginn der Evolution keine Informationen vorhanden
sind. Die Funktionalität dieser ADF's wird nur durch ihrer 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 herrausgebildet und
unterscheidet sich stark zwischen Individuen verschiedener
Evolutionsläufe. Eine weitere Methode Module in GP System zu verwenden
wurden Angeline in~\cite{angeline:94} vorgestellt. Dabei werden 
während der Crossoveroperation Teilbäume gekapselt und 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
Individuum mit den verschiedenen Schachmodulen. Jedes der Module nutzt die
Linear-Graph Struktur, obwohl bis auf das Tiefen Modul, jedes Modul die
verschiedenste 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. Denn 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 Alpha-Beta
Programme durchgeführt.


\ref{sec:ChessGP}

\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/linearTree.eps,width=12cm}}
\caption{ Aufbau des State-Space Individuums mit den einzelnen Modulen. } 
\label{fig:modulGP}
\end{figure}





%----------------------------------------------------------------------
\subsection{Materialbewertungs Modul}
%----------------------------------------------------------------------

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 eine Stellung im Spiel zu bewerten. Dies ist notwendig, da die
Berechnung nicht bis zum Matt des Spiels durchgeführt werden kann. Die
Suche muss mitten im Spiel abgebrochen werden und diese Situation muss
dann bewertet werden. Die Bewertung einer der 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 werden, 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. 

Die einfachste Materialbewertung bittet 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 auch 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 Module
stehen hierzu Funktionen zur Verfügung die folgenden Kriterien in die
Materialbewertung mit einbeziehen können:
%\board{ * * L *}
%      {* * * B }
%      { * * * *}
%      {* * * * }
%      { * * * *}
%      {* * * * }
%      { * * * *}
%      {* * * * }
%\newgame
%$$\showboard$$



\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 hat, 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 Felder mehr als 6 Bauern
        aufhalten, hat der Springer aufgrund seiner Fortbewegung
        im Gegensatz zu Läufer einen Vorteil, der durch diesen Wert
        berücksichtigt wird.
\item [Blockierter Läufer] Ein Malus, wenn im erweiterten Zentrum
        (Quadrat aus 16 Felder in der Mitte des Brettes) mindestens 3
        eigene Bauern mit der gleichen Feldfarbe wie der Läufer steht.
        Diese Bauern beeinträchtigen die Mobilität des Läufers,
        gegnerische Bauern nicht, sie können geschlagen werden.
\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 diese Kriterium
        über die Mobilität bewirkt und für den Turm über die Rochade Möglichkeit.
\item [Turm auf halboffene Linie] Ein Bonus, wenn der Turm auf einen
        Linie steht auf der sich kein eigener sondern nur ein
        gegnerischer Bauer befindet.
\item [Turm auf offene Linie] Ein Bonus, wenn der Turm auf einen
        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. Dass 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 und auch 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. Die geschieht aber immer
statisch, dass 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 Programmiere
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, ein ähnlicher Versuch wurde
in~\cite{kantschik:2000:TechRep} durchgeführt (siehe auch
Kapitel~\ref{sec:ChessGP}). Einer der Hauptunterschiede liegt jedoch
in einer festen Fitnessfunktion, so dass die Individuen nur eine
festgelegte Funktion lernen könnten. Durch den Ansatz der impliziten
Fitnessfunktion wird dem Modul die Möglichkeit gegeben eine neue
Bewertung zu erzeugen. Die Fitnessfunktion ist implizit, da die
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.  

 
\begin{description} 
\item [getFigureValue]

\item [getFigureValueAtPos]

\item [getWhiteValue]

\item [getBlackValue]

\item [getNumOfWhitePawns]

\item [getNumOfWhiteKnigths]

\item [getNumOfWhiteBishops]

\item [getNumOfWhiteRooks]

\item [getNumOfBlackPawns]

\item [getNumOfBlackKnigths]

\item [getNumOfBlackBishops]

\item [getNumOfBlackRooks]

\item [numOfWhiteFiguresInBlackCenter]

\item [numOfBlackFiguresInBlackCenter]

\item [numOfWhiteFiguresInWhiteCenter]

\item [numOfBlackFiguresInWhiteCenter]

\item [advancedPawnValueWhite]

\item [advancedKnightValueWhite]

\item [advancedBishopValueWhite]

\item [advancedRookValueWhite]

\item [advancedPawnValueBlack]

\item [advancedKnightValueBlack]

\item [advancedBishopValueBlack]

\item [advancedRookValueBlack]

\item [endgameIndex]
\end{description} 


%----------------------------------------------------------------------
\subsection{Zugbewertungs Modul}
%----------------------------------------------------------------------

Die Aufgabe des \emph{Zugbewertungs Modul}\index{Zugbewertungs Modul}
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. Den dies basiert auf einer
Suchfenster-Technik, bei der stets der Wert der zu aktuell
betrachteten Variante die besten Alternativen des weißen und schwarzen
Spielers im sogenannten Suchfenster ($\alpha, \beta$) gespeichert
wird. Je kleiner diese Fenster ist desto größer ist die Chance, das
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. 

In Kapitel~\ref{sec:Zugbewertung} werden verschiedene Wege
vorgestellt, wie 

\begin{description} 

\item [numOfAttacksBefore]

\item [numOfDefensedBefore]

\item [attackDefenseDiffBefore]

\item [numOfAttacksAfter]

\item [numOfDefensedAfter]

\item [attackDefenseDiffAfter]

\item [captureValueOfMove]

\item [captureFigureOfMove]

\item [looseValueOfMove]

\item [maxLooseValueAfterMove]

\item [maxLooseValueBeforeMove]

\item [maxCaptureValueAfterMove]

\item [maxCaptureValueBeforeMove]

\item [numOfThreatsOfSide]

\item [numOfCoverOfSide]

\item [moveFigureValue]

\item [getValue]

\item [getAggValue]

\item [getDefValue]

\item [getBoardValue]

\end{description} 

Die Dynamischen Module umfassen Aufgaben, die nicht durch eine
statische Analyse einer Stellung gelöst werden können, sondern die
dazu die Dynamik des Spiel nutzen müssen. Es wird zur Berechnung der
Ergebnisse eine Exploration im Suchbaum erfolgen, die sowohl in die
Vergangenheit des Spiel, alsauch in die mögliche Zukunft gerichtet ist.

Auflistung dynamischer Module:
\begin{itemize}
\item Zuglisten mit verschiedenen Zielsetzungen generieren. Gute Züge,
        Aggressive Züge, Defensive Züge, usw..
\item Gegneranalyse, wie hat der Gegner sich im Spiel verhalten, und
        wie kann ich darauf reagieren.
\item Zielstellungen, wie kann ich meine Zielstellungen erreichen.
\end{itemize}


%----------------------------------------------------------------------
\subsection{Tiefen Modul}
%----------------------------------------------------------------------



Das Varianten Modul berechnet die  Variante (den Zug) die
durchgeführt werden soll. Es ist der Bestandteil der
Schachalgorithmen, der in Standardverfahren durch Alpha-Beta Algorithmen
oder Negascoutverfahren gelöst wird. Diese Modul baut einen Suchbaum
auf und bestimmt in einem rekursiven Verfahren den besten Zug, daher
wird in diesem Modul die Recursive GP Struktur verwendet.

Bei anderen Version die Schachindividuen, wird diese Modul aber auch
durch einen festen Standardalgorithmus ersetzt (Diplom-Variante).
\begin{description} 

\item [currentDepth]

\item [maxDepth]

\item [numOfExpandedNodes]

\item [numOfUnexpandedNodes]

\item [isInWindow]

\item [moveRang]

\item [boardValue]

\item [moveValue]

\item [wasBeatMove]

\item [numOfThreatsOfSide]

\end{description} 


%----------------------------------------------------------------------
\subsection{Crossover und Mutation}
%----------------------------------------------------------------------





%----------------------------------------------------------------------
\section{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 Abbruchkiterium ist die Anzahl der verlorenen
Spiele. Während der Evolution wurden die Fitnessberechnung nach zwei
verlorenen Spielen beendet, diese Grenze kann durch einen Parameter bestimmt
werden. Zwei verlorene Spiele hat sich jedoch als sehr gut erwiesen, so kann
jedes Indivduum  


Zu dieser Art der
Fitnessberechnung gibt es für Schach nur zwei 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 dies auch erst erzeugen musste.  


\[

Fit(i)= \sum_{d= 0}^{MaxDepth}  \begin{cases}
                                  gauss(d+1)*result(d) > 0 & result(d) > 0 \\
                                  gauss(d)*result(d) & result(d) < 0 \\
                                \end{cases}

\]
      dGameVal= pCFitValue->blackFitAtDepth(i);
      dGameVal/=(double)(m_iGamePreDepth/2);

      if (dGameVal > 0.0)
        dBlackVal+= dGameVal*(double)(iFac+1);
      else
        dBlackVal+= dGameVal*(double)(iFac);

      iFac+=i;
    }

  iBothWin= iBothWin*1000;

  dFit= ((double)iBothWin)+dWhiteVal+dBlackVal+ ((double)iLastWinDepth*10000.0);



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

%----------------------------------------------------------------------
\subsection{Hierarchische Evolution}
%----------------------------------------------------------------------
\label{sec:HierarchEvo}


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