Houdini 3-Houdini 3: Nutzen der Bedenkzeitverlängerung

By Patrick Götz (Mod.) Date 2012-12-07 02:13

Kursiv geschrieben sind zwei kleine Übertragsungsfehler korrigiert.

Tiefe   Elodiff.   Ergebnis 
         
1  -  2   222    217,5-782,5  (+82=271-647)
2  -  3   185    256-744      (+75=362-563)
3  -  4   151    295,5-704,5  (+67=457-476)
4  -  5   128    323,5-676,5  (+69=509-422)
5  -  6   122    331,5-668,5  (+69=525-406)
6  -  7   107    350,5-649,5  (+72=557-371)
7  -  8   120    333,5-666,5  (+54=559-387)
8  -  9   175    268-732      (+28=480-492)
9  -  10  123    330,5-669,5  (+39=583-378)
10 -  11   92    370-630      (+29=682-289)
11 -  12   75    393,5-606,5  (+49=689-220)
12 -  13   63    410,5-589,5  (+41=739-220)
13  - 14   63    411-589      (+28=766-206)
14  - 15   46    433,5-566,5  (+36=795-106)

By Patrick Götz (Mod.) Date 2012-12-07 02:33

Und noch einer:


Tiefe   Elodiff.   Ergebnis
        
1  -  2   222    217,5-782,5  (+82=271-647)
2  -  3   185    256-744      (+75=362-563)
3  -  4   151    295,5-704,5  (+67=457-476)
4  -  5   128    323,5-676,5  (+69=509-422)
5  -  6   122    331,5-668,5  (+69=525-406)
6  -  7   107    350,5-649,5  (+72=557-371)
7  -  8   120    333,5-666,5  (+54=559-387)
8  -  9   175    268-732      (+28=480-492)
9  -  10  123    330,5-669,5  (+39=583-378)
10 -  11   92    370-630      (+29=682-289)
11 -  12   75    393,5-606,5  (+49=689-220)
12 -  13   63    410,5-589,5  (+41=739-220)
13  - 14   63    411-589      (+28=766-206)
14  - 15   46    433,5-566,5  (+36=795-169)

By Michael Scheidl Date 2012-12-07 02:37

Danke für diese höchst methodische Analyse! - Soweit ich verstehe, wurde Houdini 3 mit fixierten Suchtiefen eingesetzt?

Dank Deiner Grafik sehen wir sofort ein "interpretationsbedürftiges" Phänomen, nämlich daß 9-8 Plies fast ebensogut abschneiden wie 3-2. Man erkennt einen deutlichen Ausreißer vom abnehmenden Trend. Wieso? Ich glaube kaum daß 1.000 Partien pro Match zu wenig verläßlich sind.

Ich fürchte jedoch, daß die ganze Untersuchung mit modernen Engines daran leidet, daß die "nominelle" Suchtiefe nicht allgemeingültig ist, sondern entweder per Extensions ausgeweitet, oder per Prunings bzw. Reductions reduziert wird. Doch das unterscheidet sich sicherlich je nach Engine...

By Patrick Götz (Mod.) Date 2012-12-07 02:56 Edited 2012-12-07 02:59

[quote="Michael Scheidl"]
Soweit ich verstehe, wurde Houdini 3 mit fixierten Suchtiefen eingesetzt?
[/quote]
Ja.

[quote="Michael Scheidl"]
Dank Deiner Grafik sehen wir sofort ein "interpretationsbedürftiges" Phänomen, nämlich daß 9-8 Plies fast ebensogut abschneiden wie 3-2. Man erkennt einen deutlichen Ausreißer vom abnehmenden Trend. Wieso? Ich glaube kaum daß 1.000 Partien pro Match zu wenig verläßlich sind.
[/quote]

Dieser (einzige) heftige Ausreißer ist mir natürlich auch aufgefallen. Ich habe mir deswegen auch ein paar Partien angeschaut und es scheint alles mit rechten Dingen zugegangen zu sein. Auf die Trendlinie hat der eine Ausreißer von insgesamt 14 Matches allerdings keinen großen Einfluss.

[quote="Michael Scheidl"]
Ich fürchte jedoch, daß die ganze Untersuchung mit modernen Engines daran leidet, daß die "nominelle" Suchtiefe nicht allgemeingültig ist, sondern entweder per Extensions ausgeweitet, oder per Prunings bzw. Reductions reduziert wird. Doch das unterscheidet sich sicherlich je nach Engine...
[/quote]

Was auch immer in der Engine intern abläuft, passiert auf beiden Seiten und ist daher nicht relevant.
Was übrig bleibt ist die 1,75-fache Bedenkzeit für die Seite mit der Tiefe+1.

