\section*{Danksagung}

Diese Arbeit wäre ohne die Hilfe vieler Menschen nicht möglich gewesen. Mein Dank
gebührt zuerst Prof. Dr. Wolfgang Banzhaf für seine vertrauensvolle Unterstützung
bei der Erstellung dieser Arbeit.

Als sehr wichtig hat sich die freundliche und kreative Arbeitsatmosphäre am Lehrstuhl für Systemanalyse 
des Fachbereichs Informatik an der Universität Dortmund erwiesen. Diese war 
besonders wichtig und inspirierend für diese Arbeit. So möchte ich allen Mitarbeitern dieses
Lehrstuhls für die Unterstützung während meiner Zeit dort danken. Besonders 
hervorheben möchte ich dabei Dr. Christoph Richter, Dr. Jens Niehaus, Dr. Andre Leier und
 Dr. Markus Brameier. Ohne ihre Hilfe in Form von Diskussionen, programmiertechnischen 
 Tipps, der Bereitstellung von Daten und des Korrekturlesens hätte diese Arbeit 
 nicht die vorliegende Form erreicht. Weiterhin muss ich auch Roderich Groß, Keno Albrecht 
 und Martin Villwock für ihre Hilfe und Tipps danken.
 
 Ein besonderer Dank gebührt Heike Rest, ohne deren Hilfe diese Arbeit nicht so
 fehlerfrei wäre. Ein weiterer Dank gebührt Christian von Strachwitz und Ursula
 Neumann, ohne ihre Aufmunterung hätte die Arbeit länger gedauert.
 
 Mein Dank gilt ferner Prof. Dr. Heinrich Müller, Prof. Dr. Günter Rudolph und
 Dr. Stefan Droste, für Ihre Bereitschaft, sich mit dieser Arbeit auseinanderzusetzen.

\cleardoublepage


\section*{Einleitung}



"`\textbf{Der nächste Weltmeister im Schachspiel könnte ein Computer sein, der
übernächste einer, der von Computern programmiert wurde.}"'~\cite{strouhal96} 
Mit diesen Worten gab Strouhal im Jahre 1996 eine eindeutige Richtung für die 
weitere Entwicklung von intelligenten Programmen vor. Der erste Teil des Zitats 
wurde schon im gleichen Jahr Geschichte.
Die Schaffung eines Computerprogramms, das den Schachweltmeister schlagen konnte, war
eines der großen Ziele der Künstlichen Intelligenz. Diese Entwicklung nahm in der 
Nachkriegszeit ihren Anfang mit der Nutzung der Computer für das abstrakte Schlussfolgern.
Während der 60er Jahre wurden Computer hergestellt, die logische und geometrische Theoreme 
beweisen, Rechenprobleme lösen und gute Schachspiele ausführen konnten. 
Vor einigen Jahren stellte die Carnegie Mellon University zwei tischgroße 
Computer her. Dieses System, \emph{Deep Blue} genannt, konnte im Jahr 1997 Kasparow 
in einem Match mit 3.5:2.5 besiegen.

Strouhal erwartet als zweiten Aspekt seiner Vorhersage die Entwicklung
eines Weltmeisterprogramms durch einen Computer.
Zum damaligen Zeitpunkt bestand jedoch überhaupt keine Klarheit darüber, wie ein 
Computer ein Schachprogramm entwickeln könnte. 
Diese Arbeit stellt mit der Nutzung von Evolutionären Verfahren zur Entwicklung 
von Schachprogrammen eine Lösung dieser Problematik vor.

