%----------------------------------------------------------------------  
\section{Geschichte des Schachspiels}
%---------------------------------------------------------------------- 
\label{sec:HistChess}

Das Spiel Schach fasziniert die Menschen schon seit Jahrhunderten,
fast jeder kennt das Spiel und kennt sogar die Spielregeln, aber
über die Entstehung des Schachspiels wurde schon viel philosophiert. 
Zahlreiche Legenden entstanden im Laufe der Zeit, die allerdings nur einen sehr
begrenzten geschichtlichen Gehalt aufweisen. 
Zu den bekanntesten gehört wohl die Weizenkorn-Legende.  

\textbf{Weizenkorn-Legende:} \index{Weizenkorn-Legende}

Der Weise Sissa ibn Dahir schaute lange mit an, wie sein indischer
Herrscher Shihram seine Untertanen tyrannisierte. 
Um zu beweisen, wie wichtig Untertanen stets für einen Herrscher
 sind, erfand er das Schachspiel. Der Tyrann begriff sofort, ließ das
 Schachspiel daraufhin verbreiten und war von nun an milder zu seinen
 Untergebenen. Aus Dankbarkeit für dieses erfundene Spiel gewährte er
 Sissa darauf einen freien Wunsch. Der listige Weise aber wünschte
 sich als Belohnung wie folgt Weizen: Auf das erste Feld des
 Schachbrettes 1 Korn, auf das zweite Feld 2 Körner, auf das dritte
 Feld 4 Körner usw. - also immer die doppelte Anzahl. Seinen Wunsch
 gewährte ihm der Herrscher in der Annahme, die gewünschten
 Weizenkörner aufbringen zu können. Bald verkündete aber der Vorsteher
 seiner Kornkammer, dass es so viele Weizenkörner nicht gebe -
 18.446.744.073.709.551.615 Körner ( 18 Trillionen, 446 Billiarden,
 744 Billionen, 73 Milliarden, 709 Millionen, 551 Tausend, 615). %Um
% solch eine Menge überhaupt transportieren zu können, benötigt man
% soviele Transporter, dass diese - hintereinander aufgestellt - 231.666
% mal um die Erde reichen. 
%Jene Körnermenge reichen auch - nach
% Berechnungen des englischen Mathematikers Lodge, um damit ganz
% England bis zu einer Höhe von zehn Metern zu bedecken. Folgendes
% beeindruckendes Beispiel beschrieb  W. Haas in der Zeitschrift
%  Rochade im August 1982:  Ein Güterzug mit allen Körner,
% der mit 80 km/h d. h. mit 2 Waggons pro Sekunde an uns vorbeiführe,
% jeder einzelne mit 20 Tonnen Weizen beladen, brauchte dazu 730
% Jahre!                 



Lange Zeit rätselten die Historiker, ob das Spiel erstmalig in China,
Persien oder Indien in Erscheinung trat. Erst 1977, als in Afrasiab
sieben Schachfiguren bei Ausgrabungen gefunden wurden, konnte man
endlich alle Unklarheiten beseitigen.   


Darlegungen aus der indischen Geschichte sowie Experten-Meinungen über
jene Figuren lassen darauf schließen, dass das Schachspiel seine Reise
etwa im zweiten Drittel des 7. Jahrhunderts in Indien begann.

In der Zeit entwickelte sich auch der Name des Schachspiels,
dieser entstammt dem Persischen für Schah (König), dort wurde es aber
noch \emph{Tschatrang}\index{Tschatrang} genannt. Dieser Name hat sich aus
dem indischen Namen entwickelt, der
\emph{Tschaturanga}\index{Tschaturanga} lautete, (tschatur=vier,
anga=Teil,Abteilung). Ein Heer in Indien setzte sich damals aus vier
Teilen (Waffengattungen) zusammen: Infanterie (Bauern), Kavallerie
(Pferde), Streitwagen und Elefanten - daher der Sanskritausdruck
Tschaturanga. Die indische Variante hatte mit unserem heutigem
Schach wenig gemeinsam. Gespielt wurde zu viert auf 64 Feldern - wobei
zwei Spieler jeweils eine Mannschaft bildeten - jedoch unter Einsatz
von Würfeln.
Wie sich letztendlich der Übergang vom Glücks- bzw. Würfelspiel zum
Zweischach als reines Intelligenz- und Kombinationsspiel entwickelte,
ist nicht bekannt. Als es über Handelswege nach Persien gelangte,
spielte man es bereits zu zweit ohne Würfel. In Persien wurde es
schließlich in Tschatrang umbenannt. 
Von den Persern gelangte das Spiel dann zu den Arabern,
die es \emph{Schatrandsch}\index{Schatrandsch} nannten. Hier ist der
heutige Name schon enthalten. Mit der Eroberung des Irans durch die
Araber sowie mit dem Aufbau eines starken arabischen Kalifates war die
Weiterentwicklung des  Schatrandschs schließlich auch in anderen
Länder gegeben. Es hat sich dann weiter über die arabischen Länder
nach Europa verbreitet, dies geschah um 1000. Es wurde letztendlich auf drei
Wegen nach Europa gebracht. Einmal über die russischen Ströme in den
Ostseeraum, von dort aus nach Norddeutschland und England, zum anderen
durch arabische Vermittlungen nach Italien und über die
Alpen. Außerdem verbreitete sich das Schachspiel noch durch die Mauren
nach Spanien und Frankreich. Die orientalischen Spielregeln blieben
dabei stets immer aufrecht erhalten, welche für die Dame nur einen
Schrägschritt und für den Läufer einen Schrägsprung aufs übernächste
Feld vorsehen. 

Um 1200 wurden die Schachregeln leicht verändert um das Spiel
dynamischer zu gestalten, so durften nun die Bauern einen
Doppelschritt aus der Ausgangsreihe vornehmen. Aber die größte
Änderung der Schachregeln wurde um 1500 durchgeführt. Man entschloss
sich zu einer grundlegenden Reform, welche zu den heutigen Gangarten
und Zügen führte. So wurde die  Rochade und der en passant Schlagzug
eingeführt. Das früher als Partiegewinn gewertete Patt wurde nun zum
Remis. Die wichtigsten Änderungen waren aber die Gangart der Königin
und des Läufers, sie durften jetzt nicht nur ein Feld weit gehen,
sondern über die gesamte Länge des Brettes. Dafür wurde das
Überspringen für den Läufer verboten.
Seit  diesem Zeitpunkt haben sich die Regeln nicht weiter verändert
und sich letztlich in die gesamte Welt verbreitet. 


\begin{table}
\begin{tabular}{rp{12cm}}
%\hline 
 Jahr n. Chr. &  Ereignisse \\ 
%\hline 
 ca. 670      & Das frühe, indische Schach hatte mit unserem heutigen
                Schach wenig gemeinsam. Der Name dieses Spiels lautete 
                auch nicht Schach, sondern Tschaturanga\index{Tschaturanga}. \\
\vspace{0.3mm}
  um 700     &  Der Name Schach entstammt dem persischen Schah=König. Die
                Perser übermittelten das Spiel den Arabern, die es Schatrandsch
                nannten.  \\
\vspace{0.3mm}
  um 800     &  Al-Adli war der erste namentlich bekannte
                Schachspieler von Rang. Der persisch-arabische Spieler war vermutlich
                der stärkste Schachspieler jener Zeit. Mittlerweile wurde auch in
                Mittel- und Westeuropa Schach gespielt. \\
\vspace{0.3mm}
  um 1000    &  Das Schachspiel gelangte nach Europa. \\
\vspace{0.3mm}
  um 1200    &  Durch die Einführung neuer Regeln versuchte man, das
                Schachspiel schneller und dynamischer zu gestalten, so durften
                z.B. jetzt auch die Bauern von ihrer Ausgangsreihe ausgehend einen
                Doppelschritt vornehmen. \\
\vspace{0.3mm}
  um 1400    &  Das erste historische Werk erschien, welches für das
                moderne Schachspiel von Bedeutung war. Dieses wurde von dem spanischen
                Schachmeister Juan Ramirez Lucena geschrieben. \\
\vspace{0.3mm}
    1467     &  Erstmalig fand in Deutschland (Heidelberg) ein
                Schachwettkampf zwischen der dortigen Gesellschaft des
                Schachspiels und den Nördlinger Schachfreunden
                statt. \\
\vspace{0.3mm}
    1477     &  In Nürnberg wurde das erste deutsche Schachturnier
                ausgetragen. \\
\vspace{0.3mm}
  um 1500    &  Erneut wurden die Schachregeln geändert - diesmal aber
                entschloss man sich zu einer grundlegenden Reform, welche zu den
                heutigen Gangarten und Zügen führte. Spanien
                löste das arabische Reich als führende Schachnation
                ab. \\
