Bester Zug

By Benno Hartwig Date 2014-10-14 14:46 Edited 2014-10-14 14:49

Nach meiner Erfahrung gelten folgende Aussagen für alle Engines. Bitte Hinweis, wenn ich da falsch liege:

1.)
Beim Rechnen mit nur einem Thread und gleichen Rahmenbedingungen kommen die Engines gut reproduzierbar mit dem selben Zug.
Das ist wohl der, den sie einfach als besten errechnet haben.

2.)
Beim Rechnen mit mehr als einem Thread ist dies nicht so gegeben:
Es können leicht unterschiedliche Bewertungen der Züge herauskommen, so dass dann auch eben mal ein anderer tatsächlich ausgeführt werden kann.
Warum das so ist? Weiß ich nicht wirklich.
Die Laufzeit der einzelnen Teilproblemlösungen mag unterschiedlich sein, weil mal Infos für beta-Cuts rechtzeitig zur Verfügung stehen und mal nicht. Das hat dann Folgen für die gesamte Parallelverarbeitung. Das führt eventuell zu unterschiedlich langen Zeiten für bestimmte Rechentiefen, und bei gegebener Zeit eben auch zu unterschiedlichen Ergebnissen.
Aber ob dies als Erklärung ausreicht? Vermutlich nicht.

Ggf. gibt es noch wirksamere Gründe (Hat jemand eine bessere Erklärung?)

3.)
Je nach der Größe des MV-Wertes können die Züge leicht unterschiedlich bewertet werden.
Das kann sie ggf. auf die Reihenfolge der Züge auswirken, ein anderer Zug wird gewählt.

Neben den nicht-Spekulativen Cuts gibt es eben auch spekulative, durch die drastische Beschleunigungen kommen, durch die aber auch Fehlermöglichkeiten auftreten. "Meistens superschnell und -tief, selten mal ein (kleinerer) Fehler --> Spielstärkesteigerung"
Ja, an dieser Stelle ist ein kleines Lotterie-Moment eingebaut, allerdings eines, welches die Engine im Durchschnitt deutlich stärker spielen lässt.
Warum sich das ggf. erst bei MV>=2 und mind. 2 Threads auswirken sollte, weiß ich nicht. Tus aber vielleicht.

Ergo:
Die Engine macht immer den Zug, den sie für den Besten hält!
Da sich aber die Bewertungen der Züge je nach Rahmenbedingung leicht ändern können, kann auch mal ein eben noch geringfügig schlechter bewerteter Zug auf Platz 1 kommen und gezogen werden.

Benno
(der auch gern Konkreteres erfahren würde über die Gründe für dieses wankelmütige Verhalten der Engines bei Threads>1 und verschiedene MV)

By Heinz Hagenstein Date 2014-10-14 15:34

Danke für die schnelle Antwort,

im MV Modus sind oft 2 Züge gleichwertig dann muß der Rechner entscheiden welchen er ausspielt,genauso ist es dann ja auch im Ein-Varianten Modus.

Ja deine Antwort war aufschlußreich,vielleicht erfahren wir ja noch genaueres.

Gruß Heinz

By Michael Scheidl Date 2014-10-14 15:56

Zitat:

(der auch gern Konkreteres erfahren würde über die Gründe für dieses wankelmütige Verhalten der Engines bei Threads>1 und verschiedene MV)

Ich auch; das ist die erste allgemeine Verunsicherung

bei Analysen. Bisher denke ich mir immer, es wird wohl mit Hintergrundaktivitäten des Betriebssystems zu tun haben, die ja auch, und immer anders, stattfinden wenn keine sonstige Anwendung läuft. Also z.B., wenn dadurch vielleicht Threads manchmal ein paar Mikrosekunden länger auf einen Speicherzugriff warten müssen oder so (laienhaft vermutet), kommt schon ein anderes Datengemisch sozusagen zu Stande.

Hierbei nehme ich an, daß das Phänomen umso häufiger auftritt bzw. zu beobachten ist, wenn zwei oder mehrere Forstetzungen innerhalb einer engen Bewertungsbandbreite liegen. Also, ein "leichter, klarer einziger bester Zug" wird - hoffentlich

- immer herauskommen, obzwar vielleicht nicht auf derselben Tiefe und/oder nach derselben Rechenzeit.

Zu meinem Schrecken mußte ich entdecken, daß bei Deep Fritz 13 auch bei Singlethread so ein Verhalten auftreten kann. Die Engine schwankte in einem Einzeltest zwischen zwei Zügen hin- und her und der Rechenverlauf war jeweils verschieden und überhaupt nicht reprodzierbar. Natürlich stets nach Neustart der Engine und bei identischer Hashgröße. Das war allerdings in einer von mir schlecht gewählten Stellung, wo zwei eher banale Eröffnungszüge offenbar, nach Enginemeinung, fast gleich stark sind. Trotzdem ist mir das schleierhaft...