Gruß
Patrick

By anogamer Date 2012-12-07 07:17

Vielen Dank!
Informativ, Methodisch.
Schon lange keinen so guten Beitrag im Forum gesehen!

By Thomas Cutter Date 2012-12-07 07:25

Sehr schönes Ergebnis.
Allerdings ist die grafische Darstellung etwas irreführend, da Halbzüge eben nur ganze Werte annehmen.
Die realen Werte hätte ich nicht als Spline (oder was es ist) dargestellt.

Die Trendumkehr bei 7-8 und 8-9 ist überraschend.
Wäre interessant zu versuchen, die Ursache herauszufinden.

Gruß Thomas

By Benno Hartwig Date 2012-12-07 10:59

By Benno Hartwig Date 2012-12-07 11:01

Feine Analyse, Patrick, thanx.
In den frühen Jahren des Computerschachs waren die Tiefen noch bescheiden. Colossus auf C64 tat sich schon noch schwer, manches Matt in 4 zu finden, wenn er nur Turniererzeit zur Verfügung hatte!
Das brachte ein zusätzlicher Ply schon gut was.

Heute arbeiten die Engines ja auch mit recht variablen Suchtiefen, mit selektiven extra-Vertiefungen. Wieviel das dann bringt gegenüber einer andersartigen Engines, die ihre eigenen Spitzen aussucht, ist sicher nicht so einfach abschätzbar.

Auch den Partienumfang, den du absolviertest, finde ich schon ganz schön aussagekräftig. Super.

Die Spitze bei Plys=9 ist natürlich auffällig. An Zufall als ausreichende Begründung glaube ich nicht.
Mich würde Interessieren, ob Houdini bei eben dieser Suchtiefe irgendein Feature zuschaltet, was einen erheblichen Effekt hat. Mehr als +150ELO ist ja auch wirklich ein gigantischer Wert für nur einen Ply, der wohl wirklich mit weniger als Zeitverdopplung erreicht wird!!
Vielleicht guckt ja auch Robert mit Interesse auf diesen Pik, und er überlegt, ob sich der hier verantwortliche Effekt auch an anderen Stellen nutzen lässt.

(Oder er hat bereits die Erklärung, dass das nur einmal passieren kann

)

Die Extrapolation des Trends auf Ply-Werte, die weit außerhalb der beobachteten Werte liegt, ist natürlich sehr unsicher.
Welche Trend-Typ hast du denn zugrunde gelegt?

Benno

By Benno Hartwig Date 2012-12-07 12:09

[quote="Benno Hartwig"]Die Spitze bei Plys=9 ist natürlich auffällig.[/quote]An anderer Stelle schreibst du, dass ein Ply mehr etwa 1,75 mal soviel Zeit braucht.
Trifft das auch für diese Übergänge 7->8 und 8->9 zu, bei denen die ELO-Steigerungen deutlich größer waren?
Oder stieg ggf. an diesen Stellen auch der Zeitbedarf ungewöhnlich stark an?

Benno

PS:
Ja, eine feine Basis für diverse Fragestellungen bietet deine Untersuchung.

By Patrick Götz (Mod.) Date 2012-12-07 18:17

Den 1,75 Faktor habe ich nur einmal berechnet, aus den Gesamt-CPU-Zeitverbrauch eines weit fortgeschrittenen Matches ( z.B. 10 Stunden - 17,5 Stunden)
Der Faktor ist im Allgemeinen unabhängig von der Suchtiefe, aber stark abhängig von Fail-High und Fail-Low Situationen.

Patrick

By Michael Scheidl Date 2012-12-07 12:22

Zitat:

Mich würde Interessieren, ob Houdini bei eben dieser Suchtiefe irgendein Feature zuschaltet, was einen erheblichen Effekt hat.

Eine sehr plausible, überzeugend klingende Vermutung... obwohl ich rätsle, was das sein könnte.

By Benno Hartwig Date 2012-12-07 12:47

[quote="Michael Scheidl"]Eine sehr plausible, überzeugend klingende Vermutung... obwohl ich rätsle, was das sein könnte.[/quote]Als ich mit Stockfish herumspielte, verpasste ich der (Haupt)Suche testweise Stellungsbewertungen oder auch eigene Ruhesuchen, wenn denn noch tief genug weitergesucht werden musste (nur dann war der zusätzliche Aufwand vernachlässigbar klein). Und ich spendierte kleine Boni und Mali.
Ich wollte damit bei annähernd gleichbewerteten Endstellungen diejenige leicht bevorzugen, die über Stellungen erreicht wird, die besonders chancenreich aussahen bzw. dem Gegner besonders wenig Chancen und Alternativen boten.

