Baron Wolfgang von Kempelen

Die Geschichte der Schachspielenden Maschinen beginnt im 18 Jahrhundert. Bereits vor über zweihundert Jahren haben große Menschenscharen einen Apparat bestaunt, der in den Königshäusern und auf Jahrmärkten in Europa vorgeführt wurde und auf mechanischem Weg das Schachspiel zu beherrschen schien. Im Jahre 1769 hatte die österreichisch Kaiserin Maria Theresia einen Auftrag für den 35jährigen Baron Wolfgang von Kempelen: er sollte ihr eine Maschine bauen, die großartiger war als alles, was sie bis dahin gesehen hatte. Der Deutsch-Ungar, der von der Kaiserin ein halbes Jahr von seinen Pflichten entbunden wurde, kam im Frühjahr 1770 zurück nach Wien, mit dem Schachautomaten im Gepäck: Dem Türken. Alles Türkische war damals populär: der Adel trank den gleichnamigen Mokka und kleidete seine Dienerschaft orientalisch. Die erste Partie dauerte keine halbe Stunde, Staatsrat Graf Cobenzl wurde das erste Opfer, viele würden noch folgen. Der Türke wurde 84 Jahre alt, bei einem Museumsbrand in Philadelphia ließ der Türke sein mechanisches Leben. Im Jahre 1989 spielte ein voll funktionsfähiger Nachbau des Türken in Los Angeles auf einer "Konferenz zur Geschichte der Magie".

Schon 1789 hatte der clevere Baron erste Nachahmer gefunden, die aber Maschinen produzierten, die weit weniger raffiniert waren als "der Türke". Man bedenke, dass die Puppe ja tatsächlich die Figuren mechanisch gesteuert führte und dass die Übermittlung der Züge ins Innere ebenfalls mechanisch stattfand. Ein Wunderwerk der damals möglichen Technik war "der Türke" auf jeden Fall. Zwei andere berühmte Vertreter dieser ersten Generation von Schachautomaten waren "Ajeeb" und "Mephisto", die Mitte des 19. Jahrhunderts in England entstanden und beide mehr oder weniger geschickte Kopien des "Türken" waren. "Mephisto" war weniger erfolgreich und wurde schon nach ein paar Jahren wieder verschrottet, während man "Ajeeb" noch 1929 in London bewundern konnte.

Charles Babbage

Das nächste Kapitel in der Frühgeschichte der Schachmaschinen spielte sich Anfang des 19. Jahrhunderts ab. Damals fasste ein sehr begabter junger Mathematiker in Cambridge, Charles Babbage, einen für sich folgenschweren Entschluss. Die Berechnung von Logarithmentafeln, fand er, sei eine menschenunwürdige Sklavenarbeit, die von einer Maschine übernommen werden müsse. Babbage beschloss, eine sehr aufwendige Maschine zu konstruieren, die "Analytical Engine". Der Engländer hat sie allerdings nie verwirklichen können. Um die Leistungsfähigkeit der Konstruktion zu demonstrieren, erwog Babbage eine Testversion zu bauen, die für das Schachspiel geeignet wäre. Auch dieser Plan scheiterte, aber die Strategien, die Babbage für seine Schachmaschine ersann, sind erhalten geblieben. Babbages Schachmaschine sollte in jeder Stellung folgende Fragen stellen und je nach Antwort entsprechend handeln, z.B. Habe ich verloren? - Aufgeben; Habe ich gewonnen? - Den Gewinn reklamieren; Kann ich mit einem bestimmten Zug sofort gewinnen? - Dann spiele ihn. Oberflächlich betrachtet, klingt das alles wie die Algorithmen eines Schachprogramms der heutigen Zeit, weswegen Babbages mitunter zum Vater der Schachprogrammierung ernannt wird. Eine nähere Betrachtung zeigt, dass es logische Fehler gibt und die Komplexität des Problems maßlos unterschätzt wurde.

Die erste echte Schachspielende Maschine konstruierte Torres y Quevedo im Jahre 1890. Torres baute eine Maschine, die nur einen begrenzten Bereich des Schach abdeckte: der Automat war nur in der Lage ein elementares Endspiel (weißer König und Turm gegen schwarzen König) immer siegreich zu bestreiten, allerdings nicht immer auf dem kürzesten Weg. Die Maschine existiert noch und steht in der Polytechnischen Universität von Madrid.

