SF7 und die Anzahl der Threads

By Tom Paul Date 2016-02-12 11:38

Das ist doch nicht neues, ich dacht du weißt das schon seit Jahren.
Das ist doch auch ziemlich logisch oder nicht?

By Benno Hartwig Date 2016-02-12 11:42

Vor Jahren und eben bei älteren Engines wurde schon mal über solche Effekte gesprochen.
Ich finde das aber überhaupt nicht(!) logisch.
Und ich denke auch nicht, dass das bei allen Engines so ist.

Benno

By Tom Paul Date 2016-02-12 11:44

Deshalb sage ich doch schon seit Jahren das es durchaus sein kann das eine Tiefe größer als 40 weniger bringt und mal lieber unterhalb bleiben sollte und mehr in die Breite gehen sollte.

By Thomas Plaschke Date 2016-02-12 13:58 Upvotes 1

>Ich finde das aber überhaupt nicht(!) logisch.

Ich kalauere mal: Einfach nicht ignorieren

.
Substanzlose Äußerungen werden nicht besser, indem Du ihnen mit Deinen Äußerungen Gewicht verleihst.

All jene, die als Erklärung anbieten, "das Programm sucht mehr in die Breite", bitte ich, mir mal im Einzelnen zu erklären, wie das gehen soll, wenn es nicht für diesen speziellen Fall programmiert wurde (für Komodo habe ich Äußerungen von L. Kaufman in diesem Sinne verstanden).

Der Suchalgorithmus des Programms "beschreibt" den Spielbaum. Die besuchten Knoten werden gerade aufgrund konkreter Kriterien des Algorithmus besucht. Deswegen verhält sich das Programm mit einem Thread deterministisch. Wenn der Suchalgorithmus nicht zwischen "Suchen" mit verschiedener Anzahl Threads unterscheidet, dürfte es logischerweise keine "breitere" Suche in dem Sinne geben, dass andere Äste des Spielbaums besucht werden.

Mir würde Dein Ergebnis einerseits einleuchten, weil die Threads (bspw. durch die Hashtabellen) über Informationen verfügen, die sie zur Steuerung der Suche in ihrem (Teil-)Suchbaum nutzen können. Dadurch erhalten sie Informationen aus den parallel ablaufenden Suchen, die dem single-threaded laufenden Programm eventuell durch Suchbaumabschneidungen zu seinem Nachteil nicht zur Verfügung stehen.
Andererseits sollte die tiefenbeschränkte serielle Suche eines 1-Thread-Programms alle algorithmisch vorgegebenen Knoten des Spielbaums besuchen und am Ende (letzter Ast der letzten zu durchsuchenden Tiefe) den besten Zug zwingend gefunden haben. Etwas anderes können weitere Threads, die eigentlich nur Teile des gleichen Suchbaums absuchen sollten, auch nicht finden.

Es sei denn - und da sehe ich Erklärung für Deine Beobachtung - die spekulativen Teile des Stockfish-Suchalgorithmus (forward-pruning etc.) schneiden mitunter auch bessere Züge ab. - Das ist ein Fakt. - Durch die Suche mit mehreren Threads werden aber mehr Knoten (einige Knoten mehrfach, manche aber - und damit der sie "tragende" Ast - erstmals) untersucht, als mit nur einem Thread. Dadurch erhält das Programm auch Informationen über sonst abgeschnittene Äste des Spielbaums. Durch diese, von anderen Threads zusätzlich ermittelten Informationen kann das Programm letztlich besser spielen.

Man kann natürlich sagen, indem das Programm mehr absucht, suche es "breiter" (- und eine gewisse Person, deren Namen ich nicht zu nennen brauche, könnte sagen, dass sie es genau so gemeint habe).
Diesen Terminus würde ich dafür aber nicht verwenden, weil es sich eigentlich nur um einen (unwillkürlichen und nicht direkt steuerbaren) Seiteneffekt des Suchalgorithmus mit mehreren Threads handelt.

