Folgende 4 Benutzer sagen Danke zu Rasmus für den nützlichen Beitrag: | ||
|
||||||||||||
AW: Zur Hashtabellengröße
Mich wundern die nur 85-90% für die Bauerntabelle. Bei nur 2048 in Ordnung, aber das sollte doch mit mehr Speicher auf 95% steigen.
|
|
||||
AW: Zur Hashtabellengröße
Grundsätzlich kann man die Rechenzeit in Abhängigkeit der Rechentiefe n ja darstellen als t = a * b^n. Dabei ist a der Aufwand für die statische Stellungsbewertung und b der Verzweigungsfaktor. Die Bauerntabelle kann halt nur die Konstante a reduzieren, geht also nur linear ein (und das auch nur teilweise, weil außer der Bauernstellung ja auch diverse andere Sachen ausgewertet werden). Daher ist es nicht weiter merkbar, ob man nun 90% oder 95% Trefferrate hat. Die eigentlichen Hashtabellen hingegen knabbern über den besten Zug an der Konstante b, so daß der Effekt umso deutlicher wird, je tiefer man geht. Geändert von Rasmus (01.08.2017 um 00:34 Uhr) |
|
||||
AW: Zur Hashtabellengröße
Hallo Rasmus,
interessante Ausführungen und Beobachtungen Deinerseits. Nicht vergessen darf man jedoch nicht die Tatsache, dass die Hashtable-Größe und deren Auswirkungen abhängig ist von der jeweiligen Programmstruktur. Fritz beispielsweise war ein Programm, dass von großen Hashtabellen extrem profitieren konnte. Gruß Egbert |
|
||||||||||||
AW: Zur Hashtabellengröße
Da die Bauernbewertung nicht vom Partieverlauf abhängig ist, braucht sie ja zwischen zwei Zügen nicht gelöscht zu werden. Nach einem Zug eines Nichtbauern sollte also praktisch alles wieder genutzt werden können.
8192 Einträge sind für ein PC-Programm immer noch wenig, kannst Du daher den Test mit den nächsten Größen (16384. 32768 und 65536) wiederholen? Mehr scheint mir dann nicht nötig, denn Du entwickelst ja vornehmlich für die ARM-Hardware. Der Unterschied zwischen 90% und 95% Trefferquote ist ca. ein Faktor 2 bei der Bauernbewertung, das ist schon einiges. |
|
||||||||||||
AW: Zur Hashtabellengröße
Der Algorithmus zur Zugauswahl bei Fritz ist nicht optimal (aber je höher der Prozentsatz an Widerlegungen einer Teilvariante bereits durch den ersten Zug, desto effizienter arbeitet Alpha-Beta). Da Züge aus der Hashtabelle als erste nach dem Nullmove probiert werden, verbessert sich die Suche mit größeren Hashtables. Außerdem ist der Algorithmus zur Auswahl, was bei vollen Hashtables ersetzt wird, ebenfalls nicht optimal. Auch hier ist mehr Speicher nützlicher als für die Konkurrenz. P.S. Ich weiß nicht, wie gut Frans Morsch damals die Hashtables programmiert hat. Infos gab es deutlich weniger als heute und nur wenige haben vor 20-25 Jahren mit wirklich viel Speicher im Verhältnis zur Rechengeschwindigkeit testen können. Aber ich kann mich nicht an die Bewerbung von Fritz 7 oder Nachfolgern in Bezug auf die Nutzung von viel Speicher erinnern. Da könnte dann die Nutzung der Hashtables verbessert worden sein. Der Hype in der CSS stammt jedenfalls noch aus den Jahren 2000 und vorher. P.P.S. Ob der Zusammenhang zwischen Verbesserung durch mehr Speicher und Qualität des Algorithmus den Redakteuren der CSS bekannt war ist für mich pure Spekulation. |
Folgender Benutzer sagt Danke zu Solwac für den nützlichen Beitrag: | ||
Rasmus (01.08.2017) |
|
||||
AW: Zur Hashtabellengröße
Das überschreibt dann natürlich die Bewertung, wenn abwechselnd Stellungen aus Mittel- und Endspiel im Suchbaum auftauchen. Kann man mit separaten Tabellen für Mittel- und Endspiel beheben, aber dann hat man pro Phase nur die halbe Größe, was auch nicht besser ist. Ansonsten ist es von der Performance her nicht mehr wichtig, ob es 90 oder 95% sind. Ich hab's mal durch den Profiler gejagt, und mit nur 2048 Einträgen kostet die Bauernbewertung 2% der Gesamtrechenzeit. Eine Erhöhung von 90% auf 95% Trefferrate würde also nur 1% der Gesamtrechenzeit sparen, so daß das Gesamtprogramm um 1% schneller wäre. Rechnerisch ergäbe das etwa 720 mElo. Milli-Elo. ^^ |
|
||||||||||||
AW: Zur Hashtabellengröße
Der Test sollte auch nicht eine riesige Verbesserung der Spielstärke zeigen, es geht nur um die Güte des verwendeten Algorithmus.
|
|
||||
AW: Zur Hashtabellengröße
Bei den Bauernhashtabellen lohnt das nicht, weil keine weitere Performance zu gewinnen ist. Da nimmt man üblicherweise einfach den Algorithmus "Eintrag ersetzen". Wenn man das überhaupt als Algorithmus bezeichnen kann. |
|
|