Shredder fängt Brutus ab

Die 5. Runde war bot den zahlreichen Zuschauern gleich zwei Spitzenpaarungen. Junior spielte einen strategisch originellen, recht vorsichtigen Aufbau. Man hatte fast den Eindruck, dass das Junior-Team gegen den Mitfavoriten Fritz mit einem Remis zufrieden wäre. Fritz hatte als Nachziehender wenig Möglichkeiten, die Initiative zu ergreifen und musste letztendlich nach hartem Kampf in das Unentschieden einwilligen.

Junior gegen Fritz

Lokalmatador Brutus wird von den einheimischen Zuschauern und vielen Computerschachfans bei diesem Turnier eindeutig favorisiert. Der Grund dafür war klar: Brutus hatte bisher gnadenlos alle Gegner aus dem Weg geräumt. Für Gegner Shredder ging es vor allem darum, mit Weiß den vollen Punkt einzufahren, nachdem das Programm von Stefan Meyer-Kahlen gegen den Mitfavoriten Fritz bereits verloren hatte. Der Verlauf der Partie zeigte nachhaltig, welche Bedeutung die Eröffnungsbibliotheken bei diesem Turnier haben. Shredder kam diesmal im Unterschied zur Partie gegen Fritz mit leichtem Vorteil aus dem Eröffnungsbuch.

Shredder - Brutus

Kleine, aber deutlich wahrnehmbare Vorzüge reichen bei dem spielerischen Niveau der heutigen Programme aus, um einen Sieg einzufahren. Brutus hatte nach der Eröffnung im Verlauf der Partie nicht die geringste Chance und musste seinen ersten Punkt abgeben.

Wenn ein Mensch Eröffnungen spielt, reproduziert er - wie bereits ausgeführt - in der Regel Züge. Dabei spielt es überhaupt keine Rolle, ob dieser Zug aus einem Buch, von einem anderen Schachspieler oder einer Datenbank stammt. Auch wenn ein bestimmter Eröffnungszug vom Spieler in häuslicher Analyse selbst gefunden wurde (= Neuerung), handelt es sich bei der praktischen Anwendung in einer Schachpartie um eine Reproduktion. Schachprogramme verhalten sich in dieser Hinsicht nicht anders. Jedes Programm verfügt über eingespeicherte Eröffnungszüge, die es nur aus der entsprechenden Datei abzurufen braucht. Die Datei mit den gespeicherten Zügen bezeichnet man als Eröffnungsbuch oder Eröffnungsbibliothek. In gedruckten Eröffnungsbüchern befinden sich genau wie in den Eröffnungsbüchern von Schachprogrammen Zugfolgen und Bewertungen (z.B. "guter Zug" oder "schlechter Zug"). Ein Schachprogramm benötigt die Hilfe eines Entwicklers, der einerseits ein starker Schachspieler sein muss, um möglichst günstige Eröffnungen auszuspielen. Indirekt sind damit die Begegnungen auch Duelle zwischen den unterschiedlichen Buchautoren.

Zuschauerschach


Hardware

Bei der Beurteilung der Performance der einzelnen Programme muss man beachten, dass immer eine Kombination von Hard- und Software am Start ist. Dies war auch in Graz nicht anders, da fast alle Teilnehmer mit einer eigenen Maschine am Start waren. Teilweise sind sehr interessante Maschinen mit am Start.

Vincent Diepeveen

Vincent Diepeveen spielt via Internet auf einem Großrechner, dessen Ressourcen von der Universität Maastricht zur Verfügung gestellt wurden. Sein Programm Diep benutzt für die Berechnungen insgesamt 512 Prozessoren (à 500 MHz). Eigentümer des Systems ist die (NWO) Niederländische Wissenschaftliches Untersuchungsinstitut. Obwohl der Autor wenig Möglichkeiten hatte, die komplexe Konfiguration auszutesten, lief das System bisher erfreulich stabil.

Gian-Carlo Pascutto mit Sjeng

Ein interessanter Newcomer ist das belgische Programm Sjeng, das von der Firma Lokasoft vertrieben wird. Das Programm rechnet auf einer brandneuen Technologie, einem 64 Bit Opteron, der von AMD gesponsort wurde.

Opteron

Während des Turniers sah man Fritz-Autor mit einem simplen Notebook spielen. Sollte sich Fritz wirklich mit beschränkter Hardwarepower zufrieden geben ? Eine kurze Nachfrage ergab, daß Fritz seine Berechnungen exakt auf der gleichen Maschine durchführt, die man für das Match gegen Kasparov einsetzt hat. Der Rechner steht nach wie vor in New York und Fritz ist einfach via Internet mit dem Quad-Rechner verbunden.

Mit der bescheidensten Hardware muß sich Shredder zufrieden geben. Ursprünglich sollte das deutsche Spitzenprogramm auf einem Quad-Rechner spielen. Leider stand die Maschine dann doch nicht zur Verfügung und Shredder agiert auf einem im Vergleich zur Konkurrenz relativ bescheidenen Dualrechner mit 2 x 3,06 GHz - Prozessoren.

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 findet zwischen der Universität Paderborn und ChessBase statt. 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 ELO-Rangliste und Fritzs und Juniors Partien 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 meiner Meinung nach die interessanteste 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, die 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ß ...etc., 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 trickigen 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.

Den Amateuren gelang bisher im Turnier bis auf den Sieg in der Erstrunde von Ruy Lopez gegen Junior keine Überraschung. Es bleibt abzuwarten, ob der ein oder andere Amateur für eine Überraschung sorgen kann. Wünschenswert wäre es allemal, schließlich sind Außenseitersiege die Highlights jedes Turniers.