\vspace{0.3mm}
  um 1600    &  Von nun an gab es all jenes, was auch die heutige
                Schachwelt noch charakterisiert: Berufsspieler, internationale
                Wettkämpfe, Mannschaftskämpfe sowie  Blindspieler. Italien galt als
                die stärkste Schachnation. \\
\vspace{0.3mm}
  um 1750    &  Frankreich war nun das dominierende Land und der
                Franzose Francois Andre? Danican Philidor galt als der erste
                inoffizielle Schachweltmeister. \\
\vspace{0.3mm}
    1877     &  Der deutsche Schachbund (DSB) wurde in Leipzig
                gegründet. \\
\vspace{0.3mm}
    1886     &  Nach seinem Sieg über Zukertort wurde Wilhelm Steinitz
                der erste offizielle Schachweltmeister.  \\
\vspace{0.3mm}
    1924     &  Die FIDE (Abk. für: Federation Internationale des
                Echecs), Name des Weltschachbundes, wurde gegründet. Sie organisierte
                später die Weltmeisterschaften und legte unteranderem Normen für
                Großmeister, internationale Meister und schließlich auch FIDE-Meister
                bei Männer und Frauen fest. \\
\vspace{0.3mm}
    1927     &  In England (London) fand die erste Schacholympiade der
                Männer statt, bei der die Mannschaft aus Ungarn vor der aus Dänemark,
                Großbritannien, den Niederlanden, der Tschechoslowakei, Österreich und
                Deutschland gewann (insg. 16 Teilnehmerländer). Noch im gleichen Jahr
                fand auch erstmalig die Schachweltmeisterschaft der Frauen statt. Vera
                Menchik gewann damals vor ihren 11 Mitstreiterinnen die WM. \\
\vspace{0.3mm}
   1953      &  Cecil John Seddon Purdy, australischer internationaler
                Meister, wurde Sieger bei der ersten Fernschach-WM. \\
\vspace{0.3mm}
    1957     &  Die erste Schacholympiade der Frauen fand statt - die
                UdSSR siegte. Von 21 Teilnehmer erreichte die BRD den
                achten Platz. \\
\vspace{0.3mm}
 um 1960     &  Nach England, Deutschland, Österreich und nochmals
                Deutschland war jetzt die UdSSR führende Schachnation.   \\
\vspace{0.3mm}
    1993     &  Der Schachweltmeister Garri Kasparow gründet nach
                erneutem Streit mit der FIDE - mit dem englischen Großmeister Nigel
                Short die PCA (Professional Chess Association). Wie die FIDE trug auch
                die PCA Weltmeisterschaften aus, so dass die Schachwelt fortan zwei
                Schachweltmeister haben wird.  \\
\vspace{0.3mm}
   1996      &  Deep Blue verliert gegen Kasparow mit 4 : 2. \\
\vspace{0.3mm}
    1997     &  Erstmals verlor ein Weltmeister (Kasparow) bei einem
                Schachduell gegen einen Computer. Der IBM-Computer 
                Deep Blue gewann gegen den PCA-WM mit 3,5 : 2,5. \\
%\hline 
\end{tabular}
\caption{Tabelle mit den wichtigsten historischen Daten bei der
                Entwicklung des Schachspiels.}
\end{table}



% Dass das Schachspiel, diese wunderbare Gabe aus dem Morgenlande, nicht
% nur das edelste und schönste aller Spiele ist, sondern, auch an der
% Grenze von Spiel, Kunst und Wissenschaft stehend, zu den größten
% geistigen Genüssen gehört, diese Behauptung wird jeder Schachspieler
% gerne bestätigen.  




%---------------------------------------------------------------------- 
\section{Die Geschichte des Computerschachs}
%---------------------------------------------------------------------- 
\label{sec:HistCompChess}

Die Historie künstlicher Gedächtniskunst im Kampf gegen das menschliche
Hirn begann mit einem  "`Fake"'. Der ungarische Hofrat Wolfgang von
Kempelen (*1734, 1804) präsentierte auf Wunsch der
österreichischen Kaiserin Maria Theresia einen vermeintlichen
Schachautomaten mit einer eindrucksvollen Mechanik. Hinter dem
"`mechanischen Türken"'\index{mechanische Türke} verbarg sich im
Inneren der Maschine ein kleinwüchsiger Schachmeister, der die
Brettschlachten relativ souverän beherrschte.

Die erste Maschine, die wirklich Schach spielte, konstruierte der
Spanier Torres y Quevedo\index{Torres y Quevedo} im Jahre 1890. Der
Spanier war Ingenieur für elektromechanische
Steuerungssysteme. Torres wählte als Aufgabe für seine Maschine einen
begrenzten Teilbereich des Schachspiels, das Endspiel König und Turm
gegen König. Der Automat war kein Computer, auch kein Vorläufer
heutiger Rechenmaschinen, er löste die Aufgabe mit Hilfe von
mechanischer Übertragung von magnetischen Relais. Die Maschine
existiert noch heute und steht in der Polytechnischen Universität von
Madrid. 
 
Bis das erste Schachprogramm auf einem Computer lief, wurden zwar
schon Computerprogramme entwickelt, aber noch nicht 
auf Computern ausgeführt. Das erste Computerprogramm wurde wohl von
Konrad Zuse\index{Zuse, Konrad} zwischen 1942 und 1945 entwickelt, er
wollte aber nur die Möglichkeiten seiner Programmiersprache
\emph{Plankalkül}\index{Plankalkül} zeigen. Das Programm wurde nie
implementiert und erst 1972 veröffentlicht. Im gleichen Zeitraum
zwischen 1945 und 1947 entwickelte auch Alan Turing\index{Alan Turing}
Schachprogramm~\cite{turing53}, das korrekte Züge berechnete und eine Position
bewerten konnte. Auch er ließ sein Programm mangels eines 
existierenden Computers nicht laufen, jedoch simulierte er dessen
Berechnungen selbst. Im Jahr 1952 kam es zur ersten Partie von Turings
\emph{Papiermaschine}\index{Papiermaschine} und einem Kollegen, Alick
Glennie, einem reinen Hobbyspieler. Es entstand ein gleichwertiges
Spiel, die Maschine hätte im 22. Zug ohne weiteres gewinnen
können. Aber zur Frustration des Mathematikers führten die
Berechnungen zu einer schlechteren Fortsetzung. Zum Schluss verlor das
Programm durch eine einfache Fesselung. Turing erlebte erstmals
hautnah die Schwierigkeiten, mit denen  Schachprogrammierer noch
immer konfrontiert sind. Die Schwierigkeit ist dabei weniger, eine
Strategie für ein Schachspiel zu ersinnen, sondern eine Strategie so
zu formulieren, dass sie im Sinne des Erfinders von einer Maschine
ausgeführt wird.

Unabhängig von Turing hatte in den Vereinigten Staaten Claude
E. Shannon\index{C. E. Shannon}, Mitarbeiter der Bell Laboratories
über das gleiche Thema nachgedacht. Am 9. 3. 1949
hielt er einen Vortrag, in dem er die Möglichkeiten erörterte, einen
Computer für das Schachspiel zu programmieren. Er hielt diese Aufgabe
zwar für praktisch ohne Bedeutung, jedoch aus theoretischen Gründen
für äußerst wichtig. Denn die Lösung des Problems könnte, so der
Autor, den Anstoß geben, ähnlich gelagerte, jedoch weitaus wichtigere
Aufgaben auf dieselbe Weise zu lösen. Probleme, wie sie bei der
Erstellung von Schachprogrammen auftreten. In seinem Vortrag stellte
Shannon viele der wichtigsten Ideen vor, die heute in allen
Schachprogrammen enthalten sind:
\begin{itemize}
\item die interne Speicherung von Schachstellungen,
\item die Baumsuche,
\item die Bewertungsfunktion,
\item die Zugauswahl mit Hilfe des Minimax-Verfahrens\footnote{Das
Verfahren wird im Kapitel~\ref{sub:MiniMax} genauer erklärt.}.
\end{itemize}
Shannon veröffentlichte seine Überlegungen in zwei Artikeln
im Jahre 1950\cite{shannon50,shannon2}, in diesen unterschied er
zwischen einer \emph{Typ A Strategie}\index{Typ A Strategie},
einer \emph{Typ B Strategie}\index{Typ B Strategie} und einer 
\emph{Typ C Strategie}\index{Typ C Strategie}.  

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 zweierlei
beinhaltet, erstens die Aufnahme der \emph{Ruhesuche} und die Vorauswahl
sinnvoller Züge, die zur Untersuchung freigegeben werden. Die
Ruhesuche ist einfach zu implementieren, es ist sogar so, dass
praktisch kein Schachprogramm je geschrieben wurde, das ohne die
Ruhesuche oder auch \emph{statische Bewertung} auskam.
Fast alle modernen Schachprogramme arbeiten nach diesem Prinzip.
Aber auch mit dieser Verbesserung, so fürchtete Shannon, beruht der
Erfolg auf reiner Rechengewalt, statt auf einer logischen Analyse der
Situation.
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.

