Logo "blaue" Seiten

 
 
 
 
- Anzeige -
Für den Erwerb von Schachartikeln empfiehlt Ihnen der SC Leinzell den
 Schachversand Dreier 
 
 
Testen Sie Ihr Schach!
 
Diagramm 22-2006
 
Diagramm 22 – 2006
In dieser Stellung stellte Weiß seine Dame nach e5 und erwartete von Schwarz die Aufgabe. Dieser spielte aber weiter und zog …
 zur Lösung 
 
 
 
 
zur Startseite
 News | Sitekalender | Sitemap | Team | Kontakt 
Rochade-EuropaStefan Meyer-Kahlen
 
 
Die TableBases
von Stefan Meyer-Kahlen - November 1999
 
 
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. Ich kann mich allerdings an keinen Artikel erinnern, in dem beschrieben sind, was Tablebases eigentlich sind. Ich möchte dies hiermit nachholen und jedem Interessierten 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, dass 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 Fleiß 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, dass 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 Dreisteiner. 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 x 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 Viersteiner, 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 drei Figuren.
 
 
Die Fünfsteiner
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ässt sich, wenn auch schon deutlich schwieriger, fast immer ohne Hilfe von Datenbanken gewinnen. Richtig interessant wird es erst mit fünf 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.
 
Wie viel 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. 6 GB, also zehn 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 Fünfsteinern Schluss ist, der benötigte Speicherplatz wird einfach zu groß, um alle Stellungen abzuspeichern. Es gibt zwar bereits einige Sechssteiner als Endspieldatenbanken, bis es jedoch so weit sein wird, dass wir alle möglichen Kombinationen mit sechs Figuren als Tablebases vorliegen haben und jeder sie auf seinem Rechner verwenden kann, wird wohl noch einige Zeit vergehen.
 
 
Ausanalysiertes Schachspiel?
Man kann nun natürlich den Gedanken weiter spinnen und sich fragen, wann es denn soweit sein wird, dass wir alle 32-Steiner komplett erfasst 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, wie viele 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ößer 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, muss 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 ist, das Universum als ein endliches Gebilde zu betrachten. 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.
 
 
Bezugsquellen der TableBases
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 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 Fünfsteiner 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, nonstop! Ü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 Fünfsteiner 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 Dreisteiner. Dies ging wirklich sehr, sehr schnell über die Bühne, so dass als nächstes schon die Viersteiner anstanden. Hier dauerte es schon zwei 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 musste her, also kaufte ich einen weiteren 128 MB 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 Fünfsteiner 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.
 
 
Wunderwaffe TableBases
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. 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 bewusst. 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 fünf oder weniger Figuren trifft, die es zu bewerten gilt.
 
Wenn man dann jedes Mal 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 dass am Ende die Vorteile der Endspieldatenbanken bei weitem überwiegen.
 
Heute ist es übrigens deutlich einfacher, an die begehrten Tablebases zu kommen. Alle Viersteiner werden unter anderem mit Shredder 5 ausgeliefert und auch für die Fünfsteiner 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, dass die Festplattengrößen erst in letzter Zeit auf ein Maß gewachsen sind, bei dem es Sinn macht, sie einzusetzen. Auf der anderen Seite muss man auch sagen, dass Endspieldatenbanken schon ein alter Hut sind und es sie schon sehr lange gibt.
 
Die bisherigen Formate waren allerdings entweder so, dass 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 dann 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 WM in Paderborn aufzeigen, bei denen der Vorteil und die Stärke der Endspieldatenbanken klar zum Vorschein gekommen ist. In der ersten Partie wird deutlich, dass 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
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+ gxf6 29.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
 
Mit seinem nächsten Zug kündigt Shredder ein Matt in 31 Zügen an! Ohne Hilfe der Endspieldatenbanken wäre dies natürlich völlig unmöglich. Es entsteht ein Endspiel KLL-KS, das u.U. 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, dass 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, 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
 
In dieser Stellung gegeben die beiden anwesenden GM Boris Altermann und Thomas Luther dem Schwarzen keine Chance mehr. Für beide ist klar, dass Weiß 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 Analyse dann gezeigt hat. 67.Ta8 Tf7 68.Ke3 Te7 69.Tb8 Kg6 70.Tb6+ Kf5 und ½-½
 
 
Fazit
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, um das Endspielverhalten eines Schachprogramms in einigen Stellungen deutlich zu verbessern. Dies haben die meisten Programmierer von Schachprogrammen nun auch erkannt. Viele neue Programme, natürlich auch Shredder 4, unterstützen nun das neue Tablebases-Format.
 
Stefan Meyer-Kahlen – www.shredderchess.de
 
zum Seitenanfang zurück |