MiniMAX und Hashtabellen

Jedes ernst zu nehmende Schachprogramm arbeitet heute mit Hashtabellen. Vermutlich hat auch schon jeder Computerschachfreund bei seinem Programm die Größe der Hashtabellen in den Programmoptionen geändert und wusste eventuell gar nicht genau, was er damit tat. Der folgende Artikel beschreibt deshalb für alle, die es genauer wissen wollen, die Funktionsweise von Hashtabellen, sowie deren Implementation in das didaktische Schachprogramm MiniMAX.

Was sind Hashtabellen?

Hashing ist eine Programmiertechnik, die es einem Schachprogramm erlaubt, Zugumstellungen im Verlauf der Suche nach dem besten Zug zu erkennen und verhindert somit die erneute Bewertung einer Stellung, die bereits zuvor in der Suche bewertet wurde. Ein Beispiel: Das Programm berechnet aus der Grundstellung heraus die Zugfolge 1.d2-d4 Sg8-f6 2. Sg1-f3. Nun rechnet es von dieser Position an noch alle Varianten weitere 4 Züge tief und kommt zu der Bewertung +0.03. Im Verlauf der weiteren Suche taucht nun die Variante 1.Sg1-f3 Sg8-f6 2. d2-d4 auf. Auch hier befindet sich das Programm 4 Züge vor dem Rechenhorizont, eine Bewertung im Rahmen der nächsten 4 Züge würde natürlich wieder dasselbe Ergebnis (+0.03) ergeben wie vorhin, da die Ausgangsstellung absolut identisch ist - auch wenn sie auf einem anderen Weg erreicht wurde. Wenn ein Programm nun clever genug wäre, diese Zugumstellung zu erkennen, dann könnte es sich die erneute Bewertung, einschließlich der damit verbundenen Rechenarbeit, sparen und sich statt dessen an den vorhin berechneten Wert +0.03 »erinnern«. Eben dies ist die Aufgabe von Hashtabellen. In diesen Tabellen werden Stellungen, ihre Bewertung, sowie eine Reihe anderer Informationen gespeichert, in der Hoffnung dieser Stellung im Verlauf der weiteren Suche nochmals zu begegnen. Ein Programm hat mit einer Hashtabelle also eine Art Gedächtnis und kann sich bewertete Stellungen merken.

Mit diesem Hintergrundwissen wird auch die Faustregel für Hashtabellen »Je größer desto besser« plausibel: Ein größeres Gedächtnis fasst mehr Stellungen, somit ist die Wahrscheinlichkeit in der Tabelle fündig zu werden größer.

Wie wird eine Position gespeichert?

Die komplette Stellung mit allen Figuren, Zugrecht, Rochaderecht und enpassant Status zu speichern wäre viel zu aufwändig. Das Programm würde, trotz der heutigen Rechenleistungen, recht langsam werden und eine Position würde in der Hashtabelle auch unnötig viel Platz beanspruchen. Was man braucht ist ein effizientes Verfahren, welches zu einer Position eine Art »Fingerabdruck« erzeugt, anhand dessen man die Position wieder identifizieren kann. Gleiche Positionen müssen also auch gleiche Fingerabdrücke erhalten. Im Gegensatz zu dem menschlichen Fingerabdruck gilt der Umkehrschluss leider nicht. Es gibt also identische Fingerabdrücke, die aus unterschiedlichen Positionen stammen. Dazu aber später mehr.

Wie werden die Fingerabdrücke der verschiedenen Positionen nun erzeugt?

Der Geschwindigkeit wegen benötigt man ein Verfahren, welches den Fingerabdruck einer Stellung inkrementell berechnet. D.h. wenn zu einer Stellung der Fingerabdruck bekannt ist, dann kann daraus der Fingerabdruck einer geringfügig geänderten Stellung nur über die Änderungen berechnet werden. Benachbarte Stellungen im Suchbaum unterscheiden sich ja nur durch einen Zug, damit sind die Positionen sehr ähnlich. Ein Verfahren, welches keine inkrementelle Berechnung der Fingerabdrücke erlaubt, müsste für jede Position alle 64 Felder abklappern und wäre damit viel zu langsam.