Der erste Computer, der selbstständig Schach spielen konnte, war der
MANIAC I\index{MANIAC I}, jedoch handelt es sich hier um eine
vereinfachte Variante des Spiels. Es wurde nur auf einem 6x6 Feld
gespielt und dazu die beiden Läufer und die entsprechenden Bauern
weggelassen. Der Computer wurde 1950 in den Los Alamos National
Laboratories gebaut. Es war ein röhrenbestückter Rechner, der über
10.000 Operationen pro Sekunde ausführen konnte. % Er war eigentlich
%entwickelt worden um die zeitraubenden Berechnungen zur Kettenreaktion
%zu machen. Das wichtige an diesem Computer war jedoch die freie
%Programmierbarkeit und so beteiligten sich fünf Wissenschaftler an dem
%Projekt ein Schachprogramm zu entwickeln. 
Trotz der Vereinfachung des Spiels und obwohl das Programm nur 4
Halbzüge berechnete, betrug die Rechenzeit des Programms zwölf Minuten
pro Zug. Bei einem nicht eingeschränkten Schachbrett hätte die
Maschine drei Stunden für jeden Zug benötigt. Das Programm wurde Mitte
der Fünfziger Jahre fertig gestellt und spielte insgesamt drei
Partien. Die erste gegen sich selbst (Weiß gewann), die zweite gegen
einen Schachmeister, der dem Programm eine Dame vorgab, das Programm
verlor nach 10 Stunden Rechenzeit. Die dritte Partie wurde 1956, gegen
eine junge Dame des Forscherteam, ausgetragen sie hatte eine 
Woche vorher Schachspielen gelernt und für die Partie gegen den
Computer trainiert. Das Programm gewann nach 23 Zügen, diese Partie war
die erste in der Geschichte der KI, in der ein Mensch gegen eine
Maschine verlor.
In diesem Jahre prophezeiten auch Herbert Simon und Allen Newell, dass ein
Computerprogramm in den nächsten 10 Jahren Weltmeister
wird\footnote{Im gleichen Vortrag behaupteten sie, dass Computer zu
diesem Zeitpunkt auch wertvolle Musikstücke komponieren, mathematische
Sätze aufstellen und beweisen sowie psychologische Theorien
bestätigen oder widerlegen würden.}. 

Das erste vollständige Schachprogramm wurde von Alex Bernstein\index{Bernstein, Alex}
im Jahre 1957 entwickelt, es lief auf einem IBM 704 Computer.
Auch dieses Programm berechnete pro Zug 4 Halbzüge, es benötigte dafür
8 Minuten. Das Programm arbeitete nach den Prinzipien, die Shannon
aufgestellt hatte und nach denen auch die Programme von Zuse und 
Turing funktionierten und nach denen auch noch die heutigen Programme
arbeiten. Das Programm benutzte einen MiniMax-Algorithmus.


Das erste Programm, das an einem menschlichen Turnier teilnahm, war
\emph{MacHack VI}\index{MacHack VI}, das von Richard
Greenblatt\index{Richard Greenblatt} am MIT entwickelt wurde.
Das Programm war eine Mischung aus Selektion und Brute Force.
%.....Wie das Programm funktioniert??........
Im Januar 1967 spielte es in der Amateurmeisterschaft von
Massachusetts und erzielte ein Remis aus fünf Partien, die restlichen
vier Partien verlor das Programm. Dafür erhielt es ein USCF Rating von
1243, dies entspricht ungefähr 1040 Elopunkten. Im Laufe des Jahres
verbesserte sich das Rating auf 1529 Punkten. Dies passierte
allerdings nur, weil einige Gegner zu schnell aufgaben. MacHack war
nämlich im Endspiel ganz erbärmlich und hätte die Partien trotz
mancher Vorteile niemals gewinnen können. Dies ahnten die Gegner
aber nicht.

Obwohl nun 10 Jahre vergangen waren, hatte sich die Prophezeiung von
H. Simon und A. Newell\footnote{H. Simon und A. Newell sind die
Erfinder des Alpha-Beta-Verfahrens.} nicht erfüllt, dass Schachprogramm
in diesem Jahr Weltmeister werden. Das Niveau von MacHack war das
eines Amateurs und nicht eines Weltmeisters. 
Zu dieser Zeit war auch der Streit über die Fähigkeiten von Computern
in einer Hochphase, so kam es zu einer Wette zwischen David
Levy\index{Levy, David} und den Professoren John McCarthy und Donald
Michie, beide Experten auf den Gebieten des Computerschachs und der
Künstlichen Intelligenz. Levy, zu der Zeit schottischer Meister, bot
ihnen daraufhin eine Wette an, dass es innerhalb von zehn Jahren 
keinem Computer der Welt gelingen würde, ihn in einem Wettkampf zu
besiegen. Insgesamt wurden 1250 Pfund oder  3000 Dollar gewettet.
Neun Jahre lang hat er alle Rechner meist im Simultanspiel besiegen
können. Im August 1978 kam es zum Abschlussmatch der Wette über sechs
Partien gegen das beste Computerschachprogramm dieser Zeit, Chess 4.7.
Gleich in der ersten Partie verlor Levy gegen \emph{Chess
4.7}\index{Chess 4.7}. Er merkte, 
dass er seinen Gegner unterschätzt hatte und setzte fortan eine andere
Strategie ein: \emph{Tue nichts, aber tue es gut ( do nothing but do it
well)}. Er baute geschlossene Stellungen auf, die keine überraschende
Taktik gestatteten. Das Programm konnte bei dieser Strategie keinen
Plan finden und zog ziellos hin und her. Währenddessen baute Levy die
eigene Position aus und optimierte die Stellung seiner Figuren. Im
richtigen Augenblick wagte er dann einen Angriff und bezwingt seinen
Gegner. Mit dieser Strategie besiegt Levy das Programm mühelos
zweimal, anschließend versuchte er noch einmal die erste Strategie was
aber nicht funktioniert, so endete das Match mit 3.5:1.5 für Levy,
womit er die Wette endgültig gewonnen hatte.
Er verlängerte die Wette noch einmal um 5 Jahre, auch diese Wette
gewann er, erst 1988 verliert Levy gegen DEEP THOUGHT.

Der Grundstein für diese starken Schachprogramme wurde in den Jahren
nach MacHack gelegt, denn in den Jahren 1967 bis 1970 wurden
mindestens acht neue Programme geschrieben und im September 1970
wurde die erste Computerschach-Meisterschaft der Geschichte
ausgetragen. Diese fand im Rahmen der Konferenz der \emph{Association
for Computing Machinery (ACM)}\index{Association for Computing
Machinery (ACM)} statt. Seitdem gibt es in den USA jedes Jahr ein
Turnier, das als offene US-Computerschach-Meisterschaften fungiert.
Das erste Turnier gewann \emph{Chess 3.0}\index{Chess 3.0}, der
Vorgänger von \emph{Chess 4.7}, gegen den Levy 1978 gewann.

Ende der siebziger Jahre stand die Schachprogrammierung vor einem
Dilemma. Die besten Programme hatten das Niveau von Meisterspielern
erreicht. Aber es war unklar, wie man eine weitere Steigerung erzielen
konnte. Programme, die Schachwissen und intelligente Verfahren
benutzten, konnten nicht mit mittelmäßigen Programmen konkurrieren, die
eine Brute Force Methode benutzten.
Eines der Hoffnungsträger, war das Programm
\emph{Pionier}\index{Pionier} von dem Altweltmeister \emph{Mikhail
Botwinnik}\index{Mikhail Botwinnik}. Die Entwicklung des Programmes
begann im Jahre 1970, allerdings gab es bis auf wenige Ankündigungen
keinen Beweis, wie gut das Programm spielte. 
Aber auch dem traditionellen Brute Force Ansatz stand kaum ein Weg
offen die Spielstärke zu steigern, da diese durch die
Geschwindigkeit der Rechner bestimmt wurden.
Die stärksten Programme konnten eine Suchbaum bis zur Suchtiefe 7
berechnen, sollte der Suchbaum um einen weiteren Halbzug
erweitert werden, benötigte man dafür die fünffache Rechenleistung.
Auf diese Steigerung müsste man nach dem Moore'schen Gesetz mehr als
drei Jahre warten. Jedoch ging man davon aus, dass ein Programm mindestens zehn
Halbzüge analysieren müsste, bevor das Niveau von Großmeistern
erreicht werden könnte.
Dies würde aber bedeuten, dass die Anzahl der Stellungen, die pro Zug
in drei Minuten berechnete werden, von 11.000 Stellungen auf 2.8
Millionen Stellungen ansteigen müsste (siehe auch
Tabelle~\ref{tab:AlphaBeta}). Dies könnte aber nur durch eine 250-fache
Steigerung der Rechenleistung gelingen. Dies war aber in nächster Zeit
nicht möglich, selbst wenn man das Moore'sche Gesetz bemüht, würde man
noch 12 Jahre warten müssen, somit begann die Zeit der
Spezialmaschinen, die mit dem Rechner \emph{Deep Blue} den Höhepunkt
und auch ihr Ende erreichte. Er war es auch der 1997 Kasparow in einem
Match mit 3.5:2.5 besiegte und somit den Weltmeister ablöste, 30 Jahre
später als prophezeit. 
Näheres zu den Spezialrechnern im Kapitel~\ref{sub:SpezialHardware}.
Nachdem der Weltmeister von einem Computer bezwungen war, wurde
Computerschach für die KI Gemeinde ein gelöstes Problem und sie wandte
sich anderen Problemen zu. Aber hat die KI das Problem wirklich
gelöst? Sie benötigt dazu 2-3 Millionen Stellungen pro Sekunde, wobei Kasparow
ungefähr 3-4 Stellungen pro Sekunde analysieren konnte.
Man nutzte die Rechenkraft der Computer und nicht so sehr die
Intelligenz der Programme, Versuche in diese Richtung gab es nur
wenige und sie waren auch nicht sehr erfolgreich (siehe
Kapitel~\ref{sub:IntelligenteSysteme}). 

