
%---------------------------------------------------------------------- 
%\section{Computerschach Theorie}
%---------------------------------------------------------------------- 
\label{sec:comptTheo}


Viele Aktivitäten des Menschen, wie Spiele spielen, Mathematik, Auto
fahren, benötigen \emph{Intelligenz}. Wenn Computerprogramme diese
Aufgaben lösen spricht man von \emph{Künstlicher
Intelligenz}\index{Künstlicher Intelligenz}. \emph{Problem Solving}
oder auch \emph{Problemlösen} als solches ist ein sehr vages Gebiet,
welches aber ein zentrales Thema 
in der Künstlichen Intelligenz ist. Aber im weitern Sinne gehört zum
Thema \emph{Problemlösung}\index{Problemlösung} alle Aufgaben die von
Programmen gelöst werden, denn jede Aufgabe kann als ein Problem
verstanden werden, welches gelöst werden soll~\cite{problem71}.

Der zentrale Punkt des Themas steckt in dem Wort
\emph{Problem}\index{Problem}, hierfür gibt es keine einfache und
eindeutige Definition. Der Begriff selber wird immer in seiner
intuitiven Bedeutung benutzt. Im Duden wird Problem als ``zu lösende
Aufgabe; Fragestllung; Schwierigkeit, schwieriger Vorwurf''
definiert. Es ist im 16. Jahrhundert aus dem griechisch-lateinischen
pr'obl'ema, `` das Vorgelegte; die gestellt (wissenschaftliche)
Aufgabe, die Streitfrage'' entlehnt worden. 

Im weiteren wird der Begriff Problem auch in seiner intuitiven
Bedeutung benutzt aber mit der klaren Abgrenzung auf den Bereich von
Aufgaben, die durch Computerprogramme gelöst werden sollen.
Als typisches Beispiel Problem werden Spiele verwendet, den sehr viele
System die Problemlösungsverfahren getestet haben wurden auf Spielen
wie Dame, Schach, Mühle, Go aber auch TicTacTo getestet. Der Grund
dafür ist nicht das Spiele gegenüber Problemen der wirklichen Welt so
einfach sind, sondern wie Minsky\footnote{in \cite{Minsky68} Seite
12.} sagte :''It is not that the games and mathematical problems are
chosen because ther are clear and simple; rather it is that they give
us, for the smallest initial structure, the greatest complexity, so
that on can engage some really formidable situations after a
relatively minimal diversion into programming .''


%Wenn man sich nun die Ansätze in der Künstlichen Intelligenz
%betrachtet, so findet man, dass viele Ansätze \emph{trail-and-error}
%Suchen\index{Trail-and-Error Suche} sind. Diese Methode arbeitet
%im \emph{Raum} möglicher Lösungen und testet dabei \emph{Lösungen} und
%verwirft sie auch wieder, bis sie eine \emph{gute} Lösung gefunden hat.

%Große Bedeutung kommt hier der Verwendung von
%\emph{Heuristiken}\index{Heuristik} zu, dieser Begriff kann mit
%\emph{der Kunst des Entdeckens} übersetzt werden. Im Kontext der
%KI versteht man darunger eine Faustregel, die im allgemeinen \emph{effizient}
%zu einer \emph{guten Lösung} des Problem kommt, jedoch ist dies nicht
%garantiert. Bei Heuristischen Verfahren fließt meist viel problem- und
%domänenspezifisches Wissen über heuristische Regeln ein, wenn exakte
%Verfahren nicht bekannt sind oder zu aufwendig sind (siehe
%~\cite{lenat:83}). Ein Algorithmus für das Lösen eines Problems wäre
%\emph{garantiert} erfolgreich innerhalb eine endlichen Zeit, aber für
%\emph{heuristische Verfahren} kann eine solche Garantie nicht gegeben
%werden. Auch die Güte der erreichten Lösung kann nicht immer
%garantiert werden und so existieren im allgemeinen die
%unterschiedlichsten Heuristiken für das gleiche Problem. Da für die
%meisten Aufgaben im Bereich der Problemlösung keine exakten
%Algorithmen benutzt werden können ist die Suche nach guten Heuristiken
%für die gestellte Aufgabe ein zentraler Punkt um zu einer Lösung zu
%gelangen. 

So wurde das Schachspiel zu einem Benchmarkproblem für die Aufgabe, die sich
die KI gestellt hat. Aber auch die Geschichte des Computerschachs ist auch
eine Geschichte von Irrtümern und Fehleinschätzungen der Möglichkeiten von
Computerprogrammen. Obwohl Schach ein ideales Problem für Computer
ist, die Regeln des Spiels sind eindeutig, das Schachuniversum ist
klein; 64 Felder, 6 verschiedene Figuren und zwei Spieler.
Aber selbst diese beschränkte Anzahl von Elementen führt schon zu
einer sehr hohen Anzahl von Varianten, die während des Spiels entstehen
können. Die Tabelle~\ref{tab:Stellungen} gibt an, wieviele Stellungen
nach welchem Halbzug möglich sind, so kann man sehen, dass die Anzahl
möglicher Stellungen schon
nach dem 11.ten Halbzug das Alter des Universums in Sekunden erreicht
hat. Dies verdeutlicht auch das Problem der Computerprogramme. Wie
soll ein \emph{guter Zug} aus der Menge aller möglichen Züge gewählt
werden. Wie bei vielen Problemen schlägt auch hier die Kombinatorik zu
und verhindert eine einfache Lösung.


\begin{table}
\begin{tabular}{rcl}
  \textbf{Halbzug} &  \textbf{Anzahl möglicher Stellungen} &  \\
\vspace{0.3mm}
  1 &   40 &  \\
\vspace{0.3mm}
  2 &   1600 &  \\
\vspace{0.3mm}
  3 &   64.000 &  \\
\vspace{0.3mm}
  4 &   2.6 Millionen &  \\
%    &                  & $\leftarrow $  Menschenalter in Sekunden. \\
%\vspace{0.3mm}
  5 &  102 Millionen &  \\
\vspace{0.3mm}
  6 &  4.1 Milliarden &  \\
\vspace{0.3mm}
  7 &  164 Milliarden &  \\
\vspace{0.3mm}
  8 &  6.5 Billionen &  \\
\vspace{0.3mm}
  9 &  262 Billionen &  \\
\vspace{0.3mm}
  10 & 10 Billiarden &  \\
\vspace{0.3mm}
  11 & 419 Billiarden  &   $\leftarrow $ Alter des Universums in Sekunden. \\
\vspace{0.3mm}
  12 & 17 Trillionen &   $\leftarrow $ Sissas Weizenkörner. \\
\vspace{0.3mm}
  13 & 671 Trillionen &  \\
\vspace{0.3mm}
  14 & $2.7 * 10^{22}$&   $\leftarrow $ Anzahl der Sterne im Universum.\\
\vspace{0.3mm}
  - &  &  \\
\vspace{0.3mm}
  49 & $3.2 * 10^{78}$ &  \\
%\vspace{0.3mm}
  &                     & $\leftarrow $ Anzahl der Elementarteilchen im Universum  \\
%\vspace{0.3mm}
 50 & $1.3 * 10^{80}$ &  \\
\vspace{0.3mm}
  &  &  \\
\vspace{0.3mm}
\end{tabular}
\caption{Exponentielle Entwicklung der Stellungen beim
Schachspiel. Die Annahme ist, dass nach jedem Zug 40 Züge möglich
sind.}
\label{tab:Stellungen}
\end{table}




%\subsection{Wie spielt der Computer Schach?}


Die erste Frage muss daher lauten: Kann ein Computer überhaupt Schach spielen?
Die einfachste Methode Schach zu spielen ist es alle möglichen Züge zu
erzeugen und dann zu überprüfen, welche dieser Züge legal sind. Danach
wird einer der Züge gewählt. Dann befinden wir uns in der ersten Zeile
der Tabelle~\ref{tab:Stellungen} und man hat somit die Problematik mit dem
großen Suchraum vermieden. Solche Programme werden aber im
allgemeinen nach 10 Halbzügen geschlagen, was nicht sehr gut ist.

Da man also ein Computerprogramm schreiben kann, welches Schach spielen
kann, ändert sich die Frage dahingehend, ob man ein Programm schreiben
kann, was \emph{gut} Schach spielen kann. Theoretisch kann man ein
Programm schreiben, dass alle möglichen Varianten von der Startstellung
ausgehend berechnet, bis es das Ende des Spiels erreicht und eine
\emph{optimale Strategie}\index{optimale Strategie}  findet. Das heißt, egal
welcher Zug vom 
Gegner gewählt wird, es ist immer möglich eine Sequenz von Zügen
(Variante) zu finden, mit der das Programm gewinnt. Dieses Programm
müsste den gesamten Suchbaum nur einmal aufbauen und speichern,
anschließend müsste der Suchbaum nur für jede Stellung analysiert
werden und dieses Programm würde \emph{perfekt} Schach spielen. Diese
Verfahren sind auch für Probleme wie Tic-Tac-Toe möglich, aber nicht
für Schach, denn schon nach 50 Halbzügen müssten $1.3 * 10^{80}$
Stellungen überprüft werden.
Die Suche nach dem optimalen Zug unter der astronomischen Anzahl wird
durch die Begrenzung der Züge, also der Reduzierung des Suchraums,
durchgeführt.