Die gesuchte Funktion zur Berechnung des Fingerabdrucks ist das EXCLUSIVE ODER (XOR). Der Fingerabdruck dient der Erkennung einer Position und wird deshalb als Hashkennung oder einfach nur Kennung bezeichnet. Die XOR Funktion benötigt zwei Argumente, welche mit XOR verknüpft werden sollen:

a XOR b ergibt genau dann 1, wenn a und b verschieden sind, sonst 0. (a, b sind Elemente der Menge {0, 1})

Neben dem Hashcode für die Brettstellung wird noch ein Code für jede Feld-Figurentyp Kombination benötigt. Es sind 64 Felder und 12 verschiedene Figurentypen - für Weiß und Schwarz jeweils K, D, T, L, S, B - das macht zusammen 64 * 12 = 768 Codes. Für diese Codes ist es völlig egal, was für Werte sie haben, solange alle unterschiedlich sind, deshalb werden sie einmalig beim Programmstart mit Zufallszahlen gefüllt.

Die Funktionsweise des XOR läßt sich am Besten an einem Beispiel nachvollziehen.

Im Beispiel sollen die Züge d2-d4 und d2-d3, d3-d4 untersucht werden. Die entsprechenden Codes für die Feld-Figurentyp Kombination seien:

10110 (wB auf d2)
11100 (wB auf d3)
10101 (wB auf d4)

Angenommen die Grundstellung hätte die Hashkennung: 01101

Nun wird der Zug d2-d4 ausgeführt, dazu wird der Bauer in der Hashkennung quasi von d2 entfernt. Jedes Bit der Kennung wird mit dem entsprechenden Bit des Codes verknüpft:

    01101 (Hashkennung der Grundstellung)
XOR 10110 (Code für weißer Bauer d2)
---------
  = 11011 (Zwischenergebnis Hashkennung)

Der Bauer muß noch auf d4 wieder abgesetzt werden:

11011 XOR 10101 = 01110

Dies ist die inkrementell aus der Grundstellung errechnete Hashkennung für den Zug d2-d4. Es wird nun als zweites Beispiel die Zugfolge d2-d3 gefolgt von d3-d4 berechnet:

01101 XOR 10110 = 11011 (Bauer von d2 entfernen)
11011 XOR 11100 = 00111 (Bauer auf d3 setzen)
00111 XOR 11100 = 11011 (Bauer von d3 entfernen)
11011 XOR 10101 = 01110 (Bauer auf d4 setzen)

Nach beiden Beispielen ist die Stellung auf dem Brett dieselbe. Auch die Hashkennungen sind identisch. Zur Berechnung der Kennung ist es also egal auf welchem Weg eine Stellung erreicht wird. Dabei wurde eine Eigenschaft der XOR Operation ausgenutzt, die für das Hashing unbedingt notwendig ist: Ein zweifaches XOR mit demselben Code entspricht der Identität:

(A XOR B) XOR B = A

Genau dies ist im obigen Beispiel beim Setzen und Entfernen des Bauern d3 passiert. Mit den 768 Codes kann man quasi Figuren in die Hashkennung auf entsprechende Felder setzen und löschen. Natürlich darf man nicht vergessen beim Schlagen auch die geschlagene Figur aus der Kennung zu entfernen und bei der Rochade nach dem König auch den Turm zu setzen. Um eine Position eindeutig zu identifizieren reichen die Figuren alleine nicht aus, man muss auch das Zugrecht, den Rochadestatus und etwaige enpassant Felder berücksichtigen. Rochadestatus und enpassant kann man allerdings vernachlässigen, der Fehler dabei ist so gering, dass der Aufwand nicht gerechtfertigt ist. Das Zugrecht verwaltet man entweder duch einen eigenen Code, der beim Wechsel des Zugrechts mit der Kennung XOR-verknüpft wird oder man schreibt mit in die Tabelle, welche Seite am Zug ist. Auch getrennte Tabellen für Schwarz und Weiß wären eine Lösung.

Hashkollisionen

