Auch bekannt als Transpositionstabellen für den Fachbegriff im Computerschach. Man wird es kaum glauben, aber die Historie dieser Programmiertechnik reicht bis in die Siebziger Jahre zurück. Zwischen 1972 und 1979 wurde mit dem Großrechner Belle, welcher auf spezieller Hardware seine Berechnungen durchführte, ein besonderes Projekt ins Leben gerufen. Und dem will ich hier Beachtung schenken.
In der offenen amerikanischen Schachmeisterschaft 1983 erzielte Belle eine beachtliche Turnierleistung von 2363 Elo. Für die damalige Zeit war das ein Meilenstein. Auch nicht unbedingt von der Hand zu weisen, das es das Einläuten einer neuen Ära war. Denn von da an wurden die ersten Homecomputer populär. Dedizierte Schachcomputer eroberten den Markt parallel zu den ersten Softwareprodukten für Apple, Atari und IBM-Computer.
Die Hashtables, häufig auch Endspieltabellen benannt, fanden erst später, in der zweiten Hälfte der Achtziger Einzug in die Computer von Mephisto und Fidelity. Soweit ich mich entsinne, folgte Novag mit der Implementierung erst etwas später nach.
Natürlich können die Tables, abgekürzt, bereits im Mittelspiel des Schachs zum Einsatz kommen, aber da sind noch viele Figuren auf dem Brett und die Zugmöglichkeiten sind noch eingegrenzter. Die Zahl infrage kommender Varianten, die tatsächlich sinnvoll das Spiel weiterentwickeln, sind hier noch überschaubarer und der ein oder andere Halbzug tiefergerechnet, bringt hier selten einen brachialen Vorteil. Selbst dann, wenn die Tables einzelne Suchbäume nochmal etwas tiefer abgreifen. Denn in diesem Abschnitt führen meist mehrere Spielzüge zu einem potentiell gutem Ergebnis.
Im Endspiel sieht das anders aus. Der aktiven Figuren sind weit weniger geworden, dafür hat sich ihr Radius allerdings erweitert. Erheblich spürbar macht sich das in dem Sinne, das jede Figur an Bedeutung gewinnt und die Gewichtung variiert. Jeder Fehlgriff lässt in diesem Abschnitt den Spieler schneller verlieren. Einzige Gewinnzüge sind dann keine Seltenheit mehr und machen das Spiel nicht nur komplizierter, sondern erschweren einem Programm bei der Suche nach dem richtigen Zug, massiv den Gewinnweg. Konkretes Endspielwissen hilft da natürlich weiter. Jedoch haben diesen Ansatz, nicht zuletzt wegen damals knapper Hardware-Ressourcen, nur wenige Programmierer gut hinbekommen.
Ein Paradoxon übrigens. Je leerer das Brett, desto komplexer die Zugauswahl.
Ja, richtig gelesen. Nicht umsonst füllen Software-Datenbanken mehrere Terabyte an Speicherplatz, nur um lediglich den Ausgang zu errechnen, den ein Spiel nimmt, wenn ausschließlich gerade mal noch 7 Steine (Figuren) das Schachbrett bevölkern.
Sind es mehr Figuren, die auf dem Brett spielen, sind die Kapazitäten für die Berechnung noch nicht ausreichend vorhanden. Die Lösungswege werden dann rechnerisch entdeckt oder es entsteht kein optimales Spiel, rein theoretisch formuliert. Sobald ein Programm jedoch auf die Tablebases (Datenbanken) Zugriff hat, spielt es somit technisch perfektes Schach.
Ist das aber nicht der Fall, so kommen die Hashtables wirkungsvoll ins Spiel.
Die Partie aus dem Jahre 1901 (Chicago Tribune) kann uns das verdeutlichen. Gerade 120 Jahre alt, aber lehrreich.
Gespielt von E. Lasker gegen G. Reichhelm
Folgende Stellung in Kurznotation:
Weiß: Ka1, ba4, bd4, bd5, bf4
Schwarz: Ka7, ba5, bd6, bf5
Weiß am Zug gewinnt.
Hier ist eine Festung beiderseits entstanden. Zugmöglichkeit besteht nur für die beiden Könige auf dem Brett. Die Bauernstruktur ist undurchlässig.
Belle hatte einen Megabyte Speicher dafür reserviert und fand den Schlüsselzug Kb1! innerhalb einer Sekunde.
Die Hashtables erinnern sich an wiederkehrende Stellungen, die abgespeichert werden. Der Suchbaum produziert mit den Königszügen unzählige wiederkehrende Positionen. Ohne Endspielalgorithmen müssten hier teilweise 25 Halbzüge Brute Force gerechnet werden. Als Rechenaufwand zu immens für ein herkömmliches Programm der damaligen Zeit. Das gilt auch für die Ära der Schachcomputer sogar zwei Jahrzehnte danach.
Diese Technik des Programmierens spart Rechenzeit ein. Falls die Baumsuche zweimal auf die gleiche Stellung stößt, greift es auf die gespeicherte Bewertung zurück. Ähnlich dem Prinzip abgelegter Markierungspunkte in einem Labyrinth.
Im vorgelegten Fall haben wir 9 Steine auf dem Schachbrett. Für die Tablebases existiert noch kein Lösungsweg im absoluten Sinn. Pures Wissen dürfte wohl für diesen Fall kaum zu implementieren sein. Höchstens menschliche Intuition führt hier ans Ziel. KI-Software sehe ich als den einzigen Ansatz, davon unabhängig, dieses vorliegende Schach-Problem ohne Zugriff auf Hashtables effektiv zu lösen.
Das Schachprogramm ist also nicht intelligent genug um zum Ergebnis zu kommen. Also, wie gehen die Endspieltabellen hier weiter vor? Sie untersuchen auch Kb2 oder Ka2 und sehen , das der Gewinnweg ausbleibt, füllen allerdings die Tabellen mit Bewertungen. Auch werden gegnerische Fehlzüge geprüft und die Schlüsselstellung untersucht, die den Gewinn von Weiß ermöglicht. Wenn Kb1 durchgerechnet wird, geht es daher nur bis zu jener Schlüsselposition. Der Bauerngewinn muss nicht zwingend errechnet werden.
In den quer-Vernetzungen der Suchbäume entstehen da unglaubliche Dynamiken. Denn von der gespeicherten Markierung kann die vertiefte virtuelle Suche, erzeugt durch die Hashtables, viel tiefer liegend gehen.
Jener Zweig im Suchbaum, in irgendeiner Verästelung kann dann selbst gepunktet und weiter verfolgt werden. Die Potenzierungen addieren sich. Im allgemeinen hängt die Qualität des Zuges von der Bewertung ab, die als Priorität eingestuft wurde. Insofern es keine absolute Lösung gibt, entscheiden diese Kriterien über die Spielstärke des Programms.
In unserem Fall ist das Resultat jedoch eindeutig zu erkennen. So geht es einfach darum, inwieweit uns die Endspieltabellen helfen können, grundsätzlich den Weg zum Gewinn einer Partie zu finden. Ist es aufgrund der Prozessorleistung maximal gegeben, eine Suchtiefe von 9 oder 10 Halbzügen zu erreichen, kann die Software durch den Einsatz der gerade besprochenen Hashtables, 27 oder gar 30 Halbzüge in seinen Spitzen generieren.