Trotz der großen Leistungen der KI-Programme können Computer viele Problemaspekte 
nicht so effizient behandeln wie wir Menschen, so dass sie viele
Aufgaben nicht oder nur sehr schlecht lösen können~\cite{Dreyfus:79,Dreyfus:92}. 
So werden beispielsweise den KI-Programmen die Züge mit einer Tastatur 
eingegeben, denn kein computergesteuerter  Roboter kann die Figuren auf einem Schachbrett 
so wie ein durchschnittlicher Mensch sehen und ergreifen.
Warum ist es aber leichter das abstrakte Denken als Wahrnehmen und Handeln zu imitieren? 
Über hunderte Millionen von Jahren überlebten unsere Vorfahren, indem sie besser 
sahen und sich besser bewegten als ihre Konkurrenz. Die Evolution steigerte die
Effizienz unserer Vorfahren bei den überlebenswichtigen Aufgaben.
%Wir können unsere gewaltigen Fähigkeiten kaum würdigen, weil sie uns 
%einfach gegeben sind und von allen Menschen beherrscht werden. 
Auf der anderen Seite ist rationales Denken, wie man es für das Schachspiel 
braucht, eine vergleichsweise junge, recht spät erlernte Fähigkeit, die es vielleicht
nicht länger als 100.000 Jahre gibt. 
Die beim Menschen für das rationale Denken genutzten Hirnbereiche haben  noch lange 
nicht die ausgefeilte Organisation erreicht, wie dies bei den Bereichen für 
Wahrnehmen und Handeln der Fall ist. Aus diesem Grund ist die Denkfähigkeit des 
Menschen auch im Vergleich zu anderen Fähigkeiten eher schlecht.
%
%Die dazu benutzten Hirnbereiche sind nicht gut organisiert, weswegen 
%wir das nur sehr schlecht können. Wir haben bis vor kurzem nicht bemerkt, wie 
%schlecht wir dies können, weil wir keine Konkurrenz hatten, die es uns vor 
%Augen geführt hat. 
Das Schachspiel ist ein sehr gutes Beispiel um den Unterschied zwischen Menschen
und Programmen erfahrbar zu machen. Prinzipiell gibt es beim Schach
10 hoch 120 verschiedene Möglichkeiten. %Wenn ohne Vorkenntnisse alle
%Möglichkeiten geprüft werden sollen, wird ein Programm das Ergebnis 
%in keiner annehmbaren Zeit berechnen.
\emph{Deep Blue} überprüft immer noch Millionen von Brettstellungen, ehe es einen 
Zug bestimmt, während die besten Spieler allenfalls einige hundert  
Konstellationen betrachten.
Könnten Menschen den Suchraum aber genauso effizient aufspannen wie Programme, 
um wievieles besser wären dann die Menschen beim Schachspiel? 
Diese Frage können wir hier nicht beantworten, da wir wohl eine
Million Jahre Evolution abwarten müssten. 

Die Evolution hat sich als eine ausgezeichnete Optimiermethode gezeigt, deshalb
werden die Mechanismen der natürlichen Evolution auf die Entwicklung von
Programmen angewendet um ein Schachprogramm durch einen Computer entwickeln zu lassen.
Hierzu werden bekannte Verfahren wie die Genetische Programmmierung und Evolutions 
Strategien verwendet. Weiter werden auch neue Strukturen für die Genetische
Programmierung entwickelt um einen flexibleren Aufbau der Programme zu ermöglichen. 


Schach (vom pers.: Schah = König; stehende Metapher: "Das Königliche Spiel") 
ist ein strategisches Brettspiel für zwei Spieler, bei dem der Zufall keine 
Rolle spielt (außer beim Losen um die Farbe, d. h. um den ersten Zug), sondern 
lediglich das Können der Spieler über den Spielausgang entscheidet.
%Schach ist, noch vor Dame und Mühle, das populärste Brettspiel in Europa. 
%
Es bietet daher ideale Voraussetzungen, um als Benchmarkproblem für
verschiedene Algorithmen zu dienen, zudem beim Schach auch nur eine eng begrenzte 
Menge von Objekten, wie die Felder, Figuren und Züge, existieren. 
Die Regeln sind genauso eindeutig und einfach zu beschreiben, wie auch das große 
Ziel des Spiels, das Schachmatt. Dennoch besitzt
diese Welt eine so hohe Komplexität, dass es bis heute nicht gelungen
ist, die spieltheoretischen Gesetzmäßigkeiten des Spiels ganz zu durchschauen, 
siehe Abschnitt~\ref{sec:Spiel2Per0summen}.
Die Struktur des Schachspiels macht es
\emph{Brute Force} Verfahren nicht möglich gute Lösungen zu erreichen,
so dass \emph{intelligente Techniken} verwendet werden müssen. Gleichzeitig können
Techniken, die in Schachprogrammen verwendet werden, auch für
die Mustererkennung, Problemlösung, Optimierungsheuristiken und andere
\emph{real world} Probleme genutzt werden.



