Logo "blaue" Seiten

 
 
 
 
- Anzeige -
Für den Erwerb von Schachartikeln empfiehlt Ihnen der SC Leinzell den
 Schachversand Dreier 
 
 
Testen Sie Ihr Schach!
 
Diagramm 17-2006
 
Diagramm 17 – 2006
In dieser Stellung verspeiste Weiß ohne Argwohn den Bauern auf e5. Dieser war jedoch vergiftet. Was hatte Weiß übersehen?
 zur Lösung 
 
 
 
 
zur Startseite
 News | Sitekalender | Sitemap | Team | Kontakt 
Rochade-EuropaStefan Meyer-Kahlen
 
 
Was sind eigentlich - HashTabellen?
von Stefan Meyer-Kahlen - April 2000
 
 
Jedes heutige Schachprogramm benutzt Hashtabellen. Jeder der sich mit Computerschach beschäftigt, hat sicher schon einmal davon gehört. Ich bin aber nicht sicher, ob jeder weiß, was es damit eigentlich genau auf sich hat.
 
Im Grunde sind die Hashtabellen schon wieder ein alter Hut im Computerschach. Schon die legendären Großrechnerprogramme in den Urzeiten des Computerschachs benutzten sie, und auch für die heutigen PC-Programme sind sie eine Selbstverständlichkeit. Ich kann mich allerdings noch gut daran erinnern, wie die Hashtabellen damals bei den kleinen Mikrocomputern mit großem Tamtam eingeführt worden sind. Wie bei jeder Neuerung, die etwas auf sich hält, versprach man sich und vor allem natürlich den Käufern und Anwendern, den großen Durchbruch im Computerschach. Waren sie das nun wirklich?
 
 
Die Bedeutung von HashTabellen
Hashtabellen werden nicht nur im Computerschach, sondern auch bei vielen anderen Softwareanwendungen, verwendet. Es handelt sich um ein Standardverfahren der Informatik, über das es unzählige Veröffentlichungen und bekannte Algorithmen gibt, doch wollen wir uns hier auf ihre Anwendung im Computerschach konzentrieren.
 
Schauen wir uns dazu zunächst einmal an, wie man die Hashtabellen des Computerschachs im deutschen Sprachgebrauch bezeichnet: man spricht von "Zugumstellungstabellen". Dieses konstruierte Wort ist sicher besser dazu geeignet, sich etwas sinnvolles darunter vorzustellen. Es beschreibt den Sinn der Hashtabellen schon recht gut, doch um wirklich verstehen zu können, was es damit auf sich hat, muss ich noch kurz genauer auf die Funktionsweise eines Schachprogramms eingehen.
 
Jedes heute kommerziell erhältliche Schachprogramm funktioniert nach dem gleichen Prinzip: alle Zugmöglichkeiten werden der Reihe nach ausprobiert, der beste dabei ermittelte Zug wird dann ausgespielt. Natürlich ist dies nicht ganz richtig, da die große Kunst im Computerschach darin besteht, rechtzeitig zu erkennen, welche Zugmöglichkeiten sinnlos sind und deren Untersuchung möglichst schnell abzubrechen, sowie die sinnvollen Varianten genauer und vertieft zu betrachten.
 
Trotzdem wird auch noch bei den heutigen Spitzenprogramm 99.99% der Zeit damit verbracht, völlig sinnlose Zugfolgen zu untersuchen, denen ein Mensch sofort ansieht, dass sie so nie und nimmer auf das Brett kommen werden. Es ist deshalb sicher nicht völlig falsch vereinfachend anzunehmen, dass wirklich alle Varianten untersucht werden. Wenn man sich kurz darüber Gedanken macht und sich fragt, wie gut die Schachprogramme denn spielen können, wenn sie nicht ein Großteil ihrer Zeit so sinnlos verschwenden würden, dann ist dies sicher eine mehr als berechtigte Schlussfolgerung.
 