Ein Effekt, der also erst ab einer bestimmte Tiefe wirksam werden konnte.

Leider aber auch ein Versuch, der bei mir zumindest zu keiner Engineverstärkung führte.

Benno

By Benno Hartwig Date 2012-12-07 11:14

Zitat:

Eine Erhöhung der Suchtiefe um 1 bedeutet bei Houdini 3 eine Bedenkzeitverlängerung um Faktor 1,75.

Wie bist du auf diesen interessanten Wert gekommen? Irgendein Mittelwert?
Ich denke halt, dass ein extra-Ply bei komplexem, vollem Brett deutlich mehr Zeit kostet als bei einem recht leeren Brett im Endspiel.

Benno

By Stefan Pohl Date 2012-12-07 11:26

[quote="Patrick Götz"]
Hallo Zusammen,

ich habe mir die Frage gestellt, wie hoch der bekanntlich abnehmende Nutzen der Beidenkzeitverlängerung insbesondere bei hohen Bedenkzeiten ist. Es gibt dazu schon einige Tests, die allerdings auf eine etwas schwächere Datenbasis beruhen und auch keinen weiten Blick in hohe Tiefen wagen.
Ich möchte hier mein (Zwischen-)Ergebnis posten, das bis jetzt auf einer Datenbasis von 14.000 Partien aufbaut. Als Vorgabestellungen habe ich die 500 Stellungen von Stefan Pohls LS Rangliste genommen (vielen Dank an Stefan!) und sie mit Farbwechsel von zwei Suchtiefen (Suchtiefe x gegen x+1) ausspielen lassen. 1000 Partien pro Match sind für eine genaue Bestimmung zwar zu wenig, aber durch die Trendlinie die über alle 14 Matches gelegt ist, können sich idealerweise einzelne Außreißer über alle 14.000 Partien wegmitteln. Ich überlege vielleicht auch noch die Partienanzahl pro Suchtiefe auf 4.000 zu erhöhen, um die Kurve weiter zu glätten.
[/quote]

Hallo Patrick,

sehr, sehr schöne Idee, endlich mal den fallenden Elonutzen pro zugelegtem Halbzug Rechentiefe mit einer wirklich großen Partienzahl nachzuweisen. Ich habe mir erlaubt, dir soeben per mail (ich hoffe, ich hatte die richtige Adresse noch parat...) mal ein neues Vorgabestellungsset aus der FrankQ-Datenbank mit 2500 Stellungen zuzusenden. Wäre für eine noch genauere Analyse sicher nicht die schlechteste Wahl (meine 500 LS-Stellungen stammen auch daraus). Wäre toll, wenn du in dieser Richtung weitermachst!!!

Gruß - Stefan

By Joe Nettelbeck Date 2012-12-10 11:10

Das wäre dann doch eigentlich auch der Beweis dafür, dass zusätzliche Prozessoren irgendwann keinen nennenswerten Nutzen mehr bringen, oder? Also eine Erklärung für das Cluster-Debakel ...

Jenseits einer gewissen Grenze sind Spielstärkeverbesserungen dann wirklich nur noch über die Software zu erreichen. Wie ich es schon immer sagte.

By Thomas Mayer (Quark) Date 2012-12-10 15:07

Hi,

Zitat:

Das wäre dann doch eigentlich auch der Beweis dafür, dass zusätzliche Prozessoren irgendwann keinen nennenswerten Nutzen mehr bringen, oder?

sagen wir's mal so: ein doppelt so schneller Prozessor ist immer besser als doppelt so viele Prozessoren. Beides wird aber gern mitgenommen. Dennoch ist es sehr schwierig, Schach mit beliebig vielen Prozessoren noch sinnvoll zu parallelisieren. Verbesserungen im Such-Algorithmus oder in der Bewertungsfunktion sind allemal besser. BEIDE profitieren dann aber wieder von schnellerer Hardware. Eine perfekte Bewertungsfunktion z.B. würde gar keine Suche benötigen...

Ich glaube nicht, daß Steinitz gegen Gott gewinnt, da oben...

Gruß, Thomas

By Ulrich Wetzel Date 2012-12-10 12:44

Hallo Patrick,

zunächst erstmal vielen Dank für die Veröffentlichung deiner Testergebnisse und die ausführliche Darstellung! Die Ergebnisse sind (bis auf den Ausreißer bei Tiefe 9) im Rahmen der Erwartungen. Allerdings ist es etwas irreführend, wenn du von "Nutzen der Bedenkzeitverlängerung" sprichst. Denn du hast ja den Nutzen von einer zusätzlichen Rechen-Iterationstiefe untersucht. Nutzen der Bedenkzeitverlängerung wäre in etwa folgender Aufbau: Programm X spielt gegen sich selbst. Die eine Instanz hat dabei doppelt soviel BZ wie die andere. Dies dann auf verschiedenen BZ-Stufen. Der Test wäre praxisnäher als das starre Begrenzen auf fest vorgegebene Iterationstiefen. Selbstverständlich würde auch letzterer Testaufbau eine Abwärtstendenz aufweisen, aber beide sind nicht eins-zu-eins vergleichbar.