Im Jahr 1950 gab Claude Shannon\index{C. E. Shannon} eine Antwort auf
diese Frage und stellte drei Strategien vor, die die Größe des
Suchraums reduzierte. 
Die \emph{Typ A Strategie} bestand darin, dass alle legalen
Fortsetzungen bis zu einer festgelegten Suchtiefe untersucht werden,
es entspricht also einem Brute Force Verfahren. Die 
\emph{Typ B Strategie} ist eine selektive Suche die eine Vorauswahl
sinnvoller Züge durchführt, die zur Untersuchung freigegeben
werden. Schließlich kommt es noch zu einer statischen Bewertung der
Stellungen. Fast alle modernen Schachprogramme arbeiten nach diesem
Prinzip.
Die \emph{Typ C Strategie} war nun die Modellierung des
Schachwissens, dadurch sollte ein wesentlich effizienteres
Schachprogramm entwickelt werden. Bislang gab es keinen
durchschlagenden Erfolg bei der Entwicklung von Programmen die nicht
die Rechenleistung der Computer nutzten, sondern auf intelligentes
Verhalten setzten.

Nimmt man nun die Typ A und B Strategien von Shannon, ergeben sich
daraus folgende Anforderungen an ein Schachprogramm: Das Programm muss
die Möglichkeit haben eine Stellung zu bewerten, die nach einer Reihe
von Zügen erreicht wurde. Es muss die beste Sequenz von Zügen aus
allen Zugfolgen ermittelt werden können
Ein Zuggenerator muss existieren, der alle möglichen Züge für eine
Stellung berechnen kann und eine Bewertung der Züge muss möglich sein,
damit gute Züge ausgewählt werden können. Da das Programm nicht bis zu
einer festen Tiefe alle Züge berechnen soll, sondern selektiv vorgehen
soll, muss es die Möglichkeit haben seine Teile des Suchraums zu
durchsuchen und andere Teile zu ignorieren.


Die \emph{Spieltheorie}\index{Spieltheorie}, von Morgenstern und von
Neumann entwickelt, zeigt die Möglichkeit auf die beste Sequenz von
Zügen aus allen möglichen Zügen zu finden. Denn ein Spiel kann als ein
Baum aus Spielpositionen betrachtet werden, indem die Knoten die
Spielpositionen sind und die Kanten die erlaubten Züge zwischen den
Stellungen. Mit dem \emph{Minimax Verfahren} aus der Spieltheorie
kann man so die besten Zugfolgen ermitteln (siehe dazu
Kapitel~\ref{sec:Spieltheorie} und ~\ref{sub:MiniMax}).
Aber selbst mit \emph{sehr schnellen} Computern kann man mit dieser
Methode keine großen Tiefen erreichen.

Um größere Tiefen im Suchbaum zu erreichen benötigt man das
\emph{Alpha-Beta Verfahren}. Wenn eine Stellung gefunden wurde, die
für den Gegner gut ist, dann wird der 
Teilbaum unterhalb dieser Stellung, von dem Verfahren, nicht weiter
betrachtet, sondern 
die Positionen weiter untersucht, die diese Stellung vermeiden.
Neben dem Alpha-Beta Verfahren haben sich noch andere Verfahren wie
das \emph{Negamax Verfahren}, das \emph{SSS$^*$ Verfahren}, oder der
\emph{MTD Algorithmus} entwickelt. Jedoch haben sich der Alpha-Beta
Algorithmus und der Negamax Algorithmus, welcher sehr stark an den
Alpha-Beta Algorithmus angelehnt ist, bis heute in den starken
Schachprogrammen durchgesetzt. Die heute eingesetzten Algorithmen sind
durch zahlreiche Verbesserungen in ihrer Effizienz stark gesteigert
worden.

Neben den Verbesserungen der Kernalgorithmen wurden auch Module wie
die Eröffnungsbücher und die Endspieldatenbanken entwickelt, die das
Wissen der Schachvergangenheit den Programmen zur Verfügung stellen.


Wie schon in der Einführung beschrieben ist Schach ein
Benchmarkproblem, das genau definiert ist und die Güte der Verfahren
kann genau gemessen werden. Die Struktur von Schach macht es
\emph{Brute Force} Verfahren nicht möglich gute Lösungen zu erreiche,
so dass \emph{intelligente Techniken} verwendet werden müssen. So werden
Techniken, die in Schachprogrammen verwendet werden, auch für
die Mustererkennung, Problemlösung, Optimierungsheuristiken und andere
\emph{real World} Probleme genutzt. 


Im folgenden wird nun erklärt, welche Algorithmen und Datenstrukturen
genutzt werden und welche Teilprobleme gelöst werden, damit ein
Computer Schach spielen kann.

%----------------------------------------------------------------------
%\subsection{Das interne Brett}
%----------------------------------------------------------------------

%----------------------------------------------------------------------
\section{Materialbewertungen}
%----------------------------------------------------------------------
\label{sec:MaterialBewertung}

Der \emph{Materialbewertung}\index{Materialbewertung} kommt im
Computerschach eine zentrale Rolle zu, denn die Suche nach einem guten
Zug kann nicht bis zum Gewinn oder Verlust der Partie berechnet
werden. Daher wird die Suche in einer Situation unterbrochen, in welcher
der Ausgang der Partie noch offen ist. Schon Shannon~\cite{shannon50}
hat eine Bewertungfunktion postuliert, die die folgenden vier Punkte umfasst:
\begin{enumerate}
\item Die relativen Werte sollten für die Königin 9, den Turm 5, den
        Läufer 3 den Springer und den Bauern 1 betragen. Diese Werte
        müssen für beide Seiten aufaddiert werden und die Seite mit
        dem höheren Wert hat die bessere Position.
\item Türme sollten auf offenen Linien stehen. Denn die Seite mit der
        höheren Mobilität hat eine bessere Stellung, wenn sonst alles
        gleich ist.
\item Doppelbauern, isolierte und rückwärtige Bauern sind schlecht.
\item Ein exponierte König ist schlecht außer im Endspiel.
\end{enumerate}

Dieser Aufbau für eine Bewertungfunktion hat noch heute seine
Gültigkeit und neue Funktionen haben prinzipielle Erweiterungen zu
der Bewertungsfunktion von Shannon. Diese Erweiterungen entsprechen
den Punkten 2-4 von Shannons Funktion. Heutzutage versucht man 
weitere Faktoren einzubeziehen, welche die Aktivität oder die
Stellung einzelner Figuren oder Gruppen mit berücksichtigen. Viel
dieser Elemente finden man in dem Buch von Hans Berliner \emph{The
System}~\cite{berliner:99}, der als Schachspieler im ersten Teil des
Buches verschiedene zusätzliche Merkmale beschreibt, die für eine
Stellungsbewertung wichtig sind. So werden in neueren Bewertungen auch
die Beherrschung des Brettzentrums mit einbezogen, da von dort aus
alle anderen Positionen leichter erreichbar sind und dort platzierte,
starke Figuren den größtmöglichen Einfluss haben. Aber auch der
Mobilität der verschiedenen Figuren wird Rechnung getragen.

Alle Bewertungsfunktionen haben eine große Zahl von Parametern
gemeinsam, diese werden im allgemeinen durch die Entwickler
bestimmt. Es stellt sich aber die Frage, ob diese Werte auch die
optimalen Werte waren oder ob man mit anderen Werten bessere
Ergebnisse erzielen kann. Daher wurden verschiedenste Verfahren der CI
auf die Problematik der Stellungsbewertung angewendet, um sie zu
verbessern. 

Genetische Algorithmen wurden von verschiedenen Autoren
durchgeführt~\cite{tiggelen:91,tunstall:91,mys:94}, dabei wurden 
Gewichtsvektoren evolviert, die die Parameter für eine Brettbewertung
optimieren sollten. Obwohl die Brettbewertung  in jeder
Untersuchung für verschiedene Spielabschnitte eingesetzt wurde, war
die Fitnessfunktion immer als Suche nach guten Zügen für bekannte
Stellungen definiert.

Fuzzy Logik wurde auch zur Verbesserung der Stellungsbewertung genutzt,
wozu teilweise auch mehrere Fuzzywerte für verschiedene Elemente der
Bewertung genutzt werden (siehe~\cite{jung:fuzzy:94,jung:fuzzy:95}). 

Neuronale Netze wurden nicht nur für die Bewertung genutzt, aber auch
hierzu wurden verschiedene Untersuchungen durchgeführt. So lernten
Beal und Smith mit einem Netz die Figurwerte~\cite{beal:www}, die
Werte der Figuren wurden dafür normalisiert, so dass der Bauer einen
Wert von 1 hatte, für den Läufer von 2.219, den Springer von 3.114, den Turm
von 4.680 und die Königin von 9.154. Trotz der relativ geringen
Änderungen zu den Werten von Shannon konnten Programme mit diesen
Werten 57\% der Spiele gewinnen, dabei wurden 2000 Spielen
durchgeführt.

Auch die Evolutionären Verfahren wurden verwendet um die Materialwerte
zu bestimmen. Die Individuen bestehen aus den einzelnen Werten für die
Funktion der Stellungsbewertung. Das Verfahren evolviert also zu dem
gegebenen Algorithmus die Materialwerte der Figuren oder positionelle
Kriterien (siehe ~\cite{kantschik:2002:gecco,kendell:01}).

Mysliwietz nutzt das \emph{Simulated Annealing (SA)} als
Vergleichsverfahren zum GA um die Materialvektoren anzupassen
~\cite{mys:94}. Er erreicht mit dem SA bessere Ergebnisse als mit dem GA.

