In letzter Zeit wird sehr viel über Tablebases gesprochen: Welches Programm sie benutzen kann und welches nicht, was sie bringen, wo man sie kaufen kann usw.. Ich kann mich allerdings an keinen Artikel erinnern, in dem beschrieben sind, was Tablebases eigentlich sind. Ich möchte dies hiermit nachholen und jedem diese sehr nützliche Erfindung näher bringen.
Bei den Tablebases handelt es sich im Prinzip um eine sehr große Datenbank, in der alle möglichen Schachpositionen gespeichert sind. Zusammen mit der Position wird auch noch ein Wert gespeichert, der besagt, ob die Stellung gewonnen, verloren oder Remis ist. Damit ist nicht gemeint, dass dort steht, die Stellung ist “wahrscheinlich Remis” oder aber “eventuell zu gewinnen”, sondern es wird sogar die exakte Zuganzahl bis zum Matt angegeben, wenn die Stellung nicht remis ist. Steht in der Datenbank: “Gewonnen in 13 Zügen”, dann kann also auch der beste Schachspieler es nicht mehr schaffen, diese Stellung Remis zu halten. Ebenso kann niemand eine Stellung mehr gewinnen, wenn in der Datenbank steht, das der Stellungswert Remis ist. Diese Aussagen gelten natürlich nicht, wenn eine Seite nicht über die Informationen aus den Datenbanken verfügt. Dann ist es durchaus möglich und passiert sogar recht häufig, daß eine theoretisch gewonnene Stellung noch zu einem Remis wird. Wenn ein Spieler oder aber auch ein Schachprogramm die Tablebases befragen kann, während er oder es am Zug ist, dann gibt es kein entrinnen mehr: Das Spiel wird perfekt bis zum Matt fortgesetzt.
Nun kommt natürlich die Frage auf, warum so viele Schachspieler so viel Zeit und Fleiss in die Analyse einer Stellung stecken und warum es Leute wie mich gibt, die versuchen, einer Maschine das Schachspielen beizubringen wenn doch alles so einfach ist. Einfach in die Datenbank gucken und schon weiß man, welche Seite gewinnen wird oder ob es vielleicht doch ein Remis gibt. Dies ist theoretisch natürlich möglich, doch der Haken an der Sache ist, daß diese Datenbanken sehr, sehr groß sind und dass man auch unglaublich viel Zeit braucht, um sie zu erstellen.
Nehmen wir zum Beispiel einmal alle Schachstellungen mit je einem König und einer weiteren Figur. Es gibt drei Figuren oder Steine auf dem Brett, man spricht auch von einem 3-Steiner. Um diese Datenbank komplett abzuspeichern braucht man ca. 62 KB. Das ist sicher nicht mehr sehr viel, wenn man weiß, dass heute selbst die billigsten Rechner mit Festplatten mit einer Kapazität von 8 GB verkauft werden (1 GB = 1024 MB = 1024*1024 KB). Ich kann mich aber noch sehr gut an meinen ersten Computer erinnern: Der hatte 64 KB Speicher, darin war aber auch schon das gesamte Betriebssystem enthalten, so ändern sich die Zeiten. Gehen wir einen Schritt weiter und betrachten die 4-Steiner, jede Seite hat also nur noch den König und eine weitere Figur. Um diese Datenbank komplett auf der Festplatte zu speichern, braucht man 30320 KB oder ca. 30 MB, immer noch nicht sehr viel aber schon deutlich mehr als bei nur 3 Figuren.
Für viele dieser Stellungen ist der Ausgang der Partie allerdings auch ohne Endspieldatenbanken klar, so kann jeder Spieler, der das absolute Anfängerstadium hinter sich gebracht hat, mit König und Dame Matt setzen, und auch das Endspiel Dame gegen Turm läßt sich, wenn auch schon deutlich schwieriger, fast immer ohne Hilfe von Datenbanken gewinnen. Richtig interessant wird es erst mit 5 Figuren. Hier gibt es einige Beispiele, bei denen es schon sehr schwierig sein kann, die Stellung korrekt zu bewerten. Als Beispiel nenne ich nur KTB-KT oder KDB-KD, die in der normalen Turnierpraxis recht häufig vorkommen. Hier kann die Seite mit Materialvorteil nicht unbedingt immer gewinnen, und wenn die Stellung zu gewinnen ist, dann ist es zum Teil sehr schwierig und erfordert oft sehr genaue Zügen, um den Vorteil in einen Sieg umzuwandeln. Wieviel Platz auf der Festplatte benötigt man nun für alle Tablebases, die alle möglichen Kombinationen von fünf Figuren enthalten? Es sind ca. 6054466 KB = ca. 6000 MB = ca. 6GB, also 10 prall gefüllte CD-ROMs! Es wird deutlich, dass der benötigte Speicherplatz explosionsartig zunimmt, wenn man die Datenbanken mit auch nur einer Figur mehr betrachten will. Dies ist auch der Grund, warum heute bei 5-Steinern schluss ist, der benötigte Speicherplatz wird einfach zu groß, um alle Stellungen abzuspeichern. Es gibt zwar bereits einige 6-Steiner als Endspieldatenbanken, bis es jedoch so weit sein wird, dass wir alle möglichen Kombinationen mit 6 Figuren als Tablebases vorliegen haben und jeder sie auf seinem Rechner verwenden kann, wird wohl noch einige Zeit vergehen.
Man kann nun natürlich den Gedanken weiter spinnen und sich fragen, wann es denn endlich soweit sein wird, dass wir alle 32-Steiner komplett erfaßt haben. Dies würde dann natürlich bedeuten, dass Schach gelöst sein wird, wie man es in der Informatik im Bereich der Spieltheorie so schön nennt. Man könnte dann für jede beliebige Schachstellung sagen, ob sie Remis ist oder ob eine Seite gewinnt und wenn ja, wieviele Züge es noch bis zum Matt sind. Insbesondere weiß man dann natürlich auch, ob Weiß seinen Anzugsvorteil in der Grundstellung zwingend ausnutzen kann, ob es bei perfektem Spiel von beiden Seiten immer ein Remis gibt oder ob der Anzugsvorteils vielleicht doch ein Nachteil ist und Schwarz schon in der Grundstellung einen entscheidenden Vorteil hat.
Über diesen Punkt lässt sich wirklich vortrefflich streiten und diskutieren, dabei kann man auch sehr leicht in philosophische Diskussionen abdriften. Das Problem ist nämlich, dass die Anzahl der möglichen Stellungen beim Schachspiel grösser ist, also die Anzahl der Atome im bekannten Universum. Mit heutigem Wissen ist es also nicht möglich, alle Stellungen zu speichern. Auf die Frage, wie man alle Stellungen überhaupt bewerten kann, muß man also bei dieser Argumentationsweise gar nicht erst eingehen. Sinnvolle Ansatzpunkte für eine Diskussion wären nun natürlich die Fragen, ob man die Anzahl der Atome im Universum überhaupt kennt, wie man alle Schachstellungen vielleicht effizienter codieren kann und ob es vermessen der Menschenheit ist, das Universum als ein endliches Gebilde zu betrachten. Sehr schnell landet man dann auch bei “Paralleluniversen” sowie bei “Schwarzen Löchern”. Wie sie sehen, bietet dieser Punkt reichlich diskussionspotenzial, mit dem man leicht über den Rahmen dieses Artikels hinausgehen kann.
Es ist übrigens nichts ungewöhnliches, das ein Spiel gelöst wird, d.h. komplett berechnet worden ist. Dies ist schon vor einiger Zeit bei den im Vergleich zum Schach sehr einfachen Spielen “Vier gewinnt” und “Mühle” passiert. Bei “Vier gewinnt” kann der Anziehende immer den Gewinn erzwingen, “Mühle” ist bei fehlerfreiem Spiel beider Seiten immer Remis.
Widmen wir uns nun also der Frage, wie man die heute praktikablen Tablebases bekommen kann. Hier gibt es grundsätzlich zwei Möglichkeiten. Entweder man besorgt sie sich in fertiger Form oder man generiert sie auf seinem eigenen Computer. Beides hat seine Tücken. Im Internet gibt es einige Seiten, auf denen die kompletten Tablebases zum Herunterladen für Jedermann angeboten werden, man wählt sich also in den entsprechenden Rechner ein und los geht es! Doch halt, machen wir einmal ein kleines Rechenbeispiel. Wie lange würde dies denn eigentlich dauern? 6 GB für alle 5-Steiner mit einem heute handelsüblichen V.90 Modem, das macht bei guter Leitung im optimalen Fall 6 GB bei 3500 KB/s = 1840700 Sekunden = ca. 30678 Minuten = ca. 551 Stunden = ca. 21 Tage = 3 Wochen, non stop! Über verstopfte Leitungen und abgebrochene Verbindungen will ich hier erst gar nicht reden. Jeder kann sich nun selber ausrechnen, wie sich diese Möglichkeit auf seine nächste und wahrscheinlich auch noch übernächste Telefonrechnung auswirken wird. Sie sehen, dies ist also nicht sehr empfehlenswert.
Genau diese Berechnungen habe ich im Frühjahr dieses Jahres auch angestellt, als ich mich entschlossen habe, Shredder bei der WM in Paderborn mit Unterstützung von Endspieldatenbanken antreten zu lassen. Was also tun? Schnell fand ich ein kleines Programm im Internet, mit dessen Hilfe man alle Tablebases auf seinem eigenen Rechner generieren kann. Es fand sich zwar ein kleiner Hinweis in der beigefügten Dokumentation, dass man für die 5-Steiner sehr viel Speicher und auch sehr viel Zeit brauchen würde, doch dachte ich mir, dass mein Rechner, ein PII-450 mit 128 MB RAM schon schnell genug sein wird. Guter Dinge machte ich mich zunächst an die Generierung der 3-Steiner. Dies ging wirklich sehr, sehr schnell über die Bühne, so daß als nächstes schon die 4-Steiner anstanden. Hier dauerte es schon 2 Stunden, bis ich alle Datenbanken komplett hatte, doch nun fingen meine Probleme erst richtig an. Ich begann mit KLL-KS und allen anderen Leichtfigurenendspielen. Für jedes dieser Endspiele dauerte es schon 1-2 Tage, bis es komplett generiert war und so langsam fing ich an, mein Vorhaben in Frage zu stellen. Neuer Speicher mußte her, also kauft ich bei meinem Computerhändler einen weiteren 128MB Speicherriegel, zum Glück zu damals noch sehr erschwinglichen Speicherpreisen. Doch auch mit nun 256 MB Speicher kam ich sehr schnell an die Grenzen meines Rechners. Ich konnte zwar einige weitere Endspiele berechnen, doch spätestens bei Endspielen, die mindestens einen Bauern enthielten war dann schluss. Ich beschloss, nach einem anderen Weg zu suchen, die Tablebases zu bekommen und tröstete mich damit, dass ich mit meinem neu erworbenen Speicher in Shredder nun viel größere Hashtabellen einstellen konnte.
Es blieb nur die Möglichkeit übrig, die Tablebases irgendwo fertig generiert zu kaufen. In Deutschland wurde ich leider nicht fündig, offiziell waren sie damals nirgendwo erhältlich. Ich fand jedoch einen computerschachbegeisterten Amerikaner, der sich doch tatsächlich alle 5-Steiner Datenbank mit seinem normalen Modem aus dem Internet geladen hatte. Nach eigenen Angaben hat er dafür 1,5 Monate im Dauerbetrieb benötigt, dies ist wahrscheinlich wirklich nur in Amerika möglich. Wir wurden uns schnell einig und er versprach, mir die CDs so schnell wie möglich zu brennen und zuzuschicken. Es dauerte dann wirklich auch nur ein paar Tage, bis ich das Paket im Briefkasten hatte.
Nach all den Mühen war ich natürlich sehr gespannt, was die neue Wunderwaffe bei Shredder bringen würde. Ich probierte ein paar Endspielstellungen mit wenig Figuren und, siehe da, die richtigen Lösungen wurden von Shredder mit Tablebases meistens deutlich früher gefunden also von Shredder ohne Tablebases. Schnell startete ich ein paar Testspiele, und auch hier zeigten sich zum Teil deutliche Verbesserungen. Unter anderem wurden Turmendspiele mit einem Mehrbauern meistens gewonnen und mit einem Bauern weniger meistens noch ins Remis gerettet. Ich war begeistert. Schnell wurde mir allerdings auch der Nachteil der Tablebases bewußt. Wegen ihrer Größe ist es nicht möglich, sie vollständig in den schnellen Arbeitsspeicher des Computers zu laden. Sie müssen auf der relativ langsamen Festplatte bleiben. Ein sehr wichtiger Faktor im Computerschach ist aber die Geschwindigkeit und Effizienz eines Programms. In Endspielen, vor allem mit wenig verbleibenden Figuren, kommt es aber sehr häufig vor, dass man im Suchbaum, zum Beispiel nach einer langen Abtauschfolge, auf eine Stellung mit 5 oder weniger Figuren trifft, die es zu bewerten gilt. Wenn man dann jedesmal auf die langsame Festplatte zugreift, wird das Programm ausgebremst und verliert sehr deutlich an Rechengeschwindigkeit, was dann fatale Folgen haben kann. Im schlimmsten Fall wird nur noch permanent auf die Festplatte zugegriffen und es bleibt keine Zeit, die wichtigen Varianten tief genug zu untersuchen. Auch dieses Problem kann man allerdings durch intelligente Algorithmen in den Griff bekommen, so daß am Ende die Vorteile der Endspieldatenbanken bei weitem überwiegen.
Heute ist es übrigens deutlich einfacher, an die begehrten Tablebases zu kommen. Alle 4-Steiner werden unter anderem mit auf der Shredder4-CD ausgeliefert und auch für die 5-Steiner gibt es inzwischen auch in Deutschland einige Bezugsquellen. Dies ist sicher mit Abstand die beste Möglichkeit, die Tablebases zu bekommen.
Sie werden sich vielleicht fragen, warum die Tablebases erst so spät aufgetaucht sind, wenn sie doch so nützlich sind. Ein Grund ist sicher, daß die Festplattengrößen erst in letzter Zeit auf ein Maß gewachsen sind, bei dem es Sinn macht, die Tablebases einzusetzten. Auf der anderen Seite muß man auch sagen, dass Endspieldatenbanken schon ein alter Hut sind und es sie schon sehr lange gibt. Die bisherigen Formate waren allerdings entweder so, daß man schnell auf die Datenbanken zugreifen konnte, sie aber sehr viel Platz auf der Festplatte benötigen (Edwards-Datenbanken), oder aber sie waren sehr gut komprimiert und der Zugriff dauerte dementsprechend sehr lange, so dass man sie nicht effizient in der Suche einsetzten konnte (Thompson-Datenbanken). Erst mit den neuen Nalimov-Datenbanken ist ein sehr guter großer Schritt getan worden. Sie werden durch einen sehr intelligenten und effizienten Komprimierungsalgorithmus auf eine erträgliche Größe gebracht und lassen auch noch einen sehr schnellen Zugriff zu.
Abschließend möchte ich noch zwei Beispiele aus der Praxis von der Computerschachweltmeisterschaft in Paderborn aufzeigen, bei denen der Vorteil und die Stärke der Endspieldatenbanken klar zum Vorschein gekommen ist.
In dieser Partie wird deutlich, daß auch schwer zu spielende Endspiele, die noch einige Remismöglichkeiten bieten, ohne Probleme gewonnen werden, wenn man die Hilfe von Endspieldatenbanken in Anspruch nehmen kann.
Shredder - Rebel [D23]
WCCC99 Paderborn (3), 15.06.1999
1.d4 d5 2.c4 c6 3.Sf3 Sf6 4.Dc2 dxc4 5.Dxc4 Lf5 6.g3 e6 7.Lg2 Sbd7 8.Sc3 Le7 9.0–0 0–0 10.Te1 Se4 11.e3 Te8 12.Sd2 Sd6 13.De2 e5 14.d5 cxd5 15.Sxd5 Tc8 16.e4 Le6 17.Sxe7+ Dxe7 18.b3 Tc2 19.La3 Tec8 20.Tec1 Txc1+ 21.Txc1 Txc1+ 22.Lxc1 Dd8 23.La3 Db6 24.Lf1 Sc5 25.Lb2 f6 26.De3 Scxe4 27.Sxe4 Dxe3 28.Sxf6+ gxf629.fxe3 Se4 30.Le2 Kf7 31.Ld3 Ld5 32.g4 Kg6 33.h4 f5 34.Le2 Kf6 35.g5+ Ke6 36.Kh2 a5 37.Kg1 a4 38.bxa4 Lxa2 39.a5 Ld5 40.La3 Sc3 41.Lh5 Lc6 42.g6 hxg6 43.Lxg6 Sd5 44.h5 Kf6 45.Lc5 Sc3 46.Kf1 Lf3 47.Lb6 Lg4 48.Ld8+ Kg7 49.Lc7 Kf6 50.Kg2 Sd5 51.Ld8+ Kg7 52.Kg3 Sxe3 53.Kh4 Sd5 54.Kg5 Lh3 55.h6+ Kg8 56.Le8 Sf4 57.Ld7 Lg4 58.Lc8 Kh7 59.Lc7 Sh3+ 60.Kf6 Sf2 61.Lxb7 Se4+ 62.Kxe5 Le2 63.a6 Lxa6
(Diagramm)
Mit seinem nächsten Zug kündigt Shredder ein Matt in 31 Zügen an! Dies wäre ohne Hilfe der Endspieldatenbanken natürlich völlig unmöglich. Es entsteht ein Endspiel KLL-KS, daß unter Umständen nur schwer innerhalb von 50 Zügen zu gewinnen ist. Mit Hilfe der Datenbanken jedoch kein Problem für Shredder, bereits hier wird der Weg bis zum Matt komplett angezeigt.
64.Lxa6 Kg6 65.h7 Kxh7 66.Kxf5 Sc5 67.Lc4 Sd7 68.Lb5 Sc5 69.Lb6 1–0
Die zweite Partie ist ein sehr schönes Beispiel dafür, daß Schachprogramme mit Hilfe von Endspieldatenbanken selbst Großmeistern in einigen Endspielstellungen deutlich überlegen sein können, obwohl das Endspiel sicher noch die Achillesferse der heutigen Schachprogramme ist.
Ferret - Shredder
WCCC99 Paderborn (6), 18.06.1999
1.e4 e5 2.Sf3 Sc6 3.Lc4 Lc5 4.b4 Lxb4 5.c3 La5 6.d4 exd4 7.0–0 Sge7 8.cxd4 d5 9.exd5 Sxd5 10.La3 Le6 11.Lb5 Lb4 12.Lxc6+ bxc6 13.Lxb4 Sxb4 14.Da4 Dd6 15.Sc3 Sd3 16.d5 Sc5 17.Dxc6+ Dxc6 18.dxc6 Ke7 19.Tfe1 Sd3 20.Te3 Sb4 21.Sd4 Thd8 22.Td1 Kf6 23.a3 Sd5 24.Se4+ Ke7 25.Tee1 Lg4 26.f3 Lc8 27.Sc5+ Kf6 28.Sb5 Le6 29.Sa6 Tac8 30.Sbxc7 h5 31.h3 h4 32.a4 Sxc7 33.Txd8 Txd8 34.Sxc7 Tc8 35.Sxe6 fxe6 36.Tc1 e5 37.Kf2 Ke6 38.g3 hxg3+ 39.Kxg3 Kd6 40.Td1+ Ke6 41.Td7 Txc6 42.Txg7 Tc3 43.Tg4 Kf5 44.h4 Tc1 45.h5 Tc6 46.Tg7 Ta6 47.Tg4 Tc6 48.Tg7 Ta6 49.Tg8 Tb6 50.Kh4 Tb4+ 51.Kg3 Tb6 52.Kh4 Tb4+ 53.Tg4 Tb2 54.Kg3 Tb6 55.a5Td6 56.Tg7 Ta6 57.Tg8 Td6 58.Kh4 Td4+ 59.Kg3 Td6 60.Tb8 Kg5 61.Te8 Td5 62.a6 Ta5 63.Te7 e4 64.Txa7 Ta3 65.Kf2 Txf3+ 66.Ke2 Kxh5
(Diagramm)
Von dieser Stellung an gegeben die beiden anwesenden Großmeister Boris Altermann und Thomas Luther dem Schwarzen keine Chance mehr. Für beide ist klar, dass Weiss dieses Endspiel leicht gewinnen kann. Beide Programme verfügen aber über die Tablebases und beide zeigen seelenruhig hier und im folgenden eine Remisbewertung an, völlig zu Recht, wie sich in der nachträglichen Analyse dann gezeigt hat.
67.Ta8 Tf7 68.Ke3 Te7 69.Tb8 Kg6 70.Tb6+ Kf5 ½–½
Was kann man nun als Fazit über die Tablebases sagen? Wenn man die wenigen Klippen bei der Implementierung umschifft, dann hat man ein sehr mächtiges Hilfsmittel zu Hand, mit dem man das Endspielverhalten eines Schachprogramms in einigen Stellungen deutlich verbessern kann. Dies haben die meisten Programmierer von Schachprogrammen nun auch erkannt. Viele neue Programme, natürlich auch Shredder4, unterstützen nun das neue Tablebases-Format.