MfG,
Ulrich

By Benno Hartwig Date 2012-12-10 14:17

[quote="Ulrich Wetzel"]Allerdings ist es etwas irreführend, wenn du von "Nutzen der Bedenkzeitverlängerung" sprichst. Denn du hast ja den Nutzen von einer zusätzlichen Rechen-Iterationstiefe untersucht. [/quote]So ganz grob gilt wohl der Zusammenhang: 1 ply mehr bedeutet doppelte Zeit (oder etwas weniger, wie Patrick feststellte) Insofern lässte Patricks Untersuchung auch prima auf die Auswirkung von
- Rechenzeitverlängerung
- Geschwindigkeitssteigerung
und als obere Grenze auch von
- Vergrößerung der Anzahl von Kernen/CPUs/Rechnern im Cluster
schließen.

Benno

By Ulrich Wetzel Date 2012-12-10 16:25

[quote="Benno Hartwig"]
So ganz grob gilt wohl der Zusammenhang: 1 ply mehr bedeutet doppelte Zeit (oder etwas weniger, wie Patrick feststellte) Insofern lässte Patricks Untersuchung auch prima auf die Auswirkung von
- Rechenzeitverlängerung
- Geschwindigkeitssteigerung
und als obere Grenze auch von
- Vergrößerung der Anzahl von Kernen/CPUs/Rechnern im Cluster
schließen.
[/quote]

Ganz grob mag das gelten, aber man sollte nicht außer Acht lassen, dass es trotzdem einen Unterschied macht, ob ich eine Engine mit fix-X-plies vs. Engine mit fix-X+1-plies spielen lasse oder eben Engine mit X-min-per-game vs. Engine mit 2*X-min-per-game. Der nicht zu unterschätzende Unterschied liegt darin, dass sich die Engine im zweiten Fall die BZ selbst einteilen kann und somit auch entscheiden darf, wieviele Iterationen sie überhaupt in einen Zug investiert. Das kann im Extremfall mal deutlich weniger sein als beim ersten Modell oder auch mal deutlich mehr. Das kann sicherlich einen größeren Unterschied ausmachen.

Außerdem eignen sich Rechentiefevergleiche wie sie Patrick angestellt hat nur für Selfplay-Experimente mit ein und derselben Engine. Dies kann zwar für die Praxis relevant sein (z.B. im Fernschach, wo z.Zt. vermutlich 95% mit Houdini analysieren - somit wäre es wichtig zu wissen, ob es sich für einen Fernschächer lohnt, noch einen weiteren Ply tiefer rechnen zu lassen), muss aber nicht (bei Turnieren spielen nur unterschiedliche Gegner gegeneinander). Insofern muss man immer im Hinterkopf behalten, dass es sich im Grunde genommen um ein Laborexperiment handelt, welches nicht 1:1 in die Praxis übertragbar ist.

Ulrich

By Benno Hartwig Date 2012-12-10 17:41

[quote="Ulrich Wetzel"]...ob ich eine Engine mit fix-X-plies vs. Engine mit fix-X+1-plies spielen lasse oder eben Engine mit X-min-per-game vs. Engine mit 2*X-min-per-game.

Klar, da ist ein Unterschied. 12 plys Tiefe im Mittelspiel haben auch eine andere Bedeutung als im Endspiel. Dass dies bei der Beurteilung der relativen Spielstärke aber sehr gravieren ist, glaube ich nicht.

Zitat:

...dass sich die Engine im zweiten Fall die BZ selbst einteilen kann und somit auch entscheiden darf, wieviele Iterationen sie überhaupt in einen Zug investiert.

Klar ein Unterschied. Aber wir groß mag der denn sein?
Wie groß mag z.B. der ELO-Vorteil sein, die 60 Züge in 60 Minuten macht, gegenüber einer Engine, die immer genau 1 Minute rechnet?

Zitat:

Insofern muss man immer im Hinterkopf behalten, dass es sich im Grunde genommen um ein Laborexperiment handelt, welches nicht 1:1 in die Praxis übertragbar ist.

Klar.
Aber es ist immerhin der Versuch, den Nutzen von Mehrzeit/Geschwindikeitssteigerung/Kernanzahlvergrößerung zumindest einigermaßen abzuschätzen.
Immerhin!!

Benno