Auch die Genetische Programmierung (GP) wurde für die
Materialbewertung genutzt, dabei war es in den System von ChessGP nur
ein GP Modul von anderen, die zusammen Schach spielen
konnten~\cite{kantschik:2000:TechRep}. 


%----------------------------------------------------------------------
\section{Der Zuggenerator}
%----------------------------------------------------------------------

Der \emph{Zuggenerator}\index{Zuggenerator} ist ein Modul eines
Schachprogramms das nur selten erwähnt wird. Die Aufgabe ist es
\emph{legale Züge} für eine Stellung zu erzeugen, dass heißt der
Generator muss die Regeln des Schachspiels kennen und sie
anwenden. Von diese Regeln kann auch nicht abgewichen werden, denn
sonst würde der Generator keine legalen Züge ermitteln, daher gibt es
keinen Raum für Optimierungen innerhalb des Generator und so wird in
allen System vorrausgesetzt, dass es einen Zuggenerator gibt und das
er korrekt arbeitet. Neben den Regeln über die Gangarten der Figuren
muss der Generator aus allen möglichen Zügen noch die legalen
extrahieren. Dies geschieht normalerweise durch Beantwortung folgende
Fragen: 
\begin{itemize}
\item Ist das jeweilige Zielfeld noch auf dem Schachbrett?
\item Ist das Zielfeld leer oder besetzt? Wenn es besetzt ist, ist es
        eine gegnerische Figur oder eine eigene.
\item Wird der eigene König nach dem Zug angegriffen?
\item Ist ein En-passant Zug für einen Bauern möglich?
\item Ist eine Rochade möglich?
\end{itemize}


%----------------------------------------------------------------------
\section{Zugbewertung}
%----------------------------------------------------------------------
\label{sec:Zugbewertung}

Die \emph{Zugbewertung}\index{Zugbewertung} ist nicht so klar
definiert wie der Zuggenerator. Die Frage, die von dem Algorithmus
beantwortet werden muss, ist, ob ein Zug \emph{gut} oder
\emph{schlecht} ist. Aber dafür gibt es im Schach keine einfache
Formel, nicht einmal eine zuverlässige Strategie\footnote{Für weniger
komplizierte Spiele wie NIM sind solche Formeln bekannt.}. Die
Zugbewertung ist besonders für Alpha-Beta und ähnliche Verfahren
sinnvoll, denn sie basieren auf einer Suchfenster-Technik, bei der
stets der Wert der besten Alternativen des weißen und schwarzen
Spielers im Suchfenster ($\alpha, \beta$) gespeichert wird. Je
schmaler das Fenster ist, desto größer ist die Chance von Schnitten im
Suchbaum. Eine gute Vorsortierung der möglichen Züge kann somit zu
einer Steigerung der Suchleistung führen, da der Algorithmus früher
die Suche in schlechten Stellungen beenden kann(~\cite{heinz00,slag69,schae89}).

Die Zugbewertung ist ein schwieriges Problem, das aber eine große
Bedeutung für die Güte von Schachprogrammen hat. So werden in vielen
Programmen einfache Heuristiken oder eine Kombination aus den
Heuristiken verwendet um eine Sortierung durchzuführen. Folgende
Heuristiken werden in Schachprogrammen genutzt:  
\begin{description}
\item [Spielphase] Als Merkmal wird dabei eine Kombination aus
        der Spielphase und dem Figurtype genutzt. Hierbei werden
        Regeln aufgestellt, die Besagen, dass verschiedene Figuren zu
        verschiedenen Phasen des Spiels wichtig sind.
\item [Figurwert] Der Materialwert der ziehenden Figur wird als
        Kriterium für die Sortierung genutzt.   
\item [MVV/LVA] \emph{(Most Valuable Victiom / Least Valuable
        Aggressor)} ist der Quotient der geschlagenen und der
        schlagenden Figur. Je höher der Wert der geschlagenen Figur und
        je geringer der Wert der schlagenden ist, desto höher ist das
        Merkmal ausgeprägt. Ist der Zug aber kein Schlagzug, ist das
        Merkmal 0.
\item [Zentrumsaktivität] Wenn die Zielfelder eines Zuges im Zentrum des Schachbrettes
        liegt wird ein Bonus vergeben.
\item [Killermoves] \emph{Killermoves}\index{Killermoves} sind Züge,
        die in früheren Situationen zu einem Schnitt im Suchbaum
        geführt haben. Wird so ein Zug an einer anderen Stelle im
        Suchbaum wieder verwendet, wird er mit einem Bonus versehen.
\item [Iterative Deepning] Der Spielbaum wird in Iteration $n$ bis zur
        Tiefe $n$ ausgewertet, die Informationen über die Bewertung wird
        in der Iteration $n+1$ zur Sortierung der Knoten genutzt (siehe auch~\ref{sec:iterDeep}).
\end{description}
 
Obwohl verschiedenste Heuristiken in Schachprogrammen verwendet werden,
findet man nur sehr wenige Versuche diese Probleme mit Methoden der CI
zu lösen. In \emph{Evolving Chess Playing
Programs}~\cite{kantschik:2002:gecco} wurde für die Zugsortierung ein
Evolutionärer Algorithmus verwendet, der für verschiedene Merkmale
Werte evolviert, die anschließend zu einer Bewertung zusammengefasst
werden. 


%----------------------------------------------------------------------
\section{Minimax / Negamax  Verfahren}
%----------------------------------------------------------------------
\label{sub:MiniMax}
\label{sec:FNega}



Die \emph{Spieltheorie}\index{Spieltheorie}, von Morgenstern und von
Neumann entwickelt, zeigt eine Möglichkeit auf, die beste Sequenz von
Zügen aus allen möglichen Zügen zu finden, indem ein Spiel als ein
Baum aus Spielpositionen betrachtet wird. Die Knoten sind die
Spielpositionen und die Kanten die erlaubte Züge zwischen den
Stellungen. Eine optimale Strategie kann dann effizienter als durch
eine vollständige Enumeration aller Strategien gefunden werden, indem
man den Baum mittels des \emph{Minimax Algorithmuses} durchläuft.
%Die Abbildung~\ref{fig:minMaxTree} verdeutlicht Teil eines
%Spielbaum für ein Schachspiel.
%Weitere Informationen zur Spieltheorie siehe
%Kapitel~\ref{sec:Spieltheorie}.

\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/minMax.eps,width=12cm}}
\caption{Die Abbildung zeigt einen Spielbaum mit den Bewertungen an
den Knoten, wie sie vom Minimax Algorithmus bei bekannter
Blattbewertung bestimmt werden. Die \emph{Max-Knoten} im Baum werden durch
blaue Pyramiden dargestellt und die \emph{Min-Knoten} durch grüne Pyramiden,
die auf dem Kopf stehen. } 
\label{fig:minMaxTree}
\end{figure}

Das \emph{Minimax Verfahren}\index{Minimax Verfahren} wurde von
Shannon 1950 in seinem Artikel beschrieben~\cite{shannon50}.
Der Minimax Algorithmus baut einen Spielbaum bis zu einer festen Tiefe
auf und ordnet jedem Blatt durch die Brettbewertung einen Wert zu. Der
beste Zug wird dann unter der Annahme ermittelt, dass sowohl der
Spieler als auch der Gegenspieler immer den besten Zug wählen.
Die Abbildung~\ref{fig:minMaxTree} zeigt einen Spielbaum der Tiefe
drei, mit den Werten für die Blattbewertung und die Bewertung der
Inneren Knoten durch den Minimax Algorithmus.

Rekursiv lässt sich der Algorithmus für den
 \emph{Minimaxwert}\index{Minimaxwert}
$v(k)$ für eine Blattbewertungsfunktion $\gamma$ wie folgt aufschreiben:
\begin{equation}
  v(k)=
        \begin{cases}
                \gamma(k) & \text{falls k ein Blatt ist} \\
              \max (v(n)) & \text{falls k ein innerer Max-Knoten ist} \\
              \min (v(n)) & \text{falls k ein innerer Min-Knoten ist} \\
         \end{cases}
\end{equation}


Der Spieler, der am Zug ist, wählt immer den Zug, der seinen Gewinn
maximiert, für den Gegner wählt er immer den Zug, der seinen Gewinn
minimiert. Daher wird diese Strategie auch \emph{Minimax} genannt.
Welcher der Züge nun den Gewinn maximiert, kann exakt nur an den
Blättern des Baumes bestimmt werden, wenn es zum Gewinn oder Verlust
des Spiels gekommen ist. Dies ist aber nur bei einfachen Spielen
möglich, wenn man einen kleinen Suchbaum hat. Für Schach ist es 
nicht möglich alle Stellungen zu berechnen (siehe
Tabelle~\ref{tab:Stellungen}). Daher wird bei diesem Verfahren der
Baum bis zu einer vorgegebenen Tiefe aufgespannt und die letzte Ebene
als Blätter interpretiert und mit einer Stellungsbewertungsfunktion
bewertet. Diese Werte werden dann in Richtung Wurzel propagiert.

Durch das exponentielle Wachstum des Spielbaums kann ein Minimax
Verfahren nie sehr tiefe Bäume aufspannen und ist dadurch in der
Spielstärke stark beschränkt. Denn die \emph{optimale Strategie} kann nicht
gefunden werden, da die Bewertung der \emph{Blätter} des Minimax
Baumes nur heuristisch sein kann. Für Spiele wie Tic-Tac-Toe und
Vier-Gewinnt sind die Spielbäume für heutige Computer überschaubar und
so ist die \emph{optimale Strategie} schon bekannt und der Spielbaum
muss nicht konstruiert werden. 

