Ach, Experte ist übertrieben - Hyatt, den sehe ich als Experten. Donninger allerdings auch. Ich habe nur etwas Erfahrung durch "learning by doing".



Man muß hierbei zwei Aspekte unterscheiden, erstens Performance und zweitens Sicherheit. Die Sicherheit kriegt man mit 64bit-keys in den Griff, die man zusammen mit der Position abspeichert.

Denn reine Indexkollisionen sind unbedenklich, sofern man beim konkreten Auswerten noch mitbekommt, daß zwar der Index, nicht aber der volle Schlüssel übereinstimmen. Das wirkt sich "nur" auf die Performance aus.

Ich nehme an, bei 160kB Hashtables wird Richard Lang auf ähnliche Probleme gestoßen sein wie ich. Sein Sourcecode ist nicht verfügbar, so daß ich nur mutmaßen kann, ob er womöglich eine ähnliche Lösung gewählt haben könnte. Grundsätzlich speichert der CT800 nicht den vollen 64bit-key einer Position, weil das eben ganze 8 Byte pro Position sind. Stattdessen werden nur die oberen 32bit eines 64bit-Keys gespeichert, und die unteren 12bit sind implizit schon im Index enthalten. Dadurch kommt man auf 48bit, was Hyatts Untersuchungen zufolge locker ausreicht.

Zusätzlich ist manchmal ja auch der beste Zug gespeichert, und ebenso wie Hyatt habe ich es bei tausenden Testspielen nie erlebt, daß das Debug-OOOPS erschienen wäre. Das käme, wenn der gespeicherte Zug in der Position nicht pseudolegal wäre, was bei einer Hashkollision höchstwahrscheinlich geschähe.

Das andere Problem ist die Performance, denn die Frage ist, wie geht man damit um, daß man viel weniger Hash-Einträge hat, als man gerne hätte? Klar wirken sich da 160kB negativ aus gegenüber mehreren MB. Da gibt's auch verschiedene Strategien, die man wählen kann.

Man kann "depth preferred" wählen, mit der Logik, daß das ja einen ganzen Suchbaum repräsentiert und deswegen sehr viel wert ist. Man kann aber auch das genaue Gegenteil machen, "leaf preferred", mit der Logik, daß dann die Treffer viel häufiger sein werden.

Entschuldige das Denglisch, aber in dem Bereich denke ich auf englisch, und ich muß erst übersetzen.

Mal ein konkretes Beispiel aus meinem Projekt, was mich übrigens ein komplettes Wochenende Vollzeit gekostet hat, das war echt übel. In einem Testspiel warf der CT800 ohne erkennbaren Anlaß seine Dame weg und verlor dann natürlich. Wie sich am Ende (vereinfacht) rausstellte, lag das aber nicht an Hashkollisionen, sondern im Suchbaum war die Stellung als mies erkannt worden, so daß jeder Antwortzug aufgrund der Suchbaum-Beschneidung letztlich als Unfug klassifiziert wurde. Mit dem Resultat, daß es keine brauchbaren Züge gab.

Da fehlerhafterweise nur die brauchbaren und nicht die vorhandenen Züge für die Patterkennung herangezogen wurden, erkannte der Suchalgorithmus fehlerhaft auf Patt, so daß das Wegwerfen der Dame als Remis fehlerkannt wurde. Da der CT800 ohnehin gerade etwas schlechter stand, war das eine attraktive Wahl. Ein Fehler, der übrigens bereits in der vor mir existierenden Codebasis vorhanden war, was das Debugging in einem nur halb verstandenen Algorithmus nicht gerade vereinfacht hat.

Aber solche krassen Fehler sind es, die zu total irrationalen Zügen führen können, und die dann gerne mal Hashkollisionen zugeschrieben werden. Ist halt eine bequeme Ausrede.



Dem kann ich mich anschließen; es ist nur so, daß ich von Hyatt ein quantitatives Paper erinnere, von Donninger nicht.

Hier übrigens der Link via wayback archive:

https://web.archive.org/web/20120614...ollisions.html



Nein, bislang nicht. Allerdings hatte ich vor einem Jahr auch noch keine Erfahrungen mit Schachprogrammierung.