Zwecks der Übersicht wurde im Beispiel eine 5 Bit Kennung verwendet. Eine Zahl in Binärsystem mit 5 Stellen kann 2^5 = 32 verschiedene Werte annehmen. Da es im Schach wesentlich mehr Stellungen gibt, kann man leicht sehen, dass es viele verschiedene Stellungen geben muss, welche dieselbe Hashkennung erhalten. Bei einer so kleinen Kennung würde ein Programm sehr häufig beim Blick in die Tabelle fündig werden und glauben eine Zugumstellung entdeckt zu haben. In Wirklichkeit stammt die Kennung in der Tabelle aber von einer anderen Position und der Wert passt nicht zur untersuchten Stellung. Eine sogenannte Hashkollision ist eingetreten. Zu viele Hashkollisionen lassen das Programm grundlos Figuren einstellen und schlecht spielen.

Man muss also dafür sorgen, die Wahrscheinlichkeit einer Hashkollision zu minimieren, indem die Hashkennung möglichst groß gewählt wird. Üblich sind Hashkennungen mit 32 oder auch 64 Bit. Damit ist das Kollisionsrisiko zwar nicht verschwunden, aber so gering, dass man sich keine Sorgen mehr machen muss. Mit etwas Glück pflanzt sich eine fehlerhafte Bewertung durch eine Hashkollision nicht bis zur Wurzel des Suchbaums fort.

Der Zugriff auf die Tabelle

Nun weiß das Programm, wie zu einer Stellung die eindeutige Hashkennung berechnet wird, damit es erkennt, dass es diese Stellung schon einmal berechnet hat. Die Hashkennung wird zusammen mit dem Wert der Stellung und einigen anderen Informationen in der Hashtabelle aufbewahrt. Die Frage ist nun, wie die Einträge in der Tabelle möglichst effizient verwaltet werden. An welche Position werden neue Einträge geschrieben? Wie kann man schnell feststellen, ob ein Eintrag bereits existiert?

Man könnte nun auf die Idee kommen, einen neuen Eintrag an die jeweils nächste freie Tabellenposition zu schreiben. Das würde aber bedeuten, dass man sequentiell suchen muss um festzustellen, ob ein Eintrag bereits existiert. Dieses Verfahren kommt also aus Effizienzgründen nicht in Frage, da der Aufwand linear mit der Anzahl der Tabelleneinträge wächst.

Als weiterführende Idee könnte man die Tabelle nach den Kennungen sortieren, was eine binäre Suche mit logarithmischem Aufwand erlauben würde. Aber auch das ist nicht schnell genug, zumal zur Suche noch der Aufwand hinzukommt, die Liste sortiert zu halten.

Eine Suche nach der richtigen Kennung, sequentiell oder binär, kommt also nicht in Frage. Das Programm braucht vielmehr einen eindeutigen Index, der die Position angibt, an der ein Eintrag geschrieben bzw. wieder gelesen wird. Dieser Index soll genau wie die Hashkennung eindeutig von der Position auf dem Brett abhängen. Man braucht also noch mal 768 Codes und berechnet damit völlig analog zur Kennung den Index. Für den Index reicht allerdings eine 32 Bit Zahl, damit sind mehr als 4,2 Mrd. Zahlen darstellbar, was immer noch mehr ist als die Anzahl der Tabelleneinträge.

Was passiert, wenn der Index größer ist, als die Anzahl der möglichen Tabelleneinträge? Zum leichteren Rechnen nehmen wir an, die Hashtabelle fasst 10 Einträge. Lautet der Hashindex nun 7 ist klar, es wird auf dem siebten Eintrag der Tabelle zugegriffen. Was aber wenn der Index zu groß wird? Beispeilsweise 11? Intuitiv wird vermutliche jeder die Zehnerstelle abschneiden und wieder auf Eintrag Nummer 1 zugreifen. Genaus so macht es auch das Schachprogramm. Es berechnet aus dem Hashindex den Rest der Division durch 10. Das erledigt die Modulo Funktion:

Beispiel:

