Schachcomputer.info Community
  #1  
Alt 31.07.2017, 23:13
Benutzerbild von Rasmus
Rasmus Rasmus ist offline
Mephisto London 68030
 
Registriert seit: 26.08.2016
Land:
Beiträge: 373
Abgegebene Danke: 165
Erhielt 443 Danke für 175 Beiträge
Member Photo Albums
Aktivitäten Langlebigkeit
1/20 8/20
Heute Beiträge
0/3 ssssss373
Zur Hashtabellengröße

Moin,

ich habe mal ein paar Messungen gemacht, die ich recht interessant finde, und zwar zu der Frage, ob und wie sich Hashtabellen eigentlich abseits des Endspiels auswirken. Schließlich werden die meisten Partien ja vorher schon entschieden.

Grundannahme ist ein Programm, was mit iterativer Vertiefung arbeitet, also eine Stellung erst mit 3 HZ rechnet, dann mit 4 usw., bis die Zeit für den Zug aufgebraucht ist. Das ist die übliche Vorgehensweise, weil man dann immer einen annehmbaren Zug hat. Zudem kostet es nicht wirklich mehr Rechenzeit, weil die Züge dadurch besser vorsortiert werden.

Einer der Effekte davon ist, daß man in der folgenden Iteration auf Hashtreffer stößt, die man nicht direkt heranziehen kann, weil sie nicht von genug Tiefe "gedeckt" sind, aber den besten Zug des Hashtreffers kann man zur Zugsortierung benutzen. Deswegen funktioniert das übrigens auch teilweise, wenn man Teststellungen eingibt, ohne daß eine Partie dahintersteht, so daß beim Loslegen die Hashtabellen erstmal leer sind.

Ich habe das bei 10 Sekunden pro Zug in den ersten 10 Zügen einer Partie gemessen, ohne Buch. Also in der Eröffnung, wo Hashtabellen anders als im Endspiel sogar den geringsten Effekt haben. Gemessen nicht auf der ARM-Hardware, sondern in der PC-Version.

In ungefähr 60% aller Knoten führt der erste Zug bereits zur Abschneidung bei Vorsortierung mittels MVV/LVA. Das sind im Wesentlichen Widerlegungen völlig unsinniger Züge, welche direkt Material verlieren. Ist dieser erste Zug aber der beste aus der Hashtabelle, dann führt das in über 90% der Fälle zur Abschneidung.

Das Problem ist nun, daß bei kleinen Hashtabellen so ein bester Zug nur selten zur Verfügung steht. Gemessen mit 96 kB in nur 3.2% der Knoten (wobei das auf dem PC auch so ist, weil die Rechengeschwindigkeit ja sehr viele Stellungen generiert).

Bei 1.5 MB hat man so einen besten Zug in 6.6% der Fälle, und wegen voller Hash-Treffer verringert sich außerdem die Zahl der Gesamtknoten um 20%. Bei 400 MB hat man in 15% der Fälle einen besten Zug, während die Gesamtzahl der Knoten (relativ zu 96kB) mit 22% Reduktion nicht mehr wesentlich weiter absinkt.

In späten Spielphasen würde der Anteil der Fälle, in denen es einen besten Hash-Zug gibt, noch steigen, ebenso die Zahl der Volltreffer. Aber im Wesentlichen dient die Sache dazu, schnelle Widerlegungen für unsinnige Züge im Suchbaum zu haben.

Rechnet man das mal grob hoch unter der Annahme eines mittelprächtigen Verzweigungsfaktors von etwa 3, dann ergäbe sich (relativ zu 96 kb) bei 400 MB bei 8 Halbzügen Basistiefe eine Beschleunigung von ungefähr einem Faktor 4, was also einen guten HZ mehr Rechentiefe erlauben würde, und pi mal Daumen gute 100 ELO mehr erlaubt. Der Löwenanteil davon kommt nicht durch die vollen Hashtreffer zustande, welche die Knoten nur um 22% reduzieren, sondern durch die 15% der Knoten, in denen ein Hash-Zug zur Abschneidung des Suchbaumes führt.

1.5 MB wären noch für einen Faktor 1.67 gut, was schon nicht mehr so deutlich ist und um die knapp 40 ELO ergäbe.