Zu Beginn der neunziger Jahre wurden die PC Schachprogramme immer
beliebter und besser, so haben die Steigerung der Rechenleistung der
PC Systeme, aber auch die Verbesserung der Software dazu beigetragen,
dass nun im Jahre 2002 die PC-Systeme die Stärke erreicht haben um
sich selbst mit dem Weltmeister des Schachspiels zu messen.



\begin{table}
\begin{tabular}{rp{12cm}}
%\hline 
 \textbf{Jahr}  &  \textbf{Ereignisse} \\ 
%\hline 
1890  & Torres y Quevedo konstruiert eine Maschine, die das Endspiel
        König und Turm gegen König beherrscht. \\
\vspace{0.3mm}
1942  & Konrad Zuse entwickelt das erste Schachprogramm in der
        Programmiersprache Plankalkül. \\ 
\vspace{0.3mm}
1947  & Alan Turing entwickelt das erste Schachprogramm, das korrekte
        Züge berechnen und eine Position bewerten konnte. Mangels eines
        existierenden Computers simuliert er dessen Berechnungen
        selbst.\\
\vspace{0.3mm}
1949  & Der Computer Ferranti löst Matt in 2 Aufgaben.   \\
\vspace{0.3mm}
1950  & Claude Shannon veröffentlicht zwei Artikel, die beschreiben,
        wie ein Computerprogramm Schach spielen kann,
\cite{shannon50}. \\ %,claude2}. \\
\vspace{0.3mm}
1956  & MANIAC I (0.011 MIPS), entwickelt in Los Alamos spielt auf
        einem 6x6-Brett Schach. Dies ist das erste funktionsfähige
        Schachprogramm.\\
       & Herbert Simon und Allen Newell prophezeien, dass ein
        Computerprogramm in den nächsten 10 Jahren Weltmeister
        wird. \\
\vspace{0.3mm}
1957  & Bernstein entwickelt ein Schachprogramm für einen IBM 704
        (0.085 MIPS). Das erste vollständige Schachspiel eines
Computers. \\
\vspace{0.3mm}
1967  & Das Schachprogramm MacHack VI, entwickelt am MIT von
        Greenblatt. Es erreicht bei dem Massachussets Amateur
        Wettbewerb 1 Unentschieden und 4 Niederlagen, USCF rating 1243
        (ca. 1040 Elopunkten).  \\ 
\vspace{0.3mm}
1968  & David Levy wettet einen Betrag von 3000\$, dass er 10 Jahre
        lang von keinem Computerschachprogramm besiegt wird.   \\
\vspace{0.3mm}
1974  & Das russische Schachprogramm KAISSA, auf einem englischen
        Rechner entwickelt, gewinnt die
        Welt-Computerschachmeisterschaften in Stockholm mit 4:0.  \\
\vspace{0.3mm}
1978  & Levy gewinnt seine Wette, bei einem Abschlußmatch gegen Chess
        4.7, er verlängert seine Wette um 5 Jahre. \\
\vspace{0.3mm}
1983  & Das Programm BELLE erreicht eine ELO-Bewertung von 2263. \\
\vspace{0.3mm}
1988  & Das Programm HITECH erreicht eine Bewertung von 2530 Punkten.
        \\
      & David Levy verliert gegen DEEP THOUGHT. \\
\vspace{0.3mm}
1989  & DEEP THOUGHT erreicht eine Bewertung von 2800 und analysiert 2
        Mio. Positionen/sek.. In einem Spiel gegen Kasparow verliert
        das Programm mit 0:2. \\
\vspace{0.3mm}
1990  & Die PC Programm werden immer stärker und beliebter.\\
\vspace{0.3mm}
1996  &  Deep Blue verliert gegen Kasparow mit 4 : 2. \\
\vspace{0.3mm}
1997  &  Erstmals verlor ein Weltmeister (Kasparow) bei einem
        Schachduell gegen einen Computer. Der IBM-Computer 
        Deep Blue gewann gegen den PCA-WM mit 3,5 : 2,5. \\
\vspace{0.3mm}
%\hline 
2002  & amtierende Schachweltmeister Vladimir Kramnik\index{Vladimir Kramnik}
        tritt gegen das Computerprogramm \emph{Deep Fritz}\index{Deep
        Fritz} zu einem Match über acht Partien an. Deep Fritz läuft
        auf einem PC und keiner Spezialhardware.\\
\vspace{0.3mm}
2002  & Fritz 7 erreicht auf einem Athlon 1200 MHz Rechner ein Rating
        von 2748 Punkten.  \\
%\hline 
\end{tabular}
\caption{Eine kurze Liste der wichtigsten Ereignisse in der
        Entwicklung der Computerschachprogramme.}
\end{table}

Die Maschinen haben mit ihren Siegen über menschliche Gegner
den Turing-Test längst noch nicht bestanden. Aber sie haben gezeigt,
dass in der Welt der 64 Felder, der mit dem besseren Gedächtnis regiert.


%---------------------------------------------------------------------- 
\subsection{Die Spezialhardware}
%---------------------------------------------------------------------- 
\label{sub:SpezialHardware}

Die Zeit der Spezialhardware begann Ende der siebziger Jahre als klar
wurde, dass eine nennenswerte Steigerung der Leistung der
Schachprogramme mit den traditionellen Brute-Force Verfahren nicht
weiter kommen wird. Die besten Programme spielten in dieser Zeit auf
dem Niveau von Meisterspielern um aber das Niveau von Großmeistern zu
erreichen, glaubte man die Berechnungstiefe des Schachbaums von 7
Halbzüge auf 10 Halbzüge erhöhen. Dies würde aber eine Steigerung der
Rechenleistung um den Faktor 250 benötigen und ein Rechner mit dieser
Leistung musste erst noch entwickelt werden.

Es gab also zwischen dem schachlichen Leistungsvermögen der besten
Computerprogramme und dem der menschlichen Spitzenspieler eine
prinzipiell unüberwindbare Kluft. Diese sollten durch Spezialrechner
geschlossen werden, die nur für das Schachspielen entwickelt wurden.

%---------------------------------------------------------------------- 
\subsubsection{BELLE}
%---------------------------------------------------------------------- 
\label{sub:BELLE}

Die \emph{BELLE}\index{BELLE} war einer der ersten Spezialrechner, der
die Computerschachwelt auf die nächste Stufe heben sollte. Der
Computer wurde von zwei Wissenschaftlern der Bell Laboratories in New
Jersey entwickelt. Die Wissenschaftler \emph{Ken
Thompson}\index{Thompson, Ken} und \emph{Joe Condon}\index{Condon,
Joe} haben in der Maschine ein traditionelles Brute-Force Verfahren
fest verdrahtet. Die meisten schachspezifischen Aufgaben, wie die
Erzeugung legaler Züge, Material- und Stellungsbewertung, konnten
somit weitaus effizienter durchgeführt werden als mit einer
Universalrechnenanlage. 

Das ursprüngliche Ziel des Projektes war es 1.000.000 Stellungen pro
Sekunde zu berechnen, das Programm \emph{Chess 4.8} auf einem
Superrechner der Zeit schaffte zirka 5000 Stellungen. Damit wären neun
bis zehn Halbzüge möglich, dies sollte den Rechner die Möglichkeit
geben auf dem Niveau eines Großmeisters zu spielen. Das gesetzt Ziel
wurde nicht erreicht, die Belle konnte nur 150.000 bis 180.000
Stellungen berechnen, was einer Suchtiefe von acht bis neun entspricht.

