
\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


%----------------------------------------------------------------------
\section{How to evolve chess playing individuals?}
%----------------------------------------------------------------------
The fundamental idea is to evolve chess playing individuals.
The task to play chess is a hard problem, hand written programs
contain up to many thousend lines of code. So the question was how can
we construct a \gp-individual that at first can play chess, and second
that can be evolved in a time span which will not extend our
\emph{lifetime} and the limits of our computer power.

To solve this problem we have to identify the structure of the
individuals, the function and terminal set and also the datastructure
of the individuals. The one question was, it is possible to solve the
problem if the individual has only the datatype double or integer, or
must we provide the individual with a more advanced datastructure.
We decide to go the second way and give \gp\ the opportunity to use a
data sturcture which was implemented for chess playing individuals we
called it \emph{chess-board}~\ref{sSub:dataStruct}. 

The next question was how the individuals look like. Can we use a
common \gp-structure to solve the problem; take one \gp-program and
some adf's as the individual structure and some chess games % $$$ Partien
as fitness case. Include some chess functions to the function and
terminal set and start the evolution. We decide the this approch will
lead to a deadend, because of the complexity of hand written programs
and the time span this approach will need to evolve a simple chess
program. So we developed a hierarchical structure for the individual.
Each part of an individual solves a subproblem so the hole individual
can play chess see section~\label{sub:ChessInds}.

After we have identitied the different modules of the inidivuduals we 
have to create the fitness cases and the fitness function for this
modules see section~\ref{sub:FitCases}.

\subsection{Architecture of the Chess Individuals}
\label{sub:ChessInds}

The main goal of our work is the creation of chess playing
\gp-individual. The question was how would the \gp-individual 
looklike that can play chess.

We decided to split the task of the individual into three sub task which
could be evolved separately. Therefore it is a good advice to examine
what skills might be typical for a good human chess player and hand
written computer chess programs. Out of this skills we have identified
this task which might be solved by  evolved \gp-programs.

Basically, the most relevant tasks are, 
\begin{enumerate}
\item \label{it:openingTheory} a \emph{opening theory}, a good
        knowledge of modern opening theory,
\item \label{it:middleTheory} a \emph{middle game theory}, recognize
        and remember specific piece constellations in the middle game
        and use a good tactic fitting to the situation,
\item \label{it:endingTheory} a \emph{ending theory}, the knowledge of
        the ending theory, 
\item \label{it:positionEval} a \emph{position evaluation}, evaluate a
        given chess position both carefully and correctly,   
\item \label{it:planEval} a \emph{plan evaluation}, figure out a plan
        which best fits to the given position, 
\item \label{it:variantsEval} a \emph{variant evaluation}, find out
        what are possible consequences given a position and an
        appropriate plan. What position variants can emerge in the
        ongoing game? Which variant is the best?. 
\end{enumerate}

The \gp-individuals do not to tackle aspects of the \emph{opening
 theory}, the \emph{middle game theory} or the \emph{ending theory}.
We do not include this possibility to our \gp-individuals for two
reasons, first we are at a starting point for the creation of chess
programs with \gp\ and so we like to begin with core program which
can play chess which is solved in traditional program by a minimax
tree search. And second the current programs try to solve this
problems with knowledge based databases, so you need first a core
program to play chess and than use this modules to assist the core
program. 



The focus of the \gp-individual lies on aspects of the 
\emph{position evaluation}, the \emph{plan evaluation} and the 
\emph{variant evaluation}. These three aspects
inspired a hierarchical structure for the architecture of our
\gp-individual (see fig. \ref{fig:chessIndStruct}). These modules are the
core modules of chess program and human chess players. 
Please note that it is quite natural to choose a hierarchical
structure out of this modules. Because for developing
plans it is useful to be able to evaluate positions as part of 
the plans with respect to some criteria. On the other hand,
calculating the variants is a directed search if some 
plans and position evaluation subroutines are available.

\begin{figure}
   \centerline{\epsfig{figure=chessIndividualStruct.eps,width=12cm}}
   \caption{Structure of a chess individual.}
   \label{fig:chessIndStruct}
\end{figure}


%$$$ Formulierung gefaellt mir nicht
We name the different levels of the individual in the following manner:
\begin{itemize}
\item The \levelA is the position evaluation module of the individual.
\item The \levelB is the plan evaluation module of the individual.
\item The \levelC is the variant evaluation module of the individual.
\end{itemize}

The \levelA programs are the first level in the individual hierachie,
the \levelB programs are the second level. These programs can use the
\gp programs of the first level in their terminal set, so the program
can use the preprocessed information of the underlying level. The last
level of our architecture is \levelC. Together the \gp-programs create
the chess playing individual.   

The \levelA contains several \gp-programs which can be used from programs of
\levelB and \levelC. \LevelB contains  \gp-programs which can be used form programs
of \levelC. The evolution of a chess playing individual of \levelC is seperated into
the evolution of the three parts of the  
Each level of the hierachie will be evolved one after the other

For developing plans it is useful to be able to evaluate positions as part of 
the plans with respect to some criteria. On the other hand,
calculating the variants is a directed search if some plans and
position evaluation subroutines are available. 


\subsubsection{\LevelA\ Module}