Nehmen wir mal eine um den Faktor 60 geringere Rechengeschwindigkeit einer modernen ARM-CPU gegenüber PC an, dann werden also auch 60 mal weniger Stellungen generiert. Für einen nennenswerten Effekt reichen dann also auch 60 mal weniger Hashtabellen. Dann wären also 256 kB Hash soviel wert wie 15 MB auf dem PC. Man sieht, es langt nicht, um in der Spielphase zu deutlichen Effekten zu kommen.

Das wird natürlich im Endspiel wesentlich mehr. Allerdings bringt es ja nur eine höhere Rechentiefe, kann also grundsätzliche strategische Defizite nicht beheben, sondern nur mehr taktische Schlagkraft bieten. Nur wird es zum Endspiel hin immer weniger taktisch und mehr strategisch.

Ist das Wissen aber vorhanden, dann bringt das im Endspiel natürlich auch viel. Der Chess Genius mit seinen Endspielfähigkeiten sollte einiges draus machen können. Das TASC-Programm hingegen hat seine Stärken mehr im aggressiven Mittelspiel - demzufolge sollte es auf MCGE-Hardware mit reduzierten Hashtabellen kein sonderliches Problem haben, sondern mehr von der generell schnelleren CPU profitieren.

Wo es generell am meisten Schub bringt, das ist das späte Mittelspiel im Übergang zum Endspiel - aber auch nur auf taktischer Ebene. Eine verfehlte Spielanlage wird damit nicht rausgerissen.

Ein anderes Kapitel ist die separate Hashtabelle für die Bauernauswertung, welche ohne Parameter wie Rechentiefe usw. auskommt. Hier ergeben sich mit nur 2048 Einträgen, was bei mir 20 kB sind, in der Eröffnung Trefferraten von knapp 90%, was im Mittelspiel auf etwa 85% absinkt und zum Endspiel dann auf über 90% ansteigt. Das wird mit zunehmender Größe kaum deutlich mehr, weil nicht mehr viel zu holen ist.

Die wesentliche Konsequenz ist, daß Programme, die diese Art von Hashtabelle haben, sich ohne Einbußen bei der Rechentiefe eine sehr aufwendige Auswertung der Bauernstruktur erlauben können - wo dann z.B. auch die Aufstellung der Türme dranhängt. Also nicht nur offene Linien, das ist ja recht einfach, sondern auch z.B. die Attackierung gegnerischer zurückgebliebener Bauern auf halboffenen Linien - sowie das Bestreben, selber solche Schwächen zu vermeiden. Oder selber die klassische Granitformation auf einer für den Gegner halboffenen Linie aufbauen.
Mit Zitat antworten
Folgende 4 Benutzer sagen Danke zu Rasmus für den nützlichen Beitrag:
applechess (31.07.2017), Egbert (01.08.2017), Mythbuster (31.07.2017)
  #2  
Alt 01.08.2017, 00:02
Benutzerbild von Solwac
Solwac Solwac ist offline
Revelation
 
Registriert seit: 18.07.2010
Land:
Beiträge: 782
Abgegebene Danke: 189
Erhielt 338 Danke für 216 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss782
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.
Mit Zitat antworten
  #3  
Alt 01.08.2017, 00:28
Benutzerbild von Rasmus
Rasmus Rasmus ist offline
Mephisto London 68030
 
Registriert seit: 26.08.2016
Land:
Beiträge: 373
Abgegebene Danke: 165
Erhielt 443 Danke für 175 Beiträge
Member Photo Albums
Aktivitäten Langlebigkeit
1/20 8/20
Heute Beiträge
0/3 ssssss373
AW: Zur Hashtabellengröße

 Zitat von Solwac Beitrag anzeigen
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.
Ich hab's auch mit 8192 Einträgen getestet, immer noch bei etwa 92%. Das Problem ist eben, daß im Suchbaum auch neue Stellungen generiert werden, wodurch auch neue Bauernformationen entstehen.

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)
Mit Zitat antworten
  #4  
Alt 01.08.2017, 04:51
Benutzerbild von Egbert
Egbert Egbert ist offline
Lebende Foren Legende
 
Registriert seit: 20.12.2009
Ort: Dreieich
Alter: 59
Land:
Beiträge: 9.553
Abgegebene Danke: 13.920
Erhielt 16.420 Danke für 6.395 Beiträge
Member Photo Albums
Aktivitäten Langlebigkeit
14/20 15/20
Heute Beiträge
1/3 sssss9553
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
Mit Zitat antworten
  #5  