Weitere Neuerungen des Systems waren das
\emph{Eröffnungsbuch}\index{Eröffnungsbuch} und die
\emph{Hashtabellen}\index{Hashtabellen}. Die Eröffnungsbücher
ermöglichen es dem Computer in der Anfangsphase des Spiels in einer
Datenbank gespeicherte Züge zu wählen, die schon bewertet sind und sie
nicht jedes Mal neu zu bewerten (siehe Kapitel~\ref{sub:ErBuecher}).
Die Hashtabellen oder auch \emph{Transition Tables},
waren eine weitere Neuerung, die es der Belle ermöglichte die
Spielstärke des Systems stark zu erhöhen (siehe
Kapitel~\ref{sub:HashTab}). In den Hashtabellen werden Stellungen mit
 ihren Bewertungen abgespeichert, so dass diese Stellung nicht
nochmal bewertet werden muss, wenn sie schonmal erreicht wurde.


Die Leistung, die der Belle in den Jahren 1980 bis 1983 zeigte, war
bemerkenswert. Die Maschine hat alles gewonnen, was es im Bereich des
Computerschach zu gewinnen gab. Sie hat die Konkurrenz vollständig
dominiert und in jedem Computerturnier den ersten Platz belegt. Noch
während der Vierten Computerschach-Weltmeisterschaft in New York im
Oktober 1983 wurde dem Rechner von der US-Schachföderation der
offizielle Titel eines Nationalen Meisters verliehen, dies war das
erste Mal, dass einem Programm dieser Titel verliehen wurde.

%---------------------------------------------------------------------- 
\subsubsection{HITECH}
%---------------------------------------------------------------------- 
\label{sub:HITECH}

Der Rechner \emph{HITECH}\index{HITECH} wurde Anfang der achtziger
Jahre an der Carnegie-Mellon-Universität in Pittsburgh
entwickelt. Professor Hans Berliner, ein ursprünglicher Vertreter der
\emph{intelligenten} Methoden, konstruierte aus 64 Prozessoren, für
jedes Feld des Schachbretts einen, ein System, welches auf der
Brute-Force Methode beruhte und 120.000 Stellungen pro Sekunde
berechnen konnte. So erfolgreich wie die Belle war Hitech nicht, was
an der schlechten Parallelisierbarkeit des Schachproblem liegt.
Jedoch war auch Hitech immer für einen Sieg über jeden Konkurrenten
seiner Zeit gut.
 


%---------------------------------------------------------------------- 
\subsection{Schach auf der Cray}
%---------------------------------------------------------------------- 
\label{sub:Cray}

Als die Spezialrechner die ersten Triumphe mit der Belle feierten, gab
es aber auch einen Rivalen, der daran arbeitete, mit einem
Universalrechner die Spezialrechner zu schlagen. \emph{Robert
Hyatt}\index{Hyatt, Robert} begann 1975 mit der Entwicklung seines
Comupterprogramms \emph{Blitz}\index{Blitz}, bald stieß der
Musikprofessor und Fernschachspieler \emph{Al Grower}\index{Grower,
Al} hinzu und ab 1979 stellte ihnen die Firma Cray für ihre
Experimente ihren Spitzenrechner, die \emph{Cray I}\index{Cray I}, zur
Verfügung. 

Die Cray I war zu der Zeit der schnellste und teuerste Rechner der
Welt. Sie konnte 80 Millionen arithmetische Operationen pro Sekunde
ausführen.

1981 hatte \emph{Cray Blitz} einen Auftritt bei den offenen
Meisterschaften in Mississippi. Das Programm gewann sämtliche Partien
und war eigentlich Schachmeister des Staates Mississippi. Das
eigentliche Ziel war jedoch ein Sieg über Belle. Bei mehreren Turnieren
zwischen Belle und Cray Blitz errang aber immer die Belle einen Sieg.
Erst am Ende des Jahres 1983 konnte der Rivale geschlagen werden, dazu
wurde die neueste Version der Cray, die \emph{Cray I X-MP}, eingesetzt.
Das X bezeichnete die neueste Forschungsversion der Cray mit
schnelleren Prozessoren und das MP stand für Multi
Processing. Dahinter verbargen sich zwei Rechner, die zusammen eine
Rechenleistung von 210 Millionen Operationen pro Sekunde bewältigten.
Soviel Rechenleistung wurde bis dahin noch nie für ein Schachspiel
verwendet.


%---------------------------------------------------------------------- 
\subsubsection{Von Chiptest über Deep Thought zu  Deep Blue}
%---------------------------------------------------------------------- 
\label{sub:DeepBlue}

Der Sieg von Cray Blitz mit seiner gewaltigen Rechenleistung über die
\emph{kleine} Belle läutete aber nicht das Ende der Spezialhardware
ein. Im Gegenteil, denn die Siege der Belle über die Cray machten das
ungleiche Kosten-Nutzen-Verhältnis deutlich.


Neben Prof. Berliner gab es an der Carnegie Mellon Universität noch
eine andere Gruppe, die sich um einen Schachcomputer bemühte, dies waren
%1985 Doktorand der Carnegie Mellon Universität Feng-hsiung Hsu
Feng-hsiung Hsu, Elektroingenieur aus Taiwan, Thomas Anantharaman aus
Indien, Murray Campbell, ein Schachturnierspieler aus Kanada, und
Andreas Nowatzyk, Physiker und Informatiker aus Hamburg. Alle waren
dabei, an der Carnegie Mellon Universität ihre Doktorarbeit zu
schreiben. 

Es war Hsu (ausgesprochen Schü), der einen kompletten Zuggenerator auf einen Chip
bringen wollte, um damit direkt mit der Hardware Schachzüge generieren
zu können. Er brauchte zehn Monate um die Algorithmen auf 35.925
Transitoren zu verteilen, aber der fertige Prozessor konnte zwei
Millionen Züge pro Sekunde erzeugen. Es gab jedoch 1985
keinen Computer, der diese Geschwindigkeit unterstützen
konnte. Anantharaman schrieb aber ein kleines Schachprogramm, das den
Chip benutzte und dadurch seine Ablaufgeschwindigkeit
verfünffachte. Das Programm wurde auf den Namen
\emph{Chiptest}\index{Chiptest} getauft und konnte 50.000 Positionen
pro Sekunde berechnen.

In den nächsten beiden Jahren verbesserte Anantharaman das Programm
weiter und entwickelte eine spezielle Erweiterung, die \emph{Singular
Extensions}\index{Singular Extensions}.  Diese
Erweiterung ermöglicht tiefere Suchen in forcierten Varianten,
d. h. immer wenn das Programm am Ende des Suchbaums nur einen einzigen
vernünftigen Zug findet, wird die Suche dort erweitert. Während 
dieser Zeit verbesserte Hsu den Microcode des Zuggenerator Chips.
Alle Verbesserungen erhöhte die Geschwindigkeit um einen Faktor von
zehn, so dass jetzt 500.000 Positionen pro Sekunde berechnet werden
können. Der neue Rechner, der mit einem Aufwand von 5000\$ gebaut wurde,
bekam den Namen \emph{Deep Thought}\index{Deep Thought}.
1987 gewann Deep Thought die nord-amerikanische
Computerschachmeisterschaft und besiegte u.a. Cray Blitz, den
amtierenden Computerschach WM. 
%
%schnellere Hardware -> Deep Thought :
%Bewertungsfunktion: Figurenplatzierung, Bauernstruktur, Freibauern und
%Reihenstruktur (Besetzung offener Linien etc.)Deep Thought spielt 1988
%in Fredkin Masters Open und erzielt Performance von 2599 ELOUS Open in
%Boston 
%
1988 schlug Deep Thought als erster Computer einen GM (Igor Ivanov,
ELO 2641), im gleichen Jahr gewann Deep Thought ein Preisgeld von
10.000\$, da es das erste Computerprogramm mit einer Bewertung von
über 2500 ELO war. 

Ab 1989 wurde Deep Thought zu einem IBM Forschungsprojekt, mit dem
mittelfristigen Ziel den Schachweltmeister zu schlagen. In Folge der
besseren Hardware und der Parallelisierung des Schachprogramms konnte
eine Version, die auf 6 Prozessoren lief
2 Millionen Positionen pro Sekunde berechnen. Trotzdem verlor er in
diesem Jahr sowohl gegen Kasparow mit 0:2 als auch gegen David Levy
mit 0:4.

%1993 besiegt Deep Thought Judit Polgar (stärkste Frau ELO ca. 2650)
%
%1994 Erneuter Gewinn der Computer WM