Daraus wäre zu schließen, dass Stockfish umso weniger ("ver"-)spekulativ sucht/spielt je mehr Threads eingesetzt werden können. (-Jetzt bitte nicht sagen: "taktisch dichter sucht"! Das stimmt nämlich auch nicht.)

Daraus könnten sich interessante Konsequenzen ergeben. Bspw.:
Was folgt daraus für die Ranglisten, die singlethreaded testen?
Auch dürften Untersuchungen über die Effizienz der Parallelsuche (die Relation Tiefe zu Spielstärke) unter einem neuen Aspekt zu betrachten sein.

Schönen Dank für den Test, Benno!

Viele Grüße
Th. Plaschke

By Heiko Bruns Date 2016-02-12 16:28

Hallo,

unter welchen Konditionen hast du das gespielt?
Zeit, Eröffnungen etc.

Ich würde das gerne mal mit Komodo wiederholen.

Gruß Heiko

By Benno Hartwig Date 2016-02-12 16:50

Ich habe eben keine Zeitvorgabe gemacht sondern eine feste Tiefe vorgegeben, unter Arena 5.1.
Auf meinem schlappen Notbook wählte ich 17 Plys, das ergab Partien, die ungefähr 5 Minuten dauerten.
Als Buch für alle Teilnehmer nutzte ich Perfect2015.
Das Notebook hat einen recht langsamen (aber sparsamen) i3-Prozessor, 2 Kerne, mit Hyperthreading.

Ja, mich würde interessieren, ob Komodo das ähnlich macht.
Während Stockfish 7 mit 4 Threads bei mir stärker ist als mit nur 2 Threads, hatte sich sowas bei Komodo 8 aber nicht abgezeichnet.

Benno

By Stefan Pohl Date 2016-02-14 07:41 Upvotes 1

Benno Hartwig schrieb:

"Wenn eine Engine eine bestimmte Tiefe durchrechnet, dann erreicht sei ein bestimmte Spielstärke, egal wie viele Threads sie benutzen durfte!"
hatte ich naiv gedacht und ein kleines Turnier mit SF7 bei 1, 2 und 4 Threads aufgesetzt.
Fest eingestellt Suchtiefe: 17 (also keine Zeitvorgabe)
Heraus kam:

<code>   Motor    Punkte
1: Stockfish 7 x64 popcnt 4T   551,5/1016
2: Stockfish 7 x64 popcnt 2T   494,0/1017
3: Stockfish 7 x64 popcnt 1T   479,5/1017</code>

Bei gleicher Suchtiefe sind also die mit vielen Threads gefunden Züge im Durchschnitt einfach besser!
Die Nutzung vieler Threads bringt die Engine also nicht nur ggf. schneller auf Tiefe, auch die bei diesen Tiefen erreichte Qualität ist höher.

Fand ich schon erstaunlich!
Dies spielt natürlich auch in die Thematik "HT nutzen, ja/nein".
Benno

Moin Benno,

ich finde das Ergebnis logisch bzw. erwartbar. Aus dem einfachen Grund, daß bei parallel laufenden Threads die Suche bzw. die Beschneidung des Suchbaumes nicht so effektiv ist (nicht sein kann), wie im singlethread-mode, da der Alpha-Beta-Algorithmus nun mal im Kern ein rekursiver Algorithmus ist. Also wird bei parallel laufenden Threads insgesamt (prozentual) weniger weggeschnitten, was im Umkehrschluß logischerweise bedeutet, daß einfach mehr Stellungen durchgerechnet werden. Das bedeutet wiederum logischerweise, daß bei gleicher Suchtiefe dann weniger übersehen wird und werden kann. Also wird das Suchergebnis qualitativ (schachlich) besser, aber eben auch weniger effizient (zeitlich). Nur letzteres fällt bei deinem Experiment natürlich unter den Tisch, da nicht mit einer Bedenkzeit, sondern mit maximaler Suchtiefe als Vorgabe gerechnet wird.
Ergo, alles so, wie es zu erwarten war.
Trotzdem schön, daß du es mal probiert und damit verifiziert hast.

Gruß - Stefan

