


Begonnen haben wir die Arbeit mit dem Zitat von Strouhal:
"`\textbf{Der nächste Weltmeister im Schachspiel könnte ein Computer sein, der
übernächste einer, der von Computern programmiert wurde.}"'~\cite{strouhal96}. 
Dies war kein Ziel der Arbeit, aber ein Leitmotiv, dem man durch diese Arbeit schon ein
Stück näher gekommen ist. So kann man jetzt Individuen evolvieren, die auf dem
Niveau eines Experten Schach spielen. Diese Entwicklung benötigte bei
der klassischen KI circa 25 Jahre, siehe Kapitel~\ref{sec:HistCompChess}.
Hier muss man natürlich eingestehen, dass die langsame Entwicklung der Spielstärke
auch der geringen Rechenleistung der Computer geschuldet ist.
 


\subsection*{Zusammenfassung}

Die Arbeit verfolgt die Entwicklung eines Systems zur Evolution von Schachprogrammen,
es wurden dazu drei verschiedene Systeme entwickelt, die verschiedene Fähigkeiten,
Strukturen und Ergebnisse hatten. 
Begonnen wurde mit dem \emph{ChessGP} System,
dies ist ein sehr komplexes und ambitioniertes System. Es gibt der Evolution
sehr große Gestaltungsmöglichkeiten, arbeitet dabei mit Standard GP-Strukturen 
und einem hierarchischen Aufbau. Die Hierarchisierung wurde für die folgenden Systeme
beibehalten, wenn auch in einer einfacheren Variante, jedoch zeigten die Standard
GP-Strukturen hier ihre Grenzen, daher wurden für die folgenden Systeme neue GP-Strukturen 
entwickelt, um komplexere Individuen evolvieren zu können. 
Dadurch soll der extrem komplexe Aufbau eines Individuums des ChessGP Systems vereinfacht werden.
Denn diese Individuen bestehen aus drei hierarchischen Modulen, die zusammen aus
19 GP-Modulen bestehen, siehe Kapitel~\ref{sub:ChessInds}. Die besten Schachindividuen
konnten zwar sinnvoll Schach spielen, jedoch erreichten sie nur eine Spielstärke,
die einem Alpha-Beta Algorithmus der Suchtiefe zwei entspricht~\ref{sub:ChessGPFazit}.


Die Linear-Tree und Linear-Graph Struktur wurden entwickelt, um komplexere 
Lösungswege zu evolvieren und somit auch komplexere Probleme zu lösen.
Dies wurde durch die Kombination von Programmfluss und Datenfluss in einer GP-Struktur
ermöglicht, siehe Kapitel~\ref{sub:LinTree} und~\ref{sub:LinGraph}. 
Die Linear-Graph Strukturen zeigten für die Aufgabenstellung die besten Ergebnisse.
 Im Kapitel~\ref{sec:EmpAnaInd} sind die
Ergebnisse dieser Strukturen mit Benchmarkproblemen beschrieben. Neben der gestellten
Aufgabe, komplexere Probleme zu lösen, hatten die neuen GP-Strukturen noch einen
weiteren Vorteil gegenüber den Standardstrukturen, so können sie Lösungen zu
Problemen mit viel kleineren Pools erzeugen und hatten gleichzeitig noch eine kleinere
Streuung bei der Güte der Ergebnisse. Dies ist nicht nur für das Schachproblem
sinnvoll, sondern auch, wenn man die Evolution von Programmen für industrielle 
Probleme nutzt. Denn durch die Nutzung kleinerer Demes kann sehr viel Rechenzeit
eingespart werden.