Index = 34
Tabellengröße = 10
Das Programm greift auf Eintrag Nr. 34 MOD 10 = 4 zu.

Allegemein:
Index = a
Tabellengröße = b
Das Programm greift auf Eintrag Nr. a MOD b zu.

In diesem Beispiel wurden bei zu großen Zahlen die Zehner-, Hunderter-, Tausenderstellen usw. ausgeblendet um die Einerstellen übrig zu behalten und auf eine Zahl zu kommen, die im Bereich der Hashtabellengröße liegt. Nun rechnet ein Computer nicht im Zehner- sondern im Zweiersystem, das Problem bleibt aber dasselbe. Um bei einer Binärzahl Ziffern auszublenden kann man sich der bitweisen logischen UND Verknüpfung bedienen:

a UND b ergibt 1 falls a = 1 und b = 1, sonst 0

Eine UND Verknüpfung von a mit 0 ergibt also unabhängig vom Wert a immer 0.
Eine UND Verknüpfung von a mit 1 ergibt einfach a, verhält sich also neutral.

Ein Beispiel zur Ausblendung der ersten drei Bits eines 8 Bit großen Index:

    10110101 // Index
AND 00011111 // Maske zum Ausblenden der Bits 1-3
------------
    00010101

Die Modulo Funktion ist zwar universell, also für jede Größe der Hashtabelle geeignet, aber im Vergleich zum bitweisen UND recht langsam. Bitweises UND ist sehr schnell, erfordert aber, dass die Tabellengröße (T) einer Potenz von 2 entspricht. Die Einträge stehen dann an den Positionen 0 bis T - 1, ausgeblendet wird durch UND Verknüpfung mit T -1. Es muss also zwischen Flexibilität und Rechengeschwindigkeit abgewogen werden.

Mit Tabellengröße ist hier immer die Anzahl der Einträge gemeint, wieviel Platz im Arbeitsspeicher dadurch belegt wird hängt von der Dimensionierung der Variablen und der Information, die in die Tabelle geschrieben wird, ab.

Die Position in der Hashtabelle bietet einen weiteren Schutz gegen die oben beschriebenen Hashkollisionen. Das Programm schaut also abhängig von Hashindex, der seinerseits von der Stellung auf dem Brett abhängt, an eine ganz bestimmt Stelle in die Hashtabelle. Nur wenn an dieser Stelle auch die richtige Kennung zu finden ist, wurde eine Zugumstellung entdeckt. Es muss also die richtige Kennung auch an der richtigen Position stehen - deshalb wurden zur Berechnung des Index auch andere 768 Codes verwendet wie für die Kennung.

Im Verlauf der Suche bewertet das Programm mehre Millionen Positionen. Die Hashtabelle fasst aber beispielsweise nur 2^16 (=65536) Einträge, folglich werden ständig alte Einträge mit neuen überschrieben, das Programm beginnt zu vergessen.

Verwendung der Tabelle in der Suche

Im Verlauf der Suche wird das Programm nun jedes Mal, wenn zu einer Stellung im Suchbaum der beste Folgezug mit entsprechender Bewertung berechnet wurde, diese Information in die Hashtabelle schreiben. Jedes Mal, wenn das Programm die Aufgabe hat eine Stellung im Suchbaum zu bewerten, schaut es zuerst einmal in die Hashtabelle. Stimmt die Kennung an der Position Index AND (T-1) mit der aktuellen Kennung überein, so wurde eine Zugumstellung entdeckt. Anstatt die Stellung nun aufwendig rekursiv zu bewerten kann einfach der Wert aus der Tabelle gelesen und die Suche abgebrochen werden.

Die Frage ist nun welche Informationen in der Tabelle aufbewahrt werden sollen. Zum Verständnis ist hier die Kenntnis des Alpha-Beta Suchalgorithmus von MiniMAX oder einem anderen Programm Voraussetzung.

