Belle's Enkel,
die Brutus-Entwicklungsgeschichte
von Chrilly Donninger

Prozessoren wie der Intel-Pentium sind Generalisten. Sie stellen dem Programmierer arithmetische Operationen, Lese/Schreibzugriffe auf das RAM, Vergleiche und Sprünge im Programmcode zur Verfügung. Mit diesem Satz von Maschinenbefehlen kann man alles programmieren, was sich überhaupt programmieren lässt. Wie bei jedem Alleskönner sind diese Befehle für eine spezielle Aufgabe nicht sehr effizient. Man benötigt sehr viele Befehle um eine Aufgabe zu lösen, für die ein spezialisierter Prozessor unter Umständen nur einen Befehl benötigen würde. Falls der Bremseffekt zu groß und das Problem auch wichtig genug ist, gibt es zwei Lösungen. Man entwirft einen eigenen speziellen Chip der dem Generalisten die Arbeit abnimmt. Ein Beispiel dafür ist die Videokarte. Oder die Befehle werden direkt in den Chip integriert. Die ursprünglichen Intel Chips konnten nur mit ganzen Zahlen (Integers) rechnen. Floating-Point (Bruchzahlen) Arithmetik wurden durch eine Serie von Integer-Operationen emuliert. Das ist sehr umständlich und langsam. Also verpasste man dem Chip im Laufe der Zeit eine Floating-Point-Unit. Diese spezielle Einheit kann eine Bruchzahloperation in einem Schritt ausführen.

Schach ist eine Anwendung für die ein Generalist besonders ungeeignet ist. Es müssen tausende Befehle abgearbeitet werden um eine Schachstellung berechnen zu können. Es gilt vor allem: Je mehr Wissen man in ein Schachprogramm einbaut, desto länger wird die Befehlsfolge. Das Programm wird langsamer und damit taktisch schwächer. Schachprogrammierung auf einem "normalen" Prozessor ist daher immer ein Kompromiss zwischen Wissen und taktischer Stärke.

Bereits Ende der 70er Jahre hatte der Unix-Vater Ken Thompson die Idee eine spezielle Schachhardware zu entwerfen. Anstatt in ein paar Tausend kann man mit einer speziellen Schachhardware eine Stellung in ein Dutzend Schritten berechnen. Eine komplexere Bewertung bremst das Programm nicht ein. Floating-Point-Befehle sind ja auch komplizierter als jene für ganze Zahlen. Trotzdem sind beide Befehle auf einem Pentium gleich schnell. Man braucht für die Floating-Point-Operation nur mehr Hardware-Schaltungen. Diese Ressourcen hatte man beim Ur-PC noch nicht preisgünstig zur Verfügung.

Die Schachhardware Belle berechnete damals unglaubliche 150.000 Stellungen pro Sekunde. Belles Schachwissen war allerdings nicht berauschend. Ken hatte - wir sind in der Zeit des Ur-PCs - dafür nicht genügend Hardware zur Verfügung. Belle war aber trotzdem um mehr als eine Klasse besser als die übrigen auf allgemeinen Prozessoren laufenden Programme. Ken hatte damit bewiesen was er beweisen wollte und widmete sich wieder anderen Aufgaben.

Seine Idee wurde ein paar Jahre später von einer Gruppe von Studenten an der Carnegie-Mellon-Universität in Pittsburgh aufgenommen. Ihr Programm ChipTest war eine Kombination aus Soft- und Hardware. Die ersten Teil einer Variante wurde auf einem normalen Prozessor ausgeführt. Die letzten Züge wurden - wie bei einer Grafikkarte - der Schachhardware zur Berechnung übergeben. Die Schachhardware kann diesen letzten zeitkritischen Teil der Suche viel schneller ausführen. Diese Aufteilung hat einen großen Vorteil. Komplizierte Suchmechanismen sind in Hardware sehr schwer zu programmieren. Es ist auch technisch sehr schwierig auf die Hashtabellen des Programmes zuzugreifen. Wenn man einmal ein Programm in Hardware gegossen hat, dann ist es fest verdrahtet. Man kann - falls man was ändern will oder auf einen schweren Fehler draufkommt - den Chip nur mehr wegwerfen und mit viel Geld und Aufwand einen neuen machen. Eine auf einem allgemeinen Prozessor laufende Software kann hingegen relativ leicht verändert werden. ChipTest berechnete bereits 750.000 Positionen pro Sekunde. Die Bewertungsfunktion war wie jene von Belle aber auch nicht sehr ausgeklügelt. Die Kombination von guter Software-Suche und schneller Hardware war dennoch konkurrenzlos. IBM wurde auf ChipTest aufmerksam, kaufte sich das Team ein und taufte es Deep Blue. Ein paar Jahre später machte Deep Blue-II Kasparov fertig.