Ab dem Jahr 1995 wird aus Deep Thought \emph{Deep Blue}\index{Deep
Blue}, dies war jedoch nicht nur ein neuer Name, sondern auch ein
neuer Rechner. Deep Blue besaß neue Schach-Chips, die mehr als 2-3
Millionen Positionen pro Sekunde erzeugen könnten und das Programm
lief auf einem IBM RISC System/6000 parallel System mit 256 Prozessoren.
Die Software war in C geschrieben und kann 50 - 100 Millionen
Positionen in 3 Minuten (Turniermodus) berechnen. Weiterhin besaß
das Programm eine Datenbank mit Großmeister-Spielen der letzten 100
Jahre und einer Eröffnung und Endspieldatenbank mit Billionen von
Endspiel-Scenarien.  

Im Jahr 1997 wurde die Geschwindigkeit von Deep Blue noch einmal um den
Faktor 2 erhöht. Deep Blue kann nun 200 Millionen Positionen pro
Sekunde berechnen, zusätzlich wird das Wissen des Großmeisters Joel
Benjamin (USA-Meister) in die Datenbanken von Deep Blue eingegeben.
In diesem Jahr verliert auch Kasparow unter Turnierbedingungen gegen
Deep Blue mit 3.5:2.5.

%Once the world champion had been
%defeated, computer chess became a kind of solved problem and the
%artificial intelligence community moved to more challenging areas.




%---------------------------------------------------------------------- 
\subsection{Intelligente Systeme}
%---------------------------------------------------------------------- 
\label{sub:IntelligenteSysteme}

Trotz der Unmöglichkeit, das Schachwissen von Großmeistern zu
formalisieren, hat deren Fähigkeit, nach Überprüfung von sehr wenigen
Varianten gute Züge zu finden, die Schachprogrammierer von Anfang an
fasziniert. Wäre es möglich einem Computerprogramm bei zubringen
nicht jeden Zug zu überprüfen, auch wenn er noch so sinnlos ist, dann
könnte es gelingen, die Anzahl der Züge in jeder Stellung drastisch zu
reduzieren. Könnte man von den durchschnittlich 30 möglichen Zügen pro
Stellung nur zwei oder drei besten Züge weiterverfolgen, dann könnten
Computerprogramme wie die Großmeister Varianten bis 
zu 20 Halbzügen tief verfolgen. Dazu müsste es einen Zug genauer
analysieren um in jeder Stellung mit großer Zuverlässigkeit die Züge
auszusortieren, die auch ein Großmeister unsinnig nennt. Dieses
Programm wäre nach Shannon eine \emph{Typ C Strategie}, da sie
Schachwissen einsetzt um auf jeder Ebene eine Teilmenge interessanter
Züge zu bilden.\footnote{Diese Strategie wird auch als Typ B Strategie
bezeichnet, obwohl Shannon hier effiziente Brute Force Verfahren
meinte (s.o).}

Keines der intelligenten Verfahren, die Schachwissen benutzten und nur
wenige Varianten analysierten, schaffte es an die Leistung der Brute
Force Verfahren heranzukommen. Das erfolgreichste Programm war  
\emph{MacHack}\index{MacHack}, das von Richard
Greenblatt\index{Richard Greenblatt} am MIT entwickelt wurde.
Das Programm war eine Mischung aus Selektion und Brute Force und
erreichte 1967 in einem Turnier ca. 1040 Elopunkte. %Das Programm
%verwendete 50 aufwendige Bewertungsfunktionen, um \emph{plausible}
%Züge zu ermitteln und nur solche beim Aufbau des Suchbaums weiter zu
%berücksichtigen. In den ersten beiden Halbzügen untersuchte sein
%Programm je 15 und in beiden folgenden Halbzügen neun und danach
%sieben Züge. Jedoch war dieses Programm viel zu schwach und übersah
%häufig simple Kombinationen. Daher lief parallel noch das Programm
%\emph{Cheops}\index{Cheops}, das nur Material bewertete.
%.....Wie das Programm funktioniert??........

%Pionier
Eines der Hoffnungsträger war das Programm
\emph{Pionier}\index{Pionier} von dem Altweltmeister \emph{Mikhail
Botwinnik}\index{Mikhail Botwinnik}. Die Entwicklung des Programmes
begann im Jahre 1970, allerdings gab es bis auf wenige Ankündigungen
keinen Beweis, wie gut das Programm spielte. 


%PARADIS David Wilkins 1980
Eine weitere Schwäche von Minimax und auch Alpha-Beta-Pruning besteht
in der Konstruktion des Suchbaumes. Obwohl nur der jeweils beste Zug
gesucht wird, berechnet der Alpha-Beta-Algorithmus die Werte für alle
erlaubten Züge, auch wenn dann nicht jeder dieser Züge komplett
weiterverfolgt wird. Es wird also immer noch sehr viel Rechenleistung
verschenkt. Betrachten wir beispielsweise eine Position, bei der es
nur einen legalen Zug gibt. Der Alpha-Beta-Algorithmus generiert
trotzdem einen sehr großen und völlig unnötigen Suchbaum. Dieses
Problem führte die Entwickler auf die Idee, zunächst nur jene Züge
weiterzuentwickeln, die voraussichtlich zu guten Positionen
führen. Dieses Verfahren hilft auch in Situationen weiter, in denen
zwei gleichwertige Züge zur Verfügung stehen und keine noch so genaue
Suche entscheiden könnte, welcher Zug nun der bessere ist. Diese Art
der Überlegung, welche Berechnungen nun anzustellen sind, nennt man
Metareasoning. Dieses Verfahren kommt natürlich nicht nur bei Spielen
zum Einsatz, sondern überall, wo Entscheidungen getroffen werden
müssen. 

Dies ist selbstverständlich nicht die Art und Weise, wie ein Mensch
Spiele spielt. Gerade im Schach setzt sich ein menschlicher Spieler
eher ein Ziel, welches er mit seinen nächsten Zügen erreichen
will. Beispielsweise kann er versuchen, die gegnerische Dame in die
Ecke zu drängen oder seine Verteidigung zu stärken oder ähnliches. Auf
diese Weise entwickelt er dann einen Plan, wie er dieses Ziel
erreichen kann. Dieses zielgerichtete Planen eliminiert meist die
kombinatorische Suche fast vollständig. PARADISE von David Wilkins (
1980 ) ist bislang das einzige Schachprogramm, das zielgerichtetes
Planen erfolgreich eingesetzt hat. Es gibt derzeit jedoch noch keinen
Ansatz um diese verschiedenen Algorithmen miteinander effizient zu
verbinden. Die Entwicklung eines solchen Systems wäre ein großer
Fortschritt für die KI-Forschung.  

%Spiel Brute-Force gegen intelligente Verfahren 

%---------------------------------------------------------------------- 
\subsection{Die PC-Systeme}
%---------------------------------------------------------------------- 
\label{sub:PC-Systeme}

Ab Anfang der 90ziger Jahre traten die PC Schachprogramme langsam die
Nachfolge der spezialisierten Schachcomputer an, Deep Blue war der letzte
Schachcomputer dieser Art. Die ersten Schachprogramme wurden noch in Assembler
programmiert, ab 1995 mit Fritz 3 setzte sich die Programmiersprache C im
Bereich der Schachprogramme durch. 

1998 konnten die schnellsten Programme Crafty und Deep Junior eine Millionen
Stellungen pro Sekunde berechnen und sie waren somit noch mehr als sechsmal
langsamer als Deep Blue zu dieser Zeit, jedoch liegt dies Hauptsächlich an dem 
Unterschied zwischen der verwendeten Hardware.
Die Entwicklung der Programme und der Hardware des PC's ging und geht aber,
weiter im Jahr 2002 erreicht Fritz 7 auf einem Athlon 1200 MHz Rechner ein
Rating  von 2748 Elo Punkten. Diese liegt nur noch knapp unter der Elo Wertung
von Deep Blue. 

%Ob er sich dabei wohl auf die
%menschliche Gegenüberstellung von Psychologie, Persönlichkeit und
%Geistesblitz versus Algorithmen, Prozessorgeschwindigkeiten und
%bewusstlose Speicherleistungen verlassen kann? Auf den 64 Feldern, die
%die Welt bedeuten, regiert vor allem das bessere Gedächtnis. Allein
%wie es erfolgreich mobilisiert wird, entscheidet über Sieg oder
%Niederlage. Und die menschlichen Siegeschancen werden immer
%schlechter... 



%---------------------------------------------------------------------- 
\section{Das Elozahlen-System}
%---------------------------------------------------------------------- 
\label{sec:Elo}