Im \emph{qoopy} System wurde die Linear-Graph Struktur zum ersten Mal angewendet,
die Individuen wiesen gleichzeitig einen viel einfacheren Aufbau auf.
Es zeigte gegenüber dem ChessGP-System eine extreme Steigerung in der 
Spielstärke der Individuen. Diese rührt hauptsächlich durch den einfacheren 
Aufbau der Individuen und die Konzentration auf die Verbesserung eines Alpha-Beta
Algorithmus her. So konnten die Individuen aus dem qoopy-System bei gleicher 
Spielstärke im Vergleich zu einem guten Alpha-Beta Algorithmus 50\% des Suchraums einsparen. 
Die besten Individuen erreichten eine Spielstärke, die besser ist als die
eines Schachalgorithmus der Suchtiefe fünf.
Das Ergebnis wurde dabei hauptsächlich durch das gute Zugsortierungsmodul der Individuen
erzielt, siehe Kapitel~\ref{sub:qoopyFazit}.



Im \emph{GeneticChess} wurde die Aufteilung der Individuen vom qoopy-System übernommen,
jedoch wurde ihnen eine größere Freiheit bei der Lösung ihrer Aufgabe zugestanden.
Dies kann man anhand der neuen \emph{State-Space} Struktur erkennen, siehe Kapitel~\ref{sec:stateSpaceGP}.
Dabei handelt es sich im Aufbau und in der Ausführung der Struktur
um einen rekursiven Suchalgorithmus. Anders als im qoopy-System bestehen alle
drei Module der Individuen aus GP Programmen. Sie haben  durch die
Funktions- und Terminalmengen eine viel größere Freiheit bei der Evolution
von Programmen als die Individuen des qoopy-Systems. Hierdurch konnte noch einmal eine 
deutlichere Steigerung  der Spielstärke der Individuen erreicht werden.
Bei gleicher Einschränkung des Suchraumes, wie beim qoopy-System, konnten die
Individuen Programme mit einer Suchtiefe von sechs schlagen, bei einer Vergrößerung
des Suchraumes konnten sogar Individuen evolviert werden, die Programme der 
Suchtiefe acht schlagen konnten. Dies entspricht in etwa einem Elowert von 
2200, dies ist die Spielstärke eines Schachexperten.
Gleichzeitig konnten die Individuen auch eine
deutliche Verringerung der expandierten Knoten erzielen. So konnte man bei
einer genaueren Analyse sehen, dass 60\% der Knoten des Suchraumes eingespart werden,
siehe Kapitel~\ref{sub:GeneticChessFazit} und~\ref{sub:Ind250}. 

\subsection*{Ausblick}

In dem Vorgehen, einen Suchalgorithmus mit Hilfe von GP-Modulen zu verbessern
und zu optimieren, wie man es im qoopy- und noch besser im GeneticChess-System
sehen kann, kann ein erhebliches Potential bei der 
Evolution von Programmen freigesetzt werden.
Dadurch, dass man dem GP-System bekannte und notwendige Funktionen zur
Lösung eines Suchproblems zur Verfügung stellt, können diese durch die Evolution
auf sinnvollen Kombination getestet werden. 
Dadurch können sehr schnell und effizient für neue Problemstellungen 
maßgeschneiderte Algorithmen entwickelt werden. Denn oft sind sinnvolle Funktionen für
Lösungen  von Teilproblemen bekannt, jedoch können von den Entwicklern nicht
alle Kombinationen ausgetestet werden, da man entweder nicht die Zeit hat oder
der Zielalgorithmus nicht zu spezialisiert sein darf, da sonst die Entwicklungskosten
für mehrere Algorithmen zu leisten wären. Die Möglichkeit spezialisierte
Algorithmen für beliebige Probleme zu erstellen, könnte durch eine Weiterentwicklung
des GeneticChess-Systems geleistet werden.


