Wie ist es möglich, dass die Lomonosov-Endgame-Tabellenbasis von 2012 immer noch die leistungsstärkste Tabellenbasis ist?

7

Aufgrund von Wikipedia: Endgame-Tabellenbasis ist die Lomonosov-Endgame-Tabellenbasis immer noch die größte Tabellenbasis (mit einer Größe von 140 TB). Jetzt wurde diese Tabellenbasis im Jahr 2012 mit dem Lomonosov 1 berechnet ( Top500-Liste November 2012, Rang 26 ). Der Lomonosov 1 hatte 78.660 Kerne mit ~ 900 TFlop / s (Peak: 1.700 TFlop / s). Wenn ich mir die neueste Top500-Liste (Juni 2016) ansehe, sehe ich, dass der Lomonosov 2 mit ~ 2.100 TFlop / s (Spitzenwert: ~ 2.900 TFlop / s) auf Platz 41 der Welt steht. Computer hat 93.000 TFlop / s.

Ich frage mich also, warum die Lomonosov-Tischbasis nach 4 Jahren immer noch die größte Tischbasis ist. Sollte es mit der wachsenden Computerleistung nicht einfach sein, eine 8-Mann-Tischbasis zu berechnen? Oder ist der Schritt von 7 auf 8 einfach zu groß? Vielleicht würde die Größe exponentiell ansteigen, so dass Standardspeichersysteme damit einfach nicht umgehen können?

Würde mich über alle Informationen zu diesem Thema freuen. Danke im Voraus!

BNetz
quelle
10
Der Schritt von 7 auf 8 ist einfach zu groß. Laut diesem Wikipedia-Artikel sind 7 GB erforderlich, um die Tischbasen mit bis zu 5 Männern (im Nalimov-Format) zu speichern, 1,2 TB, um die Tischbasen mit bis zu 6 Männern zu speichern, und 140 TB, um die Tischbasen mit bis zu 7 Männern zu speichern. Das Speichern einer 8-Mann-Tischbasis erfordert also weit über ein Petabyte Speicherplatz.
dfan
3
@dfan Deine Kommentare sollten eine Antwort sein.
SmallChess
1
@StudentT Ich dachte nicht, dass es definitiv genug war.
dfan
Sie könnten 7-Mann mit gegnerischen Bauern auf denselben Aktenkonfigurationen machen, die als "1" anstatt als "2" gezählt werden, oder so. Dies wäre nur etwa 3x so groß wie der Strom. Außerdem ist der Speicher (über alle Knoten hinweg) wichtiger als die Geschwindigkeit ("TFlops", nicht gerade das beste Maß), denke ich.
Post-It-Note
1
Laut dieser Seite werden für die Berechnung von 8-Mann-TB schätzungsweise 10 TB Speicher und 50 TB RAM benötigt. Ganz zu schweigen von der erforderlichen Zeit - bei diesem Speichervolumen und den Anforderungen für den Direktzugriff ist viel Technologie erforderlich, um die Speicherzugriffszeiten zu verwalten.
MM

Antworten:

3

Ich bin ein Entwickler, der derzeit an Software zur Berechnung von Endgame-Tabellenbasen arbeitet. Der eigentliche Engpass bei der Berechnung von Positionen ist nicht der Speicher an sich, sondern der Arbeitsspeicher und die Rechenzyklen, die zur Berechnung eines Netzwerks für einen exponentiell wachsenden Satz von Positionen erforderlich sind.

Die Anzahl der Positionen wächst exponentiell entsprechend der Anzahl der Männer im Vorstand. Dies bedeutet , dass der Arbeitsspeicher benötigt werden (ob es RAM oder Festplatte liest, sein , das ist weniger teuer und besser skalierbar , aber signifikant langsamer) nimmt proportional zu , A^Nwo Aein Skalierungskonstante (etwas weniger als 64) und Nist die Anzahl der Männer in dem Tischbasis. Der Lomonosov-Supercomputer verwendete 92 TiB RAM , was für eine 7-Mann-Tischbasis ausreicht. Wie Dfan in seinem Kommentar sagte, ist der Sprung zu groß.

Wenn mehr Knoten zur Tabellenbasis hinzugefügt werden, steigt die Anzahl der Berechnungen schneller als linear zur Anzahl der Knoten. Zum Beispiel in einem Datenzugriff binären Suchbaum (BST) ist proportional zu , ln(M)wo Mdie Anzahl der Knoten im Baum; Da M = A^Nfür den einmaligen Zugriff auf jeden Knoten des Baums A^N * ln(A^N)Operationen erforderlich sind. Es gibt mehrere Schritte im retrograden Bewertungsalgorithmus der Tabellenbasis , die ähnlich skaliert werden.

Kurz gesagt, der Speicher nimmt exponentiell zu und die Anzahl der Operationen steigt schneller als exponentiell, wenn mehr Männer hinzugefügt werden. Das Rechnen ist in (zum Zeitpunkt des Schreibens) 6 Jahren noch nicht so weit fortgeschritten.

bcdan
quelle
2

Ich kann keinen Kommentar abgeben, da ich keinen "50-Ruf" habe, aber ich habe mich gefragt, ob man die 7-Tabellenbasis als Teil der Antwort für eine 8-Tabellenbasis verwenden könnte. Haben sie das für die 7 Tischbasis gemacht?

Das heißt, wenn Sie die Lösung für 8 Teile bestimmen, hören Sie auf, wenn Sie 7 Teile haben, und beziehen Sie sich einfach auf die 7 Tabellenbasis. Zugegeben, selbst damit wäre es riesig, weil es immer noch viele Kombinationen geben würde, bevor man zu 7 Teilen kommt, aber weniger als wenn man es herausfinden würde, ohne auf die 7 Tabellenbasis zu verweisen?

Wenn die Lösung eine Methode verwendet, um in die andere Richtung zu gehen, hilft es vielleicht nicht?

Eric
quelle
2
In der Tabellenbasis wird gespeichert, ob eine Position Gewinn, Unentschieden oder Verlust ist. und auch eine Metrik (z. B. DTC - bedeutet Anzahl der Züge, bis die Position in eine andere Kategorie verschoben wird). Es wird nicht "eine Lösung" gespeichert, wie Sie vorschlagen. Stattdessen überprüft die Engine, die die Tabellenbasis verwendet, alle möglichen Bewegungen an einer Position, ordnet die Metriken für jede resultierende Position und wählt eine Bewegung basierend auf der besten Metrik aus. Wenn der beste Zug eine Gefangennahme war, sucht der Motor die Basis für die neue Position, um den nächsten Zug zu ermitteln
MM