Als Maß für die Stärke eines Schachspielers werden die
\emph{Elozahlen}\index{Elozahl} benutzt. Diese wurden von \emph{Arpad
E. Elo}, einem amerikanischen, Physiker entwickelt. Elo wandte die
Methoden der Statistik und der Wahrscheinlichkeitstheorie auf die
Leistungen von Schachspielern an. Er entwickeltet ein zuverlässiges
Wertungssystem, das ein Maß für die relativen Spielstärken der
einzelnen Spieler definiert. Im Elo-System erhält jeder Spieler eine
Zahl, die sich aus einer mathematischen Auswertung der Ergebnisse
seiner Tunierpartien ergibt. Hat er in einem Turnier viele Partien
gewonnen, erhöht sich seine Wertung und zwar um so mehr, je stärker
seine Gegner waren. Umgekehrt werden ihm Wertungspunkte, abgezogen wenn
er bei einem Turnier verliert.

%
% Hier muss noch die mathematische Definition der Elozahlen usw hin.
%

In seinem Kern ist das Elo-System ein \emph{Paired Comparison}
Verfahren aus der quantitativen Pschologie, dies bedeutet in der
Mathematik \emph{vollständige Ordnung}, wobei alle Elemente paarweise
vergleichbar sind. Auf der Menge der Schachspieler gibt es damit eine
irreflexible Ordnung. Damit ergeben sich aber für Schach zwei
Probleme, erstens sind solche Ordnungen transitiv, dies muss aber für
die einzelnen Schachspieler nicht immer gelten. Und zweitens müsste
die Ordnung antisymmetrisch sein, jedoch gibt es beim Schach Remis.
Beide Probleme werden dadurch umgangen, dass man nicht mit einzelnen
Spielausgängen arbeitet, sondern mit Erwartungswerten von Spielausgängen.
Eine Einführung in die mathematischen Grundlagen des Elo-Systems
findet man in \cite{ble98}.

Da ein starker Spieler nicht immer einen schwächeren Spieler besiegt,
wird eine Normalverteilungsfunktion für die Performance der Spieler
angenommen. Die Normalverteilungsfunktion sagt nur aus, dass
leichte Abweichungen von der Performance öfter vorkommen als starke
Abweichungen. Die Abweichung wird als Standardabweichung ($\sigma$)
angegeben. Auf dieser Grundlage wurde eine Wahrscheinlichkeitsfunktion
entwickelt, die bei bekannter Elodifferenz zwischen zwei Spielern die
Gewinnwahrscheinlichkeit des besseren Spieler angibt. Die Funktion
$P(D)$ ist wie folgt definiert:


\[
P(D) = \frac{1}{2} \int_{0}^{D} e^{- \frac{1}{2} t^2} dt,
\]
\begin{itemize}
\item $P(D)$:  die Gewinnwahrscheinlichkeit,
\item $D$:  die Elodifference zwischen zwei Spielern,
\item $\sigma$: die Standardabweichung.
\end{itemize}

Die Werte der Funktion $P(D)$ kann auch durch die folgende Funktion
approximiert werden:
\[
P'(D)= \frac{1}{1+10^{-\frac{D}{400}}}.
\]


Die Tabelle~\ref{tab:EloDiff} zeigt auf der Grundlage der
Gewinnwahrscheinlichkeitsfunktion $P(D)$, wie sich die
Gewinnwahrscheinlichkeit (in Prozent angegeben) bei verschiedenen
Differenzen ändert. Man kann deutlich sehen, dass man
ab einer Elodifferenz von 400 Punkten davon ausgehen kann, dass der
bessere Spieler immer gewinnt. Jedoch selbst bei Elodifferenzen von
100 Punkten hat der schwächere Spieler immer noch gute Gewinnchancen.


\begin{table}
\begin{tabular}{|c|c|c|c|}
\hline
 \textbf{Elo-Differenz} &  \textbf{Gewinnwahr.} &
 \textbf{Elo-Differenz}  &  \textbf{Gewinnwahr.}\\
\vspace{0.3mm}
%\hline \\
 0  & 50\%  & 140  & 76\% \\
\vspace{0.3mm}
20  & 53\%  & 160  & 79\% \\
\vspace{0.3mm}
40  & 58\%  & 180  & 82\% \\
\vspace{0.3mm}
60  & 62\%  & 200  & 84\% \\
\vspace{0.3mm}
80  & 66\%  & 300  & 93\% \\
\vspace{0.3mm}
100  & 69\%  & 400  & 97\% \\
\vspace{0.3mm}
120  & 73\%  & 900  & 99\% \\
%\vspace{0.3mm}
\hline
\end{tabular}
\caption{Gewinnwahrscheinlichkeit in Abhängigkeit von der Elodifferenz.}
\label{tab:EloDiff}
\end{table}

Die Gewinnwahrscheinlichkeitsfunktion gibt aber keine Auskunft über
die Bewertung der einzelnen Spieler untereinander. 

Die erste Funktion im Elo-System ist die \emph{Performance Rating Formel}
oder  auch \emph{Periodic Rating Formel}, sie stellt die
Bewertung für ein kurzes Intervall dar oder ist eine provisorische
Bewertung für Spieler, die wenige Spiele gegen bewertete Spieler
gemacht haben.
Die Funktion ist wie folgt definiert:
\[
        R_p = R_c + D(P),
\]
\begin{itemize}
\item $R_p$: Bewertung des Spielers, 
\item $R_c$: Bewertung des Gegners,
\item $D(P)$: Bewertungsdifferenz bezogen auf die Funktion $P(D)$.
\end{itemize}

Die \emph{Rating Funktion} wird benutzt um die neue Bewertung auf
einer kontinuierlichen Basis zu berechnen. Diese Funktion fügt die
neue Bewertung in die alte Bewertung ein und führt somit zu einem
geglätteten Verlauf der Bewertung. Die Logik dieser Funktion ist, dass
ein Spieler, der besser als nach seiner Bewertung spielt,
Bewertungspunkte gewinnt und einer, der unter den Erwartungen spielt sie
verliert. 

\[
        R_n = R_o + K * (W - W_e)
\]
\begin{itemize}
\item $R_n$: die neue Bewertung nach dem Spiel,
\item $R_o$: die alte Bewertung,
\item $K$: Bewertungspunktzahl für ein Spiel
\item $W$: Spielausgang (1 für Gewinn, 0.5 für Remis und 0 für Verlust),
\item $W_e$: Erwarteter Spielausgang auf der Basis von $R_o$.
\end{itemize}

Der Koeffizient $K$ in der Bewertungsfunktion gewichtet das neueste
Ereignis und gibt somit an, wie die Elozahl verändert wird.
Der Wert von $K$ variiert dabei zwischen 10 und 32, von den
Schachverbänden wird normalerweise $K=$ 30 verwendet.

Das Wichtige am Elo-System ist, dass sich auf diese Weise Spieler
miteinander vergleichen lassen, die nie gegeneinander angetreten sind.
Die Tabelle~\ref{tab:EloRate} zeigt dabei, in welche Spielklasse 
welche Elozahl in Verbindung gesetzt wird.

\begin{table}
\begin{tabular}{|c|l|}
\hline
 \textbf{Elo-Wert} &  \textbf{Spielklasse}\\
\vspace{0.3mm}
%\hline \\
 2600+  & Großmeister (GM)  \\
\vspace{0.3mm}
 2400+  & Internationale Meister (IM) \\
\vspace{0.3mm}
 2200+  & Nationale Meister (FM)  \\
\vspace{0.3mm}
 2000+  & Expertenlevel  \\
\vspace{0.3mm}
 1800+  & Vereinsspieler Klasse A  \\
\vspace{0.3mm}
 1600+  & Vereinsspieler Klasse B  \\
\vspace{0.3mm}
 1400+  & Vereinsspieler Klasse C \\
\vspace{0.3mm}
 1200+  & Vereinsspieler Klasse D \\
\vspace{0.3mm}
 1200-  & Anfänger \\
%\vspace{0.3mm}
\hline
\end{tabular}
\caption{Einteilung der Elowerte nach Spielklassen.}
\label{tab:EloRate}
\end{table}

%---------------------------------------------------------------------- 
\subsection{Elozahlen und Computer}
%---------------------------------------------------------------------- 

Seitdem es Schachprogramme gibt, möchte man auch ein Maß für ihre
Stärke haben um sie untereinander zu vergleichen, aber auch in Relation
zu Schachspielern zu stellen. So stellt sich die Frage, ob sich die
Elozahlen auch auf Computerprogramme anwenden lassen. Als Arpad Elo sein
System zur Messung der Spielstärke von Schachspielern schuf, hat er
nicht daran gedacht, dass man es zur Beurteilung von Programmen
benutzen wollte. Dies zeigt sich auch, wenn man das Elo-System auf
Computer anwenden möchte.

