Schachmonster

Inhaltsverzeichnis

Schach eignet sich - entgegen weit verbreiteter Ansichten - sehr schlecht dafür, parallel in Computer-Clustern berechnet zu werden. Alle PC-Schachprogramme, die mehrere Prozessoren nutzen können, sind auf Shared Memory angewiesen und skalieren nur auf vier oder höchstens acht Prozessoren einigermaßen gut. Massiv parallele Programme gab es bislang nur in wenig erfolgreichen Universitätsprojekten - und bei IBM: Deep Blue, ein Netz aus mehr als 200 eigens entwickelten Schach-Prozessoren in 32 parallel geschalteten RS/6000-Workstations, schlug 1997 den damaligen Weltmeister Garri Kasparow - und wurde anschließend sofort demontiert. Seitdem war es still um Hardware-Programme - bis ein echter Ölscheich (der anonym bleiben möchte) aus den Vereinigten Arabischen Emiraten mit großer Finanzkraft eingriff.

Mit den Öl-Dollars entwickelte die in Abu Dhabi ansässige PAL Group of Companies das Programm Hydra. Ähnlich wie einst Deep Blue arbeitet es auf Spezial-Hardware. In einem Duell über acht Partien im Rahmen des alljährlichen Schachturniers in Abu Dhubai schlug es das wohl stärkste PC-Programm Shredder mit 5,5 zu 2,5 Punkten.

Die Ideen des Unix-Vaters

Während IBMs Deep Blue eigens entworfene ASICs (Application Specific Integrated Circuits) einsetzte, läuft Hydra auf FPGAs (Field Programmable Gate Arrays). Der Vorschlag, FPGAs statt ASICs zu verwenden, stammt vom Unix- und C-Erfinder Ken Thompson, der Anfang der achtziger Jahre die damals stärkste Schachmaschine der Welt gebaut hatte. Ungefähr im Jahr 1999 schrieb er in LDE (einer nur in den Bell-Labs verwendeten Programmiersprache für Hardware-Bausteine) einen Zuggenerator und einen Konverter nach Verilog, womit FPGA-Entwickler die Bausteine programmieren. Im Auftrag der Hamburger Firma Chessbase machte sich der österreichische Schachprogrammierer Dr. Chrilly Donninger ans Werk, ein „Brutus“ getauftes FPGA-Schachprogramm zu entwickeln.

FPGAs sind zwar langsamer als Deep Blues ASICs, dafür aber programmierbar; spielerische Schwächen und Programmfehler lassen sich so jederzeit beseitigen. Bei fehlerhaften ASICs bliebe nur der Müllschlucker, während FPGAs ein neues Programm überspielt bekommen.

Alles parallel

Nach zwei Jahren Entwicklungszeit stellte sich heraus, dass mit nur einer FPGA-Karte kein Staat zu machen ist gegen die auf immer schnelleren Pentium- und Athlon-Prozessoren laufenden reinen Software-Schachprogramme. Als Brutus im November 2003 bei der Computerschach-Weltmeisterschaft in Graz nur einen enttäuschenden vierten Platz belegte, strich Chessbase die Finanzierung. Donninger suchte neue Geldgeber, war zunächst damit aber erfolglos und dachte ernsthaft darüber nach, ein Go-Programm zu entwickeln.

Dann trat die PAL Group of Companies aus Abu Dhabi auf den Plan und übernahm das Projekt von Chessbase - zum Nulltarif, weil alle Rechte außer der Vermarktung beim Programmierer lagen. Nur falls Hydra also jemals irgendwo im Verkaufsregal stehen soll, müsste die PAL Group vorher mit Chessbase neu verhandeln. Die Technik wurde zunächst den finanziellen Gegebenheiten angepasst: Eine Karte war zu wenig und ohnehin nicht konkurrenzfähig, ein Cluster musste her, auf dem viele FPGA-Karten gleichzeitig Stellungen bewerten können.