Mit Hilfe der Genetischen Programmierung und Evolutionärer Algorithmen 
sollen in dieser Arbeit Programme entwickelt werden, die Schach spielen
können.
Während der Versuche hat sich sehr schnell gezeigt, dass
die bekannten Individuenstrukturen  zur Lösung der
Aufgabe nicht flexibel genug sind. 
Daher wurden zwei neue Strukturen für die Genetische Programmierung entwickelt.
Die Linear-Tree und Linear-Graph Strukturen vereinen durch ihren hybriden Aufbau 
den Programmfluss und den Datenfluss in einer Struktur. Die Analyse der Struktur
hat ihre Leistungsfähigkeit auch für andere Problemstellungen gezeigt.
Das Schachproblem ist aber ein Suchproblem und hier wurde auf der Grundlage
der Linear-Graph Struktur ein spezialisiertes Individuum entwickelt,
das durch seine Struktur und sein Verhalten gut zur Lösung von Suchproblemen
genutzt werden kann. 

Neben diesen neuen Strukturen werden den Individuen sehr viele Funktionen 
mit Problemwissen zur Verfügung gestellt. Denn für
viele Problemstellungen sind in der Literatur und Praxis schon Verfahren
und Funktionen bekannt, die Teilprobleme lösen
können. Das System kann dann geeignete Kombinationen dieser Funktionen 
finden, die es dem Individuum gestatten die Problemstellung gut zu lösen.
Durch die Einschränkung des Systems auf spezialisierte Funktionen wird die Evolution
zwar auf bestimmte Lösungsansätze festgelegt, aber durch den eingeschränkten
Suchraum wird auch die Möglichkeit deutlich verbessert, überhaupt eine Lösung zu 
finden. Der
Ansatz nutzt Wissen über die Problemstellung aus und versucht so
schneller zu einem Ergebnis und zu einer Verbesserung bekannter Ansätze zu
gelangen. Dies spiegelt sich auch  in den verschiedenen
GP-Strukturen wieder, die für das System entwickelt wurden. 
Neben der Lösung des Schachproblems geht es auch darum, durch eine
Modularisierung und Nutzung von Vorwissen mit GP-Systemen neue Möglichkeiten
zu entwickeln um komplexe und \emph{real world} Probleme zu lösen.

%10
Im ersten Kapitel \emph{Einführung in die Spieltheorie} werden der theoretische
Hintergrund von Spielen kurz vorgestellt und auch die Eingliederung 
des Schachspiels in diesen Zusammenhang beschrieben. Im zweiten Kapitel \emph{Schach}
werden die wichtigen Elemente zum Schachspiel vorgestellt sowie die Entwicklung
des Computerschachs und die Elemente der Schachprogramme mit ihrer Funktion.
Das dritte Kapitel \emph{GP Einführung} gibt eine kurze Einführung in das Gebiet
der Genetischen Programmierung und erläutert die grundlegenden Begriffe.
Im Kapitel vier werden die drei für diese Arbeit neu entwickelten Strukturen 
vorgestellt. Daran schließt sich eine empirische Analyse der Linear-Tree und Linear-Graph
Struktur mit Hilfe verschiedener Benchmarkprobleme an. Hierzu werden die neuen Strukturen
auf Benchmarkproblemen mit anderen Strukturen der Genetischen Programmierung verglichen.
Das fünfte Kapitel \emph{Das GeneticChess-System} beschreibt den Aufbau des GeneticChess
Systems und der Vorgängersysteme. Daran schließt sich das Kapitel mit der Auswertung
der Ergebnisse an. Im siebten Kapitel \emph{Fazit und Ausblick} werden die Ergebnisse 
noch einmal kurz zusammengefasst und die möglichen Weiterentwicklungen des Systems
vorgestellt. Im Anhang findet man eine Auflistung aller Funktionen, die in den
verschiedenen Schachsystemen verwendet wurden, mit einer kurzen Beschreibung der Funktion. 