In einer praktischen Analyse würde ich dann auf Multi-PV schalten, zwei oder drei Varianten, und dann muß die Engine die jeweiligen Bewertungen der Lieblingszüge gleichzeitig darstellen. Braucht halt dann nur etwas länger bis zur gewünschen Rechentiefe. Sind dann mehrere sehr nahe beieinander mit der Eval, dann darf man sich den wirklich besten individuell herauspicken. So hat wenigestens das Eigenhirn noch etwas zu tun.

By Hauke Lutz Date 2014-10-14 17:05 Edited 2014-10-14 17:08

Ich arbeite bei Analysen mit MV=6 und 6 Kerne und bei mir reproduziert sich die Bewertung ziemlich gut.
Sich aus den vielen spielbaren Varianten die Lieblings/Geheimvariante auszusuchen macht Sinn.

By Benno Hartwig Date 2014-10-14 22:29

Mit welcher Engine hast du das beobachtet?
In http://forum.computerschach.de/cgi-bin/mwf/topic_show.pl?pid=77752 skizzierte ich, wie SF bei verschiedenen MV werten den einzelnen Zügen recht unterschiedliche Bewertungen gönnte und wie insb. der beste Zug bei verschiedenen MV-Werten durchaus unterschiedlich sein kann.
Fand ich sehr überraschend.
Bei mehreren Durchläufen für bestimmte MV-Werte mag hingegen (zumindest bei 1 Thread) meistens dasselbe herauskommen. Das weiß ich nicht.

Benno

By Hauke Lutz Date 2014-10-14 22:50 Edited 2014-10-14 22:54

Ich nutze meist Komodo 8 und habe bei Tiefe 23/24 sehr gut reproduzierbare Bewertungen, aber das kann natürlich auch an den Stellungen liegen.

By Benno Hartwig Date 2014-10-14 23:08 Edited 2014-10-14 23:10

Bitte teste doch mal, wie Komodo 8 sich bei verschiedenen MV-Einstellungen verhält, am Besten in Stellungen, in denen es mehrere annähernd gleichgute Züge gibt.
Ändern sich die Bewertungen für die ersten 5 Züge?
Ändert sich ggf. sogar die Reihenfolge, wenn du MV variierst?

Insbesondere bei Einstellung "Feste Tiefe=" hatte ich naiv erwartet, dass ein Zug, der mal unter den Besten mit einer Bewertung auftaucht, auch bei größeren MV-Werten mit demselben Wert erscheint. Aber so war es bei SF nicht mal annähernd.

Benno

By Hauke Lutz Date 2014-10-14 23:33

Komodo 8, Tiefe 23, 6 Kerne (HT off), 2 GB Hash

MV=6
d4 = 0,25
e4 = 0,18
Sf3 = 0,14

MV=5
e4 = 0,22
d4 = 0,19
Sf3 = 0,18

MV=4
d4 = 0,24
e4 = 0,21
Sf3 = 0,17

MV=3
d4 = 0,25
e4 = 0,17
Sf3 = 0,15

MV=2
d4 = 0,24
e4 = 0,20

MV=1
d4 = 0,22

Bis auf MV=5 ist die Abfolge identisch und die Bewertung unwesentlich anders.
Gruß, Hauke

By Benno Hartwig Date 2014-10-15 07:03

Thanx.
Also schon (erstaunlicherweise auftretende) Schwankungen, die aber recht klein sind.
Bei Stockfish beobachtete ich unterschiedliche Bewertungen ein und desselben Zuges (bei gleicher Engine, gleicher Tiefe, nur anderem MV-Wert), die immerhin um satte 0,2 Bauern differieren konnten.
Das hat dann ggf. schon empfindlichen Einfluss auf die Reihenfolge.

Jede Kurve beschreibt die Bewertung eines Zuges für verschiedene MV-Werte.
In diesem Beispiel hat d4 immerhin immer an erster Stelle bleiben dürfen.

Benno

By Benno Hartwig Date 2014-10-15 08:53

ergänzende Erklärung:
Hier wurde die Ausgangsstellung analysiert.
Ganz rechts die MV=1-Situation: nur d4 wurde als bester Zug mit Bewertung angezeigt
weiter nach links steigen die MV-Werte und damit die Anzahl der Kurven, die hier ankommen.
(Wenn zwei Linien hintereinander zu liegen kommen, zeichnet Excel leider nur eine davon sichtbar)
ganz links haben wir MV=20, hier sind alle Züge ausdrücklich bewertet worden.

