Von André Schulz
Foto:
Das Duell gegen "Deep Fritz" hat Schachweltmeister Wladimir Kramnik gestern verloren. Kein Wunder, denn die Software beherrscht die Kunst des Parallelrechnens - und kommt bei identischen Spielsituationen zu verschiedenen Zügen. Ebenso interessant erscheint, dass die in diesem Duell eingesetzte Software auf einem handelsüblichen 4-Wege-Rechner gelaufen ist. Wie, beschreibt André Schulz, Mitarbeiter von Chessbase, dem Hamburger Hersteller von Deep Fritz.
Schon im Mai dieses Jahres bekam Wladimir Kramnik eine erste Version von Deep Fritz zu Gesicht, im Oktober wurde ihm für seine Vorbereitung die endgültige Version zugeschickt - eine Vergünstigung, die der Weltmeister sich vertraglich festschreiben ließ. Ausgiebig prüfte er das Programm auf Herz und Nieren und suchte nach Schwächen. Offenbar vergeblich, denn Kramnik konnte die Software nicht besiegen - er musste sich nach einem schweren Fehler vielmehr einmal geschlagen geben und hat mit 2: 4 ging der Wettkampf zwischen Mensch und Maschine in Bonn zu Ende
Und selbst wenn der Schachweltmeister Schwächen gefunden hätte, kann er sich dennoch nicht sicher sein, dass das Software-Hardware-Paket, dem er im Forum der Bonner Bundeskunsthalle gegenübersitzt, diese tatsächlich auch wiederholt.
Denn Kramnik spielt das Programm namens Deep Fritz, wobei der Namensvorsatz "Deep" andeutet, dass es sich um eine Parallelversion des Schachprogramms Fritz handelt. Während Fritz für den normalen Wald- und Wiesen-Rechner konzipiert ist, wurde Deep Fritz für die Parallelwelt entwickelt.
Mehr-Wege-Prozessoren
Bei der Weiterentwicklung von Prozessorleistungen stoßen die Hersteller inzwischen allmählich an physikalische Grenzen. Die Gleichschaltung von mehreren Prozessoren ist der Ausweg und hat für den Datenstrom die gleichen Vorteile wie eine mehrspurige Autobahn für den Verkehrsfluss.
Der Intel Core 2 Duo Prozessor findet sich inzwischen schon in handelsüblichen Notebooks, so dass auch Otto Normalverbraucher sich den Kick beim Geschwindigkeitsrausch im Datenverkehr verschaffen kann - zumindest beim Schach.
Schon Ende der neunziger Jahre wurde aus Fritz die Parallelversion Deep Fritz entwickelt. Dies war nötig, um damals bei den Vergleichen mit den menschlichen Schnelldenkern auf den Superturnieren in Frankfurt und später in den Wettkämpfen gegen Kramnik und Kasparov nicht abgehängt zu werden.
Dynamic Tree Splitting
Beim parallel denkenden Schachprogramm wird der Rechenprozess zunächst auf einem Prozessor gestartet. Dieser erzeugt bei seinen Berechnungen einen Variantenbaum mit Listen der möglichen Züge an den verschiedenen Abzweigungen. Die Zuglisten schreibt er in den gemeinsamen Speicher an eine Art Tafel - im Programmierer-Jargon Hash-Tabellen genannt. Nun kommen die übrigen Prozessoren, schauen nach, was Prozessor 1 gerechnet hat und rechnen an anderen Stellen weiter. Auch sie schreiben ihre Ergebnisse für die Prozessorkollegen in den Speicher. Genutzt werden kann die Technik jedoch nur auf einem Rechner, in dem die Prozessoren gemeinsamen Zugriff auf den Arbeitspeicher haben. In einem Cluster aus mehreren separaten Computern wäre sie wirkungslos.
Während die meisten Schachprogramme sich an dieser Stelle mit dem erreichten Geschwindigkeitszuwachs durch gemeinsamen Zugriff auf die Hash-Tabellen zufrieden geben, geht Deep Fritz einen Schritt weiter. Prozessor 1 nimmt nämlich auch noch eine Aufgabenverteilung vor und weist den übrigen Rechnerkernen vor, welche Bereiche sie im Suchbaum bearbeiten sollen. Dieses Verfahren des Dynamic Tree Splitting ist sehr viel effizienter und sorgt für weiteren Geschwindigkeitszuwachs.
In Bonn spielt Deep Fritz auf einem Rechner mit zwei Intel Core 2 Duo. Jeder dieser Prozessoren besitzt zwei Prozessorkerne im gleichen Chip, die einen eigenen First Level Cache nutzen und sich den Second Level Cache teilen. Die Kommunikation zwischen den beiden Einheiten ist sogar schneller als bei zwei normalen parallelen Prozessoren. Gegenüber der Singleversion kommt Deep Fritz damit auf einen Zuwachs, der sehr deutlich über Faktor drei liegt.
Schmetterlings-Effekt im Computer
Dabei sorgt die Rechnerarchitektur mitunter für seltsame Effekte. Während im Singlebetrieb mit einem Prozessor die Zugvorschläge von Schachprogrammen sehr gut reproduzierbar sind - ein Programm rechnet unter gleichen Hardwarebedingungen bei gleicher Bedenkzeit immer wieder das gleiche Ergebnis aus -, ist dies im Parallelbetrieb nicht der Fall.
Ein wesentlicher Faktor dabei ist beispielsweise die Zeit, die der Bediener braucht, um den Zug von Kramnik einzugeben. Das Programm rechnet auch in der Zeit, in der es nicht am Zug ist im sogenannten Permanent Brain. Gibt der Bediener seinen Zug eine Millisekunde früher oder später ein, verändern sich die in der Hashtabelle abgelegten bisherigen Rechnergebnisse.
Minimale Abweichungen in der Berechnungsfolge der einzelnen Teilprozessoren können am Ende zu einer Art Schmetterlings-Effekt und der Ausführung eines ganz andern Zuges am Brett führen. Selbst wenn Kramnik also einen Vierprozessor-Rechner dieses Typs zur Vorbereitung verwenden würde, könnte er immer noch nicht sicher sein, dass in einer bestimmten Position immer der gleiche Zug ausgespielt wird.
Auch die Größe der Hash-Tabellen spielt eine Rolle für eine mögliche Reproduzierbarkeit der Züge. Deshalb wird sie vom Deep-Fritz-Hersteller ChessBase geheim gehalten.
Obwohl das eigentliche Schachspiel zu Ergebnissen führt, die für den Fortgang der menschlichen Geschichte von ziemlicher Nutzlosigkeit sind, führt das Nachdenken über eine effiziente maschinelle Bearbeitung der damit verbundenen Probleme, wie hier beim Symmetrical Multi Processing, zu nützlichen Techniken, die dann anderswo mit Gewinn einsetzbar sind. An komplexen Rechenaufgaben, die mit Multi-Core-Prozessoren deutlich schneller bewältigt werden können, herrscht kein Mangel - siehe Berechnung des Klimawandels.
Der Artikel ist zuerst bei "Spiegel Online" erscheinen. (wl)