Zobrist-Hashtables oder AVL-Baum?

Um es bei einem Schachprogramm zu vermeiden, für identische Stellungen immer wieder auf's Neue einen Spielbaum-Kindknoten samt Unterbaum zu erzeugen, werden bei vielen Programmen sogenannte Transposition Tables verwendet.
Die Methode, um für eine Schachstellung (von denen es ca. 10^50 gibt) einen eindeutigen Key bzw. Speicherort zu berechnen, besteht in der exklusiven Veroderung von mehreren, 'pseudo-zufälligen' 64-Bit Werten (wobei natürlich nur ein Teil des Schlüssels zum Auffinden des Speicherortes der Position verwendet wird). Das ganze Verfahren nennt sich Zobrist-Hashing, aber es erscheint mir wie eine Casino-Zockerei zu sein, weil damit Kollisionen (identischer 64-Bit Schlüssel, aber trotzdem nicht dieselbe Stellung) vermutlich eher die Regel als die Ausnahme sein müssten, was ziemlich ungemütlich ist, weil dann mitunter völlig falsche Bewertungen zurückgegeben werden.
Deshalb hätte ich mir überlegt, bei meinem Programm die Transpositionen in einem AVL-Baum zu speichern, wo solche Kollisionen unmöglich passieren könnten.
Allerdings weiß ich nicht genau, ob der Suchzugriff bei so einem AVL-Baum erheblich langsamer als bei einer (kollisionsgefährdeten) Zobrist-Hashtabelle sein würde, sodass der Overhead von dem AVL-Baum laufzeittechnisch teurer ist als die eingesparten Knoten.
Vielleicht ist aber so ein AVL-Baum auch gar nicht mal SO furchtbar viel langsamer als eine Zobrist-Hashtabelle?
Bei meinem Schach-Spielbaum muss viel häufiger eine Stellung gesucht werden, als dass eine neue eingefügt wird. Wäre in diesem Falle ein AVL-Baum die optimale Lösung, wenn man partout keine Hash-Tabelle verwenden möchte, oder gibt's sonst noch eine gut geeignete Ersatz-Datenstruktur für eine Zobrist-Hashtabelle ?
Besten Dank für jederlei Ratschläge!

Deine Begründungen sind unberechtigt, du solltest dir erst einmal die Grundlagen des Hashings aneignen, denn man rechnet beim Hashing mit Kollissionen und weiß auch wie man diese behandeln kann.

Von den von dir gegebenen Infos über das Zobrist-Hashing gehe ich davon aus, dass ein 64 Bit Key verwendet wird und beim Zugriff die restlichen 64 Bit Zufallsverwerte verglichen werden um herauszufinden welcher Zug gewollt ist.

Jester

Ein AVL-Baum scheint mir da recht ungeeignet zu sein, die Zugriffstzeit wächst logarithmisch mit der Anzahl der untersuchten Stellungen und das können schon recht viele sein. Außerdem wird durch die stets vollständige Balancierung vermutlich viel Rechenzeit verbraten.

Ich denke, es gibt zwei Gründe, warum man sich klassischerweise für Hashing entschieden hat:

Geschwindigkeit: Hashwert berechnen + in Tabelle nachschlagen, das geht schnell und einfach, insbesondere ist es unabhängig von der Anzahl der schon untersuchten Stellungen.
Datenmenge: Es genügt den 64Bit-Schlüssel (im Prinzip genügt es sogar weniger Information abzulegen). Das komplette Schachbrett zu kodieren würde deutlich mehr Speicher erfordern. Der Verzicht darauf bedeutet aber auch einen Verzicht auf Kollisionserkennung. Trotzdem würde ich schätzen, dass diese Datenmengen erst dadurch auch wirklich handhabbar werden. Wichtig ist vor allem die Wahl der Hashfunktion. Solange nur Stellungen kollidieren, die nie (oder nur sehr sehr selten) im selben Spiel bzw. aus derselben Situation innerhalb von ein paar Zügen auftreten können, stören die theoretisch vorhandenen Kollisionen praktisch ja nicht.

Das einzige, was ich mir sonst noch vorstellen könnte, wären evtl. Splay-Trees, weil diese automatisch Anfragen, die vor kurzem gestellt wurden schneller beantworten. Trotzdem haben diese auch weiterhin den Nachteil, dass das komplette Brett mit abgespeichert sein muß.

Besten Dank für die Ratschläge, ich werde mal nach anderen Hashfunktionen oder Methoden zur Konstruktion einer solchen Ausschau halten. (Es muss doch heuristisch - und nicht zufällig! - möglich sein, eindeutige Schlüssel zu berechnen!)

rapso

AmateurCoder schrieb:

Das ganze Verfahren nennt sich Zobrist-Hashing, aber es erscheint mir wie eine Casino-Zockerei zu sein, weil damit Kollisionen (identischer 64-Bit Schlüssel, aber trotzdem nicht dieselbe Stellung) vermutlich eher die Regel als die Ausnahme sein müssten, was ziemlich ungemütlich ist, weil dann mitunter völlig falsche Bewertungen zurückgegeben werden.

das verfahren ist sehr spezialisiert, die idee ist, dass man die selben zuege in unterschiedlichen reihenfolgen durchfuehren kann, das resultiert dann in den selben stellungen.
kannst also erst zug A machen, dann B, oder erst B, dann A, beides wird danach den selben hash generieren.
bei 64bit ist die wahrscheinlichkeit unglaublich klein dass du einen falschen Hashtable-treffer bekommst, weil du vermutlich nichtmal ne milliarde zuege testen wirst (was 30bit waere).
dafuer wirst du aber vermutlich ne unglaublich grosse menge an richtigen treffern haben, deswegen ist es keine casino zockerei.

das ist auch ein grund, weshalb man bei der tiefensuche ebenenweise vorgeht, also erst _alle_ zuege fuer rekursion 1, dann _alle_ fuer rekursionstiefe 2, dann _alle_ 3 etc. statt sich einen zu schnappen und es durch zu gehen. Das bringt natuerlich synchronizationsaufwand bei mehreren threads, aber das ist es wert.
Synchronisation ist ein weiterer grund ne table statt nen baum zu nehmen. Es ist zwar nicht wirklich "threadsafe" ohne syncpoint lookups zu machen, aber als fehler tritt nur auf dass mehrmals das selbe berechnet werden wuerde (die chancen sind aber unglaublich gering), bei verlinkten strukturen musst du jedoch in den allermeisten faellen einen syncpoint einbauen (was langsam ist).

(beim einfuegen, koennte man vielleicht ohne syncpoint auskommen, wenn man davon ausgeht dass alle threads das selbe an die selbe stelle einfuegen wuerden, aber beim aufloesen von collisions koennte ein syncpoint zwingend sein (je nach implementierung).

eine hashtable ist auch speicherfreundlicher.

kurz: nimm die hashtable

AmateurCoder schrieb:

Es muss doch heuristisch - und nicht zufällig! - möglich sein, eindeutige Schlüssel zu berechnen!

Bei 10^50 Möglichkeiten muss es dann auch 10^50 verschiedene Schlüssel geben, was einen 167-Bit-Schlüssel erfordert (bei gleichgroßen Schlüsseln).