Natülich müssen die Kennung und der beste Wert in der Tabelle aufbewahrt werden. Wir brauchen aber auch die Rechentiefe , aus der diese Bewertung stammt und den besten Folgezug. Wie das obige Beispiel mit d2-d3-d4 gezeigt hat können die Wege zu einer Position unterschiedlich lang sein. Deshalb kann es passieren, dass an einer Stelle im Suchbaum ein Hashtreffer entdeckt wird, dessen Wert auf einer Rechentiefe von 3 beruht, das Programm aber noch 4 oder mehr Züge tief zu rechnen hat. Würde das Programm nun den Wert der Hashtabelle nehmen, dann hätte es indirekt nicht tief genug gerechnet, deshalb muss die Tiefe in der Tabelle größer oder gleich der verbleibenden Rechentiefe sein. Dies entspricht in MiniMAX der Variablen distanz. Aber auch wenn der Wert nicht direkt verwendet werden kann, so war der Treffer doch nicht erfolglos. Der beste Folgezug in der Tabelle stammt aus Tiefe 3, und kann zur besseren Effizienz des Alpha-Beta Algorithmus bevorzugt untersucht werden. Auch der umgekehrte Fall kann eintreten, dass die Tiefe in der Tabelle größer ist als die verbleibende Suchtiefe, dann rechnet das Programm indirekt tiefer als es soll, was aber nicht schaden kann.

Da im Verlauf der Suche nicht alle Werte exakt sind, sondern aufgrund von fail-low und fail high nur untere oder obere Schranken darstellen, darf das Programm später nicht alle Werte einfach blind verwenden. Der Typ des Wertes, ob er EXACT, HIGH oder LOW ist muss mit in die Tabelle geschrieben werden. Beim Wiederfinden darf ein HIGH-Wert nur dann verwendet werden, wenn er größer gleich dem aktuellen Beta-Wert ist. LOW-Werte müssen entsprechend kleiner oder gleich Alpha sein. Nur die EXACT-Werte dürfen bedingungslos verwendet werden.

Erreichte Steigerung der Effizienz

Was bringen nun die Hashtabellen an Geschwindigkeitssteigerung? Die Effizienz hängt von mehreren Faktoren ab. Einerseits von der Größe der Hashtabelle, je größer die Tabelle, desto geringer die Wahrscheinlichkeit, dass neue Einträge die alten überschreiben und Informationen verloren geht. Eine obere Grenze für die Größe der Hashtabelle ist der freie Arbeitsspeicher des Computers, wenn die Tabelle nicht komplett im RAM gehalten werden kann, dann werden Teile davon auf die Festplatte ausgelagert. Die Zugriffe auf die Platte sind sehr langsam, das Programm würde durch das sogenannte "swapping" geradezu einschlafen.

Die Effizienz hängt aber auch von der Stellung auf dem Brett ab. Zugumstellungen sind im Endspiel, wo die Figuren weniger aber beweglicher werden, häufiger anzutreffen als in der Eröffnungsphase oder im Mittelspiel. Je mehr Zugumstellungen im Verlauf der Suche auftreten, desto besser greift das Hashing. Auf Grund der Stellungsabhängigkeit macht es kaum Sinn hier exakte Zahlen anzugeben, deshalb werden die Zugzeiten in verschiedenen Partiephasen untersucht und grob gerundet. Die Hashtabelle wurde dabei groß genug gewählt, dass sie während des Rechnens bestenfalls halb voll wurde.

In der Eröffnungsphase wurde die Antwortzeit auf Tiefe 8 ca. halbiert, während im Mittelspiel die Suche bereits um den Faktor 4 beschleunigt wurde. Im Endspiel, als einige Bauern und die eine oder andere Figur geschlagen wurden, beginnt das Hashing langsam richtig zu greifen, der Beschleunigungsfaktor ist hier sehr stellungsabhängig und nach oben quasi offen. Ein Extrembeispiel soll die Möglichkeiten des Hashings verdeutlichen:

Im Buch "Schach am PC" wurde bereits folgende Stellung angesprochen, die als Paradebeispiel zum Hashing dient:


Weiß: Ka1, Ba4, d4, d5, f4
Schwarz: Ka7, Ba5, d6, f5
FEN: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
1. Kb1!