%In den Kapiteln "`Einführung in die Spieltheorie"' und "`Schach"' werden wichtige
%Elemente und Hintergründe zum Schachspiel dargestellt. Anschließend folgt eine
%kurze Einführung in die Genetische Programmierung, in der grundlegende
%Begriffe erläutert werden. Dann folgt ein Kapitel über die neuen GP Strukturen, die
%für das \emph{GeneticChess} System entwickelt wurden. Daran schließt sich
%eine empirische Analyse dieser Strukturen mit Hilfe verschiedener Benchmarkprobleme an. 
%Diesen Kapiteln folgt die Beschreibung des GeneticChess Systems und seiner
%Vorgängersysteme. Die Arbeit endet mit den Ergebnissen aller Schachsysteme und
%einem Ausblick auf die mögliche weitere Entwicklung des Systems.


%
%
%  Ende
%
%


%Jedoch können wir die Fragestellung
%verändern und somit eine künstliche Evolution mit der Verbesserung von Schachprogrammen
%beauftragen. Die Fragen, die diese Arbeit beantworten soll, lauten: Kann
%man mit einer künstlichen Evolution Schachprogramme entwickeln? Wenn diese Frage
%positiv beantwortet werden kann, stellt sich die Frage, ob evolutionäre Verfahren,
%wie die Genetische Programmierung, bekannte Computerschachverfahren verbessern können.


%Trotz dieses großen Unterschieds  können gute Schachspieler immer noch mit Computern
%wie Deep Blue mithalten.

%und 
%nicht ein Programmierer entwickelt ein Computerschachprogramme mit expliziten Anweisungen.
%Diese Programme können von alleine nicht ihrer 
%chachkunste verbessern. Das intelligente Verhalten wurde nicht durch
%in Programm erzeugt, sondern durch die Personen, die das Programm
%ntwickelten. 

%KI-Programme sollen in der Lage sein, aus Informationsmengen Objekte
%zu erkennen und sie für die Formulierung und Durchführung von zielorientierten
%Handlungen zu nutzen. In beiden Fällen geht es um die Erkenntnis von
%Regelmäßigkeiten und in beiden Fällen sind hierfür Regeln anzuwenden.
%Die KI-Forschung selbst stößt sofort auf das Problem der kombinatorischen
%Explosion. Und die Frage, von welchem Vorkenntnissen ausgegangen werden
%kann und wie ein Vorkenntnissen zu gewinnen ist.





%In den meisten Fällen wird es genügen, sich auf bestimmte Standardregeln zu
%verlassen. Intelligenz ist aber gerade in kritischen, ungewohnten,
%unvorhersehbaren Situationen verlangt, wo es erforderlich ist, aus der
%Situation heraus ein angemessenes Verfahren zu entwickeln. Mit einem Wort:
%Wirklich intelligente Programme dürften sich nicht damit begnügen, dass sie
%einen vorgegebenen Satz von Regeln abarbeiten, sondern sie müssen in der Lage
%sein, neue Regeln zu entwerfen. Der Ansatz für die KI-Programme ist daher
%grundsätzlich zu erweitern: Es geht nicht nur um die Erkenntnis von Mustern
%und Regelmäßigkeiten nach Regeln, sondern auch umgekehrt, aus vorgefundenen
%Mustern sind Regeln zu erkennen, mit denen die Untersuchung fortgeführt werden kann.

