Nutzung von Hauptvar. und Bewertung in nachfolgender Suche

By Benno Hartwig Date 2008-09-09 08:41

Als ich eben im "Brauche Nachhilfe in Engine-Ausgabe!"-Thread las, stellte sich mir eine Frage, für die ich mal einen eigenen Thread starte:

Alle(!?) Engines gehen ja iterativ vor bei der Analyse, d.h. sie starten mit Suchtiefe 1 und machen eine Suche und erhöhen diese Tiefe dann nach und nach. Macht ja auch Sinn. Man hat stets eine gute Vorstellung von dem zu erwartenden Stellungswert, und man hat mit der Hauptvariante auch gute Anfangszüge, die dann mit großer Wahrscheinlichkeit zu sehr vielen Cuts führen.

1.)
Und nun denke ich mir für den Fall Ponder=off:
Wenn die Engine die Analyse z.B. mit Tiefe 10 gemacht hat, einen Wert value10 herausbekommen hat und eine Hauptvariante z1,z2,z3,z4,z5,z6,z7,z8,z9,z10
Der Zug z1 wird ausgeführt, der Gegner denkt und macht nach einer Weile tatsächlich z2,
dann könnte doch meine Engine sagen:
"meine Suche in Tiefe 8 kann ich mir sparen, denn der Wert ist value10 und die Hauptvariante ist z3,z4,z5,z6,z7,z8,z9,z10, und ich kann gleich mit Tiefe 9 weitermachen!"

2.)
Und auch bei Ponder=on könnte die Engine gleich sagen:
"z1 habe ich ja selbst gerade gemacht, also ist auch für die jetzt anstehende Ponder-Anlyse die Tiefe=9 bereits erledigt, meine Hauptvariante ist z2,z3,z4,z5,z6,z7,z8,z9,z10 und der Wert ist value10, und ich starte jetzt mit Tiefe 10!"

Dass vorgegangen wird wie in 1.) habe ich aber nirgends beobachten können.
Und auch dass wie in 2.) vorgegangen wird, habe ich bislang nirgends gelesen.

- Wird sowas gemacht?
- Sollte man sowas machen (auch wenn es nicht so wahnsinnig viel bringt)?
- Oder spricht wirklich was dagegen?

Benno

By Benno Hartwig Date 2008-09-09 10:56

Sorry, der Punkt 2.) war, wie ich ihn schreib, natürlich Quark.
Wenn gepondert wird, könnte das Programm aber wie im Fall 1.) vorgehen, also den Zug z2 als Antwort vermuten und dann davon ausgehen, dass Tiefe 8 bereits durchlaufen wurde mit Wert value10 und Hauptvariante z3,z4,z5,z6,z7,z8,z9,z10 um dann gleich mit Tiefe 9 zu starten.

Wird sowas gemacht?

Wenn ich mal frech von Faktor 2,5 ausgehe für den Zeitbedarf zum Erreichen der nächsten Stufe, dann braucht suche(t) 6,25 mal soviel Zeit wie suche(t-2). Der Zeitaufwand ließe sich dann also immerhin reduzieren um den Faktor (1-1/6,25)=0,84.

Benno

By Axel Caro Date 2008-09-09 15:00

Hallo Benno,

deckt sich Deine Frage nicht mit meiner aus dem von Dir erwähnten Thread?

Wird sie dann nicht durch die Erläuterung von Kai Skibbe beantwortet?

http://forum.computerschach.de/cgi-bin/mwf/topic_show.pl?pid=1284#pid1284

Oder verstehe ich Deine Frage falsch?

Ich habe mal im Rybka-Forum gelesen (ich glaube von Larry Kaufman), dass Ponder-on im praktischen Spielbetrieb recht wenig bringt (so um die 10 ELO-Punkte).
Da hat sich mir dann die Frage gestellt, ob und wie man (die Engine) die lange Wartezeit effektiver nutzen könnte. Vielleicht mit der Anwendung von Monte-Carlo?
Zumindest scheint es mir lohnenswert, über eine effizientere Methode zur Nutzung dieser erheblichen Wartezeit-Ressourcen nachzudenken.

Gruß
Axel

By Benno Hartwig Date 2008-09-09 16:02

Zitat:

deckt sich Deine Frage nicht mit meiner aus dem von Dir erwähnten Thread?

Ich denke "nein, nicht wirklich", auch wenn die Themen natürlich zusammenhängen.

In jenem Thread ging es doch um die erneute Nutzung bereits vorhandenenr Hasheinträge.
Da werden die unteren Suchstufen also schon noch einmal durchlaufen, und in dem Maße wir Hash-Einträge gefunden werden, geschieht diese Suche sehr schnell. Bei größeren Suchtiefen werden aber inzwischen auch manche Einträge überschrieben worden sein und müssen neu analysiert werden.
Hast du vielleicht eben in der Breite 18 Halbzüge tief gerechnet und willst nun in der Hashtabelle die Werte der Positionen aus einem Teilbaum der Tiefe 16 Halbzüge herauslesen, so wirst du ggf. nicht alle Werte finden, es sind bei derartigen Tiefen ja auch wirklich schon eine ganze Menge Einträge!

Bei meinem Ansatz in diesem Thread will ich gar keine erneute Suche machen für die Tiefen bis 16.
Wenn die Suche der Tiefe 18 eine Hauptvariante z1,z2,z3,...,z18 ergeben hat mit Wert v, dann möchte ich mich gern ohne weitere Überprüfung darauf verlassen, dass nach den Zügen z1,z2 eine Stellung entsteht, aus der heraus ich mit Suchtiefe 16 eine Hauptvariante z3,z4...z18 mit diesem Wert v bekomme, und ich möchte deshalb sofort mit Suchtiefe 17 beginnen.
Das würde dann auch ggü. der 'erneut Hashtabelle nutzen'-Variante Zeit sparen.

Und ich bin mir unsicher, ob ich hier was die Logik Störendes übersehen habe.

Benno

By Axel Caro Date 2008-09-09 16:57

Klingt logisch. Anstatt schneller von A nach B zu kommen um C zu erreichen, läuft man gleich von B los!

Also

Methode 1 (Neuberechnung): A -> B 10 Sekunden und B -> C 10 Sekunden = Summe 20 Sekunden

Methode 2 (Hashnutzung): A -> B 1 Sekunde und B -> C 10 Sekunden = Summe 11 Sekunden

Methode 3 (Start bei B): A -> B 0 Sekunden und B -> C 10 Sekunden = Summe 10 Sekunden

Vielleicht äußert sich ja mal ein kundiger Programmierer zur Möglichkeiten und Grenzen von Methode 3.

Gruß
Axel

By Benno Hartwig Date 2008-09-10 10:48

Interessanterweise steigt der Nutzen dieser Idee an, wenn es den Entwicklern gelingt, den effektiven Verzweigungsgrad v zu reduzieren.


Grad Bedarf
v    (1-1/(v^2))
--------------------------
6    0.97
5    0,96
4    0,93    
3    0,89
2,5  0,84
2,2  0,79 <-- ist das heute ein realistischer Wert?
2    0,75
1,8  0,69
1,6  0,61
1.5  0,56

Allerdings weiß ich nichts über die Überschreib-Strategienen bei der Hashtabellennutzung heutiger Schachprogramme.
Wenn in einer Suche der Tiefe 18 zum Beispiel dafür gesorgt wird, dass alle Einträge zu Stellungen der ersten 4 Halbzüge nicht überschrieben werden, dann wird in der nachfolgenden Suche (2 Halbzüge weiter) die Engine direkt aus der Hastabelle lesen können, welcher Zug bei Suchtiefe 16 nun der beste ist und wie er zu bewerten ist. OK, die Hauptvariante hat die Engine dann nicht. Aber immerhin.

Was bedeutet das Nichtvorhandensein der Hauptvariante eigentlich für die nachfolgende Suche mit Tiefe 17?
Mit Hauptvariante könnte die Engine mit sehr guter Wahrscheinlichkeit so gut starten, das sofort und während der gesamten Suche in dieser Tiefe jede Menge cuts auftreten.

Ohne Hauptvariante wird die Engine aber vermutlich häufiger mit weniger guten Zügen loslegen, weniger häufig cuts machen und mehr Zeit brauchen.

Geht hier vielleicht von der durch die Hashtabelle eingesparten Zeit ein erheblicher Teil wieder verloren?

Benno