Nach Torres' Erfindung war erst einmal 60 Jahre lang Ruhe in Sachen Schachmaschinen. Erst mit der Erfindung der elektronischen Rechenmaschine durch Konrad Zuse (um 1941) begannen die Spekulationen über nichtmenschliche Schachspieler erneut. Zuse hatte 1941 mit dem Z3 die erste einsatzfähige, Programmgesteuerte Rechenanlage gebaut, schon in der Planungsphase über die Möglichkeiten eines Schachprogramms spekuliert und sich bereits Gedanken über die notwendigen Algorithmen gemacht. Zwar blieb Zuse auch nach dem Krieg Praktiker auf dem Gebiet der Rechner, ein Schachprogramm hat er jedoch nie geschrieben.

Alan Turing

Alan Mathieson Turing, ein Mathematiker, der sich während des 2. Weltkriegs mit der Entschlüsselung deutscher Funksprüche befasste, war ein leidenschaftlicher Schachspieler. Zwei der besten Schachspieler des Inselreichs, Harry Golombek und C.H.O.D. Alexander arbeiteten mit Turing zusammen und es gab oft lange Gespräche darüber, wie einer Maschine das Schachspiel beizubringen sei. Nach dem Krieg war Turing eine Leitfigur für viele Mathematiker, ein Vordenker auf dem Gebiet der maschinellen Intelligenz. Seine Beschäftigung mit Schach gab er nie auf, und er bastelte an einer Handsimulation, zusammen mit seinem Freund David Champernowne. Diese bestand aus einem halben Dutzend Seiten, auf denen genaue Anweisungen für die Berechnung von Zügen aufgezeichnet waren. Es war ein vollständig ausformuliertes Schachprogramm, allerdings existierten noch keine programmierbaren Computer, die ein solches Programm hätten ausführen können! Turing musste jeden Zug mühsam per Hand ausrechnen, was meist einen kaum erträglichen Zeitaufwand bedeutete. 1952 kam es zu einer ersten Partie zwischen Turings Programm "Turochamp" und einen Kollegen, Alick Glennie, einem reinen Hobbyspieler. Turing begann noch ein richtiges Schachprogramm für den neuen Rechner der Universität Manchester zu schreiben, verstarb aber im Juni 1954 unter tragischen Umständen.

Claude E. Shannon

Unabhängig von Tuning hatte in den Vereinigten Staaten ein Mann, der an den berühmten Bell Laboratories in Murray Hill, New Jersey, arbeitete, über das gleiche Thema nachgedacht. Der Mathematiker Claude E. Shannon hielt am 9. März 1949 einen für die Computerschachgeschichte entscheidenden Vortrag, der gut ein Jahr später als Aufsatz "Programming a Computer for Playing Chess" in der Zeitschrift "Philosophical Magazine" erschien. In seinem Aufsatz erörterte Shannon die Möglichkeit, einen Computer für das Schachspiel zu "programmieren" (damals ein neues Wort). Er hielt diese Aufgabe zwar für praktisch ohne Bedeutung, jedoch aus theoretischen Gründen für äußerst belangreich. Probleme, wie sie bei der Erstellung eines Schachprogramms auftreten, seien auch bei der Entwicklung von Maschinen zu erwarten, die z.B. Telefongespräche flexibel vermitteln oder Sprachen übersetzen. In seinem Vortrag stellte Shannon damals viele der wichtigsten Ideen vor, die heute in allen Schachprogrammen enthalten sind, darunter die Bewertungsfunktionen und die Baumsuche. Shannon gab detaillierte Anweisungen zur Erstellung eines Schachprogramms mit Figurenwerten und Positionsmerkmalen. Er beschrieb in seinem Vortrag weitere Merkmale der heutigen Schachprogramme, wie z.B. den Einsatz einer Eröffnungsbibliothek. Shannons grundsätzliche Gedanken zur Schachprogrammierung beeinflussten ganze Generationen von Wissenschaftlern. Die Bedeutung von Shannons wissenschaftlichen Werken ist nicht zu unterschätzen. Ohne seine Informationstheorie gäbe es kein Internet. Auch die Fehlerkorrigierenden Codes auf CDs, die Kompressionsalgorithmen in der Bildverarbeitung und vieles mehr stützen sich auf Claude Shannon.

