Computerschach-WM 2003 in Graz - Lokalmatador Brutus & andere Favoriten

von Peter Schreiner - Februar 2004

Die Favoriten waren leicht auszumachen. Im Vorfeld wurde der Lokalheld Chrilly Donninger, der selbst in der Steiermark lebt, mit seiner Hard-Software-Kombination Brutus ganz hoch gehandelt. Der aktuelle SSDF-Spitzenreiter und mehrfache Weltmeister Stefan Meyer-Kahlen war ebenfalls sehr optimistisch, was die Chancen seines Programms Shredder betraf. Fritz von Frans Morsch und Mathias Feist kam frisch aus New York mit einem vielbeachteten Remis im Match gegen Garry Kasparov zurück. Das Fritz-Team war ebenfalls sehr optimistisch, da die Engine im Vorfeld exzellente Testergebnisse vorzuweisen hatte. Der Titelverteidiger Junior von Amir Ban und Shay Bushinsky gehörte ebenfalls zu der Spitzengruppe.

Im Vergleich zu diesen vier renommierten Top-Programmen war man natürlich gespannt, welches der restlichen Programme einem der Favoriten etwas »Sand ins Getriebe« streuen könnte. Als Geheimtipp wurde das belgische Programm Sjeng gehandelt. Beeindruckend war die Hardware des niederländischen Programms Diep von Vincent van Diepeveen. Eine Parallelversion des Programms war über das Internet mit dem Superrechner TERAS verbunden und konnte seine Rechenarbeit auf 460 Prozessoren a 500 MHz verrichten.

Die Hardware war nicht vorgeschrieben und es waren die unterschiedlichsten Hardwarekonfigurationen am Start. Zur Verblüffung vieler Zuschauer sah man Mathias Feist mit Deep Fritz auf einem Notebook spielen. Sollte Fritz wirklich auf einem relativ langsamen Notebook seine Rechenarbeit verrichten? Die Lösung: Das Notebook war über das Internet direkt mit dem Rechner in New York verbunden, auf dem auch gegen Kasparov gespielt wurde. Junior lief übriges auf einer identisch ausgestatteten Maschine, die allerdings direkt im Turniersaal zu bewundern und deutlich zu hören war.

Die Parallelversion von Brutus verrichtete ihre Rechenarbeit in Paderborn und Bediener Ulf Lorenz war ebenfalls über das Internet mit dem System verbunden. Brutus wird scherzhaft mit Beruf als »Schachmonster« bezeichnet. Autoren von Brutus sind Chrilly Donninger, Alex Kure und Ulf Lorenz von der Universität Paderborn. Die Aufgabenverteilung innerhalb des Teams:

  • Chrilly Donninger: Gesamtkoordination, Entwicklung des Schachprogramms Brutus, Implementator;
  • Alex Kure: Entwicklung der Bewertungsfunktion und Entwicklung des Eröffnungsbuchs;
  • Ulf Lorenz: Entwicklung eines parallelen Prototypen, Entwicklung des parallelen Suchalgorithmus und insbesondere Debugging des parallelen Suchverfahrens, Testspiele.

Die Forschungskooperation fand zwischen der Universität Paderborn und ChessBase statt. Der 8-Prozessoren-Cluster-Rechner befindet sich im Paderborner Zentrum für Paralleles Rechnen und wird auch dort gewartet und betreut:

  • Uni Paderborn: stellt Cluster bestehend aus 4 Dual-Serverknoten, Myrinet-Verbindungsnetzwerk und 8 FPGA-Karten zur Verfügung;
  • Alphadata: liefert Karten (zu speziellen Preisen);
  • PC2 (Paderborn Center for Parallel Computing): stellt Raum, Strom, Betreuung, Hardwareexpertise zur Verfügung.

Nach tollem Erfolg im Lippstädter Großmeisterturnier legte Brutus bei der WM einen Traumstart hin. Interessant ist die Ansicht von Mitentwickler Ulf Lorenz: »Wenn ich mir die Testpartien gegen die anderen Spitzenprogramme anschaue, und außerdem die Schwedische SSDF-Rangliste und die Partien von Fritz und Junior gegen Kasparov mit einbeziehe, müsste Brutus weit über 2900, eher 3000 ELO haben.« (Ulf Lorenz kennt die Verhaltensweisen von Brutus vielleicht noch am besten, da er die Testspiele organisiert hat und viele dieser Spiele live verfolgt hat.) Testspiele: je 70 Partien gegen Fritz8 und Shredder 7.04 und Junior8 auf 2,4 Ghz. Singleprozessorsystem: gegen jeden mehr als 70% Ausbeute, obwohl auch viele Startstellungen dabei, die man in Turnieren nicht anstreben braucht. Ein typisches Beispiel für die Stärken des Programms traten in der Partie gegen Mitfavorit Fritz zutage. Brutus bietet eine interessante Konfiguration.

