wie viel Hash ist richtig?

By Günther Höhne Date 2012-12-24 08:19

Hallo Wilfried,

man kann einem Programm die Hashtabellen stets so groß wie möglich einstellen, ohne dass man dadurch irgendwelche Nachteile für das Programm befürchten muss.
Sollte aber die Hashtabellen auf gar keinen Fall größer machen, als freier Arbeitsspeicher zur Verfügung steht.

Gruß
Günther

By Thomas Lagershausen Date 2012-12-24 09:12

Dein Freund hat recht.

Das Suchen in den Hashtabellen nimt dem Programm die Ressourcen für eine neue Suche.

Doch jedes Programm ist da ein wenig anders.

Daher solltest Du eine Teststellung aussuchen und mit verschiedenenen Hasheinstellungen durchprobieren. Dabei mußt Du aber immer vor jedem neuen Testdurchlauf die Hashtabellen löschen.

Da ich kein Blitz spiele kann ich Dir für diese Zeitkontrolle keine Hashwerte angeben.

Aber es sollten für kürzere Bedenkzeiten deutlich weniger als 2 GB sein.

Gruß

By Ingo Bauer Date 2012-12-24 10:22

Moin,

Immer wiederkehrendes Gerücht das durch nichts belegt ist!

Fakt ist, das Programmierer in der Regel raten, soviel Hash wie möglich einzustellen ohne das der Computer anfängt Dateien auszulagern. "Gesucht" wird im Hash auch nicht, sondern mit einem Hashkey (http://en.wikipedia.org/wiki/Zobrist_hashing) der Aufgrund der Stellung erzeugt wird, geziehlt auf eine Speicherstelle zugegriffen. Da diese Keys nicht 100% verschieden sind kann es auch immer wieder zu "Hashkolisionen" kommen. Das ist das, was immer Schuld ist wenn man sich einen Zug im Nachhinen nicht mehr erklären kann, auch wenns meistens einfach ein MP-Problem war.

Auf der anderen Seite werden die Knotenzahlen bei kleinerem Hash bei den meisten Programmen ein wenig schneller wenn man kleinere Hashgrößen verwendet. Wer nun will darf glauben das "sein" Programm" die Lösung eines Zuges im Spiel schneller findet und ein kleinerer Hash besser wäre. Das stimmt sogar für Teststellungen - manchmal, ob es mit einem gefüllten Hash in einem Spiel auch stimmt ...

Was mit Sicherheit stimmt ist das kein Hash deutlich schlechter spielt. Man kann also davon ausgehen das ein zu kleiner Hash auch schlechter spielt, je größer der Hashwert wird, desto geringer wird allerdings der Zugewinn. Ob sich dieser Trend umkehrt und die Spielstärke wieder abnimmt (und ist das messbar?) ... nun, damit sind wir wieder bei meinem ersten Satz. Es gibt keine zuverlässigen Zahlen, nur so etwas wie ein ungutes Gefühl wegen der etwas abnehmenden Knotenzahl. Ob du nun weniger Hash nimmst und bessere Ergebnisse erhälst hängt wahrscheinlich mit deinem Glauben zusammen. Je nachdem was man da glaubt zu wissen ändert sich die Wahrnehmung und dann stimmt das auch! Also mach was du willst, glaub dran und gut ist.
Alternativ darfst du gerne mal ein paar 10000 Spiele unter definierten Bedinungen jeweils mit unterschiedlichen Hashgrößen machen. Am besten noch bei verschiedenen Bedenkzeiten. Das Ergebniss wird die Gemeinde brennend interessieren und du wirst sehr viel Zuspruch bekommen - zumindest von denen deren Glauben du bestätigt hast, die anderen werden in deinem Test schon den grundlegenden Fehler finden

Gruß
Ingo

By Wilfried Arheit Date 2012-12-24 12:02

Vielen Dank an alle für die guten Ratschläge.
Werde es ausprobieren.
Noch eine kurze Anmerkung:
Wenn ich mehr als 4096 Hash einstelle, z.B. 6144 oder höher, meldet sich mein
Wartungscenter mit dem Hinweis "Die Grösse der Hashtabellen könnte den Computer verlangsamen"

MfG
Wilfried

By Günther Höhne Date 2012-12-24 13:11

Wenn die Hashtabellen zu groß eingestellt werden, wird der Speicher auf die Festplatte ausgelagert, wodurch das Programm enorm verlangsamt wird.

Gruß
Günther

By Martin Hander Date 2012-12-24 22:28

[quote="Ingo Bauer"]
Da diese Keys nicht 100% verschieden sind kann es auch immer wieder zu "Hashkolisionen" kommen. Das ist das, was immer Schuld ist wenn man sich einen Zug im Nachhinen nicht mehr erklären kann, auch wenns meistens einfach ein MP-Problem war.

By Ingo Bauer Date 2012-12-25 11:15

[quote="Martin Hander"]
[quote="Ingo Bauer"]
Da diese Keys nicht 100% verschieden sind kann es auch immer wieder zu "Hashkolisionen" kommen. Das ist das, was immer Schuld ist wenn man sich einen Zug im Nachhinen nicht mehr erklären kann, auch wenns meistens einfach ein MP-Problem war.

[/quote]
Ich bin mir nicht sicher, wie "MP-Problem" zu verstehen sein soll?
Eine Hashkollision bedeutet ja nur, das an der Position des Hash-Eintrages schon eine andere Stellung gespeichert wurde, zu "Fehlern" kommt es dabei nicht (bei korrekter Programmierung).
[/quote]

"MP Problem" meint nur das man eben nicht deterministisch immer den selben Zug bekommt ... völlig normal bei MP und weit häufiger bei einer MP Engine als eine Hashkollision.

[quote="Martin Hander"]
Der Zugriff auf einen kleineren Hashspeicher (z.b. 512 MB statt 2 GB) kann im übrigen deswegen etwas schneller sein, weil weniger TLB-Einträge beim Zugriff gebraucht werden.
http://de.wikipedia.org/wiki/Translation_Lookaside_Buffer
In der Praxis spielt das aber keine große Rolle und kann durch die Verwendung von "Large Pages" bei modernen Engines auch umgangen werden.
[/quote]

Yup, deswegen auch meine Zweifel das die vermeintlich schnellere Knotenzahl bei weniger Hash wirklich zu einem besseren Spiel, respektive höheren Elozahl führt ...

Ansonsten werde ich zu Hause mal durchprobieren ob sich die Knoten bei unterschiedlichen Hashgrößen (nicht zu klein natürlich) UND Verwendung von LP anders ändern (oder ob überhaupt) als ohne LP (bei nur einem Core!). Interessanter Test!

Gruß
Ingo

By Martin Hander Date 2012-12-25 13:02

[quote="Ingo Bauer"]
"MP Problem" meint nur das man eben nicht deterministisch immer den selben Zug bekommt ... völlig normal bei MP und weit häufiger bei einer MP Engine als eine Hashkollision..
[/quote]
Alles klar, dann hatte ich den Satz nur falsch verstanden.

Indeterministisch wird die Engine durch das nicht deterministische Timing des Thread Schedulers.
Man darf nur nicht "Hashkollision" durcheinanderbringen mit einem "Hashfehler", der aufgrund der verwendeten 64 bit extrem unwahrscheinlich ist, wenn auch nicht unmöglich.

[quote="Ingo Bauer"]
Ansonsten werde ich zu Hause mal durchprobieren ob sich die Knoten bei unterschiedlichen Hashgrößen (nicht zu klein natürlich) UND Verwendung von LP anders ändern (oder ob überhaupt) als ohne LP (bei nur einem Core!). Interessanter Test!
[/quote]
Es gibt einen "einfachen" programmtechnischen Grund, warum Engines bei weniger Hashspeicher oft eine höhere Zahl von Knoten ausgeben, aber trotzdem langsamer in die Tiefe kommen.

Der Zugriff auf den Arbeitsspeicher/Hash ist sehr langsam, verglichen mit der Geschwindigkeit der CPU.
Generall kann man in der Zeit, die ein Hashzugriff braucht, je nach Prozessor ca. 4-7 (wild geschätzt) Züge erzeugen, den Endknoten evaluieren und die Züge wieder zurücknehmen.
Das bedeutet, das nicht in jeder Stellung nachgeschaut wird, ob ein Hasheintrag vorliegt, sondern nur, bis man ca. 5 Züge vor dem Endknoten ist.
(In der normalen Suche, in der "Quiescence search" wird normalerweise gar nicht auf den Hashspeicher zugegriffen).
Wichtig ist dabei noch, das ein Hashtreffer normalerweise als ein Knoten gezählt wird, und nicht als die Anzahl der Knoten, die man sich durch den Treffer erspart.

Was passiert also jetzt, wenn der Hashspeicher kleiner wird?
Der Anteil der langsamen Hashtreffer sinkt (die einem aber viele generierte Knoten ersparen), und der Anteil der schnellen generierten Nodes steigt.
Dadurch werden also insgesamt mehr (gezählte) Nodes generiert, aber in Wirklichkeit ist man aber trotzdem langsamer, da die Knoten-Ersparnis durch die Hashtreffer deutlich größer ist.

Ich hoffe, ich konnte es einigermaßen anschaulich erklären

Gruß
Martin

By Ingo Bauer Date 2012-12-25 15:20

[quote="Martin Hander"]

Alles klar, dann hatte ich den Satz nur falsch verstanden.

Indeterministisch wird die Engine durch das nicht deterministische Timing des Thread Schedulers.
Man darf nur nicht "Hashkollision" durcheinanderbringen mit einem "Hashfehler", der aufgrund der verwendeten 64 bit extrem unwahrscheinlich ist, wenn auch nicht unmöglich.
[/quote]

Du hast eine sehr, und wie es scheint fundierte, Programmiersicht auf die Dinge. Der gemeine User, wie ich, sieht das da etwas nicht stimmt und zieht etwas als Erklärung heran, von dem er glaubt das könnte es sein. Da es letztendlich für ein individuelles Ereigniss unmöglich ist im nachhinein den Grund sicher festzustellen, ist es auch egal - für den User. Das es einem Programmierer da anders geht, er gerne etwas wiederholt und dann nach dem Fehler sucht, ist verständlich ...

[quote="Martin Hander"]
[quote="Ingo Bauer"]
Ansonsten werde ich zu Hause mal durchprobieren ob sich die Knoten bei unterschiedlichen Hashgrößen (nicht zu klein natürlich) UND Verwendung von LP anders ändern (oder ob überhaupt) als ohne LP (bei nur einem Core!). Interessanter Test!
[/quote]
Es gibt einen "einfachen" programmtechnischen Grund, warum Engines bei weniger Hashspeicher oft eine höhere Zahl von Knoten ausgeben, aber trotzdem langsamer in die Tiefe kommen.

Der Zugriff auf den Arbeitsspeicher/Hash ist sehr langsam, verglichen mit der Geschwindigkeit der CPU.
Generall kann man in der Zeit, die ein Hashzugriff braucht, je nach Prozessor ca. 4-7 (wild geschätzt) Züge erzeugen, den Endknoten evaluieren und die Züge wieder zurücknehmen.
Das bedeutet, das nicht in jeder Stellung nachgeschaut wird, ob ein Hasheintrag vorliegt, sondern nur, bis man ca. 5 Züge vor dem Endknoten ist.
(In der normalen Suche, in der "Quiescence search" wird normalerweise gar nicht auf den Hashspeicher zugegriffen).
Wichtig ist dabei noch, das ein Hashtreffer normalerweise als ein Knoten gezählt wird, und nicht als die Anzahl der Knoten, die man sich durch den Treffer erspart.

Was passiert also jetzt, wenn der Hashspeicher kleiner wird?
Der Anteil der langsamen Hashtreffer sinkt (die einem aber viele generierte Knoten ersparen), und der Anteil der schnellen generierten Nodes steigt.
Dadurch werden also insgesamt mehr (gezählte) Nodes generiert, aber in Wirklichkeit ist man aber trotzdem langsamer, da die Knoten-Ersparnis durch die Hashtreffer deutlich größer ist.

Ich hoffe, ich konnte es einigermaßen anschaulich erklären

[/quote]

Was aber heißt, das diejenigen die Ihren Speicher auf Playchess verkleinern und "schnellere" Engines zu bekommen ihre PSielstärke eher herrabsetzen ... richtig?
Warum werden dann effiktiv bei manchen Engines manche Stellungen mit einem "best move", auch bei einem Kern, schneller gelöst als mit mehr Hash?

Danke für die Erklärungen denen ich mit mienem Halbwissen sogar folgen konnte.

Gruß
Ingo

By Martin Hander Date 2012-12-25 17:58

Danke für die positive Resonanz, ich hab mich vor Jahren mal intensiver mit der Engine Programmierung befaßt und noch etwas an Wissen davon übrig behalten. Aber letztlich beginnt für jeden von uns irgendwann der Bereich des Halbwissens, ansonsten gäb es jetzt mehr Engines an der Spitze

[quote="Ingo Bauer"]
Was aber heißt, das diejenigen die Ihren Speicher auf Playchess verkleinern und "schnellere" Engines zu bekommen ihre PSielstärke eher herrabsetzen ... richtig?
[/quote]
Genau, die Verkleinerung des Hash-Speichers bewirkt trotz evtl. geringfügig höherer Knotenzahl in der Regel eine Herabsetzung der Spielstärke.

"In der Regel" deshalb, weil man natürlich mit extremen Einstellungen so eine Regel auch wieder durchbrechen kann.
So könnten z.B. 8 GB non-LP Hash beim Blitzen auf Playchess durchaus schlechter sein als 512 MB, weil dann die Zugriffsgeschwindigkeit überproportional einbricht und bei dieser Bedenkzeit die 8 GB gar nicht effektiv genützt werden können.

Bei längeren Bedenkzeiten ist es aber einfach: Je mehr Hash desto besser, da hier der Nutzen des großen Hashspeichers die Zugriffsgeschwindigkeit überwiegt.

[quote="Ingo Bauer"]
Warum werden dann effiktiv bei manchen Engines manche Stellungen mit einem "best move", auch bei einem Kern, schneller gelöst als mit mehr Hash?
[/quote]

Dafür gibt es auch einen Grund, der mit dem Algorithmus für die Baumsuche bei aktuellen Engines zusammenhängt.
Durch die hohe Selektivität wird ein Suchbaum erzeugt, der einen bestimmten "Shape" hat, d.h. bestimmte Varianten werden sehr tief untersucht, andere wiederum schnell abgebrochen.

Jetzt könnte man denken, bei weniger Hash wird dieser Suchbaum einfach überall etwas weniger tief durchsucht, und deswegen sollte keine Stellung schneller gelöst werden können.
Das ist aber nicht der Fall.

Die Form/Shape des Suchbaumes wird bestimmt von allen evaluierten Knoten, d.h. auch von denen im Hash abgelegten.
Dabei kann es durchaus vorkommen, das bei kleinerem Hash und damit weniger/anderen gespeicherten Knoten sich nicht nur die Tiefe, sondern auch der Shape des Suchbaumes ändert.

Das heißt, es werden zwar ingesamt weniger Knoten durchsucht, aber gelegentlich auch ganz andere Varianten tiefer durchsucht, als mit mehr Hash.
Was wiederum bedeutet, das ab und zu eine Lösung mit weniger Hash gefunden wird, weil sie in einem Zweig liegt, der mit mehr Hash nicht bzw. etwas später durchsucht wird.

Insgesamt gesehen sollten natürlich trotzdem mit mehr Hash bei gleicher Bedenkzeit statistisch mehr Lösungen gefunden werden.

Gruß
Martin

By Ingo Bauer Date 2012-12-25 19:07

[quote="Martin Hander"]

[quote="Ingo Bauer"]
Warum werden dann effiktiv bei manchen Engines manche Stellungen mit einem "best move", auch bei einem Kern, schneller gelöst als mit mehr Hash?
[/quote]

Dafür gibt es auch einen Grund, der mit dem Algorithmus für die Baumsuche bei aktuellen Engines zusammenhängt.
Durch die hohe Selektivität wird ein Suchbaum erzeugt, der einen bestimmten "Shape" hat, d.h. bestimmte Varianten werden sehr tief untersucht, andere wiederum schnell abgebrochen.

Jetzt könnte man denken, bei weniger Hash wird dieser Suchbaum einfach überall etwas weniger tief durchsucht, und deswegen sollte keine Stellung schneller gelöst werden können.
Das ist aber nicht der Fall.

Die Form/Shape des Suchbaumes wird bestimmt von allen evaluierten Knoten, d.h. auch von denen im Hash abgelegten.
Dabei kann es durchaus vorkommen, das bei kleinerem Hash und damit weniger/anderen gespeicherten Knoten sich nicht nur die Tiefe, sondern auch der Shape des Suchbaumes ändert.

Das heißt, es werden zwar ingesamt weniger Knoten durchsucht, aber gelegentlich auch ganz andere Varianten tiefer durchsucht, als mit mehr Hash.
Was wiederum bedeutet, das ab und zu eine Lösung mit weniger Hash gefunden wird, weil sie in einem Zweig liegt, der mit mehr Hash nicht bzw. etwas später durchsucht wird.

Insgesamt gesehen sollten natürlich trotzdem mit mehr Hash bei gleicher Bedenkzeit statistisch mehr Lösungen gefunden werden.
[/quote]

In anderen Worten: Bei einer unendlichen Anzahl an Stellungen (soweit möglich) sind natürlich ein paar dabei die mit weniger Hash schneller gelöst werden, in der breiten Masse sollten es aber weniger sein als bei viel Hash.

OK, Danke für die Informativen Ausführungen. Wir brauchen mehr Leute mit Ahnung. Hier kann man ein Stammposterpasswort erwerben

Nochmal Danke und Gruß
Ingo

By Michael Scheidl Date 2012-12-25 16:28

Sehr interessante Ausführungen! Diese Details waren mir bisher nicht bekannt. Nur das von wegen TLB habe ich schon einmal gelesen, aber nicht viel davon verstanden.

Wenn man keine Large Pages benutzt: Wo ungefähr beginnt die kritische Größe der HT. sodaß die TLB-Performance leidet, (a) bei 32 Bit, und (b) bei 64 Bit falls das davon abhängt? Danke.

By Martin Hander Date 2012-12-25 18:57

[quote="Michael Scheidl"]
Wenn man keine Large Pages benutzt: Wo ungefähr beginnt die kritische Größe der HT. sodaß die TLB-Performance leidet, (a) bei 32 Bit, und (b) bei 64 Bit falls das davon abhängt? Danke.
[/quote]
Leider läßt sich dafür wohl nur eine Faustregel angeben, da es von mehreren Faktoren abhängt:

Die TLB Performance ist bei jeder Prozessorarchitektur anders, je neuer, desto schneller natürlich im allgemeinen.
Die Speicher Zugriffszeit spielt auch eine Rolle, da die TLB's bei Überlauf auch im Memory gecached werden.
32 und 64 bit kann, je nach Prozessorarchitektur, einen Unterschied machen.
Bei Overclocking kann sich geringfügig etwas ändern.

Wenn man im Blitz bei aktuellen CPU's z.B. 512 MB verwendet, wird der Unterschied zu anderen Hashgrößen sicherlich nur minimal sein.
Ansonsten gilt bei langen Bedenkzeiten: Je größer, desto besser.

Gruß
Martin

By Ingo Bauer Date 2012-12-25 19:19

[quote="Michael Scheidl"]
Sehr interessante Ausführungen! Diese Details waren mir bisher nicht bekannt. Nur das von wegen TLB habe ich schon einmal gelesen, aber nicht viel davon verstanden.

Wenn man keine Large Pages benutzt: Wo ungefähr beginnt die kritische Größe der HT. sodaß die TLB-Performance leidet, (a) bei 32 Bit, und (b) bei 64 Bit falls das davon abhängt? Danke.
[/quote]

Ohne die Antwort hier schon lesen zu können und unabhänig von LP, 32 oder 64 bit. Ich nehme an das wiederum hängt von der Engine ab UND dürfte auch noch an der CPU bzw dem optimierten COmpilat zusammenhängen ... kurz: Wir wissen genau so viel wie am Anfang dieses Threads - nur Wissen wir jetzt ein bisschen warum wir nichts wissen

Gruß
Ingo

By Ernest Bonnem Date 2012-12-25 14:32

[quote="Ingo Bauer"]durchprobieren ob sich die Knoten bei unterschiedlichen Hashgrößen (nicht zu klein natürlich) UND Verwendung von LP anders ändern (oder ob überhaupt) als ohne LP (bei nur einem Core!). [/quote]
...sehe wirklich kein Grund für Änderung!
Aber mal sehen...

Nota (anderes Thema): wenn man MP Analysis vergleichen will, muß man natürlich die Hashtable Size ändern. Zum Beispiel:
1 Thread und 512 MB
2 Threads und 1024 MB
4 Threads und 2048 MB
8 Threads und 4096 MB
(... und für 6 Threads ist das ein Problem, denn mit 6*512 MB kann z.B. Houdini nur 4*512 MB benützen

)

By Ingo Bauer Date 2012-12-25 15:24

Hallo Ernest,

MP Vergleiche habe ich aufgegeben.

Aber ich werde mir das aber mal mit einem Thread machen, wobei ich deutlich niedriger mit dem Hash anfange.
4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 MEGAbyte!
und das mit einem Kern, LP an und aus, jeweils 300 Sekunden und dann Anzahl an knoten - Absolut und relativ/s

Gruß
Ingo

By Klaus S. Date 2012-12-25 17:08

Hallo Ingo,

hier gibt es auch noch Infos über das Thema.

http://www.schachfeld.de/f202/rybka-3-seltsamer-einfluss-hash-speichergroesse-rechenleistung-7874/

Gruß
Wilfried

By Stefan Pohl Date 2012-12-24 13:20 Edited 2012-12-24 13:23

[quote="Wilfried Arheit"]
Im Maschinenraum spiele ich mit meinem i7 980 immer mit 2048 Hash.
Egal ob 3-5 Min. 16+0, 60+15 oder länger.
Nun sagte mir ein Schachfreund, bei verschiedenen Bedenkzeiten müsse man
auch die Hashgrösse ändern. Stimmt das?
Für gute Ratschläge bedanke ich mich im voraus bestens.

Allen ein besinnliches Weihnachtsfest.

Wilfried
[/quote]

Naja, als Faustregel kann man sagen, daß eine gut programmierte Verhashung ca. 10-12 Byte pro Stellung "verbraucht". Ergo schau ich immer, wie lang ist ungefähr die Bedenkzeit pro Zug, die die Engine so im Schnitt verbraucht und wieviele Stellungen pro Sekunde erreicht sie auf meiner Hardware. Das ganze nehme ich dann mal 10 und habe eine brauchbare Hashgröße in Bytes.
Konkret: In meiner LS-Rangliste rechnen die Engines bei vollem Brett und noch vollem Zeitkonto zu Anfang der Partie ca. 2-3 Sekunden pro Zug. Nehmen wir hier also 3 Sekunden. Dann werden bei den meisten Engines auf meiner Hardware (und mit nur einem Core, weil bei mir ja immer 4 Partien parallel laufen) gute 2 Millionen Knoten pro Sekunde durchgerechnet. Also 3*2 Millionen*10= 60 Millionen Bytes = 60 MByte. Ergo teste ich alle Engines mit 64MB Hash (die Hashtables sollten immer eine Größe in 2er Potenz haben (64,128,256,512,...), das ist optimal).

Wenn du das so ausrechnest, hast du eine gute Hashgröße - nicht zu groß und nicht zu klein. Natürlich darf die Hashgröße nicht so groß werden, daß Windoofs anfängt, Bereiche der Hashtables auf Festplatte auszulagern. Ich würde also immer als generelles Maximum die RAM-Größe des Rechners abzüglich 1.5 Gigabyte (für Windoofs) ansetzen...
Hat dein Rechner als 4GB, dann sind 2048MB das Maximum.

Gruß - Stefan