Das \emph{Negamax Verfahren}\index{Negamax Verfahren} ist eine
Variante des Minmax Verfahren, dabei gilt nur das 
\[ 
 min(a,b) = -max(-a,-b)
\]
ist. Dadurch verändert sich die Definition der Minimaxwerte wie folgt:
\begin{equation}
  v(k)=
        \begin{cases}
                \gamma(k) & \text{falls k ein Blatt auf der Max-Ebene ist} \\
              \gamma(k) & \text{falls k ein Blatt auf der Min-Ebene ist} \\
              -\max (v(n)) & \text{sonst} \\
         \end{cases}
\end{equation}

Der Unterschied zum Minimax Algorithmus ist hauptsächlich in der
Implementierung zu sehen, denn sie ist einfacher, da man nun nur eine
Operation für die inneren Knoten hat, die nicht vom Typ abhängig
ist. Die Effizienz des Verfahrens ist die gleiche und die Bewertung
der Blätter ist gleich aufwendig. An den Blättern wird zusätzlich noch
die Entscheidung  getroffen, ob ein Min- oder Max-Blatt vorliegt, was
aber einfach ist.

%----------------------------------------------------------------------
\section{Alpha-Beta Verfahren}
%----------------------------------------------------------------------
\label{sec:alphaBeta}

Da Alpha-Beta Verfahren\index{Alpha-Beta Verfahren} wurde von Herbert
Simon und Allen Newell\footnote{Sie sagten 1956 voraus, dass ein
Computerprogramm in den nächsten 10 Jahren Weltmeister wird.} entwickelt. 

\begin{table}
\begin{tabular}{|c|c|c|c|}
\hline
 \textbf{Halbzüge} &  \textbf{Anzahl der Stellungen} &
 \textbf{$5*\sqrt{n}$}  &  \textbf{Stellungen/Sek. bei 3 min/Zug}\\
\vspace{0.3mm}
%\hline \\
 1  & 40                & --            & -- \\
\vspace{0.3mm}
%\hline
 2  & 1600              & 200            & 1.1 \\
\vspace{0.3mm}
%\hline
 3  & 64.000            & 1265           & 7 \\
\vspace{0.3mm}
%\hline
 4  & 2.6 Millionen     & 8000           & 44 \\
\vspace{0.3mm}
%\hline
 5  & 102 Millionen     & 50.000         & 281 \\
\vspace{0.3mm}
%\hline
 6  & 4.1 Milliarden    & 320.000        & 1777 \\
\vspace{0.3mm}
%\hline
 7  & 164 Milliarden    & 2 Millionen    & 11.000 \\
\vspace{0.3mm}
%\hline
 8  & 6.5 Billionen     & 13 Millionen   & 70.000 \\
\vspace{0.3mm}
%\hline
 9  & 262 Billionen     & 80 Millionen   & 450.000 \\
\vspace{0.3mm}
%\hline
 10  & 10 Billiarden    & 512 Millionen  & 2.8 Millionen \\
\vspace{0.3mm}
%\hline
 11  & 419 Billiarden   & 3.2 Milliarden & 17 Millionen \\
\vspace{0.3mm}
%\hline
 12 & 17 Trillionen     & 20 Milliarden  & 113 Millionen \\
\vspace{0.3mm}
%\hline
 13  & 671 Trillionen   & 129 Milliarden & 719 Millionen \\
\vspace{0.3mm}
%\hline
 14  & $2.7 * 10^{22}$  & 819 Milliarden & 4.5 Milliarden \\
%\vspace{0.3mm}
\hline
\end{tabular}
\caption{Auswirkungen des Alpha-Beta Verfahrens auf die Größe des
Suchbaumes.}
\label{tab:AlphaBeta}
\end{table}




Der Alpha-Beta-Algorithmus~\cite{schae89} ist eine Verbesserung des
Minimax Verfahrens, denn bei der Anwendung des Minimax Verfahrens
fällt auf, dass zum Teil Knoten des Baumes untersucht werden, die das
Ergebnis, d. h. den Minimax-Wert an der Wurzel, gar nicht
beeinflussen.

Die Alpha-Beta Suche basiert auf der Idee nur die Werte zu berechnen
die untersucht werden müssen, aber ohne relevante Informationen zu
verlieren. Dazu wird jedem \emph{Max-Knoten}\index{Max-Knoten} ein
Wert $\alpha$\index{$\alpha$} und jedem \emph{Min-Knoten}\index{Min-Knoten} ein Wert
$\beta$\index{$\beta$} zugewiesen. $\alpha$ stellt eine untere
Schranke, $\beta$ eine obere Schranke für den Minimax-Wert des
jeweiligen Knotens dar. Desweiteren unterscheidet man zwischen
vorläufigen und endgültigen $\alpha-$ bzw. $\beta-$Werten. Ein
vorläufiger $\alpha-$Wert für einen Max-Knoten (bzw. $\beta-$Wert für
Min-Knoten) kennzeichnet eine Bewertung, die Max (bzw. Min) von diesem
Knoten aus auf jeden Fall erreichen kann. Ein endgültiger
$\alpha-$Wert (bzw. $\beta-$Wert) bezeichnet die Bewertung des für Max
(bzw. Min) von diesem Knoten aus günstigsten Zuges. Analog zum
Minimax-Verfahren versucht Max, den $\alpha-$Wert zu maximieren,
während Min den $\beta-$Wert minimieren möchte. Daher wird $\alpha$
mit $-\infty$ initialisiert und wächst monoton, $\beta$ mit $+\infty$
initialisiert und fällt monoton.

Der Algorithmus verfährt dann wie folgt: Der Baum wird mit Hilfe der
Tiefensuche bis zu einer fest vorgegebenen Suchtiefe expandiert. Auf
die Blattknoten wird die Bewertungsfunktion direkt angewendet. Dieser
Wert entspricht nun dem $\alpha-$Wert des Knotens (bei Max-Knoten)
bzw. dem $\beta-$Wert (bei Min-Knoten). Steht nun für einen Knoten der
endgültige $\alpha-$Wert fest, so wird er als vorläufiger $\beta-$Wert
an den unmittelbaren Vorgänger weitergereicht, wobei sich der neue
$\beta-$Wert aus dem Minimum des neuen und alten Wertes ergibt. Analog
wird der endgültige $\beta-$Wert als vorläufiger $\alpha-$Wert an den
Vorgänger weitergereicht und der neue $\alpha-$Wert des Vorgängers aus
dem Maximum des hochgereichten Wertes mit dem alten $\alpha-$Wert
berechnet.

Die für jeden Knoten mitgeführten $\alpha-$ bzw. $\beta-$Werte
ermöglichen nun das \emph{Abschneiden (cutoff)} von Teilbäumen.
Der Spielbaum in der Abbildung~\ref{fig:alphaBeta} zeigt die $\alpha-$
und $\beta-$Schnitte. Der $\beta-$Schnitt für den Max-Knoten mit der
Bewertung 9 ergibt sich, da der $\beta-$Wert für diesen Knoten bei 5
liegt und die Bewertung des Nachfolgers zum Wert 9 gelangte. Da der
Vorgänger von 9 ein Min-Knoten ist, muss dieser Pfad nicht weiter
verfolgt werden. So müssen alle weiteren Nachfolger nicht mehr
betrachtet werden, man hat einen $\beta-$Schnitt durchgeführt. Der
linke Sohn der Wurzel ist dann vollständig bewertet und hat einen Wert
von 5, dieser wird als $\alpha-$Wert an die Wurzel weitergegeben, mit
diesem  $\alpha-$Wert wird dann der rechte Teilbaum bearbeitet. Dieser
erhält den $\beta-$Wert, nachdem der linke Teilbaum bearbeitet
wurde. Da im rechten Teilbaum ein Wert von 5 erreicht wurde, kann nun
ein $\alpha-$Schnitt für die anderen Nachfolger durchgeführt werden.
Die Bewertung der Wurzel hat einen Wert von 5 wie bei dem Minimax
Verfahren, jedoch mussten nicht alle Knoten bearbeitet werden.

\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/alphaBeta.eps,width=12cm}}
\caption{ Der Spielbaum mit $\alpha, \beta$ Werten. Unter dem Knoten
stehen immer die Werte des Knotens und an den Kanten die propagierten
Werte. Knoten, die abgeschnitten werden, sind transparent dargestellt,
diese werden nicht bewertet, ihre Bewertung steht aber daneben.} 
\label{fig:alphaBeta}
\end{figure}

Die Einsparungen des Alpha-Beta Verfahrens hängen stark von der
Reihenfolge ab in der die Knoten bearbeitet werden. Die Möglichkeiten,
dass Teile des Suchbaums abgeschnitten werden können, hängt davon ab,
dass gute Züge früh gefunden werden. Die
Abbildung~\ref{fig:alphaBetaWC} zeigt den Suchbaum mit den gleichen
Werten, aber einer anderen Sortierung der Zügen. In diesem Fall kann
das Alpha-Beta Verfahren keinen Teilbaum abschneiden. Im worst case
muss das Verfahren genauso viele Knoten expandieren wie das Minimax
Verfahren. Im günstigsten Fall jedoch ist der zuerst gefundene
vorläufige $\alpha-$Wert immer gleich der endgültige $\alpha-$Wert
(analog für $\beta$). Dies führt dann zur größtmöglichen Anzahl von
Schnitten. Es lässt  sich zeigen, dass bei einem Baum der Tiefe $T$
und Verzweigungsfaktor $V$ im best case
\begin{equation}
  n=
        \begin{cases}           
              2V^{T/2}-1  & \text{für gerade } T \\
              V^{(T+1)/2}-V^{(T-1)/2}-1 & \text{für ungerade } T \\
         \end{cases}