Auf der anderen Seite ist die Stärke der Computer nun einmal deren Rechengeschwindigkeit und es hat sich im Laufe der Jahre gezeigt, dass es besser ist, einen Großteil seiner Zeit mit der Bewertung von sinnlosen Stellungen und Zugfolgen zu verbringen, als von vornherein zu versuchen, nur die sinnvollen Züge zu selektieren. Computer spielen eben anders Schach als Menschen, sie wissen erst dann, dass etwas schlecht ist, wenn sie es selbst ausprobiert haben.
 
  Nun aber zurück zu unserem Thema. Schauen wir uns einmal in der Grundstellung die Zugfolgen
 
1.Sf3 Sf6 2.Sc3 Sc6,
1.Sc3 Sc6 2.Sf3 Sf6,
1.Sf3 Sc6 2.Sc3 Sf6 und
1.Sc3 Sf6 2.Sf3 Sc6 an.
 
Jeder Schachspieler und sicher auch jeder Nichtschachspieler wird schnell feststellen, dass die entstandene Stellung nach den vier obigen Zugfolgen völlig identisch ist. Wie wir aber bereits gelernt haben, sind Schachprogramme nicht annähernd so klug, wie man vermuten könnte, deshalb überrascht es hoffentlich niemanden mehr, wenn ich sage, dass für ein Programm die obigen Zugfolgen erst einmal völlig verschieden sind und sie bei der Abarbeitung aller Zugmöglichkeiten jede dieser Zugfolgen getrennt bewerten. Sie machen also hier das vierfache der eigentlich notwendigen Arbeit!
 
Diesen äußerst unbefriedigenden Zustand haben Programmieren von Schachprogrammen schon sehr früh entdeckt und sich auch natürlich daran gestört. Sie sannen nach Abhilfe und fanden eine Lösung für dieses Problem mit Hilfe der Hashtabellen. Hashtabellen im Computerschach sind also primär dazu da, solche Zugumstellungen zu erkennen, indem man die bereits untersuchten Stellungen abspeichert, und durch deren nur einfache Abarbeitung Zeit zu sparen. Daher auch der deutsche Name Zugumstellungstabellen.
 
 
Die Verwaltung der HashTabellen
Ganz so einfach ist die Sache allerdings nun auch wieder nicht. Es bleiben noch zwei Probleme zu lösen. Der Arbeitsspeicher der heutigen Computer ist schon sehr, sehr groß, allerdings bei weitem nicht groß genug, um alle auftretenden Stellungen abzuspeichern, um sie bei Bedarf wieder abrufen zu können. Außerdem gibt es Hashtabellen ja schon sehr lange, auch als Arbeitsspeicher noch sehr knapp und teuer war. Wie schafft man es also trotzdem, solche Zugumstellungen wie oben zu erkennen?
 
Das nächste Problem ist dann, wie man sie sehr schnell und effizient erkennen kann, denn wenn dies zu lange dauern würde, dann wäre es doch besser, alle Möglichkeiten getrennt auszuprobieren. Zum Glück gibt es für diese Probleme in der Informatik Standardverfahren, hier eben Hashtabellen. Der Trick ist der, dass man einer Stellung zunächst eine Codezahl zuordnet, mir deren Hilfe man dann sehr schnell erkennen kann, ob diese Stellung später noch einmal auftritt. In meinem Schachprogramm Shredder 5 wird der Grundstellung zu Beispiel die 64-Bit-Zahl 0x7623EEBC5FD42FDA zugeordnet.
 
Ein Mensch kann damit sicher nicht sehr viel anfangen, doch für einen Computer ist dies alles kein Problem, er kann in Bruchteilen von Sekunden Tausende solcher Zahlen miteinander vergleichen. Auch für das zweite Problem der Effizienz gibt es natürlich eine Lösung, deren ausführliche Beschreibung hier allerdings deutlich zu weit führen würde. Es genügt zu wissen, dass es sehr schnell möglich ist, aus einer gegebenen Stellung eine Zahl wie die obige zu berechnen.
 
 
Die Praxis
Wie geht man als Schachprogrammieren nun vor? Nun, für jede Stellung, die man untersucht hat, speichert man den Wert dieser Stellung zusammen mit dem Code dieser Stellung in den Hashtabellen ab. Vor jeder neuen zu untersuchenden Stellung schaut man einfach in den Hashtabellen nach, ob diese Stellung schon einmal bewertet worden ist und wenn ja, dann nimmt man einfach den abgespeichert Wert und ist sofort fertig. Das ist im Prinzip alles, aber leider gibt es immer noch zwei Probleme zu beachten.
 