In Abu Dhabi rechneten nun 16 FPGA-Karten (ADM-XRC-I) von Alpha Data, verteilt auf einen Linux-Cluster aus acht Rechnern mit jeweils zwei Xeon-Prozessoren, die mit drei GHz Taktfrequenz liefen. Programmierer Dr. Chrilly Donninger hat trotzdem noch spielerische Schwächen entdeckt, denen zu Leibe zu rücken aber nicht ganz einfach ist: „Gerade im Endspiel gibt es noch viel zu tun. Die Karte mit dem Virtex-I-1000e-Chip ist eigentlich nur der 486er unter den FPGA-Karten, momentan auch ziemlich voll. Ich kann das erst mit dem Nachfolgechip machen, auf dem ich mehr Kapazität habe. Aber die neue Virtex-Pro ist schon bestellt. Ebenso ein 32-Prozessor-Cluster. Da sind wir dann ungefähr fünfmal so schnell wie jetzt und werden ein wirklich schreckliches Monster.“

Alles parallel

Hydras Arbeitsweise ähnelt der von Deep Blue: Eine auf einem normalen PC laufende Software durchsucht den Spielbaum - nicht anders als andere Schachprogramme auch. Sie bewertet die entstehenden Spielsituationen jedoch nicht, sondern übergibt die Endstellungen, also die Blattknoten des Spielbaums, an die FPGA-Karte. Diese hängt noch eine kurze Suche über etwa drei bis fünf Halbzüge hintendran und bewertet die dann entstehenden Stellungen. Während in einem normalen Schachprogramm jeder zusätzliche Bewertungsterm der Baumsuche Zeit stiehlt und so dafür sorgt, dass die erreichte Suchtiefe im Spielbaum schrumpft, trifft das auf eine in Hardware gegossene Bewertung nur in sehr eingeschränktem Maße zu, weil hier (fast) alle Bewertungen parallel ohne Zeitverlust erfolgen.

Während Hydra durch den Einsatz von Spezial-Hardware bei der Stellungsbewertung sehr gut skaliert, ist die Parallelisierung bei der Suche im Spielbaum nach wie vor schwierig: Ohne ausgefeilte Programmiertechnik werden Berechnungen doppelt, dreifach oder gar zehnfach ausgeführt. Daher holte sich das Hydra-Team einen Spezialisten ins Boot, Dr. Ulf Lorenz von der Universität Paderborn, der seit Jahren auf diesem Gebiet forscht und schon einmal an der Programmierung eines massiv parallelen Programms beteiligt war. Bei der Vernetzung der Cluster-Rechner geht es weniger um hohen Durchsatz als um kurze Latenzzeit, weshalb die Rechner des Hydra-Clusters per Lichtwellenleiter über schnelle Myrinet-Karten verbunden sind, die mit rund 1000 Euro pro Stück allerdings etwas mehr kosten als eine gewöhnliche Netzwerkkarte.

Auch sonst klotzte die Pal Group, statt zu kleckern: Der einzige Großmeister des Landes, Talib Mousa, wurde engagiert, um das Programm zu testen und dessen Spieleigenschaften zu verbessern. Der deutsche Spitzenspieler Großmeister Christopher Lutz kümmert sich halbtags um die Eröffnungen, die das FPGA-Programm spielen soll. Normalerweise enthalten die Eröffnungsbibliotheken aktueller Schachprogramme mehrere Millionen Züge, kompiliert aus allen elektronisch erfassten Partien zwischen Menschen ab einer bestimmten Spielstärke. Danach nimmt sich ein Experte ausgewählte Varianten vor und erweitert sie um eigene Analysen, überprüft, ob sie zu dem Programm passen oder ob sie überhaupt korrekt sind. Die meisten enthaltenen Varianten bleiben aber schon wegen ihrer schieren Anzahl ungeprüft.