Zwar erreicht MiniMAX auch ohne Hashtabellen auf Grunde der eingeschränkten Zugmöglichkeiten recht schnell eine Rechentiefe von 17 Halbzügen, ist aber doch weit davon entfernt, die Lösung 1.Kb1! zu finden. Um diesen Zug mit entsprechender Bewertung zu sehen muss das Programm 25 Halbzüge tief rechnen. Mit Hashtabellen zeigt MiniMAX den richtigen Zug mit Bewertung binnen 2 Sekunden.

Zusammenfassend lässt sich festhalten, dass die Effizienz des Hashings zum Endspiel hin stark zunimmt, aber selbst in der Eröffnungsphase (u.a. wegen der besseren Zugsortierung) mindestens eine Verdoppelung der Antwortgeschwindigkeit bringt.

Weitere Verbesserungsvorschläge

Hashreplacement

Wie kann man die Effizienz der Hashtabellen noch steigern? Eine Idee sind die sogenannten "replacement-schemes". Die Idee dabei ist, wichtige Positionen bevorzugt aufzubewahren. Hashtreffer in der Nähe der Wurzel des Suchbaums bewirken größere Abschneidungen als Treffer weiter unten im Suchbaum. Es ist deshalb unerwünscht, dass wurzelferne Positionen wurzelnahe überschreiben. Ein indirektes Kriterium dafür ist die Distanz, die ja sowieso in der Tabelle als Tiefe vermerkt wird. Ein Eintrag darf also einen anderen nur dann überschreiben, wenn er eine größere oder gleiche Tiefe besitzt. Damit werden wurzelnahe Positionen bevorzugt behandelt. Bei solchen Regeln muss man allerdings sehr aufpassen, dass sich keine Karteileichen ansammeln, die dann nie wieder überschrieben werden und veraltet sind. Der Platz in der Tabelle würde dahinschwinden und das Kollisionsrisiko erhöht. Am einfachsten löscht man vor jedem Zug die Hashtabelle, dabei gibt es einen kleinen Trick: es wird nicht die komplette Tabelle gelöscht, sondern nur die Tiefeneinträge auf einen unmöglichen Wert (-255) gesetzt. Somit werden die Einträge nicht verwendet und sind zum Überschreiben freigegeben. Es bleibt aber die Information über die besten Züge zur Zugsortierung erhalten.

Enhanced Transposition Cutoff

Eine weitere Idee soll nur kurz angerissen werden, da sie meines Wissens nach in Schachprogrammen nicht oder kaum verwendet wird. Die Technik nennt sich enhanced transposition cutoff (ETC) und verlegt den Blick in die Hashtabelle bereits eine Suchtiefe höher. Oft bewertet das Programm zu einer Stellung mühevoll die ersten fünf Züge und entdeckt dann beim Blick in die Hashtabelle einen beta-cutoff. Ein Programm, das erst einmal jeden Zug ausgeführt und in die Hashtabelle schaut, hätte den cutoff entdeckt und sich die Bewertung der ersten fünf Züge erspart. Der Aufwand ist aber relativ hoch, wenn bei diesem Vorausblick nicht gute Erfolgsaussichten bestehen. Im Schach scheinen die Zugumstellungen nicht häufig genug, bei anderen Spielen mit einem höheren Anteil an Zugumstellungen findet diese Technik Anwendung. Bei komplexeren Spielen müsste man ETC wohl wenigstens auf Wurzelnähe beschränken, denn dort ist die Knotenzahl geringer als in Blattnähe und die Abschneidungen sind größer.

Implementierung in MiniMAX

Die Erläuterungen und Rechenbeispiele wurden hier so allgemein wie möglich gehalten. Wer nun ganz konkret an einer Implementierung in der Delphi-Version von MiniMAX interessiert ist, der findet hier eine genaue Anleitung zur Deklaration der Konstanten, Typen und Variablen, sowie einige Code-Beispiele der entsprechenden Stellen im Programm. Da der Code keine Delphi spezifischen Anweisungen enthält, sollte er auch für Programmierer interessant sein, deren Schachprogramm in C oder irgendeiner anderen Sprache geschrieben ist.