The \levelA is the position evaluation module of the individual.
Little is known about human position evaluation procedures. 
%But it can be said that those of experts are complicated total
%orderings over all chess positions.
In current chess programs the position evaluation is a function which
maps the pieces on the chess board to a real value. Simple procedures
only calculates the summe of all piece on the board, where the pieces
of the opponent have a negative value. More advanced procedures also
take the position of the pieces into account. Computer
programs only use one position evaluation, but chess expert's try to
have a different approach by using different \emph{procedures} for
the position evaluation.
We try to imitate an expert's position evaluation by evolving several functions 

\[ posEval_{a_i} : LP \rightarrow \Re 
   \mbox{, with $a_i$ specifying a certain evaluation aspect.} \]

This is done in the first level of the evolution module, the {\em
static evaluation}. It is called static because each of the evolved
functions has only access to the given position. There is no history
or prediction of chess positions at hand. Let all the evaluation
functions together form the set \textrm{POS\_EVAL}: 
\[ \mathrm{POS\_EVAL} = \{ posEval_{a_i} \mid i \in I_\mathrm{I} \} \]

We have develop five different position evalution procedures. Each of
this procedures returns a certain prospect of a given chess position.
\begin{enumerate}
\item A \emph{position evaluation}, is a simple position evaluation
        procedure which calculates the weight of the piece of each
        side and substracted the value of the opposite side.

\item A \emph{clever position evaluation}, returns a value of the
        material on the board. Beside a simple counting of the values
        of the pieces the 

\item A \emph{aggressiv evaluation},

\item A \emph{defensiv evaluation},

\item A \emph{complexity evaluation},

\end{enumerate}


\subsubsection{\LevelB\ Modules}


The next task is about finding plans. Again, human behavior is hard to
describe. Personal preferences play a major role, for example the will
to attack or defense. %$$$??? 
A trained chess player often has several plans at hand with different
intentions. But it is crucial to ensure that the current position has
been analyzed well. That is why level $2$ of our evolution module, the
{\em semi-dynamic evaluation}, is designed to be able to make use of
the static evaluation of level $1$.  Several functions are evolved in
level $2$ each of them results in a set of legal moves representing a
specific plan: 

\[ planEval_{c_i} : LP \times \mathrm{POS\_EVAL} \rightarrow
L_{LP}^{c_i}  \mbox{, with $c_i$ describing a plan criteria.} \] 
\[ \mathrm{PLANS} = \{ planEval_{c_i} \mid  i \in I_\mathrm{II} \} \]

In the evolution process the level-$2$ individuals must not execute
operations modifying the position, and (for example) evaluating the
result is not permitted. These individuals only have a static view by
this means, however, this level provides a semi-dynamic evaluation of
plans because of their fitness functions: The fitness of an individual
of this level is determined by comparing its results with the dynamic
calculated fitness values in the database. 

\subsubsection{\LevelC\ Module}



In contrast to position evaluation and tactical plan finding, human
beings are not excellent at calculating the variants. This task can be
done perfectly by powerful computers which perform a more or less
costly search  in the (appropriate) game tree. Whereas {\em Deep Blue}
(CopyrightBemerkung) is able to evaluate $200$ million nodes within a
second, international tournament players often analyze not more than
$20$  variant positions  per move. Nevertheless it is a kind of
sparse, but intelligent tree search with a minimax
strategy\footnote{Minimax strategy or its variants are appropriate for
chess ???is ??? a  zero-sum situation.}  they perform. Again, we
want to imitate human behavior and evolve a sparse  tree search in
level $3$. The structure of a minimax tree search is imposed 
(???), but node expansion, if any, is due to evolution. So is the
evaluation at the leaves. For that reason level-$3$ individuals are
allowed to use level-$1$ and level-$2$ individuals: 

\[ variantCalc : LP \times \mathrm{POS\_EVAL} \times \mathrm{PLANS}
\rightarrow LM \] 


\begin{figure}
\centerline{\epsfig{figure=evolutionmodule.eps,width=12cm}}
\caption{The structure of the evolution module.}
\label{fig:evoModule}
\end{figure}
The fitness of a level-$3$ individual is determined by competition
with other level-$3$ individuals and measured with the Elo number
system. Level-$3$ individuals have a dynamic view and together with a
chess rule component and an user interface are capable of playing
chess.




\begin{figure}
   \centerline{\epsfig{figure=chessIndLevelC.eps,width=12cm}}
   \caption{Structure of a chess individual.}
   \label{fig:chessIndLevelC}
\end{figure}

\subsubsection{The Datastructures \emph{chess-board}}
\label{sSub:dataStruct}



This component relays on the
data structure and chess rule knowledge, both provided by the so-called
\emph{chess-board}. %$$$??! 
The data structure represents a chess board including all pieces. In
addition, some extra-information about the game progress such as
castling, en passent pawns and pawn transformation are stored. The
rule knowledge allows to decide whether a move is legal according to
the chess rules or not. 

The data structure represents a chess board including all pieces. In
addition, some extra-information about the game progress such as
castling, en passent pawns and pawn transformation are stored. The
rule knowledge allows to decide whether a move is legal according to
the chess rules or not.

\begin{figure}
   \centerline{\epsfig{figure=dataStruct.eps,width=12cm}}
   \caption{The datastructure of the chess individuals in our system.}
   \label{fig:dataStruct}
\end{figure}




\subsection{Database}