Die Ausspielwahrscheinlichkeit hängt mit der Erfolgsquote zusammen, welche die Großmeister damit erreicht haben. Das führt nicht selten dazu, dass ein Programm aus dem Eröffnungsbuch heraus schlechte Züge spielt, nur weil in den zugrunde liegenden Datenbanken diese Züge erfolgreich von Menschen gespielt wurden - von Menschen, die meist viel schwächer sind als die besten Schachprogramme, die ohne Buch oftmals bessere Züge gespielt hätten. Diesen Effekt hält Hydra-Programmierer Chrilly Donninger für so schädlich, dass er nur mit einem sehr flachen Buch antrat. Im Match gegen Shredder spielte Hydra im Mittel nur zehn Züge aus der Eröffnungsbibliothek und rechnete dann selbst, während sein Gegner durchschnittlich bis zum 16. Zug Buchvarianten parat hatte.

Das Match

Gegen einen Cluster aus 16 Prozessoren, aufgerüstet mit spezieller Schach-Hardware, wirkte der Quad-Opteron mit 2,2 GHz, auf dem Shredder spielte, geradezu schwachbrüstig. Dennoch war es der schnellste Rechner, auf dem Shredder jemals über Schachzüge brütete. Trotz des gewaltigen Hardware-Nachteils gab es nicht wenige Experten, die an einen Sieg des PC-Programms glaubten. Schließlich ist Shredder das erfolgreichste Programm der letzten zehn Jahre, führt in der schwedischen Computerrangliste seit mehr als zwei Jahren mit ziemlichem Vorsprung und verliert dank seiner sprichwörtlichen Zähigkeit fast niemals ein Match.

Doch trotz des Vorteils, länger aus dem Eröffnungsbuch spielen zu können (was auch Bedenkzeit spart; beide Programme hatten nur 90 Minuten für die gesamte Partie), bekam Shredder kein Bein auf den Boden und verlor gleich die ersten beiden Partien. Nach einer Serie von vier Remis unterlag das PC-Programm dem Hardwaremonster in der siebten Partie erneut, im achten und letzten Treffen gab es wieder ein Unentschieden.

Stefan Meyer-Kahlen, Shredders Programmierer, war nach dem Match der Ansicht, Shredder habe höher als nötig verloren: „Die ersten beiden Niederlagen waren Fehler im Eröffnungsbuch, also völlig überflüssig. Wir haben die schlechten Varianten dann einfach gesperrt. Die siebte Partie war Hydras beste. Keiner der Anwesenden hat die Partie aber so richtig verstanden, wir müssen das erst analysieren.“ Es gab in drei Partien durchaus Siegchancen für Shredder, sagte Meyer-Kahlen, aber Hydra habe sich gut verteidigt.

Hydras Programmierer Chrilly Donninger sah seine Schöpfung dagegen nie wirklich in Gefahr. „Mit dem Ergebnis bin ich natürlich zufrieden; auch unser Eröffnungsbuch-Autor Großmeister Christopher Lutz hat hervorragende Arbeit geleistet. Nur in der achten Partie hatten wir eine schwierige Position. Hydra hat aber Konterchancen gefunden und diese Stellung auch besser eingeschätzt als Shredder, der schon 1,3 Bauern Vorteil für sich anzeigte.“

Wie gut Hydra gegen Menschen spielt, wird sich im Herbst in Bilbao zeigen, wo vom 6. bis 9. Oktober ein Mannschaftskampf zwischen drei Programmen und drei starken Großmeistern stattfindet. An der Seite von Hydra treten die Chessbase-Programme Fritz und Junior an, die beide schon gegen Kasparow Matches unentschieden spielten; die Menschheit vertritt unter anderem der ehemalige Weltmeister Ruslan Ponomarjow aus der Ukraine. Einen Warnschuss feuerte das Hydra-Team aber schon ab: Am Rande des Turniers in Abu Dhabi kam Großmeister Wladimirow gegen den Schach-Cluster mit 0:3 böse unter die Räder. (jk) (jk)