Deep-Blue-II war nicht nur ein besonders schnelles Schachprogramm. Es wurden auch erstmals die Möglichkeiten der Hardware für eine komplexe Bewertungsfunktion ausgereizt. IBM war aber nie am Schachprogramm sondern am Mythos Deep-Blue interessiert. Deep-Blue musste daher - wie Marilyn Monroe - am Höhepunkt seines Ruhmes sterben. Nur so war der ewige Ruhm garantiert.

Im Jahr 2000 fragte Ken Thompson seinen alten Spezi Frederic Friedel. "Frederic, es gibt da  eine interessante Hardware-Entwicklung, kennst nicht einen Programmierer der einen Deep-Blue Nachfolger machen könnte". Die interessante Hardware-Entwicklung sind die so genannten FPGAs (Field-Programmable-Gate Arrays). FPGAs sind ein Zwitterwesen. Sie verhalten sich wie Hardware, sind allerdings - mit einer speziellen Sprache - programmierbar. Die Programmierung von FPGAs ist zwar komplizierter und aufwendiger als jene von normalen Prozessoren. Man muß eine FPGA aber nicht wegwerfen, wenn man etwas ändern will. Damit sind FPGAs wie geschaffen für die Schachprogrammierung. Es gibt keine in allen Stellungen richtige Bewertungsfunktion. Man kann diese nur durch sehr viel Ausprobieren schrittweise weniger falsch machen.

Frederic kannte so einen Programmierer. Es war meine Wenigkeit. Ich hatte zwar keine Erfahrung mit Hardware-Design. Aber nach ein paar Nachhilfestunden von Ken Thompson (inklusive einem Flugkurs mit seiner Cessna) und ein paar Monaten Schweiß im kühlen Waldviertel bekam ich die Sache doch in den Griff. Schachprogrammieren hatte ich ja mit Nimzo lange genug geübt. Zu Beginn des Projektes wurde ich dennoch von Hardware-Experten nicht ganz ernst genommen. Man hielt meine Pläne für größenwahnsinnig. Ken Thompson besitzt aber bei ChessBase gottartigen Status. Nachdem von Ken die Idee ausging und er mir die Sache auch zutraute, stand ChessBase voll hinter dem Projekt. Ich konnte auch Graham Smart, den Chef der schottischen Firma Alpha-Data, vom Projekt überzeugen. Graham versorgt mich seither nicht nur mit FPGA Entwicklungskarten, sondern auch mit schottischem Malzkonzentrat. Seit November 2002 ist auch die Abteilung für Paralleles Rechnen der Universität Paderborn unter Prof. Monien mit im Boot. Wir können es punkto Ressourcen noch immer nicht mit IBM aufnehmen, aber es ist ein schönes Gefühl, wenn man klein und etwas belächelt anfängt und man merkt, dass immer mehr an das Projekt-Brutus glauben und auch bereit sind es zu unterstützen.

Die Arbeit an Brutus startete im Oktober 2000. Die ersten Monate war ich hauptsächlich mit dem Erlernen - sehr viele Versuche und fast ebenso viele Irrtümer - der Hardware-Programmierung beschäftigt. Am 5-ten Oktober 2001 machte mir Brutus ein schönes Geburtstagsgeschenk. Es berechnete die erste Stellung. Ein derartig komplexes Projekt kann und soll man aber nicht alleine machen. In diesem ersten Jahr leistete GM Genadij Timoscenko wertvolle Arbeiten für die Gestaltung der Bewertungsfunktion. Mit dem Dark-Thought Programmierer Ernst Heinz diskutierte ich viele Aspekte des Programmdesigns. Ohne diese beiden Geburtshelfer hätte ich dieses kritische erste Jahr wohl nicht durchgehalten. Nach diesem ersten Pieps konnte ich auch den altgedienten Nimzo-Mitarbeiter Alex Kure für das Projekt gewinnen. Alex war von Beginn an mein Wunschkandidat gewesen, er wollte sich aber zunächst die Sache - neben seinem normalen Job - nicht antun. Aber nach dem ersten Brutus-Lebenszeichen hat es ihn einfach gepackt. Alex ist ein guter Schachspieler, der Computerschach-Eröffnungsspezialist und gelernter Programmierer. Er konnte damit Teile der Software-Programmierung übernehmen. Am wichtigsten ist jedoch: Alex kann sich in die Gedankenwelt eines Programmierers hinein versetzen, versteht dessen Sprache. Dies war das Hauptproblem bei der Zusammenarbeit mit GM Timoscenko. Timoscenko betrachtete das Problem aus der Sicht und in der Sprache eines Schachspielers, ich aus der Sicht eines Programmierers. Es ist nicht leicht ein gemeinsames Projektbild zu entwickeln.

