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