Im Elo-System hat jeder Spieler eine Identität, die er während seines
gesamten Schachlebens behält. Diese grundlegende Voraussetzung gilt
aber nicht für Schachprogramme. Die Identität eines Programmes hängt
einmal von der benutzten Hardware ab, aber auch von den Parametern, mit
denen ein Programm gestartet wird. Ein weiteres Problem ist das
Programme weiterentwickelt werden, dann stellt sich die Frage, ab
welcher Modifikation ein Programm eine neue Identität für die
Elobewertung bekommt oder entspricht dies dem Lernen von Menschen? Zu
diesem Thema können noch 
zahlreiche Fragen gestellt werden, daher hat der Weltschachbund
FIDE\index{Weltschachbund,FIDE} Computer von der Teilnahme an
offizielen Turnieren ausgeschlossen. Daraus folgt, dass es für
Computer keine offiziellen Elozahlen gibt.\footnote{Die nationale
Schachförderation der USA bildet eine Ausnahme. In der US-Rangliste
sind einige Schachcomputer aufgeführt.}


%---------------------------------------------------------------------- 
\subsection{Die schwedische Eloliste}
%---------------------------------------------------------------------- 

Die \emph{schwedische Schachcomputer-Vereinigung (SSDF)}
\index{SSDF} führt seit
Jahren systematischen Testpartien mit Schachcomputern und -programmen
durch, um eine Rangliste auf der Basis von Elozahlren zu
ermitteln. Denn wenn man sich nicht nur auf Schätzungen der
Spielstärken verlassen will, müssen Turniere Partien gespielt werden.

Alle Partien werden grundsätzlich auf Turnierstufe (40 Züge in 2
Stunden) ausgetragen. Es werden mindestens 100 Partien gespielt, damit
ein Programm in die Liste aufgenommen wird.

Das Identitäts-Problem lösen sie auf eine pragmatische Weise, die auf
einfachen Regeln beruht. Erstens: Programme mit unterschiedlichen Namen
werden als verschieden betrachtet. Wenn sich die erste Versionsnummer
eines Programms ändert, wird das Programm als ein neues Programm
gewertet. Ähnlich verhalten Sie sich bei der Hardware, solange die
Zunahme der Rechenleistung nicht sehr groß ist, wird dies nicht
berücksichtigt. 

Obwohl es bei der Messung einige Fehlerquellen gibt, kann man sich
dies erlauben, da man ein statistisches System hat und sich die
einzelnen Fehler im Mittel ausgleichen und abschwächen.

%---------------------------------------------------------------------- 
\subsection{Stellungstests}
%---------------------------------------------------------------------- 

Eine weitere Methode Computerprogramme zu bewerten sind die
Stellungstest. Dabei müssen die Programme eine vorgegebene Menge
verschiedenster Stellungen analysieren, aus der Zeit die bis zur Ermittlung
des besten Zuges für diese Stellung benötigt wird, wird dann eine Elozahl
berechnet. Die bekanntesten Stellungstests sind:
\begin{itemize}
\item der LCT-Test,
\item der Bednorz-Schumacher-Test und
\item der Nunn-Test.
\end{itemize}

Diese Test sind auf verschiedene Elobereiche zugeschnitten, diese liegen
jedoch alle jenseits der 2000 Punkte. Dadurch macht nur die Bewertung starker
Schachprogramme mit dieser Methode Sinn. Neben diesem Problem gibt es noch
andere Kritikpunkte an den Stellungstest, so variieren die Ergebnisse der
Tests zu den Ergebnissen der SSDF um mehr als 50 Elopunkte, wie man anhand der
Tabelle~\ref{tab:EloDiff} sehen kann, ist dies keine kleine Veränderung. Denn
dadurch erhöht sich Gewinnwahrscheinlichkeit des Programmes mit 50 Punkten
mehr um 60\%. 

Ein weiteres
Problem sind die ausgewählten Stellungen, hier werden oft Stellungen aus
bekannten Partien gewählt, die gut analysiert sind und wodurch man sehr genau
die besten Züge bestimmen kann. Jedoch verwenden die heutigen Schachprogramme
gute Datenbanken, so dass diese Stellungen schon in den Datenbanken enthalten
sein könnten, daher werden die Programme immer ohne Datenbank
gestartet. Jedoch sind die Datenbanken ein wichtiger Bestandteil der Programme
und die Deaktivierung der Datenbank führt zu einer entsprechenden
Verschlechterung der Ergebnisse. 

Daher sollten die Werte die durch Stellungstest ermittelt werden nur als ein
Richtwert angesehen werden und nicht als genauer Elowert die Güte eines
Programmes genau bestimmt.  


%---------------------------------------------------------------------- 
\section{Der Unterschied zwischen Mensch und Maschine}
%---------------------------------------------------------------------- 

Um den Unterschied zwischen Schachprofi und Schachamateur aufzuzeigen,
führte Alfred Binet 1894 erste Experimente durch, deren Ergebnissse
er in seiner Veröffentlichung \emph{Psychologie des grands
calculateurs et jousers d'\'echecs} darlegte. Binets Annahme vor
Beginn der Untersuchung war, dass erfahrene Spieler quasi
photographische Abbilder der Schachbretter in ihrem Geist
aufbauen. Seine Untersuchungen zeigten, dass Schach drei Kategorien
von mentalen Fähigkeiten erfordert:
\begin{itemize}
\item erworbenes Wissen aus Studienmaterial um früher gespielten
Partien,
\item Gedächtnis, um dieses Wissen und die bisherigen Züge zu
speichern und
\item abstraktes Vorstellungsvormögen, um den nächsten Zug zu finden
und die daraus resultierenden Positionen zu ermitteln.
\end{itemize}


%\cite{bernstein58}

Menschliche Gehirne haben Speichergrenzen, die für Computer nicht
gelten. Die Geschichte des Mensch-Maschinen-Wettkampfs ist vor allem
aber paradigmatisch für die Demontage einer Semantik, die den blinden
Flecken in der Selbstbeobachtung des Menschen besonders deutlich
macht. So sagte der große Meister Richard Reti, im Schachspiel
offenbare sich, ob jemand Fantasie und Initiative habe. Der
eigentliche, feinste Reiz des Schachspiels liege darin, dass man dabei
geistig produktiv tätig ist. Zwischen Vatermord und Kastrationsangst
wurde Schach als menschliches Urdrama beschrieben und der französische
Psychologe Alfred Binet meinte: "Wenn wir in den Kopf eines
Schachspielers schauen könnten, würden wir eine ganze Welt aus
Gefühlen, Bildern, Emotionen und Leidenschaften sehen." Mag sein, aber
Schachprogramme kommen auch ohne diese bunte Welt erfolgreich zu
beeindruckenden Ergebnissen. Der Jahrhundertspieler Akiba Rubinstein,
dessen Kombinationen mitunter um die Welt telegrafiert wurden, um die
Virtuosität des menschlichen Geistes unter Beweis zu stellten, hatte
eine Einstellung, die nach den genannten Erkenntnissen dem Wesen des
Spiels wohl sehr viel näher kommt: "`Gegen wen spielen Sie heute
Abend? "'  Rubinstein antwortete wie ein emotionsloser Rechner: "`Heute
Abend spiele ich gegen die schwarzen Steine!"
 

\subsection{Wie man gegen Computer spielt}

Computer haben neben ihren Stärken aber auch Schwächen die man beim
Spiel ausnutzen kann. So sollte man die folgenden 10 Regeln anwenden,
wenn man gegen einen Computer antritt.


\begin{enumerate}
\item   Wählen eine ruhige Eröffnung und versuchen, den Rechner
        aus seiner Eröffnungsbibliothek zu werfen, aber auf keinen
        Fall, indem man gleich in den ersten Zügen völlig unorthodox
        spielt. 
\item   Halten die Stellung möglischt übersichtlich und
        geschlossen. Vermeide taktische Verwicklungen.
\item   Treffe die Angriffsvorbereitungen ruhig und
        gelassen. Verfrühte Angreiffe rufen nur den perfekten
        Verteidiger auf den Plan.
\item   Spielen nie spekulativ, mit Fallenspiel gegen einen
        Computer hat man wenig Aussichten auf Erfolg.
\item   Positionelle Opfer für langfristige Ziele können dagegen sehr
        effektive sein. Computer lassen sich leicht zum bauernraub verführen.
\item   Versuche den Horizont-Effekte zu provozieren. Man kann
        Drohzüge zu lassen, wenn man sicher ist, dass  dadurch kein
        Schaden entsteht.
\item   Wenn man glaubt, der Computer habe etwas übersehen und
        könnten kurzfristig Material gewinnen, dann hat man sich
        wahrscheinlich geirrt.
\item   Man darf sich von planlosen Zügen des Computers nicht
        unachtsam werden lassen.
\item   Bei unklarem Mittelspiel sollte man lieber ins Endspiel
        ab. Hier sind die Computer relativ zum Menschen am schwächsten.
\item   Man darf niemals in Zeitnot geraten.
\end{enumerate}




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