Parallele Schachprogrammierung

Paralleler Brutus, der kommende Schachgigant
Die Autoren des Schachprogramms Brutus sind Chrilly Donninger, Alex Kure, Ulf Lorenz

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 feingranulare 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.

Grobgranulare Highlevel Parallelität auf der PC-Seite: Der empfindlichste und wichtigste Teil von Brutus Suchalgorithmus läuft verteilt 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.

System Überblick:

Dr. rer. nat. Ulf Lorenz