d4 hat also Bewertungen (je nach MV-Wert), die zwischen +0,22 und +0,43 schwanken
c4 torkelt zwischen +0,01 und +0,22
und für a4 werden von Stockfish, bei ansonsten gleichen Bedingungen, aber je nach MV-Einstellung, Werte zwischen -0,13 und -0,37 angeboten.

Benno

By Ralf Mueller Date 2014-10-14 17:53

Nach meinem Verständnis verhält es sich so: Bei Nutzung mehrerer Kerne wird die zu erledigende Arbeit (Berechnung einer Stellung) auf mehrere Arbeiter (in diesem Fall Kerne) verteilt. Diese Arbeitsaufteilung ist jedoch sehr verzahnt, zur größtmöglichen Effizienz tauschen sich die Arbeiter andauernd über ihre erreichten Ergebnisse aus. Dadurch, dass die Arbeiter parallel aber noch andere Prozesse erledigen müssen (das Schachprogramm ist ja nicht der einzige geöffnete Task des Computers), können sie nicht ihre volle Konzentration auf die Stellungsberechnung legen. Diese nebenher zu erledigenden Prozesse sind natürlich unregelmäßig und damit entstehen auch kleine, winzige Unterschiede in der Aufgabenbearbeitung jedes einzelnen Kernes. Diese winzigen Unterschiede können aber gravierende Auswirkungen durch die extreme Verzahnung und ständige Abstimmung zwischen den Arbeitern haben.

Ein klassisches Beispiel dafür sind sogenannte Races: Die Ausgangssituation ist die, dass beide Kerne die Aufgabe haben, eine Zahl mit 1 zu addieren und damit die alte Zahl zu überschreiben. Idealerweise erfolgt die Abarbeitung so verzahnt, dass zunächst Kern 1 die Zahl mit 1 addiert und dann Kern 2 die neue Zahl mit 1 addiert, dann wieder Kern 1 usw. Sollte es jedoch zu winzigen Verschiebungen kommen, könnte das schon bedeuten, dass Kern 2 noch die alte Zahl mit 1 addiert, also die Zahl, die Kern 1 gerade auch addiert. Das Endergebnis könnte vollkommen verschieden sein. Die Parallelisierung von Schachprogrammen ist natürlich weit komplexer und solche Sachverhalte durch verschiedene Mechanismen weitestgehend verhindert, aber dennoch bleibt das Grundproblem, nämlich dass kleinste Unregelmäßigkeiten durch die enorme Geschwindigkeit und Effizienz schon große Auswirkungen haben können, das gleiche.

By Wolfram Bernhardt Date 2014-10-14 21:03

Hi!

Das Wichtigste wurde schon mehrfach gesagt: Wenn es einen mit deutlichem Abstand stabil besten Zug gibt, wird der auch gewählt, egal ob Single- oder Multi-Thread.

Interessant ist die Frage nur, wenn es zwei oder mehr Züge gibt, die sehr dicht beieinander liegen.
Was dann passiert, hängt stark vom Algorithmus ab.

1) Sinlge-Thread
a) deterimnistisch / ohne Zufallsanteil: Normalerweise ist Schach-Code deterministisch und sollte unter denselben Umständen denselben Zug liefern. "Deterministisch" soll hier bedeuten "ohne absichtlichen Zufalls-Anteil". (Computercode ist immer eigentich deterministisch, auch der Zufallsgenertor).
b) nicht deterministisch / mit Zufallsanteil: Es ist auch denkbar, dass Single-Thread-Programme in einem schmalen Bewertungsbereich einen von mehreren Züge zufällig auswählen. Einfach damit das Spiel abwechslungsreicher aussieht. So werden Eröffnungsbibliotheken ja auch genutzt.

2) Multi-Thread
Multi-Threading ist natürlich schwieriger und es kommt eher zu Effekten, die zu unterschiedlichen Zügen führen. Das ist vor allem eine Timing-Frage. Es werden letztlich mehrere Züge gleichzeitig untersucht, jeden Zug fliesst eine gewisse Menge CPU-Leistung ein und es lässt sich nicht exakt vorhersagen, wie weit die Suche jedes Zuges gerade ist.
Das Programm muss irgendwann entscheiden, dass die Zugberechnung beendet werden soll (die Zeit drängt ja immer). Und zu dem Zeitpunkt liegen für alle interessanten Züge Wert vor und der beste wird genommen, der zweitbeste nicht.
Beim nächsten Durchlauf ist die Menge der eingeflossenen CPU-Leistung vielleicht geringfügig anders, so dass ein Zug, der im letzten Durchlauf auf Platz 2 gelanden ist, nun etwas genauer berechnet wurde und sich herausstellte, dass er doch einen Ticken besser ist. Und so landet diesmal dieser auf Platz 1.
Das ist dieses Wechsel-Phänomen bei Multi-Threading.

Viele Grüße,
Wolfram