\end{equation}
von $V^T$ möglichen Blattknoten zu analysieren sind. Moore und Knuth
haben 1975 in ihrem Artikel beweisen, dass im best case nur
$V^{(T+1)/2}-V^{(T-1)/2}-1$ Knoten im Baum expandiert werden
müssen~\cite{knuth:75}. Damit kann man in perfekten Spielbäumen bei
gleicher Knotenanzahl also doppelt so tief suchen wie mit dem Minimax
Verfahren. 

\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/alphaBetaWorstCase.eps,width=12cm}}
\caption{ Der Spielbaum mit $\alpha, \beta$ Werten. Unter dem Knoten
stehen immer die Werte des Knotens und an den Kanten die propagierten Werte. } 
\label{fig:alphaBetaWC}
\end{figure}


%---------------------------------------------------------------------- 
\section{Verbesserungen}
%---------------------------------------------------------------------- 
\label{sub:SchachHeuristiken}

Die Effizienz eines Suchverfahrens hängt im wesentlichen von der
Anzahl der expandierten Knoten im Suchbaum ab. Die Zugreihenfolge ist
hierbei ein sehr wichtiges Instrument zur Verbesserung der Alpha-Beta
Algorithmen.  

%---------------------------------------------------------------------- 
\subsection{Iterative Deepening}
%---------------------------------------------------------------------- 
\label{sec:iterDeep}

Das \emph{Iterative Deepening}\index{Iterative Deepening} ist eine
Heuristik zur Vorsortierung von Zügen im Suchbaum~\cite{deep}. Das
Verfahren geht dabei so vor, dass der Spielbaum zunächst bis zu einer
Tiefe $n$ ausgewertet wird, danach werden die Informationen über die
Knoten zur Sortierung der Knoten genutzt und in der nächsten Iteration
wird der Spielbaum bis zur Tiefe $n+1$ ausgewertet. Da die Verfahren
nicht zwingend den korrekten Minimaxwert der einzelnen Kinder an die
Wurzel zurückliefern, sondern nur obere Schranken, ist die Sortierung
der Knoten nicht ganz korrekt. In jeder Iteration werden bessere Werte
für die Knoten ermittelt und somit verbessert sich auch die
Sortierung. Der iterative Prozess wird beendet, wenn die maximale
Suchtiefe erreicht wurde oder ein Zeitlimit erreicht wird.
Das iterative Vorgehen ist möglich, da die Auswertung eines
Spielbaumes bis zur Tiefe $n$ billig im Vergleich zur Auswertung bis
zur Tiefe $n+1$ ist. Weitere Ersparnisse kann man noch erreichen, wenn
die Informationen aus früheren Auswertungen gespeichert werden und
somit nicht mehrfach berechnet werden müssen.

%---------------------------------------------------------------------- 
\subsection{Principal Variation Search}
%---------------------------------------------------------------------- 

Die \emph{Principal Variation Search}\index{Principal Variation
Search} ist eine weitere Verbesserung des Alpha-Beta Verfahrens, die
aber auf einer einfachen Idee beruht. Die Annahme ist, dass man eine
gute Zugsortierungsfunktion hat. Auf dieser Annahme aufbauend, braucht
man nur die \emph{besten} Züge aus der Liste sehr genau zu untersuchen und
die \emph{schlechteren} Züge nicht so genau. Bei einem Alpha-Beta
Verfahren wird das Suchfenster verkleinert, der $\alpha$ wird bei der
weiteren Suche einfach erhöht. Wenn die Annahme richtig war, sind die
besten Züge schon betrachtet worden und die weitere Suche wird
schneller zu einem Näherungswert kommen, da das Verfahren mehr Bereiche des
Baums abschneiden kann. Wenn es sich aber doch um einen guten Zug
handelt, kommt es zu einem Fehler, da ein $\beta$-Schnitt nicht
durchgeführt werden kann. Der Fehler ist ein zu hoher $\beta$-Wert und
er zeigt an, dass der Zug den aktuellen $\alpha$-Wert verbessern
würde. Daher muss an dieser Stelle die Suche mit den Originalwerten
wiederholt werden. Dies passiert, da man den $\alpha$-Wert erhöht
hatte und nun einen Zug gefunden hat, der ihn noch mal verbessert.

Die Erwartung dieser Heuristik ist, dass der Zeitgewinn durch die
Modifikation des Suchfensters größer ist als der Zeitverlust durch
die erneute Suche falls es zu einem Fehler kommt. Wichtig bei dieser
Heuristik ist eine gute Zugsortierung, die für alle Alpha-Beta
Verfahren vorteilhaft ist, denn sie ermöglicht es schneller die
entscheidenden Züge zu finden und große Teile des Baums abzuschneiden.

 
%---------------------------------------------------------------------- 
\subsection{Hashtabellen}
%---------------------------------------------------------------------- 
\label{sub:HashTab}

Die \emph{Hashtabellen}\index{Hashtabellen} speichern Stellungen des
Suchbaums mit deren Bewertung. Denn der Suchbaum im Schach ist
eigentlich ein Graph und so kann eine Stellung durch verschiedene
Zugfolgen erzeugt werden. So ist es möglich, dass eine Stellung einmal
nach 5 und auf einem anderen Weg erst in 7 oder 8 Zügen erreicht
wird. Wenn das Ergebnis der Stellung nun gespeichert ist, braucht sie
nicht noch einmal analysiert werden. Die Hashtabellen werden dabei
während der Analyse der aktuellen Stellung aufgestellt. Diese Tabelle
wird aber nicht nach dem Zug gelöscht, sondern im Spiel weiter
verwendet. Bei der nächsten Stellung wird dann zuerst immer überprüft,
ob die Stellung schon in der Tabelle vorhanden ist. Wenn nicht, wird die
Suche normal weiter verfolgt. Falls die Stellung schon einmal
analysiert wurde, wird noch überprüft, ob dies zum aktuellen Zeitpunkt
noch ausreichend ist. Wenn der Eintrag als veraltet eingestuft wird,
da aktuelle Tiefe im Suchbaum ähnlich der Analysetiefe der Stellung in
der Tabelle ist, wird die Stellung weiter analysiert und die Werte in
der Hashtabelle mit den neuen Werten modifiziert.
Normalerweise werden in einem Tabelleneintrag neben dem Hashschlüssel
für die Stellung die Bewertung der Stellung, die Tiefe, bis zu der
die Stellung bewertet wurde, und der \emph{Typ} des Wertes gespeichert.
Durch das Alpha-Beta Verfahren kann es auch dazu kommen, dass nicht
die exakten Werte für eine Stellung berechnet werden, sondern nur
obere und untere Grenzen und diese Information wird in dem Typ Feld
der Hashtabelle gespeichert. Die oberen oder unteren Grenzen sind zwar
nicht so gut wie die exakten Werte einer Stellung, wenn jedoch die
obere Grenze für den Wert einer Stellung schlechter ist als der
$\alpha$-Wert, dann muss diese Stellung nicht weiter expandiert
werden.

Der Hashschlüssel einer Stellung ist normalerweise eine ganze Zahl, die
aus der Stellung generiert wird. Dabei wird davon ausgegangen, dass es
zu keinen Kollisionen kommt. Es gibt aber auch Systeme, in denen
Kollisionen durch eine weitere Hashfunktion oder andere Verfahren, die
aus dem Hashing bekannt sind, verhindert werden. Jedoch darf der
Aufwand nicht zu groß sein, da sonst die Einsparungen durch die
Hashtabellen aufgebraucht werden.

 
%---------------------------------------------------------------------- 
\subsection{Killer Moves und History Heuristic}
%---------------------------------------------------------------------- 
\label{sub:KillerMove}

Die \emph{Killer Moves}\index{Killer Moves} und die \emph{History
Heuristic}\index{History Heuristic} sind weitere Verfahren um die
Zugsortierung zu verbessern.

Die \emph{Killer Moves} Heuristik speichert Züge, die sich schon an
anderen Stellen der Suche als gut herrausgestellt haben. Es handelt
sich dabei um Züge des Gegners, die sich als gut für den Gegner
herrausgestellt haben. Diese Züge haben zu $\beta$-Schnitten im Baum
geführt. Sie werden dann in Listen gespeichert abhängig davon wie
oft sie gespielt wurden, werden sie, wenn sie in einer Zugliste wieder
vorkommen, bei der Zugsortierung vorrangig beachtet. Hierbei ist zu
beachten, dass immer nur Züge betrachtet werden, die auf der gleichen
Ebene im Suchbaum liegen. Das heißt, ein Killer Move der Tiefe 6 wird
zu Beginn der Suche nicht als solcher für Tiefe 7 genutzt, außer es
stellt sich heraus, dass dieser Zug auch auf dieser Ebene ein Killer
Move ist.


