Hashtable, Zobrist Key und Transpositionstabelle

Ein Hashtable ist zunächst nicht anderes als eine Tabelle. Praktischer Weise sollte ihre Größe eine Zweierpotenz sein. Zur Hashtable wird diese Tabelle durch die Art des Zugriffes.
Aus den zu speichernden Daten wird ein Wert, der Hashwert, erzeugt. Dieser Hashwert wird (eventuell nach Verkürzung) als Schreib-, Leseindex benutzt.
Hier, im Zusammenhang mit den Brettspielen, wird der (Zobrist)BoardKey als Hashwert benutzt. Dieser Key muss auf die Tabellenlänge gekürzt werden, um ihn direkt als Index nutzen zu können. Die Kürzung erfolgt mit :
Index = BoardKey & (Tabellenlänge - 1);
Man kann sich leicht vorstellen, daß die Schlüsselkürzung den negativen Nebeneffekt hat, daß die Beziehung zwischen Index und BoardKey nicht mehr in beide Richtungen eindeutig ist. D.h. unterschiedliche Stellungen können nun zum selben Index führen (Kollision). Das muss beachtet werden.

Wozu brauche ich so etwas?

Bei den Brettspielen müssen u.U. sehr große Bäume, die mehrere gleiche Stellungen bzw. Teilbäume enthalten können, durchsucht werden. Ziel dieses Hashtables ist die Verhinderung doppelter Arbeit. Im Idealfall bietet ein Treffer in der Tabelle die Möglichkeit, die Suche und /oder Bewertung für diese Stellung bzw. Teilbaum sofort zu beenden und die gespeicherten Werte aus der Tabelle weiter zu verwenden. Das sollte so oft passieren, daß sich der ganze Overhead mit der Tabelle rechnet. Ein solche Nutzung macht die Tabelle zu einer Transpositionstabelle.

Was sollte in den Einträgen gespeichert werden?

Der (Tabellen)Index ist aus oben genannten Gründen nicht eindeutig. Um auf die sicher Seite zu gelangen, wird der vollständige Key gespeichert. So wird beim Lesezugriff gewährleistet, die richtige Stellung in der Hand zu haben.
Da man sich insgesamt in einer Zugsuche befindet, sind der bisher beste gefundene Zug und seine Bewertung auch sinnvolle Daten. Die Bewertung wird mit 4 weiteren Flags genauer spezifiziert. Sie setzten die Bewertung in Beziehung zum Alpha bzw. zum Beta Wert und bestimmen beim Lesen die weiter Nutzung der Daten.
Im Suchbaum kann die selbe Stellung in unterschiedlicher Tiefe auftauchen. Sie hat dann sicher den selben BoardKey, wird sich aber wahrscheinlich in der Bewertung unterscheiden. Auch das muss berücksichtigt werden. Daher wird die Suchtiefe gespeichert. Je nach Spiel wird für den zu speichernden Zug eine passende Struktur gewählt.

Das Einfache zuerst: der Schreibzugriff.

Am Ende der Suche sind die Daten für den HashEntry vorhanden. Die Kollisionsstrategie ist die einfachste von allen: Kollisionen ignorieren, immer überschreiben. In der WriteEntry Funktion muss das Flag für die Beziehung Score - Alpha - Beta gesetzt werden. Dies ist entscheidend fürs Vorgehen beim Lesen.

Der Lesezugriff.

Falls mit dem Index etwas gefunden wurde, wird das Ergebnis nur benutzt, falls der BoardKey identisch und die Suchtiefe des Eintrags >= der eigenen aktuellen Suchtiefe ist.
Auswertung der Flags:
Flagwert: lower, score >= beta, ein CutNode. Lower, weil der Wert eine untere Grenze ist. Der 'tatsächliche' Wert ist >= beta. Ein "fail high" mit der Bedeutung: "return beta; Eine weitere Suche ist nicht nötig." zurückgeben.
Flagwert: exact, score > alpha und score < beta, ein PV (principal Variation) Knoten. Gelesenen score zurückgeben, er hat die volle Qualiät einer 'normalen' Suche. Eine weitere Suche ist nicht nötig.
Flagwert: upper, score <= alpha, ein ALL Node, Upper, weil der Wert eine obere Grenze ist. Der 'tatsächliche' Wert kann <= alpha sein aber nicht größer. Ein "fail low" mit der Bedeutung: "return alpha; Eine weitere Suche ist nicht nötig." zurückgeben.

Quelltext ein-/ausblenden

Kommentar(e)

Kommentarformular ein-/ausblenden