Wir wissen, dass es mehr Stellungen gibt, als in den Arbeitsspeicher hineinpassen und auch weit mehr Stellungen, als man mit 64-Bit-Zahlen darstellen kann. Was passiert also wenn der zur Verfügung stehende Arbeitsspeicher voll ist oder zwei verschiedene Stellungen auf die gleiche Zahl abgebildet werden? Letzteres passiert zwangsläufig irgendwann einmal, da es ja viel mehr verschieden Stellungen als Codezahlen gibt.
 
Das erste Problem lässt sich ziemlich leicht lösen. Wenn der Speicher voll ist, dann muss man eben einen Eintrag löschen, um wieder Platz zu schaffen. Dabei geht man natürlich so vor, dass man einen Eintrag löscht, der höchstwahrscheinlich nicht mehr benötigt wird. Wenn man sich dabei allerdings vertut und der eben gelöschte Eintrag später noch einmal benötigt wird, dann muss man ihn erneut berechnen und kann nicht mehr einfach dessen Wert auslesen. Alles kann man eben nicht haben.
 
Das zweite Problem ist da zunächst schon schwieriger. Wenn man nämlich nur die beiden Codezahlen hat, und diese identisch sind, dann kann man nicht mit hundertprozentiger Sicherheit sagen, ob die beiden zugrundeliegenden Stellungen es auch sind, d.h., man ist nicht wirklich sicher, ob die gerade untersuchte Stellung wirklich vorher schon einmal untersucht worden ist, wenn man die gleiche Codezahl in den Hashtabellen findet.
 
Wenn zwei verschiedene Stellungen auf die gleiche Codezahl abgebildet werden, dann spricht man von einer Hashkollision. Hashkollisionen hören sich wild an, sie sind es aber eigentlich gar nicht. Wenn man nämlich die Funktion, die einer gegebenen Schachstellung eine Codezahl zuordnet, geschickt wählt, dann können Hashkollisionen schon fast ausgeschossen werden. Allerdings nur fast, denn ein gewisses Restrisiko bleibt trotzdem. Wenn eine Hashkollision dann wirklich auftritt, dann ist sie auch fast immer harmlos, denn die Wahrscheinlichkeit, dass sie in einer unwichtigen Variante auftritt ist sehr, sehr groß. Wie wir wissen, sind schließlich 99.99% aller Varianten, die ein Schachprogramm berechnet, unwichtig.
 
Tritt eine Kollision allerdings in einer wichtigen und sinnvollen Variante auf, dann kann es schon Probleme geben. Stellen sie sich vor, sie Wissen dass eine Stellung mit einer Dame und einem Turm mehr sehr, sehr gut ist und plötzlich übernehmen sie diesen Wert einfach für eine völlig andere Stellung, in der womöglich noch die andere Seite einen Springer mehr hat.
 
Falls sie jetzt denken, dass das Spiel eines Schachprogramms eine reines Zufallsprodukt ist und nur mit großem Glück und ohne dadurch Kollisionen zu vernünftigen Ergebnissen führen kann, dann kann ich sie hier beruhigen, in meiner Laufbahn als Schachprogrammierer ist mir bis jetzt noch keine Hashkollision bewusst untergekommen. Hashkollisionen dienen allerdings oft als sehr gute Entschuldigung der Programmierer für extrem dumme Züge ihres Programms, da man so schlecht ja nie programmiert haben kann. Zitat: "Da kann ich nichts dafür, dass muss wohl eine Hashkollison gewesen sein."
 
 
Die Größe der HashTabellen
Bei allen Schachprogrammen kann man die Größe der Hashtabellen einstellen, d.h. man legt fest, wie viel Arbeitsspeicher für die Hashtabellen reserviert werden soll. Dabei stellt sich nun die Frage, welcher Wert optimal ist. Allgemein kann man sagen, dass man die Hashtabellen auf gar keinen Fall größer machen soll als freier Arbeitsspeicher zur Verfügung steht. Dies ist in einem modernen Betriebssystem wie Windows ohne Probleme möglich, da Windows dann gerade nicht benötigten Speicher auf der Festplatte auslagert. Man spricht auch von "swappen".
 