Die \emph{History Heuristic} nutzt einen ähnlichen Ansatz wie die
Killer Move Heuristik, der wichtige Unterschied ist aber, dass sie
die guten Züge unabhängig von der Ebene im Suchbaum speichert. 
Die guten Züge werden gespeichert und wenn ein Zug im Verlauf des
Spiels wieder verwendet wird, er wird bei der Zugsortierung wie im Falle
der Killer Moves bevorzugt behandelt.

   
%---------------------------------------------------------------------- 
\subsection{Ruhe Suche}
%---------------------------------------------------------------------- 

Die \emph{Ruhe Suche}\index{Ruhe Suche} soll das Problem
des \emph{Horizont Effekts}\index{Horizont Effekt} Rechnung tragen.
Der Horizont Effekt tritt immer bei Verfahren auf, die die Suche nach
einer festen Tiefe abbrechen. In diesen Situationen kann es dazu
kommen, dass das Programm glaubt eine \emph{gute} Position erreicht zu haben,
aber 
wenn es noch einen Zug weiter suchen würde, würde es erkennen, dass es
in einer \emph{schlechten} Position ist. 
Um dieses Problem zu vermeiden werden in dieser Situation alle
Schlagzüge weiterverfolgt, bis man eine \emph{ruhige
Stellung}\index{ruhige Stellung} erreicht hat. Diese sind Stellungen,
von denen kein Schlagzug durchgeführt werden kann. Dieses Vorgehen
ermöglicht es dem Programm, auch lange Zugfolgen zu erkennen.

Diese Methode hat das Problem, dass der Suchbaum dadurch
sehr groß werden kann und somit den Aufwand nicht mehr
rechtfertigt. Hierzu werden verschiedene Heuristiken angewendet, die
die Größe einschränkt.




%Quiescence Width Extensions 
%I have already mentioned this method in a small amount of  detail, but
%it is worth clarifying. This is simply a way of improving the accuracy
%of the quiescence search when you think that it is necessary. Clearly
%there is little point in performing a full width search in all
%conditions, but if one of the kings is under heavy attack, it might
%well be worth it. 

% I keep track of a variable at each ply which tallies up the total
% number of extensions so far. This is set to zero initially. Any form
% of check at any point in the move analysis sets it to one. If at any
% point one of the sides has only one legal move in any position then
% the extension value is increased (to a maximum of 2 ply) and
% similarly if a side is in check and avoids it by moving its king. I
% always test positions that are in the principal variation with a
% depth of 3 ply. 

% This algorithm, amongst others, helped ColChess to make two large
% jumps in test score results between versions 5.4, 5.5 and 5.6. 

 
  
%---------------------------------------------------------------------- 
\subsection{Null Move Heuristik}
%---------------------------------------------------------------------- 

Ein \emph{Null-Move}\index{Null-Move} ist die Aufgabe des Zugrechts an den
Mitspieler ab, es ist also kein legaler Zug. Normalerweise wäre es
schlecht von seinem Zugrecht keinen Gebrauch zu machen. Wenn man nun
die Stellung analysiert, nachdem man auf sein Zugrecht verzichtet hat und
der Gegner somit zwei Züge hintereinander ausgeführt hat und die
eigene Stellung immer noch gut ist, dann handelt es sich um eine sehr
gute Stellung. Wenn man dies nun auf das Alpha-Beta Verfahren
anwendet, bedeutet es, dass, nachdem ein Null-Move ausgeführt wurde und die
Suche für den Gegner einen Wert kleiner als $\alpha$ (oder für die
Seite mit dem Zugrecht einen Wert größer als $\beta$) zurückgibt,
dann braucht der Teilbaum nicht
weiter Untersucht werden, da die Stellung so stark ist, dass sie bei
einer guten Strategie nie erreicht werden kann. Man erwartet also
einen $\beta$-Schnitt an dieser Stelle ohne den gesamten Teilbaum zu
expandieren.
Dieses Verfahren wurde von Donniger 1993 entwickelt und
eingesetzt~\cite{Donniger}. 

Die Heuristik hat neben den Vorteilen, dass der Baum stärker
beschnitten wird und dass die Knoten im Suchbaum, an dem ein Null-Move
eingesetzt wird, nur einen Ausgrad von eins haben, auch erhebliche
Nachteile. Wenn diese Methode ohne Bedacht eingesetzt wird, kann es zu
einer hohen Zahl von Fehlern kommen, besonders in Stellungen, in denen
\emph{Zugzwang}\index{Zugzwang} herrscht. Dies sind Stellungen, in
denen die Person, die ziehen muss, verlieren wird. 

Null-Moves sollten daher nicht durchgeführt werden, wenn folgende
Bedingungen gelten:
\begin{itemize}
\item  eine Zugzwang Situation herrscht, 
\item  die Seite, die zieht, nur wenige Figuren hat,
\item  die Seite, die zieht, nahe einem Schachmatt ist
\item  oder die Seite, die am Zug ist, im Schach steht.
\end{itemize}
Diese Liste kann und wird in verschiedenen Programmen noch durch
andere Regeln erweitert, diese sind aber die wichtigsten.


Ein weiterer wichtiger Parameter ist noch, um wieviel die Tiefe nach
einem Null-Move in dem Baum reduziert wird, diese wird normalerweise
um eins bis drei reduziert. Jedoch 
hat Heinz et al gezeigt, dass eine adaptive Tiefenreduktion besser ist
(siehe~\cite{heinz99c}). 


%---------------------------------------------------------------------- 
\subsection{Futility Pruning}
%---------------------------------------------------------------------- 

Das \emph{Futility Pruning}\index{Futility Pruning} wurde in
\emph{Dark Thought} zuerst eingesetzt (siehe
auch~\cite{heinz98a,heinz98b,heinz98c}).
Das Konzept ist recht einfach und wird auf Knoten angewendet, die sich
einen Halbzug vor der Ruhesuche im Suchbaum befinden. Für diese
Knoten wird überprüft, ob 
\begin{itemize}
\item die Seite, die zieht, nicht im Schach steht,
\item der aktuelle Zug kein Schlagzug ist,
\item der aktuelle Zug kein Schach verursacht,
\item die Bewertung aktuelle Stellung plus einen Schwellwert
(normalerweise ein Bauernwert) den $\alpha$-Wert nicht verbessert
\item oder der aktuelle Zug schlecht ist.
\end{itemize}
Wenn eines dieser Punkte zutrifft, wird die Stellung direkt bewertet
und die Suche abgebrochen. Die Grundidee der Heuristik ist also der
Abbruch der Suche, wenn man den $\alpha$-Wert nicht erhöhen kann.

Das Ziel dieser Heuristik ist es die Geschwindigkeit der Suche zu
erhöhen. Obwohl man durch dieses Vorgehen einige taktische Fehler in
Kauf nimmt, kann man sie im allgemeinen mehr als ausgleichen, wenn man
dadurch die Suche um einen Halbzug erhöhen kann.

Es gibt noch die Variante des \emph{Extended Futility
Pruning}\index{Extended Futility Pruning}, sie wird noch einen Halbzug
vor den Knoten des Futility Pruning durchgeführt. Diese Knoten werden
dann auch als \emph{pre-frontier} Knoten bezeichnet. Diese Variante
benutzt dann auch einen höheren Schwellwert für die Verbesserung des
$\alpha$-Wertes, dieser wird von einem Bauernwert auf einen Turmwert
erhöht.



%---------------------------------------------------------------------- 
\subsection{Search Extensions}
%---------------------------------------------------------------------- 

Die \emph{Search Extensions}\index{Search Extensions} Heuristik
ist der Versuch Züge die \emph{interessant} sind, genauer zu
untersuchen. Normalerweise wird die Suche bei einer maximalen Tiefe
abgebrochen, jedoch kann es sein, dass die Stellungsbewertung in
dieser keinen Vorteil für den Zug sieht. Wenn die Suche an dieser
Stelle etwas weitergehen würde, könnte man den Zug genauer beurteilen.

Genau dies wird bei dem Singular Extension Verfahren gemacht, es
versucht gute Züge weiter zu analysieren, um eine bessere Bewertung
für die Züge zu erhalten. Dafür werden diese Züge über die maximale
Tiefe der Suche hinaus analysiert. Dieses Verfahren führt zu einer
Steigerung der Spielstärke, kann aber auch zu sehr großen Suchbäumen
führen, was die Vorteile wieder aufzehrt.

 
Es gibt verschiedene Varianten der Search Extensions, wobei es aber
immer um eine Ausweitung der Suche geht. Folgende Search Extensions
werden in verschiedenen Programmen verwendet:
\begin{itemize}

\item \emph{Check Extensions}: Wenn die Seite, die am Zug ist, im
        Schach steht wird die Suche etwas erweitert, bei einem
        Schachmatt wird sie drastisch erweitert. 

\item \emph{Singular Extensions}:  Wenn es nur einen legale Zug in
einer Stellung gibt, wird die Suche fortgesetzt. Die Kosten sind
minimal, da der Ausgrad des Knotens nur eins ist.

\item \emph{Threat Extensions}:  Wenn es zu einer starken Bedrohung
        kommt, wird die Suche intensiviert, auch mit Hilfe von
        Null-Moves, um eine Lösung zu finden.

\item \emph{Pawn Push Extensions}:  Wenn ein Bauer auf der siebten
        Reihe steht oder die Möglichkeit zur Umwandlung hat. Dieses
        Verfahren hilft besonders im Endspiel.

\item Wenn die Sicherheit des Königs plötzlich stark sinkt,