Ein Schachprogramm besteht typischerweise aus drei Teilen: Ein Zuggenerator erzeugt schlicht alle Züge, die man in einer gegebenen Stellung machen darf. Eine Bewertungsprozedur implementiert, so weit dies möglich ist, das Schachwissen eines menschlichen Schachexperten in Form von Regeln. Die Werte, welche die Bewertungsprozedur zurückgibt, sind heuristischer Natur, unscharf und äußerst begrenzt. Der Suchalgorithmus organisiert eine Vorausschau und ist der Kern eines Schachprogramms, das es dem Computer ermöglicht, eigene schachliche Fähigkeiten zu entwickeln, die weit über die seiner Autoren hinausgehen.

Wenn man sich einmal vorstellt, welche Züge der Weiße in einer gegebenen Stellung hat, und welche Züge Schwarz auf jeden der weißen Züge machen kann, und welche Züge Weiß, usw., entsteht eine sich verzweigende Struktur, die man Spielbaum nennt. Da wir auf die genannte Weise nicht alle Möglichkeiten, die das Schachspiel uns potentiell bietet untersuchen können, nimmt sich das Schachprogramm einfach nur einen gewissen Teilbaum an der Spitze des Schach-Gesamt-Spielbaums her, bewertet die künstlich entstandenen Endstellungen mit Hilfe der heuristischen Bewertungsprozedur und wertet den Spielbaum so aus, als benutzte es keine heuristischen, sondern echte Werte. Die erstaunliche Beobachtung über die letzten 40 Jahre: Der Spielbaum arbeitet wie ein Fehlerfilter. Je schneller und je ausgefeilter der Suchalgorithmus, desto hochwertiger die Ergebnisse der Suche! Effizienz und Rechengeschwindigkeit sind hier von elementarer Bedeutung.

Merkmale des FPGA-Schachprogramms:

  • High Speed durch fein-granulare Parallelität: gerade einmal 9 (!) Taktzyklen werden für die Berechnung eines Schachknotens benötigt! Das heißt, innerhalb von 9 Takzyklen wird ein Zug erzeugt, auf dem internen Brett ausgeführt, bewertet und wieder zurückgenommen. Mehr Geschwindigkeit durch mehr Platz: Der Einbau von weiterem Schachwissen führt nicht zu einer Reduzierung der Suchgeschwindigkeit.
     
  • Flexibilität: Computerschach ist ein sehr dynamisches und sich schnell änderndes Betätigungsfeld. Harte Konkurrenz führt zu extrem kurzen Entwicklungszyklen. Das erzwingt schnelle Erneuerungsfähigkeit, und lang anhaltende Chipdesignzeiten verbieten sich fast von selbst.

Die FPGA Technologie scheint einen guten Kompromiss zur echten Hardwareentwicklung zu bieten. Brutus wurde im Oktober 2000 begonnen und ist zweieinhalb Jahre später eines der besten Schachprogramme der Welt. Der Gewinn des Lippstädter Großmeisterturniers im August 2003 war dabei das bisherige Highlight.

Der empfindlichste und wichtigste Teil von Brutus Suchalgorithmus läuft verteilt sich auf mehreren Standard PCs, welche über ein Myrienet-Hochgeschwindigkeitsnetzwerk verbunden sind. Jeder PC bedient seine eigene FPGA Karte: Einer der Prozessoren bekommt die aktuelle Schachstellung und beginnt eine im Grunde sequentielle Alphabetasuche. Die anderen Prozessoren senden Arbeitsanfragen zufällig im Netz herum, und wenn ein Prozessor, der bereits sinnvoll am aktuellen Schachproblem mitarbeitet, solch eine Anfrage einfängt, gibt er ein Teilproblem seines eigenen (Teil-)Problems ab.

Mit Hilfe eines trickreichen Nachrichtensystems zwischen den Prozessoren wird die zu verrichtende Arbeit dynamisch ausgeglichen und Suchoverhead entsteht in nur geringer Form. Nach einer kleinen Weile haben also alle Prozessoren etwas sinnvolles zu tun, und jeder einzelne Prozessor bewertet Schachstellungen in seinem Suchbaum mit Hilfe seines FPGA-Koprozessors. Ein Brutus Prozessor erzeugt ca. 100.000 kleine Suchen auf einer FPGA Karte pro Sekunde.

Shredder lief dagegen auf einem vergleichsweise langsamen Dualsystem der Tübinger Firma Transtec, einem Dual mit je 2 Xeon 3,06 GHz. Nach meinen Beobachtungen relativiert sich der Vorteil der Hardware ab einem gewissen Level. Sicher ist ein schnelles System immer günstig, entscheidend und ausschlaggebend ist aber letztendlich immer noch ein gutes Programm!

Rochade-EuropaPeter Schreiner