Hashtabellen werden allerdings immer im Speicher benötigt, so dass Windows nicht weiß, was es tun soll, bis es schließlich die Hashtabellen von dem Arbeitsspeicher auf die Festplatte hin und her kopieren muss. Dies erkennt man dann an einem wilden, permanenten Gekratzte auf der Festplatte und in einem unendlich langsam ablaufenden Programm. Dies ist unter allen Umständen zu vermeiden, da dadurch das Schachprogramm wie alles andere auf dem Rechner auch völlig ausgebremst wird.
 
Wenn man den Speicher für Hashtabellen zu klein einstellt, dann ist nicht genügend Platz für die untersuchten Stellungen und ältere Einträge, die später evtl. noch benötigt werden, müssen gelöscht werden. Man sieht auch, dass die optimale Größe der Hashtabellen auch von der Bedenkzeit und damit von der eingestellten Spielstufe abhängt, denn wenn ein Programm länger rechnet, dann hat es ja auch mehr abzuspeichern.
 
Dies hört sich alles sehr kompliziert an, doch wird einem die Arbeit in der Regel automatisch abgenommen, indem die Programme den zur Verfügung gestellten Speicher stets optimal ausnutzen. Man kann daher in meinem Programm Shredder die Hashtabellen stets so groß wie möglich einstellen, ohne dass man dadurch irgendwelche Nachteile für das Programm befürchten muss.
 
Der wirklich zur Verfügung stehende Speicher darf dabei natürlich nicht überschritten werden. Wenn man auch nur Blitzschach spielen möchte, dann bringt es sicher auch nicht viel, sich noch 128 MB Speicher extra dafür zu kaufen, um Shredder statt 100 MB 200 MB für Hashtabellen zur Verfügung zu stellen. Wer dies möchte kann es aber natürlich auch tun, es schadet nichts und für die Analyse bringt es später dann wirklich etwas.
 
 
Fazit
Nachdem sie nun wissen was Hashtabellen sind und wie groß man sie einstellen soll, stellt sich die Frage, was sie denn nun eigentlich bringen. Es sollte klar sein, dass sie immer wichtiger werden, je weiter ein Programm voraus schaut, da dann die Anzahl der möglichen Zugumstellungen natürlich viel größer wird. Da es im Endspiel weniger Zugmöglichkeiten für eine Seite gibt als im Mittelspiel oder in der Eröffnung und das Programm deshalb weiter voraus schauen kann helfen Hashtabellen im Endspiel natürlich viel mehr. Das Paradebeispiel für den Nutzen von Hashtabellen ist die folgende Stellung:
 
Durch die blockierten Bauern können zunächst nur die Könige ziehen, dadurch ergeben sich eine Unmenge von möglichen Zugumstellungen. Der Lösungszug 1.Kb1 wird ohne die Hilfe von Hashtabellen nicht oder erst nach einigen Tagen des Rechnens auch auf einem sehr schnellen Computer gefunden. Mit Hashtabellen sieht die Sache dann ganz anders aus. Schon nach wenigen Sekunden zeigt der Computer an, dass Weiß mit 1.Kb1 gewinnbringenden Vorteil erreichen kann. Dies ist natürlich ein extremes Beispiel, leider kann so eine Steigerung nicht in allen Stellungen erzielt werden, doch auch im Mittelspiel mit noch sehr vielen Figuren auf dem Brett sind Hashtabellen eine sehr große Hilfe, die man nicht mehr missen will, wenn man sie einmal in seinem Programm implementiert hat.
 
Stefan Meyer-Kahlen – www.shredderchess.de
 
zum Seitenanfang zurück |