\item die Bewertung sich ohne den Gewinn oder Verlust einer Figur
        stark ändert

\item oder wenn die Verteidigung durch ein Opfer verschlechtert wird.

\end{itemize}

 

%---------------------------------------------------------------------- 
\subsection{Datenbanken}
%---------------------------------------------------------------------- 
\label{sub:ErBuecher}

Das Schachspiel gliedert sich grob in die Eröffnung, das Mittelspiel und das
Endspiel, wann welche Phase endet und die nächste anfängt, ist nicht genau
definiert. Jedoch haben die verschiedenen Phasen unterschiedliche
Anforderungen an das Schachprogramm. Da ein Spiel immer mit der gleichen
Position beginnt, konnten die Eröffnungen sehr genau untersucht werden. Für
ein normales Schachprogramm mit seinem beschränkten Suchhorizont ist dies
ein Problem. Dies liegt daran, dass es schwierig ist, positionelle Kriterien
in  die statische Stellungsbewertung einzufügen und zu Beginn der Partie
hauptsächlich positionelle Kriterien die Güte der Stellung
unterscheiden. Diese Unterschiede werden erst jenseits des Suchhorizontes
eines Algorithmus, in ein Materialunterschied verwandelt werden. Aus diesen
Gründen wurden große  
\emph{Eröffnungsdatenbanken}\index{Eröffnungsdatenbank} in Schachprogramme
integriert, die Suche wird damit durch Wissen ergänzt oder ersetzt. Durch die
Datenbank können Schachprogramme sehr viel stärker spielen, da sie dadurch
eine gute Ausgangsposition für das Mittelspiel erreichen können.

Es gibt keine Datenbanken für das Mittelspiel, da die Menge der gespeicherten
Stellungen zu groß wäre um einen Vorteil für das Programm zu erhalten. Für die
Endspiele sieht dies jedoch anderes aus, hier ist die Anzahl der Figuren so
gering, dass man für das Endspiel alle Stellungen bis zum Ende
der Partie abspeichern kann. Diese
\emph{Endspieldatenbanken}\index{Endspieldatenbank} verbessern die Ergebnisse
der Schachprogramme, da die Suchverfahren in Endspielsituationen große
Schwierigkeiten haben. Dies liegt daran, dass in dieser Phase Strategien
notwendig sind, die sich über 50 Halbzüge oder mehr erstrecken, um den Gegner
matt zu setzen. Damit haben aber die Suchverfahren aufgrund des
Horizonteffektes große Probleme. Ende des Jahres 2002 waren bereits alle
Stellungen mit maximal 7 Figuren erfasst und analysiert, die Stellungen mit 8
Figuren sind derzeit in Arbeit, darunter sind Varianten, die erst nach über
200 Zügen zu einem Matt führen. Für den Endanwender sind derartige Forschungen jedoch eher
uninteressant, da auch der benötigte Platz mit der Anzahl der möglichen
Stellungen exponentiell zunimmt.

Wenn ein Schachprogramm zu Endspielen gelangt, die in seiner
Endspieldatenbank gespeichert sind, beschränkt sich das Schachprogramm auf
das Suchen der gegenwärtigen Stellung in einer Hashtabelle und das Ausführen
des dort für diese Stellung hinterlegten optimalen Zuges. Aus diesem Grund
werden in der Arbeit keine Schachprogramme mit Datenbanken evolviert, da dann
die Güte des Programm stark von der Güte der Datenbank abhängt und vom
eigentlichen Ziel der Entwicklung von Schachprogrammen ablenkt.
 

%---------------------------------------------------------------------- 
\section{State-space Suchverfahren}
%---------------------------------------------------------------------- 
\label{sub:SSS}

Das \emph{state-space Suchverfahren}\index{state-space Suchverfahren} wurde
1979 von George C. Stockman und unter dem Namen SSS$^*$\index{SSS$^*$}
vorgestellt (siehe~\cite{stockman79}). Der SSS$^*$ Algorithmus führt nicht wie
das Alpha-Beta Verfahren eine Rückbewertung der Blattwerte zur Wurzel durch,
sondern sucht nach der besten \emph{Max-Strategie}\index{Max-Strategie}. Der
Spielbaum einer \emph{Max-Strategie} unterscheidet sich von einem
vollständigen Spielbaum dadurch, dass jeder Max-Knoten im Baum nur einen
Nachfolger hat und alle Min-Knoten die gleichen Nachfolger haben wie im
vollständigen Spielbaum. Roizen und Peal konnten in ihrem Artikel einige Jahre
später zeigen, dass dieses Verfahren nicht mehr Knoten expandiert als ein
Alpha-Beta Algorithmus (siehe~\cite{Roizen:83}).
Später wurde von Marsland et al. eine weitere Variante des Algorithmuses
namens DUAL$^*$ eingeführt. Obwohl beide Verfahren in empirischen Vergleichen
deutlich weniger Knoten als ein Alpha-Beta Verfahren expandiert, wurde das
Verfahren kaum verwendet, dies liegt an dem hohen Speicherplatzbedarf. 

Um aber die beste Max-Strategie zu finden, werden  partiell expandierte
Max-Strategien in einer OPEN-Liste gespeichert. Der Speicherplatzbedarf der
OPEN-Liste ist $\Theta(b^{\frac{d}{2}})$, wobei $b$ der Verzweigungsfaktor und
$d$ die Suchtiefe ist, dadurch ist der Platzbedarf exponentiell und die
Rechenzeit pro Knoten wächst mit der OPEN-Liste. Aus diesem Grund ist das
Verfahren fünf- bis zehnmal langsamer als ein Alpha-Beta Verfahren.

In den neunziger Jahren folgten noch weitere Verbesserungen, der RecSSS$^*$ und
der RecDual$^*$ Algorithmus von Reinefeld (siehe~\cite{Reinefeld:94}). Diese
Algorithmen waren auf Grund einer effizienten rekursiven Impelementierung
hinsichtlich der Rechenzeit einem Alpha-Beta Verfahren leicht überlegen,
jedoch blieb der exponentielle Speicherplatzbedarf bestehen.

Durch die Darstellung des SSS$^*$ Verfahrens als eine Serie von Nullfenster
Alpha-Beta Aufrufen konnte eine weitere Variante entwickelt werden, der
MTD($f$) Algorithmus~\cite{Bruin:97,pijls99}. 

Der MTD($f$) Algorithmus kann als ein wettbewerbsfähiger Algorithmus
betrachtet werden, so wird er auch in einem spielstarken Schachprogramm des
MIT dem Clikchess, verwendet. Jedoch bleibt bei all diesen Verfahren das
Problem des großen Speicherplatzbedarfs.


%---------------------------------------------------------------------- 
\section{Nicht klassische Methoden}
%---------------------------------------------------------------------- 
\label{sec:nichtKlassisch}

Neben den klassischen Methoden des Computerschachs, wie sie oben
beschrieben wurden, gibt es auch Systeme, die Methoden des
\emph{maschinellen Lernens} oder der \emph{computational intelligence}
verwenden. Hierzu wurden 1986 ein erstes Überblick von Skiena im ICCA
Journal~\cite{skiena:86} veröffentlicht, dieser war eher pessimistisch
gestimmt, da diese Verfahren mit den klassischen Verfahren nicht
konkurrieren konnten. Zehn Jahre später wurde von
Fürnkranz~\cite{fuern:96} ein weiterer Artikel geschrieben, der die
Ergebnisse der vergangenen zehn Jahre auf diesem Gebiet zusammenfasst.

Eine Methode sind die \emph{induktiven
Lernalgorithmen}\index{induktiven Lernalgorithmen}, sie klassifizieren
Stellungen eines Schachspiels in die Klassen \emph{gewonnen} und
\emph{verloren} ein. Die Versuche mit diesem Verfahren wurden für
Endspiele im Schach verwendet, hierzu soll der Algorithmus aus einer
Menge Stellungen eine allgemeine Regel zur Klassifizierung von
Endspielen ableiten.


%---------------------------------------------------------------------- 
%\subsection{Schach SAL}
%---------------------------------------------------------------------- 
%\label{sub:Lern}


%---------------------------------------------------------------------- 
\subsection{Wissensbasierte Schachprogramme}
%---------------------------------------------------------------------- 

Systeme, die auf erklärungsbasiertem Lernen basieren, versuchen aus
vollständigen und korrektem Wissen Pläne zu konstruieren, die eine globale
Erklärung für die zu lösende Aufgabe sind. Da das Ziel aber oft nur durch
komplexe oder sehr viele Regeln beschreiben werden kann, muss der
Erklärungsprozess oft mit Vereinfachungen und Approximationen arbeiten. Diese
können aber zu Fehlern in den erzeugten Plänen führen. Wissensbasierte Systeme
sollten daher auch mit unscharfen Wissen arbeiten können, um der Komplexität
der Wissensbasis entgegen zu wirken.
(siehe~\cite{Hertzberg:89,Spies:93}). 