Alt 01.08.2017, 07:47
Benutzerbild von Solwac
Solwac Solwac ist offline
Revelation
 
Registriert seit: 18.07.2010
Land:
Beiträge: 782
Abgegebene Danke: 189
Erhielt 338 Danke für 216 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss782
AW: Zur Hashtabellengröße

 Zitat von Rasmus Beitrag anzeigen
Ich hab's auch mit 8192 Einträgen getestet, immer noch bei etwa 92%.
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.
Mit Zitat antworten
  #6  
Alt 01.08.2017, 08:02
Benutzerbild von Solwac
Solwac Solwac ist offline
Revelation
 
Registriert seit: 18.07.2010
Land:
Beiträge: 782
Abgegebene Danke: 189
Erhielt 338 Danke für 216 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss782
AW: Zur Hashtabellengröße

 Zitat von Egbert Beitrag anzeigen
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.
Fritz war von Beginn an ein schnelles Programm, also viele Knoten pro Sekunde, d.h. ein großer Suchbaum. Aber wenn ich mal die Lobhudelei der CSS etwas realistischer übersetzen darf:

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.
Mit Zitat antworten
Folgender Benutzer sagt Danke zu Solwac für den nützlichen Beitrag:
Rasmus (01.08.2017)
  #7  
Alt 01.08.2017, 17:54
Benutzerbild von Rasmus
Rasmus Rasmus ist offline
Mephisto London 68030
 
Registriert seit: 26.08.2016
Land:
Beiträge: 373
Abgegebene Danke: 165
Erhielt 443 Danke für 175 Beiträge
Member Photo Albums
Aktivitäten Langlebigkeit
1/20 8/20
Heute Beiträge
0/3 ssssss373
AW: Zur Hashtabellengröße

 Zitat von Solwac Beitrag anzeigen
Da die Bauernbewertung nicht vom Partieverlauf abhängig ist, braucht sie ja zwischen zwei Zügen nicht gelöscht zu werden.
Gelöscht nicht, aber sie hängt durchaus vom Partieverlauf ab, was auch den leichten Einbruch zum Mittelspiel hin erklärt. Man sollte fürs Endspiel eine modifizierte Bauernbewertung haben, weil z.B. Isolani im Endspiel schlimmer sind als im Mittelspiel und Freibauern mehr wert.

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. ^^
Mit Zitat antworten
  #8  
Alt 01.08.2017, 21:51
Benutzerbild von Solwac
Solwac Solwac ist offline
Revelation
 
Registriert seit: 18.07.2010
Land:
Beiträge: 782
Abgegebene Danke: 189
Erhielt 338 Danke für 216 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss782
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.
Mit Zitat antworten
  #9  
Alt 02.08.2017, 00:43
Benutzerbild von Rasmus
Rasmus Rasmus ist offline
Mephisto London 68030
 
Registriert seit: 26.08.2016
Land:
Beiträge: 373
Abgegebene Danke: 165
Erhielt 443 Danke für 175 Beiträge
Member Photo Albums
Aktivitäten Langlebigkeit
1/20 8/20
Heute Beiträge
0/3 ssssss373
AW: Zur Hashtabellengröße

 Zitat von Solwac Beitrag anzeigen
Der Test sollte auch nicht eine riesige Verbesserung der Spielstärke zeigen, es geht nur um die Güte des verwendeten Algorithmus.
Naja aber das ist doch der Punkt. Bei den Haupt-Hashtabellen arbeitet man mit Clustern und versucht, bei belegtem erstem versuchten Eintrag das im nächsten zu speichern, weil komplette Suchbäume weggeschnitten werden können.

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.
Mit Zitat antworten
Antwort

Themen-Optionen
Ansicht

Forumregeln
Du bist nicht berechtigt, neue Themen zu erstellen.
Du bist nicht berechtigt, auf Beiträge zu antworten.
Du bist nicht berechtigt, Anhänge hochzuladen.
Du bist nicht berechtigt, deine Beiträge zu bearbeiten.

BB code ist An
Smileys sind An.
[IMG] Code ist An.
HTML-Code ist An.

Gehe zu


Alle Zeitangaben in WEZ +1. Es ist jetzt 12:09 Uhr.



Powered by vBulletin (Deutsch)
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
©Schachcomputer.info