Warum beschäftigen sich ganze Generationen von Wissenschaftlern mit dem Schachspiel? Shannon ging davon aus, dass Schach ein ideales Versuchsfeld für Experimente mit maschineller Intelligenz sei, da alle denkbaren Ereignisse des Spiels in eindeutige mathematische Termen zu fassen seien. Die Schachprogrammierung ist ein intellektuelles und technisches Abenteuer für viele. Als die Forscher einer jungen Teildisziplin der Informatik, der so genannten Künstlichen Intelligenz, nach einem geeigneten Testgebiet Ausschau hielten, fiel die Wahl auf Schach: das Spiel bot ideale Voraussetzungen: man hat es mit einer eng begrenzten Menge von Objekten (Feldern, Zügen, Figuren) zu tun. Die Schachregeln sind klar definiert und das Endziel (Matt) ist eindeutig. Dennoch besitzt diese kleine abgeschlossene Welt eine unglaubliche Komplexität. Der Schachprogrammierer kann die Fortschritte seiner Arbeit besonders deutlich erkennen und messen. Schachpartien lassen sich ohne Probleme aufzeichnen, nachspielen und analysieren.

Das erste Mattproblem gelöst!

In November 1951 gelang es Dietrich Günter Prinz, der an der Universität Manchester arbeitete, ein Schachprogramm zu schreiben, das in der Lage war ein zwei-zügiges Mattproblem zu lösen:

Das Programm brauchte 15 Minuten um die Lösung (1. Th6) zu finden.

MANIAC

Mitte der fünfziger Jahre fing ein amerikanisches Forschungsteam aus Los Alamos an für den frei programmierbaren Rechner MANIAC1, der in der Lage war 10.000 Operationen pro Sekunde auszuführen ein Schachprogramm zu schreiben. Um die Aufgabe zu vereinfachen, beschlossen sie, das Spielfeld auf ein 6 x 6 Brett zu begrenzen. Die beiden Läufer und zwei Bauern wurden weggelassen, der Doppelschritt des Bauern und die Rochade waren nicht erlaubt. Trotz der Vereinfachung des Spiels betrug die Rechenzeit pro Zug zwölf Minuten. Ingesamt spielt das Programm drei Partien. Eine Partie gewann das Programm gegen sich selbst, eine zweite Partie gegen einen starken Spieler, der dem Computer eine Dame vorgab.

Die dritte Partie spielte das Programm gegen eine junge Dame aus dem Forschungsteam, die eine Woche zuvor das Schachspiel erlernt hatte. Sie verlor die Partie gegen MANIAC: zum ersten Mal hatte ein Mensch eine Schachpartie gegen eine Maschine verloren.

Das erste Schachprogramm, das auf einem 8 x 8 Brett lief, entstand 1958. Die "Bernstein-Gruppe", bestehend aus Alex Bernstein, Michael Roberts, Thomas Arbuckly und Martin Belsky entwickelten ein Schachprogramm für den IBM 704 Rechner.

Machack

Das erste Programm, das an menschlichen Turnieren teilnahm, war "MacHack", das 1966 von Richard Greenblatt zusammen mit zwei Kollegen entwickelt wurde. In der Amateurmeisterschaft von Massachusetts erzielte das Programm ein Remis aus fünf Partien und erspielte sich eine USA Wertung von 1240 (= ca. 1040 ELO). In den Jahren nach "MacHack" kam es zu einem wahren Boom in der Schachprogrammierung. Mindestens acht neue Programme wurden geschrieben und im September 1970 wurde die erste Computerschach-Meisterschaft der Geschichte ausgetragen. Das Programm Chess 3.0, das von drei jungen Wissenschaftlern David Slate, Larry Atkin und Keith Gorlen entwickelt wurde, gewann das erste ACM-Turnier. Der Nachfolger Chess 4.0 war auch der große Favorit bei der ersten Weltmeisterschaft, die 1974 in Stockholm ausgetragen wurde. Gegen das Programm Chaos verlor Chess 4.0 seine erste Turnierpartie in seiner Laufbahn. Der erste Weltmeister wurde das Russische Programm Kaissa.

Pionier