Das System von Tadepalli nutzt eine erklärungsbasierte Methode, er nennt sie
\emph{lazy explanation-based Learning, LEBL}~\cite{tad:89}. Das System
untersucht verschiedene Züge für beide Spieler mit Hilfe von \emph{O-Plänen},
bestehend aus einem Ziel und einer Abfolge von Zügen. O-Pläne sind
optimistisch, da für alle Züge angenommen wird, dass die gegnerischen Züge
entweder den Erfolg des O-Plans nicht beeinflussen oder selbst Teil des
O-Plans sind. Da bei der Erstellung und Analyse des Suchbaums nur auf die
Möglichkeiten zurückgegriffen wird, die durch die O-Pläne vorgegeben werden,
ist der Suchbaum sehr eingeschränkt. Um mehrere gegnerische Züge in Erwägung
zu ziehen, werden die O-Pläne zu komplizierteren Suchbäumen, den
\emph{C-Plänen}, verknüpft. 

LEBL erzeugt C-Pläne für jeden Spieler und testet sie gegeneinander, indem es
den Suchbaum erweitert und neu bewertet. Wenn ein C-Plan nicht mehr durch den
C-Plan des anderen Spielers geschlagen werden kann, wird die Konstruktion der
Pläne abgebrochen.

LEBL arbeitet besser, je mehr es gelernt hat, dies liegt daran, dass es
weniger Fehler macht, da es erschöpfender sucht. Das System sucht viel weniger
Knoten als eine Alpha-Beta Suche ab und berücksichtigt auch Strategien des
Gegenspielers, jedoch bleibt die Leistungsfähigkeit des Systems hinter der von
Alpha-Beta Suchen.


%---------------------------------------------------------------------- 
\subsection{Musterbasierte Schachprogramme}
%---------------------------------------------------------------------- 

Robert Levinsion entwickelte ein selbstlernendes, musterbasiertes
 Schachprogramm~\cite{levinson91,levinson01}. Das Ziel ist es ein Programm zu
 entwickeln, das mehr auf ``zusammenhängenden Urteilen''
 (associative-reasoning) basiert als auf eine Exploration des Suchbaums. Diese
 Muster sollten durch das Programm alleine entdeckt und erlernt werden.
Das Schachwissen des Systems beschränkt sich auf die Spielregeln und eine
 Graphrepräsentation für Brettpositionen. Eine Schachposition wird durch einen
 gerichteten bewerteten Graph dargestellt, wobei die Knoten die Spielfiguren
 und die unbesetzten Felder um die Könige darstellen. Die Kanten zeigen die
 Angriffs- und Verteidigungsbeziehungen zwischen den Figuren. Die Graphen
 werden bezüglich einer Halbordnung gespeichert, die durch eine Relation
 \emph{ist Teilgraph von}  gebildet wird. Diese Relation ist gleichbedeutend
 mit der Aussage, dass ein Graph \emph{allgemeiner} als der andere ist.

Als Lernverfahren wird eine Temporal Difference Methode (TD) genutzt, die
durch ein dynamisches boolesches Merkmal erweitert wurde~\cite{tempdiff}.
Das boolesche Merkmal gibt die An- oder Abwesenheit eines gegebenen Musters
für die aktuelle Position an. Die TD-Methode wird eingesetzt um das Gewicht
eines neuen Musters zu bestimmen. 

Wenn ein neues Muster gespeichert wird, sucht das Programm zuerst in den
bereits vorhandenen Mustern das dazu ähnlichste Muster und fügt einen
gemeinsamen Teilgraph als neues Muster ein. Zum Schluss wird dem Muster ein
Gewicht zugewiesen, das dem Durchschnittsgewicht seiner Eltern entspricht.
Ziel ist es durch eine gut gewählte Menge von Mustern einen ganzen Unterbaum
der Suche abschneiden zu können.

Bei Experimenten mit dem Programm hatte es keine Probleme, Schach-Prinzipien
wie \emph{Schlagen einer höherwertigen Figur} oder \emph{Schlagen ungedeckter
  Figuren} und andere zu erlernen. Das System erreichte 2001 bei einem Test im
Internet Chess Club (ICC) einen Elowert von 1024, dies entspricht dem Niveau
eines Anfängers.





%---------------------------------------------------------------------- 
\subsection{Neuronales Schach}
%---------------------------------------------------------------------- 
\label{sub:schachNeuro}

Neuronale Netze wurden auch verwendet um Schach zu spielen. Eines dieser
Systeme ist das \emph{NeuroChess System}\index{NeuroChess System} von
Sebastian Thrun~\cite{Thruns:1995}. Der zentrale Lernmechanismus ist ein
erklärungsbasiertes neuronales Netz. Thruns konstruierte im NeuroChess Netz
eine Bewertungsfunktion mit Hilfe der \emph{Temporal Difference}
Methode~\cite{temporaldiffNetz}. Die Aufgabe der TD(0) Methode, eine Variante
der TD-Methode, ist eine Bewertungsfunktion zu finden, die Schachstellungen
bezüglich ihrer Güte ordnet.

Da Schach  jedoch eine rein induktive Lerntechnik wegen der
Trainingszeiten praktisch nicht anwendbar war, verwendete Thrun
erklärungsbasierte 
Methoden, die mit weniger Trainingsdaten Spielsituationen verallgemeinern
können. Das erkärungsbasierte Neuronale Netz benutzt Wissen über das
Schachspiel, welches durch ein gesondertes Netz repräsentiert wird. Dieses Netz
besteht aus 175 Eingabeneuronen, 165 verborgenen und 175 Ausgabeneuronen, es
wurde mittels einer Datenbank mit 120000 Großmeister-Schachpartien
trainiert. Danach wird das NeuroChess System trainiert, welches die
Bewertungsfunktion lernen soll. Diese Netz besteht aus 175 Eingabeneuronen, 80
verborgenen Neuronen und einem Ausgabeneuron. 

Um nun die Stärke von NeuroChess zu messen wurden verschiedene Spiele gegen
ein Schachprogramm (GNU-Chess) durchgeführt. Dabei ist festzuhalten, dass
NeuroChess nur die Stellungsbewertung durchführt, um ein Schachspiel
durchzuführen, wird diese in einen Suchalgorithmus eingebunden.  


Ein weiteres System, welches Neuronale Netze nutzt um Schach zu lernen ist
SAL,  es wurde von Michael Gherrity  in seiner PhD Arbeit 1993
vorgestellt~\cite{sal:93}. 

SAL kann jegliche Zweipersonen-Brettspiele mit perfekter Information lernen,
 die ein quadratisches Brett  und Spielfiguren nutzen.
Hierzu muss SAL ein Zuggenerator für das Spiel zur Verfügung gestellt werden
 die Größe des Brettes, die Anzahl der Figuren und die Typen der Figuren.
SAL berechnet einen Zug dann mit Hilfe der Alpha-Beta Suche, verknüpft mit
 einer \emph{Konsistenz Suche} (consistency search). 
Die Konsistenz Suche geht davon aus, dass nur ein Kind eines inkonsistenten
Knotens im Suchbaum nicht korrekt berechnet wurde. Die Suche expandiert dann
 die Knoten weiter, bis es den fehlerhaften Knoten finden und ersetzen kann.

Als Bewertungsfunktion für die Knoten nutzt SAL ein Neuronales Netz. Die
Eingabe des Netzes sind die Position der Figuren, die Anzahl der Figuren für
jeden Typ, die Figur, die zuletzt bewegt wurde, die Figur, die geschlagen wurde
und eine weitere Anzahl von Ad Hoc Annahmen über Angriff, Verteidigung und den
Raum. Das Netz wird wie oft im Umfeld von Spielen mit der \emph{Temporal
  Difference} Methode trainiert. 


SAL wurde mit drei Spielen getestet, dem Tic-Tac-Toe, connect-four  und Schach.
Tic-Tac-Toe konnte SAL nach einer Lernphase von 20000 Spielen perfekt spielen,
d.h. SAL hatte die optimale Strategie gefunden.

Das Spiel connect-four ist komplizierter und SAL brauchte eine Lernphase von
100000 Spielen um gegen ein Programm 80 \% der Spiele zu gewinnen. Jedoch war
nicht klar, wie gut das Programm war, somit ist die Leistung nicht genau
einzuordnen. 

Bei dem Test für das Schachspiel hat das SAL-System in der Lernphase 4200
Spiele gegen GnuChess durchgeführt. GnuChess wurde dafür ohne Eröffnungs- und
Endspieldatenbank gestartet und das Programm durfte eine Sekunde pro Zug
rechnen, damit erreicht GnuChess einen Elowert von 1000-1200, was dem Niveau
eines Anfängers entspricht. SAL konnte acht Spiel gegen GnuChess zu
unentschieden spielen, alle anderen hat es verloren. Die Lernphase musste nach
4200 Spielen beendet werden, da die Rechenzeit zu hoch war. Jedoch war zu
diesem Zeitpunkt die Lernphase noch nicht beendet und SAL verbesserte sich zu
diesem Zeitpunkt noch, was anhand der Lernkurven zu erkennen ist.


%---------------------------------------------------------------------- 
%\section{Rechenleistung und Spielstärke}
%---------------------------------------------------------------------- 



%Erhöhung der Suchtiefe um 1, verändert sich der beste Zug?
 
%Spalte 1: Suchtiefe in Halbzügen (nach der Erhöhung)
%Spalte 2: Anteil der Veränderungen (in \% der Positionen), Crafty
%Spalte 3: dito, Dark Thought
 
%2       38.78   35.26
%3       36.73   39.65
%4       30.61   31.78
%5       30.32   29.45
%6       27.41   24.49
%7       24.49   21.28
%8       22.45   25.07
%9       18.37   21.57
%10      17.20   24.20
%11      16.62   17.49
%12      16.91   15.45
%13      14.58   16.62
%14      15.45   13.70



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