By Benno Hartwig Date 2016-02-14 22:42

Ja, Stefan, Thanx, du magst Recht haben mit dieser Erklärung.
Benno

By Frank Brenner Date 2016-02-14 23:08 Edited 2016-02-14 23:26

> .... Das bedeutet wiederum logischerweise, daß bei gleicher Suchtiefe dann weniger übersehen wird und werden kann. ....

Dein kompletter Text ist falsch.

Der Kernpunkt deines Irrtums liegt in diesem obigen Satzsegment.

Die in der parallelen alpha-beta Suche zuviel besuchten Äste liefern ein Ergebnis zurück welches nicht zurück zur Ausgangsstellung propagiert wird.
Die Singlethread Suche dagegen kann häufig zuerst den Widerlegungsast duchrechnen und würde dann den von der parallelen suche ungeschickterweise doch noch durchgerechneten Zug von vorne herein abschneiden.

Kurz: Die mehrarbeit der parallelen alpha-beta Suche im Vergleich zur singlethread Suche ist für den Mülleinmer und hat niemals Einfluß auf die Wurzelstellung, also auf den letzlich von der Engine gewählten Zug und dessen Bewertung und dessen hauptvariante.

Aber wie kann man Bennos Ergebnis doch noch erklären ?

Bei Stockfisch findet zwar auch eine alpha-beta Suche statt, aber zusätzlich werden noch sehr viel häufiger rein spekulative Schnitte durchgeführt.
Es ist also eine spekulative alpha-beta Suche. Deswegen ist der Verzweigungsfaktor auch nicht etwa 5 sondern etwa 2.

Spekulative Schnitte sind sehr häufig korrekt, aber gelegentlich fehlerhaft.
Wenn jetzt die Parallele Suche - aufgrund der nicht perfekten Parallelisierung - den spekulativen Schnitt nicht durchführt und den Ast mühselig durchrechnet und hinterher feststellt, dass sich das Ergebnis doch bis an die Wurzel propagiert und durch den in der Singlethread Suche gefundenen Widerlegung nicht überschrieben wird, so kann die parallele Suche in seltenen Fällen ein besseres Ergebnis erzielen.

Im Durchschnitt lohnt sich der auf diese Weise erzielte Qualitätszuwachs für die singlethreaded Suche nicht weil der sich durch deutlich mehr Zeit erkauft wird.
Die Multithreaded engine gräbt also im Schlamm mit ihrer nicht perfekten Suche und findet ab und zu einen Diamanten.

> Trotzdem schön, daß du es mal probiert und damit verifiziert hast.

Eine noch größere Geringschätzung für Bennos sehr gutes Experiment ist dir wohl nicht eingefallen, was ?

By Benno Hartwig Date 2016-02-15 08:13

> Dein kompletter Text ist falsch.

Ich hatte beim Lesen von Stephans Text schon gemeint, dass er nicht die schulmäßigen Alpha-beta-Cuts meint, sondern die spekulativen Cuts, die ja auch meist einen Bezug haben zu den jeweils aktuellen alpha-beta-Werten.

Aber du hast natürlich Recht:
Reines (schulmäßiges) alpha-beta generiert dir, egal wie viele Threads, mit weniger Aufwand genau das Ergebnis, welches das vollständige Minimax auch erbracht hätte.

Benno

By Frank Brenner Date 2016-02-15 12:04

> ich hatte beim Lesen von Stephans Text schon gemeint, dass er nicht die schulmäßigen Alpha-beta-Cuts meint, sondern die spekulativen Cuts,

Hat er nicht, er hat den Effekt allein damit begründet dass die parallele Suche nicht so effektiv sein kann wie die single threaded suche.

Dass er den Sachverhalt nicht verstanden hat siehst du auch an den folgenden Äusserungen:

> Ich finde das Ergebnis logisch bzw. erwartbar.
> Aus dem einfachen Grund...
> was im Umkehrschluß logischerweise bedeutet
> Das bedeutet wiederum logischerweise,
> Ergo, alles so, wie es zu erwarten war.