Im GeneticChess wurde dieses Vorgehen genutzt, um zu den guten Ergebnissen zu kommen,
gleichzeitig zeigte sich hier auch ein Problem, denn wenn es zu große Funktions-
und Terminalmengen gibt, war die Leistung des Systems schlecht, dies kann man
im Kapitel~\ref{sec:ErgEvo} deutlich sehen. Um nun aber zu einem System zu kommen,
das automatisch die wichtigen Funktionen herausfiltert, muss man hier eine Analyse
der benötigten Funktionen durchführen. Dies kann durch eine Häufigkeitsanalyse der
Funktionen in den besten Programmen erreicht werden, wie es hier nachträglich durchgeführt
wurde, siehe Kapitel~\ref{sub:GCAna}. Dieses Vorgehen sollte dann aber während
der Evolution durchgeführt werden, um eine gute Teilmenge aus den Funktions- und
Terminalmengen herauszufiltern.
Eine weitere Möglichkeit das Problem der Funktionsmengen zu lösen
wäre der Einsatz von  Developmental Genetic Programming (DGP), wie sie Robert Keller 
in den Artikeln~\cite{keller:1999:TEGCGP} und~\cite{keller:2001:gecco} vorgestellt hat. 
Hierbei werden die Funktionsmengen während einer Koevolution optimiert, um so
eine Vereinfachung der Evolution der Individuen zu schaffen. Eine Problematik
bei beiden Verfahren ist der zusätzliche Zeitaufwand, der durch die Auswahl der
richtigen Funktionsmenge entsteht.


Ein Ausweg aus der Problematik der Rechenzeit, sowohl für die Koevolution
als auch für die Evolution besserer Individuen, ist eine Parallelisierung des Systems.
Um den nächsten Schritt in der Evolution von Schachindividuen durchzuführen ist
eine Parallelisierung unumgänglich, da schon die Evolution der besten Individuen
bis zu 26 Tage auf einem Rechner mit 2,5 GHz gedauert hat. Das Beste wäre eine
Kombination der Verfahren, die für das ChessGP und qoopy-System verwendet
wurden. Es sollten nur einzelne Spiele und später in der Evolution nur Teile
eines Spiels an die Clients im Internet verteilt werden. Durch dieses Vorgehen
hat man weiterhin die Kontrolle über die Evolution und kann gleichzeitig sehr viel
Rechenzeit zur Verfügung gestellt bekommen.
Ein weiterer Punkt wäre die Evolution paralleler Schachindividuen, dadurch könnten
die Individuen parallele Hardware nutzen und so noch eine Verbesserung 
der Spielstärke erreichen. In der Dissertation von Herrn Niehaus wurden schon
parallele Individuen evolviert, so dass die Entwicklung solcher Schachprogramme
möglich wäre, siehe hierzu~\cite{niehaus03:Diss} Kapitel 11.


Ein weiterer Punkt zur Verbesserung der Spielstärke ist die Verwendung von
Datenbanken, hier gäbe es die Möglichkeit Eröffnungs- und Endspieldatenbanken mit
einem evolvierten Individuum zu nutzen. Jedoch gäbe es dann nur ein Nebeneinander
zweier Verfahren, sinnvoller wäre es hier, dem Individuum die Möglichkeit zu
geben mit speziellen Funktionen direkt auf die Datenbanken zuzugreifen um so
die Suche zu unterstützen. 
Der Einsatz von Datenbanken ermöglicht Schachprogrammen 
normalerweise eine Steigerung der Spielstärke von 200 bis 300 Elopunkten. Wenn man
dies auch für die evolvierten Individuen zugrunde legt und gleichzeitig noch eine
Steigerung der Suchtiefe auf zwölf erreicht, müssten die Individuen ungefähr
einen Elowert von 2.800-2.900 erreichen. 
Als Deep Blue Kasparov schlug, hatte dieser
einen Elowert von 2.775, nach dem Rating der FIDE hatte Garry Kasparov im Oktober 2005
einen Elowert von 2.812. Somit könnten evolvierte Individuen mit diesen Fähigkeiten
der neue Weltmeister werden und sie wären von einem Computer programmiert worden.
Somit hätte man eine neue Qualität im Kampf zwischen Mensch und Maschine erreicht.



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