Im Jänner 2002 konnten wir mit Brutus die ersten Testpartien durchführen. Nachdem diese für ein gänzlich neues Programm gar nicht so übel waren, nahmen wir im Februar 2002 am traditionellen Paderborner Computerschachturnier teil. Die Ausbeute von 50% entsprach unseren Erwartungen.

Die Programmierbarkeit der FPGA ist für Schach eine feine Sache. Diese Flexibilität ist aber nicht gratis. FPGAs sind langsamer wie fest-verdrahtete Hardware. Brutus läuft auf der FPGA mit 30 MHz, eine Stellung wird innerhalb von 9 Takten berechnet. Oder anders ausgedrückt, die FPGA berechnet ca. 3.3 Millionen Stellungen/Sekunde. Nachdem auch die PC-Seite Berechnungen ausführen muss und auch die Kommunikation über den PCI-Bus Zeit verbraucht, sind es unter dem Strich etwas mehr als 2.5 Millionen Stellungen/Sekunde. Das liegt - trotz FPGA - einiges über den Deep Blue II Zahlen. Die PC-Welt ist aber seit den Deep-Blue Zeiten nicht still gestanden. Intel und AMD holen mit gigantischem Hardware- und Entwicklungsaufwand Erstaunliches aus dem vollkommen vermurksten 0x88 Design heraus.

Es war uns daher von Anfang an bewusst, dass wir mit Geschwindigkeit allein Fritz&Co nicht weit abhängen können. Der entscheidende Vorteil der FPGA ist die Möglichkeit, mehr Wissen ohne Verlust an taktischer Stärke einbauen zu können. Zusätzliches Wissen kostet in FPGAs fast keine zusätzliche Zeit, es kostet aber zusätzliche Ressourcen. Das Ganze wird eine Frage des Geldes. Nach Paderborn 2002 war klar, dass die bisher verwendeten XiLinx-Virtex-400 Chips etwas zu klein sind. Graham Smart griff in seine Schatzkiste und spendierte uns rund 2.5 Mal so leistungsfähige Virtex-1000 Chips. Im April und Mai 2002 verdoppelte sich der Programmumfang von Brutus. Wir bauten alles ein was wir schon immer gern in ein Schachprogramm an Wissen eingebaut hätten. Dies war ein Kampf gegen die Zeit. Anfang Juli fand bereits der nächste wichtige Test statt: Die Computerschach-WM 2002 in Maastricht. Wir hatten plötzlich das Deep-Blue Problem. Die vielen Bewertungsterme müssen aufeinander abgestimmt werden. Das Deep-Blue Team kämpfte damit jahrelang. Wir konnten das Problem innerhalb eines Monats natürlich auch nicht lösen. So manche Kante hätte am Programm noch weggefeilt gehört. Angesichts dessen spielte das Programm sensationell. Es machte sehr viel Druck, scheute sich auch nicht vor positionellen Opfern. Graham Smart war extra nach Maastricht geflogen. Er versteht nicht sehr viel von (Computer-)schach. Er war aber sichtlich beeindruckt, dass wir meist die ersten waren, die siegreich vom Tisch aufstehen konnten.  Wir spielten zu unserem Erstauen um den WM-Titel mit. In der entscheidenden Partie gegen Junior errang Brutus ebenfalls die Initiative. Junior befreite sich aber mit einem sehr schönen Qualitätsopfer und behielt - diesmal noch - die Oberhand für sich. Ein Platz auf dem Stockerl ging sich trotzdem aus. Mit einem halben Punkt hinter den punktgleichen Junior und Shredder errang Brutus die Bronzemedaille.