In the \ChessGP database a number of legal chess game positions are
held, together forming the set $\mathcal{P}$. They serve as our
fitness cases. These fitness cases are judged(examined, evaluated) on
several criteria functions $c\!f$ of two different types. Criteria functions
of type \textrm{I} map (the universe of) legal game positions denoted as
$LP$ $\mathcal{U}$ $\mathcal{L}\mathcal{P}$ ($\mathcal{P} \subset LP$)
onto real-coded numbers. Whereas type \textrm{II} criteria functions
map $LP$ onto a set of chess moves.  

More formally, for some criteria $\phi_i$ we define type \textrm{I}
criteria functions 
%
\[ c\!f^{\mathrm{I}}_{\phi_i}: LP \rightarrow \Re. \]
%
With the set of legal moves $LM$ which are dependent on a valid chess Position $lp$
%
\[ LM_{lp} = \{ (lp,lp') \mid lp,lp' \in LP \, \wedge \, \exists r \in
C\!R: r(lp)=lp' \} \]
%
--  $C\!R$ denoting the set consisting of all chess rules -- and subsets 
%
\[ L^\phi_{lp} = \{ m \mid m \in LM_{lp} \, \wedge \, m \mbox{ meets
criteria } \phi \}\]
%
we can define type \textrm{II} criteria functions
%
\[c\!f^\mathrm{II}_{\psi_i}: LP \rightarrow L^{\psi_i}_{LP}. \]
%
%$\mathcal{P} \subset LP$
%$\mathcal{P} \subset \mathcal{U}$

Let $I_\mathrm{I}$ be the index set for type \textrm{I} criteria functions and $I_\mathrm{II}$ the index set for those of type \textrm{II}.
Then the training set $\mathcal{T}$ of the fitness values stored in
our database can be formalized as follows:
%
\[ \mathcal{T}= T_\mathrm{I} \cup T_\mathrm{II}, \mbox{ with}\]
\[ T_\mathrm{I}= \bigcup_{p \in \mathcal{P}} \bigcup_{i \in
I_\mathrm{I}} (p,c\!f^{\mathrm{I}}_{\phi_i}(p))\]
\[ T_\mathrm{II}= \bigcup_{p \in \mathcal{P}} \bigcup_{i \in
I_\mathrm{II}} (p,c\!f^{\mathrm{II}}_{\psi_i}(p)) \]
%

There are at least 3 requirements for $\mathcal{T}$



~\cite{kantschik:2000:TechRep}

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



%----------------------------------------------------------------------
\subsection{The Chess Individuals}
%----------------------------------------------------------------------


We use an alpha beta algorithm~\cite{schae89} as the kernel
of an individual which is enhanced by gp and ea-modules. The goal
of these modules is the evolution of smart 
strategies for the middle game. So no opening books or endgame
databases have been used to integrate know\-ledge for situations where
a tree search exhibits weak performance. 
Also, GP/ES individuals always play white and standard
black players are employed to evaluate the individuals. The black
players are fixed chess programs which think ahead a certain number of 
moves  and then choose the best move (according to the minimax-principle,
restricted by the search horizon)~\cite{beal99d,birmingham77}. 
The individuals are restricted in size to an average of 100.000 nodes in
the search tree per move.
Two reasons are behind this decision:
%\begin{enumerate}
(i) to allow for a reasonable speed of evolution and
(ii) to allow for enough space.
%\end{enumerate}

Like standard chess programs,  individuals perform a tree
search~\cite{iida95a}. In particular, they use an
alpha-beta-algorithm. Three parts of this algorithm are 
evolved: 
\begin{itemize}
\item The Tiefen Modul, which determines the remaining search depth for the
        given node.
\item The sortier Modul, which changes the ordering of all possible moves.
\item The Positionsmodul, which returns a value for a given chess position.  
\end{itemize}

Evaluation of a chess individual is performed in the following
way: The Tiefen Modul determines the remaining  depth for the
current level in the search tree. If the move is a leaf then the
Positionsmodul is called and calculates a value for this  position.
Otherwise the node (move) will be expanded and all possible moves will
be calculated. Subsequently the sortier Modul for these moves is
called and changes the order of the moves, so that moves which are
more important will be evaluated first in the search tree.

\begin{table}
\caption{The pseudocode show the $\alpha\beta$ algorithm with the
evolutionary parts (bold).}
\begin{center}
\begin{tabular}{rp{7cm}}
  1 & $\alpha \beta_{MAX}$ (position $K$; integer$\alpha, \beta$)  \\
  2 & \BEGIN  \\
  3 & \hspace{0.2cm} integer $i, j, value$ ;\\
  4 & \hspace{0.2cm} $nodes= nodes + 1;$ \\
  5 & \hspace{0.2cm} \IF POSITION\_DECIDED($K$) \THEN \\
    & \hspace{0.3cm} \RETURN \textbf{Positionsmodul}($K$); \\
  6 & \hspace{0.2cm} \IF $(depth$ == $maxdepth)$ \THEN \\
    & \hspace{0.3cm} \RETURN \textbf{Positionsmodul}($K$);  \\
  7 & \hspace{0.2cm} \textbf{Tiefen Modul} restdepth;\\
  8 & \hspace{0.2cm} \IF $(((restdepth$ == $0)$ OR \\
    & \hspace{0.3cm} $(nodes$ $>$ $maxnodes))$ \\
    & \hspace{0.3cm} AND $depth >$= $mindepth$)  \THEN\\
  9 & \hspace{0.4cm} \RETURN \textbf{Positionsmodul}($K$); \\
 10 & \hspace{0.2cm} determine successor positions $K.1, \ldots, K.w$;\\
 11 & \hspace{0.2cm} \textbf{sortier Modul}($K.1, \ldots, K.w$);\\
 12 & \hspace{0.2cm} $value= \alpha$;\\
 13 & \hspace{0.2cm} \FOR $j= 1$ \TO $w$ \DO\\
 14 & \hspace{0.2cm} \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, \alpha\b,eta_{min}(K.j,value,\beta))$;\\
 17 & \hspace{0.2cm} \hspace{0.2cm}  $restdepth$= $restdepthBackup$\\
 18 & \hspace{0.2cm} \hspace{0.2cm}  \IF $value \geq \beta$ \THEN \\
    & \hspace{0.2cm} \hspace{0.3cm} \{ ADJUST KILLERTABLE; \\
    & \hspace{0.2cm} \hspace{0.3cm} \RETURN $value$\}; \\
 19 & \hspace{0.2cm}  \END \\
 20 & \hspace{0.2cm}  \RETURN $value$ \\
 21 & \END    \\
\end{tabular}
\end{center}
\label{tab:program}
\end{table}

%----------------------------------------------------------------------  
\subsection{\DepthMod}
%----------------------------------------------------------------------


\begin{table}[!h]
\caption{The terminal set of the Tiefen Modul with a short
description. With  chess-specific operations the Tiefen Modul receives
 chess knowledge.}  
\label{tab:depthModTerm}
\begin{center}
\begin{tabular}{|l|p{4.5cm}|}
\hline 
{\small terminal }& {\small description of the terminal }\\
\hline \hline   
{\small accumulator } & {\small default register for all
functions. }\\ \hline   
{\small  level register }& {\small special register which holds
information of the current level in the search tree. } \\ \hline 
{\small  search register} & {\small special register which holds
information of the search. }\\ \hline 
{\small game register }& {\small special register which holds
information of the game.} \\ \hline 
{\small search depth} & {\small returns the current search depth of the tree.}  \\ \hline 
{\small search horizon} & {\small value of the current search horizon. }\\ \hline 
{\small piece value} & {\small value of a piece given by the accumulator.}\\ \hline 
{\small captured piece} & {\small value of a captured piece, if the last
 move was a capture move. }\\ \hline 
{\small alpha bound} & {\small value of  alpha bound.}\\ \hline 
{\small beta bound} & {\small value of  beta bound. }\\ \hline 
{\small move number} & {\small  number of  current move, given by then
move ordering module.} \\ \hline 
{\small \# pieces} &  {\small number of knights, bishops, rooks and pawns of the
 board. }\\ \hline 
{\small \# expanded nodes} & {\small number of expanded nodes for the current position,
 in percent.} \\ \hline 
{\small value of move} & {\small value of the move which led to the current
 position, given by the sortier Modul.  }\\ \hline 
{\small branching factor} & {\small number of move of the current position.}\\ \hline 
{\small position score} & {\small value of the current position, given
 from the Positionsmodul.}\\ 
\hline

\end{tabular}
\end{center}
\end{table}


The Tiefen Modul decides for each  position 
whether the search tree should be expanded or not. In other words the
Tiefen Modul decides whether a move is worth to 
be expanded and to what depth. 
Normally chess programs have a fixed search
horizon~\cite{plaat96}. This means, that 
after a certain number of plies the expansion in the search tree will
be terminated. 
In contrast, the Tiefen Modul should give the individual a higher
flexibility in the search to avoid the search horizon effect. 

The Tiefen Modul has two limitations, the search depth and 
the amount of nodes used in a search tree. The maximal depth is 10 plies
but if all moves until ply 10 would be executed approx. $10^{14}$
nodes should be expanded. Therefore the amount of
expanded nodes in the search tree was limited to 100.000 nodes on average per
move. On average means, that the individual might save nodes in a
particular period of the game
and spend them later.


The Tiefen Modul is a GP program of branched operation sequences. The
structure is an acyclic graph where each 
node holds a linear program and each if-then-else condition makes a
decision which node of the program will be executed next (see
section~\ref{linGraph}). 
Its function set holds very simple functions % (arithmetical, moving, storing),
but its terminal set is more chess-specific, see
tables~\ref{tab:depthModFunc} and ~\ref{tab:depthModTerm}.  

\begin{table} [!h]
\caption{The function set of the Tiefen Modul with a short
description. No function of the set has chess knowledge.} 
\label{tab:depthModFunc}
\begin{center}
\begin{tabular}{|l|p{4.5cm}|}
\hline 
{\small function} & {\small description of the function }\\
\hline \hline  
{\small +, -, * /} & {\small arithmetic function; result is written to
the accumulator register.}  \\ \hline  
{\small incHorizon} & {\small function to increment the search depth by one, but
  the search depth can only increased by 2 pre level.}\\ \hline  
{\small decHorizon} & {\small function to decrement the search depth by one, but
  the search depth can only decreased by 2 pre level.}\\ \hline  
{\small sine} & {\small the sine function. }\\ \hline  
{\small sigmoid} & {\small the sigmoid function $ \frac{1}{1+e^{-operand}}$}\\ \hline  
{\small store in level reg.} & {\small stores the operand in the level register.}  \\ \hline  
{\small store in game reg.} & {\small stores the operand in the game register.}\\ \hline  
{\small store in search reg.} & {\small stores the operand in the search register.}\\ \hline  
{\small load }& {\small load the operand to the level, game or search register.} \\ \hline  
{\small if} & {\small if the condition is true a terminal will be executed.  } \\
\hline
\end{tabular}
\end{center}
\end{table}

The depth module does not define the depth of search directly, rather it
modifies how much depth is left for searching. It can be incremented or 
decremented by the operation \emph{incHorizon} and \emph{decHorizion},
or stay untouched. The rest depth is initialised at 2. Once a move is
executed the rest depth is decremented by 1. 




%----------------------------------------------------------------------
\subsection{Stellung}
%----------------------------------------------------------------------
 
The Positionsmodul of an individual calculates a value for the position. 

The Positionsmodul is a fixed algorithm which evaluates the position by using
evolved values for the different chess pieces and some structural
value of a check. We used a simple \ea\ to evolve these
values. The idea of this module is to find a better set of parameters
than a fixed position evaluation algorithm would provide. Values of  hand-written
programs are determined through experience of the programmer or 
by taking parameters from  the literature.

Our \ea\ evolves the following weights for the position evaluation
algorithm:
\begin{itemize}
\item Values of  different pieces, e.g., pawns, bishops, queen, king [0-1000].
\item  Bishops in the initial position are punished [0-30].
\item  Center pawn bonus: Pawn in the center of the chessboard gets
        a bonus [0-30].
\item  Doubled pawn punishment: If two pawns of the same color are at
        the same column [0-30].
\item  Passed pawn bonus: A pawn having no opponent pawn on
        his and the neighboring columns [0-40].
\item  Backward pawn punishment: A backward pawn has no pawn on the
        neighboring columns which is nearer to the first rank [0-30].
\item  If a pawn is near the first rank of the opponent it gets a
        promotion bonus [100-500].
\item  Two bishops bonus: If the check position has both bishops of
        the same color then it  gets a bonus [0-40].
\item  A knight gets a mobility bonus, if it can reach more then 6
        fields on the board [0-30].
\item  Knight bonus in closed position: A closed position is defined
        if more than 6 pawns occupy the center of the board. The
        center consists of
        the 16 fields in the center of the board [0-40].
\item  Knight punishment: If opponent pawns are on each side [0-50].
\item  Rook bonus for a half open line [0-30]: A half open line is
        a line with no friendly pawn that does have an enemy pawn. 
\item  Rook bonus for an open line [0-30]: An open line is a line without a
        pawn on this line. 
\item  Rook bonus for other position advantages [0-20].
\item  Rook bonus: If a rook is on the same line as a passed pawn [0-30].
\item  King punishment, if the king leaves the first rank during the
        opening and the middle game [0-20].
\item  Castling bonus, if castling was done [0-40].
\item  Castling punishment for each weakness of pawn structure [0-30].
\item  Castling punishment, if the possibility was missed [0-50].
\item  Random value, this is a random value which will be added or
subtract from the position value [0-30].
\end{itemize}  


The structure of the position evaluation algorithm for the 
chess individual and the black player is identical. However there is a
difference: Values for individuals are evolved, values for black
players are predefined and fixed. 

%----------------------------------------------------------------------
\subsection{Sortier Modul}
%----------------------------------------------------------------------

The sortier Modul of an individual orders the moves for each chess
position by
assigning a real number to every possible move. Moves are sorted
according to these values and moves will be expanded by this order.
The value of a move is the sum of several weighted features of the move. 
%The weights are evolved by a simple \ea.

An \ea\ evolves the following weights for the sorting algorithm:
\begin{itemize}
\item Piece values in the opening: Each
        piece is assigned  a value which reflects how important this piece
        is in the opening. 
\item Piece values in the middle game: Each
        piece is assigned  a value which reflects how important this piece
        is in the middle game. 
\item Piece values in the end game: For the end game each piece is
        assigned  another value.
%\item Piece value:
%\item No Victim:
\item Most valuable victim/Least valuable aggressor: The ratio of
aggressor and victim move values is calculated. A position with a
high ratio is better than with a smaller value. 
%\item Add bonus
%\item Upper bound
\item Check: If the move leads to a check position then the move
fulfilling this feature get a bonus.
\item Capture move: These are moves which can capture a piece of the opponent.
\item Pawn moves that can attack a piece of the opponent.
\item Pawn moves that do not attack a piece of the opponent.
\item Pawn moves that lead to a promotion of a queen.
\item Center activity: Pieces which are in the center of the chess
board gets a bonus.
\item Killer moves: Killer moves are moves which lead to a cut in the
search tree. The table contains the last 4 killer moves. The table will be
filled during the search, and if a move is in the killer table it
gets a bonus.
%\item Killermove table: 
\end{itemize} 

Based on these weights, the value for moves will be calculated. 
Sorting of the moves is very important for the \ab search
algorithm. If the best move is expanded at first,  the following
move must not be expanded. A very good sortier Modul results
in a better performance of the \ab
algorithm. 


%----------------------------------------------------------------------
\subsection{GP structure of the Tiefen Modul}
\label{linGraph}
%----------------------------------------------------------------------


The depth module of an individual, as illustrated in
Figure~\ref{fig:linGraph}, is
represented by a program with nested if-then-else
statements~\cite{kantschik:2001:EuroGP}. This
representation has been developed with the goal of giving a GP-program
greater flexibility to follow different execution paths for different
inputs. It also  achieves a  reuse of the evolved code more frequent
than is the case in linear GP~\cite{nordin:linGp,nordin2}.


A program consits of a linear sequence of statements and if-then-else
statements, that contain 
a bifuration into  two sequences of statements. Nested if-then-else
statements are allowed up to a 
constant recursion depth. The resulting  structure is a graph where each node
 contains a linear GP program and a decision part. During the execution of the
program only one path of the graph will be executed for each input.



%The \linGraph representation has been developed with the goal to give a
%\gp-program a greater flexibility to develop different execution path for
%different inputs. 

%For tree or linear based programs the interpreter always executes the
%same nodes (functions) for each input.The exception here may be the \emph{if-then} nodes 
%in tree and linear based individual, but for linear based programs the instruction
%only forces the interpreter to ignore a certain number of nodes. This means 
%that the rest of the evaluated functions are always the same, but for \linGraph-programs
%the \emph{then} and \emph{else} part contains different functions, which will
%be evaluated. For tree based programs the \emph{if-then} nodes has a effect
%which is more like the effect for \linGraph\ based programs, but here we predefine
%a certain structure of the programs and it is complicated to create a equivalent
%program flow with a tree-based program. 
%\textbf{I have to write here something why lintree is better than tree or delete the hole part.}

%However, a program may contain
%many decisions and each decision calls another part of the
%program code. So the program flow of this strucutre is more
%natural, than linear or tree \gp-programs, similar to the program flow
%of hand written programs.


  \begin{figure}
  \centerline{\epsfig{figure=linGraph.eps,width=8cm}}
  \caption{The representation of the GP program, which is a graph
  structure. The squares represents the linear programs and the
  circles represents the if-then-else decisions. }
  \label{fig:linGraph}
  \end{figure}



Crossover of two programs of this type can be realized in
different ways. We have chosen the following ones. In each program a
sequence of statements is selected first. In case of selected
if-then-else-statements, the associated statements of the then- and
else-parts are selected too. Then the selected sequences are swapped.
Secondly, a swapping of branch-free sequences is allowed for 
an exchange of information between individuals.

Mutation is performed subsequent to crossover or independently from
it. There are two types of mutation operators. The first one performs a
crossover with a randomly generated individual. The second one selects
a sequence of statements (in case of if-then-else-statements including
the statements belonging to the associated then- and else-parts). Afterwards
each statement other than an if-then-else one will be mutated with an
adjustable probability (see \cite{kantschik:2002:EuroGP}).



%----------------------------------------------------------------------
\subsection{Evolution}
%----------------------------------------------------------------------

Evolution is based on populations of several individuals. Each
individual has to be evaluated by dertermining its fitness. A fitness case in 
our system is a chess game and an individual has to play several
chess games before  fitness can be assigned. We
used the approach of distributed computing~\cite{book:disComp1} to 
allow for enough computing power. We developed the \qoopy system in
order to spread our task
among the internet. 
As opponents of GP/ES-programs chess programs with fixed depth
were used.
Fitness was calculated based on the number of wins, loses and draws
against these opponents. 

In the following sections we describe this system in more detail.

%----------------------------------------------------------------------
\subsection{Internet-wide evolution based on \qoopy }
%----------------------------------------------------------------------


\qoopy is an environment for \emph{distributed computing}
tasks~\cite{book:disComp1,book:disComp2}. It is possible to develop
distributed programs 
for the \qoopy environment and use \qoopy to run these programs.

The first application of \qoopy is \Evochess, a distributed
software system which creates new chess programs in an evolutionary process. 
After \qoopy is installed on a maschine each
participant  runs a deme containing a variable number of
individuals (default value is 20). In each deme  evolution begins
and, during 
the evolution, individuals might migrate between  demes. \qoopy provides
the necessary infrastructure for  communication between  demes and the
connection to an application server. 

The application server is necessary because \qoopy has to register
users being online to let them connect to each other and to exchange
data. The server holds results of the internet evolution, and
each deme sends its best individuals and other statistics back to the 
server on a regular basis.


%----------------------------------------------------------------------
\subsection{Fitness evaluation}
%----------------------------------------------------------------------

The fitness of an individual is a real number between 0 and 15,
with higher values corresponding to better  individuals.
In order to determine fitness, individuals have to play chess
games against fixed algorithms of strength 2, 4, 6, 8, 10, 12 and
14. For fitness evaluation an individual always plays white
(see~\ref{sub:black}).    

The result of a game is a real number between -1 and 1. It is 1 in
case that the individual wins the game, -1 if the standard algorithm
wins the game and 0 in case of draw. Sometimes it is obvious that 
one side can win or that the game has to end draw. In such a case
the game is stopped to save time. Sometimes games 
are aborted because nothing happens anymore. In this case 
the position is evaluated and the result reflects the advantage of
white (positive) or black (negative) $[-1,..,1]$. 

Fitness is initialised with a value of 1. Resulting values are
weighted with the number of games played relative to the strength of
the opponent. If, e.g., the individual loses twice and wins once 
against an opponent of strength $6$ $(-1, -1, 1)$, this results in values
$(5.0, 5.0, 7.0)$, and fitness is $5.667$.

In general, the fitness of an individual is calculated by the
following function: 

\[
 fitness= \frac{\sum_{j \in \mathcal{C}}^{m} \sum_{i=1}^{n} 
        \text{class}_{j}^{\text{of
        result$_{i}$}}+\text{result}_{i}}{n*m}
\]

Classes $\mathcal{C}$ are the classes with wins, draws and losses
of the individual. These classes lie in an interval whose
borders are defined by the following rules:  
\begin{itemize}
\item If an individual wins all its games up to class $i$, these
        results are ignored. 
\item If an individual loses all its games from class $i$ to the highest
        class, these results are ignored. 
\end{itemize}

For example if an individual $i$ wins all games of  classes 2,4, and
8, and has wins, draws and losses in the classes 6 and 10, and loses all
game in the classes 12 and 14,  $\mathcal{C}_i$ holds the classes 6,8
and 10. The first rule defines the lower border of the interval (4), 
and the second rule defines the upper border of the
interval (12). The first rule does not hold for class 8
because in class 6 the individual has had a draw or loss.

In general, the fitness of an individual is calculated in four phases.
Thus weak individuals can be dropped from
fitness evaluation in the first or second phase. Fitness
evaluation in phase three and four is very CPU time expensive and we try to
reduce the computation time by removing inviable programs.

In phase one the individual plays two games against 2. If the individual
is very weak it can be identified by the fitness function and replaced
immediately. 
In the second phase the individual plays against 4, 6, 8 and
10. If the fitness is at least 4.5 at the end of phase two, the
evaluation is continued into phase three.  
In phase three the individual plays 1-2 games against 2, 4, 6, 8 and
10. Successful individuals might  skip games against 2 and 4. 
These are individuals which win each game up to strength 6 and receive good
results in games against 8 and 10.
In phase four games are performed against 12 and 14. Only the best
individuals will arrive in  this phase, however. Games
against the standard algorithm of class 12 and 14 are very expensive.

For to play more than twice against class 12 (or 14) it is required to
win in one of the two games before. Every draw results 
in $1$ point, every loss in $2$ points. If the individual has more
than 6 (5) points it does not play any more against class 12 (14). If
the individual is good enough it will play 4 times against 12 and then 
3 times against 14. 



%----------------------------------------------------------------------
\subsection{Opponents of the individual (black players)}
%----------------------------------------------------------------------
\label{sub:black}

The opponents of individuals are chess programs which can
traverse the search tree until a fixed  depth. We use these
players to calculate the fitness of an individual, by playing against
 fixed programs of  different search depth.
Fixed programs can play to a depth of 1, 2, 3, 4, 5, 6 and 7. Each of
these programs defines a corresponding fitness class of 2, 4, 6, 8, 10, 12 and
14. The value for a fitness class is the search depth multiplied
with 2, so that an individual which defeats an individual of class 4 but
loses against an individual of class 6 can be inserted into class 5.

The GP/ES individuals use a position evaluation of the same 
structure and the same criteria - but their weights are determined by the
individual's genotype. 
%Every position value is randomly 
%modified. Like this the behaviour is not deterministic. The random
%factor is very restricted - it could not reach the value of a half a
%pawn for instance.  

To reduce the number of nodes of the game tree
an f-negascout algorithm~\cite{rein89} combined with iterative
deepening is performed. The f-negascout algorithm is an improved 
variant of alpha-beta, which is the most wide-spread tree search
algorithm. Iterative deepening performs a search to depth $d-1$ before
searching to depth $d$ (recursively). In addition, so-called killer moves are
stored and tried first whenever possible. Killer moves are moves which
result in the cut of a subtree. This means that much of the game tree
can be discarded without loss of information!  


%----------------------------------------------------------------------
\subsection{Results}
%----------------------------------------------------------------------


  \begin{figure}
  \centerline{\epsfig{figure=NodesTiefenAnstiegWK.eps,width=7cm}}
  \caption{Average number of nodes used in the
  search tree for different search depths. For search depth 6 the plot
  shows a large difference between a random individual and an evolved
  individual. Even the f-negascout search algorithm requires more
  recources  than an evolved individual. The data are average
  values of 50 games.}
  \label{fig:nodesDepth}
  \end{figure}


  \begin{figure}
  \centerline{\epsfig{figure=NodesSpielverlaufBIWK.eps,width=7cm}}
  \caption{Box plot diagram of average number of
  used nodes during a game with one of an evolved individual,
  average over 50 games. The bar in the grey boxes is the median
  of the data. A box represents 50 \% of the data, this means that 25
  \% of the data lies under and over a box. The smallest and biggest
  value is a small bar which is connected to the box. The circles
  represents outliers of the data. } 
  \label{fig:GameRunInd}
  \end{figure}

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

%  \begin{figure}
%  \centerline{\epsfig{figure=leafbarplotD5WK.eps,width=10cm}}
%  \caption{The figure shows what happens if we use the Positionsmodul
%   of a evolved or random individual in a standard \ab-chess
%  program. We made 500 test with five random modules and three evolved
%  module for a search depth of 5. The diagram show that the best
%  evolved module won 70 \% of the game against a program with a
%  standard position module. The analysis also shows that the random
%  module comparable to the standard position module, this happens
%  because we have restricted the values for the module. }
%  \label{fig:leafModul}
%  \end{figure}


In this section we describe the current results of an ongoing evolution
on the internet.

First we look at the evolved individuals and what they achieved
in terms of computation time.
Figure~\ref{fig:nodesDepth} shows the number of nodes examined in the
search tree of a random individual, an evolved individual and the
f-negascout algorithm (the opponent of an individual is always an
f-negascout algorithm). The figure shows that a random
individual calculates four million nodes with a search tree
of depth 6. The f-negascout algorithm needs one million nodes. An
evolved individual only needs 250.000 nodes. So evolution has
managed to create individuals which perform a very efficient search
through the tree. 

Figures~\ref{fig:GameRunInd} and \ref{fig:GameRunRand} show the
number of search nodes visited during a game as a box plot diagram,
using data of 50 games. The figures show that 
most nodes during a game will be used between ply 10 and 60. They also
show that evolution advances most most quickly when cutting down the
number of searched nodes in this area. Evolution has managed to
create individuals with fewer nodes that are stronger than the random
individuals. 


%Our individual are created out of three different modules, we were
%also interested in the performance of one module and not the whole
%individual. Therefore we tested the position module in the standard
%f-negascout algorithm. The figure~\ref{fig:leafModul} shows the
%performance of a f-negascout program which five different random
%modules and three evolved modules against a f-negascout algorithm with
%the standard position module. The test shows that each f-negascout
%algorithm with a evolved position module has a better performance than with a
%standard position module. In the best case the algorithm with the
%evolved module wins 69\% of the games against same algorithm with the
%standard position module. It is interesting that even with a random
%module the algorithm sometimes performs better. This happens because
%we restricted the possible values of the module, so that even a random
%module can not create a to bad analysis of a position. This shows that
%the standard values for the position evaluation in chess can be
%improved by evolutionary methods.


The other aspect of the evolved chess programs is the quality of the
individuals.
Currently evolution succeeded to evolve a chess playing programs, with 
a fitness of
10.48. This means that the evolved program is better than the opponent
program of fitness class 10. The fitness value was measured by a
post-evaluation of best programs:
An individual plays 20 games against class
8,10 and 12, so that the fitness value is the result of 60 games.
Note that the individual achieves this result by
expanding on average 58.410 nodes per move in the search tree. 
A simple \ab chess program needs 897.070 nodes per move for search
depth of 5, which corresponds to class 10. The f-negascout algorithm
which is an improved variant of 
\ab, needs 120.000 nodes per move for this search depth. In other
words evolution has improved the search algorithm, so that it 
wins by only using 50\% of the resources
of a f-negascout algorithm which, inturn,  outperforms an \ab-algorithm. 
Evolved individuals win against a simple \ab-algorithm by using only 6\% of the
resources.

More details of the  results are available from www.qoopy.net.


%----------------------------------------------------------------------
\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 Abbruchkriterium ist die Anzahl der verlorenen
Spiele. Während der Evolution wird 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
einerseits die Fitnessbewertung für ein Individuum sehr schnell beendet werden,
gleichzeitig erhalten die Individuen weiterhin die Chance an der Fitnessbewertung
teilzunehmen, wenn es zum Verlust eines Spiels kommt. Es hat sich gezeigt, dass wenn
man die Grenze der verlorenen Spiele erhöht, es zu keinem Gewinn für die Evolution
kommt. 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 nicht zur Verbesserung der Evolution führt.
Die Individuen die auch gegen Gegnerprogramme mit größeren Rechentiefen gewinnen,
sind auf der anderen Seite zu unbeständig in ihrer Performance und dies ist nicht
das Ziel der Evolution. Das System soll Individuen generieren, die gute und
beständige 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 das Spiel abgebrochen, falls nicht
ein Programm vorher gewonnen hat. Als Ergebnis eines Spiels wird dann reine Materialwert
des Spiels ohne Bewertung von Stellungselementen genutzt. Der Wert bezeiht sich immer
auf das Individuum und ist auf den maximalen Materialwert ohne die Könige normiert.
Dass heißt ein Ergebnis von eins für ein Individuum bedeutet, dass es alle Figuren 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 gesenkt 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,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 wurde oder verloren
wurde. Gewonnene Spiele werden stärker gewichtet als verlorene Spiele und Spiele gegen
Gegnerprogramme mit größere 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. Als Ergebnis eines Spiels wird der Materialwert des Spiels für das
Individuum normiert auf den maximalen Materialwert ohne die Könige bezogen. Dass heißt
ein Ergebnis von eins für ein Individuum bedeutet, dass es alle Figuren hat und das
Gegnerprogramm nur noch den König. Ein Bauer hat somit einen Einfluss
von $\frac{100}{4060} \approx 0.0246$ auf den Ergebniswert. 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 10000 multipliziert
und der Wert $BothWin$ mit 1000. 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}
  BothWin= BothWin*1000;
  dFit= ((double)iBothWin)+dWhiteVal+dBlackVal+ (LastWinDepth*10000.0);
\label{eq:fitChess}
\end{equation}


Durch die Verbindung des gewichteten Materialgewinns und den Stufenfunktionen in
der Fitnessfunktion~\ref{eq:fitChess} ermöglicht man es der Evolution Programme
zu evolvieren, die gegen spielstarke Programme gewinnen können aber nicht den maximalen
Materialgewinn erzielen.

Die Rechenzeit ist ein weitere wichtiger Punkt bei der Auswahl der Individuen, so geht
neben der Fitness wird auch die Anzahl der betrachteten Stellungen bei der Selektion der
Individuen mit ein. 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, aber oft zu
einer Verkleinerung des Suchraums.

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. 



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


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