%In den meisten Fällen wird es genügen, sich auf bestimmte Standardregeln zu
%verlassen. Intelligenz ist aber gerade in kritischen, ungewohnten,
%unvorhersehbaren Situationen verlangt, wo es erforderlich ist, aus der
%Situation heraus ein angemessenes Verfahren zu entwickeln. Mit einem Wort:
%Wirklich intelligente Programme dürften sich nicht damit begnügen, dass sie
%einen vorgegebenen Satz von Regeln abarbeiten, sondern sie müssen in der Lage
%sein, neue Regeln zu entwerfen. Der Ansatz für die KI-Programme ist daher
%grundsätzlich zu erweitern: Es geht nicht nur um die Erkenntnis von Mustern
%und Regelmäßigkeiten nach Regeln, sondern auch umgekehrt, aus vorgefundenen
%Mustern sind Regeln zu erkennen, mit denen die Untersuchung fortgeführt werden kann.

%KI-Programme müssen vom Menschen unabhängig sein, sie dürfen und können nicht
%nachfragen. Denn sie sollen gerade dort eingesetzt werden, wo Menschen nicht
%hinkommen können. So kann es sich um künstliche Vehikel handeln, die
%Expeditionen in Gebiete unternehmen, die dem Menschen nicht erschlossen sind,
%etwa im Weltraum, im Erdinneren oder sonstwo. Genauso kann es sich um Programme
%handeln, die Datenmengen im Zugriff haben, die dem Menschen allein aufgrund
%ihrer Fülle nicht zur Überprüfung und Kontrolle mitgeteilt werden können. In
%all diesen Fällen ist grundsätzlich davon auszugehen, dass KI-Programme mit
%Situationen konfrontiert sind, die dem Menschen prinzipiell unzugänglich sind.
%Genau dafür sollen sie geschaffen werden. Schon aus der Atomphysik ist bekannt,
%dass davon auszugehen ist, dass hier alle Regeln verletzt sein können, die dem
%Menschen bekannt sind. Worauf kann sich KI stützen, wenn hier neue Regeln
%gesucht werden?

%2
%Das Gleiche gilt für das \emph{Computerschach}. Zum ersten Mal konnten
%Automaten etwas tun, was bei einem Menschen Intelligenz erforderte. Es
%war also ein klares Beispiel für intelligentes Verhalten bei einer
%Maschine. So kann es nicht verwunderlich sein, dass die Künstliche
%Intelligenz Schach zu einem seiner Experimentierfelder machte.
%3.1

%3.2
%Das Schachspiel bietet ideale Vorraussetuzngen als Benchmarkproblem für
%verschiedene Algorithmen zu dienen, denn man hat es im Schach mit einer
%%denn das Spiel bietet ideale Voraussetzungen. Man hat es mit einer
%eng begrenzten Menge von Objekten zu tun, wie den Feldern, den Figuren
%und den Zügen, zwischen denen eindeutige Beziehungen existieren. Die
%Regeln sind eindeutig und einfach zu beschreiben und auch das Ziel des
%Spiels, das Schachmatt, ist einfach zu beschreiben. Dennoch besitzt
%diese Welt eine so hohe Komplexität, dass es bis heute nicht gelungen
%ist die Gesetzmäßigkeiten des Spiels ganz zu durchschauen.



%3.3
%Der Enthusiasmus in der KI war aber so groß, dass schon im Jahre 1950 der
%baldige Sieg des Computers über den Weltmeister vorausgesagt wurde. Dieses Ziel trat
%aber erst sehr viel später ein und selbst nachdem \emph{Deep Blue
%Kasparow} 1997 besiegt hatte, stellte sich immer noch die Frage, ob es
%\emph{intelligentes Verhalten} oder nur \emph{Rechenleistung} war.


%4
%Auch an dieser Stelle zeigt sich die Aussage
%des No Free Lunch Theorems~\cite{nfl:99}, aber die Theorie hat selbst
%eine Lösung gezeigt, die besagt, dass man zwar nicht für alle Probleme
%ein sehr gutes Optimierverfahren realisieren kann, aber für
%Teilbereiche kann man es~\cite{pnfl:99}.


%7


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