Seit der WM haben Alex und ich weiter fleißig an Brutus gefeilt und gehobelt. Es wurden zahlreiche Detailverbesserungen eingebaut. Inzwischen haben wir ein sehr ernstes Luxusproblem. Auf unseren Test-PCs (2.4 GHz Pentium) ist Brutus wesentlich besser als Fritz&Co. Wir müssen den anderen Programmen ein Zeithandicap von etwa 30 zu 90sek./Zug geben, damit die Partien halbwegs ausgeglichen verlaufen. Das erschwert die Testarbeit sehr. Auf einem 8-fach Server hat aber Deep-Fritz gegen Brutus noch immer die Nase vorn. Es ist daher notwendig ebenfalls eine parallele Version - Brutus P - zu machen. Das war uns auch von Anfang an klar. Nur muss man zuerst eine vernünftig spielende Single-Prozessor Version entwickeln, bevor man ein paralleles Monster bauen kann. Deep Blue verwendete beim historischen Sieg gegen Kasparov mehr als 200! Chips.

Im Nov. 2002 besuchte ich auf Einladung von Ulf Lorenz für einige Tage die Universität Paderborn, Abteilung Paralleles Rechnen. Die Abteilung hat auf dem Gebiet der Parallelen Programmierung ein weltweites Renommee. Die beiden massiv-parallelen Schachprogramme Zugzwang und P.ConNerS wurden in dieser Abteilung ausgebrütet. Beide Programme waren Pioniere auf dem Gebiet der Schach-Parallelisierung. Zugzwang war "so nebenbei" 1992 Vize-Weltmeister und P.ConNerS war ebenso "nebenbei" das erste Programm, welches
ein offizielles internationales Großmeisterturnier gewinnen konnte.
 

Wir beschlossen für Brutus-P an einem Strang zu ziehen. Die Universität Paderborn stellt weitere Hardware und vor allem ihr paralleles Know-How zur Verfügung. Ulf ist die parallele Hebamme, Alex und ich bringen die bisherige Brutus-Entwicklung ein und übernehmen auch die Detailarbeit. ChessBase ist weiterhin der Generalunternehmer.

Brutus P wird ein modular aufgebautes paralleles System. Im Gegensatz etwa zu Deep Fritz oder Deep Junior braucht man für einen 8-fach Brutus P keinen - sehr teuren - 8-Prozessor Server. Man kann z.B. 4 Duals oder auch 8 PCs zu einem Netzwerk zusammen schliessen. Das System ist - von der Logik her - beliebig nach oben ausbaubar. Alles was man braucht sind zusätzliche PCs und FPGA-Karten.

Im Moment (März 2003) liegt ein erster Brutus P Prototyp vor. Die Generalprobe ist das Lippstädter GM Turnier im August 2003. Die Premiere findet bei der Computerschach-WM 2003 in Graz statt. XiLinx hat bereits wesentlich kleinere und schnellere FPGAs angekündigt. Falls diese bis Nov. 2003 auf dem Markt sind, wird ein Brutus-Chip 5-6 Millionen Stellungen/Sek. berechnen. Nach unseren Plänen soll in Graz ein auf 3 oder 4 Duals laufender Brutus P6 bzw. P8 der Konkurrenz durch die Kombination von sehr tiefen Berechnungen und aggressiver Spielweise das Fürchten beibringen. Wenn die Vereinbarungen halten, soll der Grazer Weltmeister im Frühjahr 2004 gegen Kasparov antreten. In den Iden des März 2004 könnte sich daher Cäsar Kasparovs Schicksal endgültig entscheiden. Das Brutus Messer wird jedenfalls schon eifrig gewetzt.

Nach getaner Tat soll Brutus im Gegensatz zu Deep-Blue nicht eingemottet werden. Es soll sich jeder - gegen eine Handvoll Euro - einen oder auch mehrere Cäsarenmörder unter seinem Schreibtisch stellen können. Man steckt die Brutus-FPGA wie eine Sound- oder Videokarte in den PC, ladet unter der Fritz Oberfläche die Brutus Engine und los geht der Spaß.

Das ist die eigentliche Herausforderung an diesem Projekt. Wir sollen einen Ferrari bauen der allen davonfährt und den sich jeder leisten kann.

Voraussetzung dafür ist natürlich, dass alles so läuft, wie wir es uns vorstellen. Für den Dreizehnten von Graz wird niemand ein paar grüne Scheine locker machen. Ein bisschen muss auch Kanzler Schröder und seine Wirtschaftspolitik mitspielen. Solange der Hauptmarkt Deutschland ein ökonomisches Jammertal ist und keiner mehr Lust aufs Geldausgeben hat, wird sich ChessBase die Brutus-Produktion wohl zweimal überlegen. Lassen wir uns einfach überraschen wie es weiter geht.