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.