Mit dem russischen Weltmeisterprogramm hatte der Russische Ex-Weltmeister Mikhail Botwinnik nichts zu tun. Sein Programm Pionier sollte die genauen Denkprozesse simulieren, die menschliche Meister verwenden, wenn sie Züge aussuchen. Er versuchte diese Ideen in seinem Programm zu implementieren, aber unglücklicherweise wurden die technischen Schwierigkeiten, die mit der praktischen Verwirklichung einhergingen, nie überwunden. Die letzten 25 Jahre seines Lebens war er mit dieser Aufgabe beschäftigt, ohne dass er ein spielfähiges Programm präsentieren konnte. Kritiker vermuteten, dass es in Wirklichkeit nie ein Programm gab.

Von Belle bis Deep Blue

Es ist bemerkenswert, dass ein weiterer Pionier auf dem Gebiet der Schachprogrammierung, Ken Thompson, im gleichen Gebäude der Bell Labs seine Karriere begann, in dem eine Generation zuvor Shannon die Grundlagen gelegt hatte. Thompson entwickelte Linux und die Programmiersprache C und baute in den achtziger Jahren die berühmte "Belle" Maschine. Er erfand damit die Strategie der Hardware-Programmierung für Schach, die später auch bei Deep Blue Verwendung finden sollte. Ursprünglich sollte Belle 1.000.000 Stellungen pro Sekunde erzeugen und bewerten. Die tatsächlich gebaute Maschine "Belle" schaffte allerdings "nur" 150.000 bis 180.000 Stellungen und erreichte eine durchschnittliche Suchtiefe von acht bis neuen Halbzügen. Thompson war auch der erste, der Eröffnungsbücher einsetzte, "hash tables" verwendete und Endspieldatenbanken berechnete. Auch andere Forscher spielten mit dem Gedanken leistungsfähige Spezialmaschinen zu bauen. Feng-Hsiung Hsu, ein Elektroingenieur aus Taiwan kam als erster auf den Gedanken, einen kompletten Zuggenerator auf einen einzigen Chip zu bringen. Die Gruppe um Hsu arbeitete später an besondere Erweiterungen des Suchbaum, "Singular Extensions" genannt, Hsu verbesserte den Microcode und erhöhte die Suchgeschwindigkeit der Maschine "Deep Thought" auf 500.000 Stellungen in der Sekunde. Deep Thought II erzielte Suchgeschwindigkeiten von bis zu sieben Millionen Stellungen in der Sekunde, etliche Großmeister wurden unter regulären Turnierbedingungen bezwungen. Deep Thought II war allerdings nur eine Zwischenstufe zu einem gigantischen Ziel: Deep Blue, die die Grenze von einer Milliarde Knoten durchbrechen sollte. In Oktober 1995 war der Deep Blue Chip fertig. Drei Jahre hatte die Entwicklung dieses VLSI-Chips gedauert, hauptsächlich weil der Chefkonstrukteur Hsu sehr ehrgeizig an die Bewertungsfunktion herangegangen war. Der Deep Blue Chip leistete zwei bis drei Millionen Stellungsüberprüfungen pro Sekunde. Für das erste Match gegen Garry Kasparov in Februar 1996 kamen 200 Prozessoren zum Einsatz. Kasparov gewann das Match 4-2, ein Jahr später war Deep Blue durch einen schnelleren Hostrechner und die Verwendung von bis zu 512 Schachchips zweimal schneller geworden. Nach einem harten Kopf-an-Kopf-Rennen verlor Kasparov das 6-Partien-Match 3,5-2,5. Seit dem 25. Oktober 2002 steht Deep Blue im berühmten Smithsonian´s National Museum of American History in Washington. Entgegen anderslautender Meldungen ließ IBM den Rechner also doch nicht verschrotten, sondern spendierte ihn der Öffentlichkeit. 20 Millionen Dollar hat sich IBM die Entwicklung von Deep Blue kosten lassen.

Computerschach erreicht die Kaufhäuser

Die Beschäftigung mit Computerschach war bis 1977 eine ziemlich elitäre Angelegenheit. In den siebziger Jahren wurde Computerschach auch beim großen Publikum immer bekannter und beliebter. Grund dafür waren die Schachspielenden Maschinen die es seit 1977 in Kaufhäuser zu kaufen gab. Waren sie zu Anfang nicht mehr als einfache Spielzeuge, die noch nicht einmal sämtliche Regeln beherrschten, wurden sie später immer ausgereifter und erreichten Anfang der 90er Jahre ihre Blütezeit. Der erste kommerzielle Schachcomputer der Welt, der Chess Challenger spielte zwar nur legale Züge, akzeptierte aber auch regelwidrige Eingaben. So war es möglich das Gerät mit der Zugfolge 1. Sf3 Sf6 2. Se5 Se4 3. Dd1xf7 mattzusetzen. Nachfolgemodelle entwickelten sich zu absoluten Verkaufsschlagern. Das Gerät Chess Champion Super System III wurde ca. 200.000 verkauft. Verschiedene Hersteller in Deutschland, HongKong und USA überboten sich mit immer raffinierteren Schachcomputer. Die Sensorbretter kamen, Leuchtdioden signalisierten Computerzüge und es gab sogar Schachroboter. Für talentierte junge Programmierer wie Frans Morsch, Ed Schröder und Richard Lang, die Schachprogramme für die Brettcomputer entwickelten, war diese Zeit eine wahre Goldgrube.

