Schachsoftware Deep Fritz: Kramniks Kampf gegen die Parallelwelt

Von André Schulz

Das Duell gegen Deep Fritz ist für Wladimir Kramnik nicht mehr zu gewinnen - höchstens noch ein Remis ist für ihn drin. Kein Wunder, denn die Software beherrscht die Kunst des Parallelrechnens - und kommt bei identischen Spielsituationen zu verschiedenen Zügen. SPIEGEL ONLINE überträgt live ab 15 Uhr.

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 bislang konnte Kramnik die Software nicht besiegen - er musste sich nach einem schweren Fehler vielmehr einmal geschlagen geben und liegt nun mit 3,0 zu 2,0 zurück.

Duell Mensch - Maschine: Seltsame Effekte im Parallelbetrieb
AP

Duell Mensch - Maschine: Seltsame Effekte im Parallelbetrieb

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.

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.

Live dabei: Ab 15 Uhr übertragen wir die Finalpartie mit Audiokommentar und Zugübertragung. Der "Liveticker" dient bis dahin als Archiv der bisherigen Partien

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.

André Schulz ist Mitarbeiter von Chessbase, dem Hersteller von Deep Fritz

Diesen Artikel...
Aus Datenschutzgründen wird Ihre IP-Adresse nur dann gespeichert, wenn Sie angemeldeter und eingeloggter Facebook-Nutzer sind. Wenn Sie mehr zum Thema Datenschutz wissen wollen, klicken Sie auf das i.

Auf anderen Social Networks teilen

  • Xing
  • LinkedIn
  • Tumblr
  • studiVZ meinVZ schülerVZ
  • deli.cio.us
  • Digg
  • reddit
News verfolgen

HilfeLassen Sie sich mit kostenlosen Diensten auf dem Laufenden halten:

alles aus der Rubrik Netzwelt
Twitter | RSS
alles aus der Rubrik Tech
RSS

© SPIEGEL ONLINE 2006
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH

SPIEGEL ONLINE Schließen


  • Drucken Versenden
  • Nutzungsrechte Feedback
  • Zur Startseite
Vote
Kramniks letzte Chance

Gewinnen kann er das Match nicht mehr, doch verlieren will er mit Sicherheit auch nicht: Schafft es Schachweltmeister Wladimir Kramnik noch, durch einen Sieg ein Unentschieden gegen den Rechner Deep Fritz zu erreichen?

Die Abstimmung ist beendet. Klicken Sie hier, um das Ergebnis zu sehen.


E-Book-Tipp
  • Christian Stöcker:
    Spielmacher
    Gespräche mit Pionieren der Gamesbranche.

    Mit Dan Houser ("Grand Theft Auto"), Ken Levine ("Bioshock"), Sid Meier ("Civilization"), Hideo Kojima ("Metal Gear Solid") u.v.A.

    Kindle Edition: 1,99 Euro.

  • Einfach und bequem: Direkt bei Amazon bestellen.