Zur gleichen Zeit gab es Schachprogramme die auf dem Heimcomputer liefen. Ein sehr erfolgreiches Programm, Microchess, das auf dem KIM-1, TRS-80 und schließlich auf den PET-Rechnern von Commodore lief, wurde weltweit insgesamt ca. 50.000-mal abgesetzt. Als 1991 die ersten PCs mit den leistungsstarken 80386er Prozessoren von Intel ausgestattet wurden, begann der Siegeszug der PC-Programme. Die meisten starken Brettcomputer enthielten Prozessoren von Motorola (68000) oder anderen Herstellern, und mit diesen konnte der Intel-Prozessor erstmals mithalten. Die PC-Programme gewannen schnell an Popularität, und die Programmierer waren motiviert in diesem neuen Bereich ihre größte Aktivität zu entwickeln. Die erste Versionen von Fritz, Rebel ChessMaster und Chess Genius erschienen und fast jährlich erscheinen neue Versionen.

Der Glaubenskrieg der Programmierer

Seitdem Menschen versuchen, Maschinen das Schachspielen beizubringen, wird die kontroverse Frage diskutiert, mit welcher Methode dies am besten zu bewerkstelligen ist. Die einen versuchen es mit brutaler Rechengewalt, die anderen setzten auf die Umsetzung menschlichen Wissens. Durch eine Steigerung der Rechengeschwindigkeit ist die Spielstärke eines Schachprogramms kaum noch zu steigern. 1999 gewann das auf Schachwissen basierte Programm Shredder von Stefan Meyer-Kahlen die Weltmeisterschaft auf einem handelsüblichen Rechner vor einigen Großrechnern. Der Österreicher Dr. Christian Donninger versucht mit seinem Mini Deep Blue Projekt "Brutus" Geschwindigkeit und Schachwissen zu kombinieren. Brutus ist ein neuartiges FPGA-basiertes Schachprogramm. Der FPPA-Chip (= Field Programmable Gate Array) ist ein programmierbarer Chip und bietet bei entsprechender Ausnutzung den Vorteil, dass feste Bewertungen sehr schnell abgearbeitet werden können. Das heißt, dass "Schachwissen" schneller als bei PC-Programmen umgesetzt werden kann, bzw. dass man sehr viel mehr Schachwissen in das Programm einbauen kann, ohne dass es deshalb zu mangelnden Suchtiefen kommt.

Klein oder groß?

Donninger konzentriert sich mit seinem von ChessBase geförderten Projekt auf die Themen größer, schneller, besser. Andere Programmierer suchen einen anderen Weg: klein und handlich. Letztes Jahr portierte Meyer-Kahlen sein Programm Shredder für Pocket PC´s: Pocket Fritz ist das stärkste Handheld Schachprogramm. Auch der Engländer Richard Lang, der mit seinen Programmen in den achtziger Jahren viele Weltmeisterschaften gewinnen konnte, konzentriert sich auf dieses Gebiet: er hat sein Chess Genius Programm für Handheld Computer (Palm, Pocket PC) umgesetzt und das erste starke Schachprogramm für Nokia Handys geschrieben. Mit atemberaubendem Tempo hat sich der Traum Computerschach erfüllt.

Quellen:

Schach am PC: Dieter Steinwender, Frederic A. Friedel

Schaken voor Computers: Peter van Diepen, Jaap van den Herik

Behind Deep Blue: Feng-Hsiung Hsu

The Turk, Chess Automaton: Gerald M. Levitt

Kasparov versus Deep Blue: Monroe Newborn

Chips challenging Champions: Editors Jonathan Schaeffer, Jaap van den Herik

zur Coko