Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / CSS-Forum / 7+n Steiner, wie verhält sich Berechnungszeit
- - By Philipp Date 2014-06-05 10:43
Hallo

Ich habe im Internet gesucht, aber über eine mögliche 8 Steine und mehr Datenbank in Bezug auf die Realisierung nichts gefunden.

Grob über den Daumen kann man ja sagen. Es gibt 5 verschiedene Figuren (Bauer, Springer, Läufer, Turm, Dame) und 57 restliche Felder vom 7 zum 8 Steiner.

Damit käme ich auf einen Faktor 285.

Der benötigte Speicherplatz für den 8 Steiner wären also 135 TB * 285.

Für einen Supercomputer kein Problem, er brauch nicht mal 10000 4 TB Festplatten.

Jetzt ist die Frage.

Wie viel mehr Berechnungszeit brauche ich, sind das deutlich mehr als das 285-fache ?

Für den 7 Steiner brauchte man 6 Monate auf einem Computer, der lediglich 3600 Kerne hatte.

Moderne Supercomputer sollten die Rechenleistung von 1 Mio Kerne haben, genau weiss ich es nicht, aber man könnte auch Many Core Systeme verwenden.

Das ganze ist natürlich eine Kostenfrage, da wohl kaum jemand das Geld aufbringt einen Supercomputer mal eben ein Jahr zu mieten.

In wieviel Jahren wird sich wohl jemand an die Lösung machen ?
Parent - By Benno Hartwig Date 2014-06-05 12:59 Edited 2014-06-05 13:09

> Damit käme ich auf einen Faktor 285.


Ich bin mir unsicher, ob die Betrachtung nicht zu einfach ist.
Manche der bekannten Stellungen (z.B. reine Figurenstellungen) sind ggf. einmal in der DB und werden per Spiegelung und Drehung mehrfach genutzt. Und wenn du nun einen Bauer irgendwo dazusetzt, dann musst du jede Drehung und Spiegelung gesondert und mit anderen Bewertungen betrachten.
Aber ggf. ist der Anteil solcher Stellungen auch nur recht klein.

Die Rechenzeit hängt ja ab von der Anzahl der zu betrachten Stellungen und von der Zugzahl, die notwendig ist, um jeder Stellung eine Bewertung zu verpassen. Ich wäre nicht überrascht, wenn diese Zugzahl beim 8-Steiner ein ein Mehrfaches von der des 7-Steiners ist. Damit wäre dann der Rechenaufwand auch ein Mehrfaches des 285-Fachen. (285 ist wohl auch etwas zu groß, denn der Bauer können ja ggf. nicht überall hin, andererseits muss ggf. noch etwas auf Rochaderechte und ep-Rechte geachtet werden)
Ich habe aber keine Vorstellung davon, was hier das 'Mehrfache' konkreter sein könnte.

Benno
Parent - - By Michael Bechmann Date 2014-06-05 20:57
Grob über den Daumen komme ich auf 6 verschiedene Figuren: König, Dame, Turm, Läufer, Springer, Bauer.

Fragen:
- Welche 135 TB?
- Wie kommt man an ein "Faktor 285" und zum welchem Produkt soll es führen? 57*7 oder 57*8 ist jedenfalls nicht 285.
- Was heißt "er brauch nicht mal 10000 4 TB"? Was für 10000? Was für 4 TB? Wozu soll der Computer sie brauchen?

Zur Frage an sich: Es gibt erst dann eine Motivation, Endspieldatenbanken für 8 Figuren wenn man die 7-Figuren-Endspieldatenbanken zur Verfügung hat.
Gerüchteweise sollen sie in der Universität Moskau gespeichert sein. Gesehen hat sie bisher keiner und wenn sie dort existieren sollten aber keiner benutzen kann oder darf ist es
so, als existierten sie gar nicht.
Parent - - By Michael Scheidl Date 2014-06-05 21:12
Ich hab's zwar selbst nicht, aber soviel ich weiß hat man mit Aquarium einen Onlinezugriff auf diese Siebensteiner. Ich nehme an, etwa so wie die Online-Sechssteinerabfrage in Shredder Classic.

Was Achtsteiner betrifft, so bin ich skeptisch ob man dafür so gigantische Computerressourcen verbrauchen sollte bzw. darf. Schach ist ein Spiel. Wir haben wahrlich dringendere Probleme auf der Welt, meine sogar ich als großer Computerschachfan. Für die nächsten 100 Jahre könnten wir es ruhig bei Sechs- bis Siebensteinern bewenden lassen.
Parent - - By Michael Bechmann Date 2014-06-05 21:25 Edited 2014-06-05 21:28
Dann sollte Chessbase diese Abfrage in der nächsten Version auch ermöglichen. Das wäre dann eine Neuerung, zumal die Version 14 keine neuen Funktionen enthalten waren.
Oder man erweitert die Shredder-Frage im Internet auf 7 Figuren.

Ich würde die 8-Endspieldatenbanken schon gern nutzen wollen und das nicht erst in 100 Jahren.
In den letzten 20 bis 30 Jahren waren die Festplattenkapazitäten in durchschnittlichen PC jährlich 2 mal größer. Somit sollten wir in 10 bis 15 Jahren Jahren Speichermedien im PC haben, die auch die Datenmenge vertragen.
Parent - - By Olaf Jenkner Date 2014-06-05 21:44
Und das geht natürlich so weiter.
Wir hatten auch ewige Zeiten eine Verdopplung der Taktfrequenz alle zwei Jahre.
Mein Rechner lief vor zehn Jahren mit zwei Gigahertz. Heute haben die schnellsten PC vier.
Parent - - By Michael Bechmann Date 2014-06-05 23:16 Edited 2014-06-05 23:26
Wobei man unwillkürlich zur Spekulation kommt, wann Schach vollständig gelöst ist, also man keine Eröffnungsbücher und Endspielbücher mehr braucht sondern nur eine einzige Datei.
Unmittelbar danach ist die Frage natürlich, wie groß ist der vollständige "Schachbaum". Eine superschnelle CPU hätte sich dann auch erübrigt, denn man müsste nur die Stellung finden.
Die Anzahl der möglichen Stellungen und Züge zu berechnen müssen Experten berechnen.

Optimisten schätzen, dass Schach im nächsten Jahrhundert gelöst sein sollte. Pessimisten meinen, dass man nie alle Stellungen erfassen kann sondern nur einen ganz kleinen Bruchteil. Sie begründen das damit, dass es niemals Speichermedien geben kann
um alle Stellungen oder sogar alle denkbare Partien abzuspeichern.

Ich bin Optimist: Vor 30 Jahren hatte ich zum ersten Mal eine 8-Zoll-Diskette gesehen - etwa so groß wie eine Langspiel-Schallplatte - und war beeindruckt, weil man über 100 Seiten Text darauf speichern konnte und 1990 hatte ich den ersten PC (Euro-XT) mit 20 MB und bis 1992 war ich überzeugt, dass ich diese Festplatte für den Rest des Lebens nie füllen würde. Dass ich heute 3-TB-Platten hätte, war mir damals undenkbar.

100 Jahre ist möglicherweise aber zu wenig. Ich schätze mutig mal, es könnte 500 bis 1000 Jahre sein. Ob man in 1000 Jahren noch Schach spielt oder ob es völlig uninteressant geworden ist und deswegen nach der endgültigen Lösung gar nicht mehr forscht ist eine andere Frage.
Parent - By Olaf Jenkner Date 2014-06-05 23:26
Lies dir meinen Beitrag bitte nochmal aufmerksam durch.
Parent - By Benno Hartwig Date 2014-06-07 11:40 Edited 2014-06-07 11:51

> Wir hatten auch ewige Zeiten eine Verdopplung der Taktfrequenz alle zwei Jahre.
> Mein Rechner lief vor zehn Jahren mit zwei Gigahertz. Heute haben die schnellsten PC vier.


Klar, Entwicklungen können an Grenzen stoßen, denen sie sich ggf. nur noch annähern können.
Andererseits: Ist die Entwicklung der Rechenleistung nicht doch wie seit vielen Jahren gewohnt weitergewachsen?

Die Taktrate wuchs nur noch langsamer (oder manchmal gar nicht mehr). OK.
Die Kernanzahl wuchs aber (mein läppischer Arbeitsplatzrechner hat 'natürlich' 4 Kerne)
der Bedarf an Takten für eine Operation ist ggf. weniger geworden (wie viele Takte brauchte ein Pentium 1 für eine Division, wie viele heute ein i7?)
und wir nutzen 64 statt 32 bit.
Sind nicht auch die Hauptspeicherzugriffe schneller geworden und mehrstufige Caches schneller und größer?
Hyperthreading wird oft Leistungsfördernd eingesetzt.
(was vergessen?)

Ich habe gar nicht den Eindruck, dass die jährliche Steigerung der Rechenleistung des 'typischen PCs' wirklich kleiner geworden ist. Aber sie wird nicht so sehr durch die Taktrate bestimmt.

Wie lange das noch so aufrecht erhalten werden kann, weiß ich aber auch nicht.
128 Kerne kann ich mir ja vorstellen, aber eine Wortbreite 1024 bit kommt mir suspekt vor. Aber wer weiß.

Benno
Parent - By Stefan Pohl Date 2014-06-08 07:18
Olaf Jenkner schrieb:

Und das geht natürlich so weiter.
Wir hatten auch ewige Zeiten eine Verdopplung der Taktfrequenz alle zwei Jahre.
Mein Rechner lief vor zehn Jahren mit zwei Gigahertz. Heute haben die schnellsten PC vier.


Ja, das stimmt. Pro Kern gerechnet, geht es kaum noch vorwärts, was die Geschwindigkeit angeht. Wohl primär ein Kühlungsproblem. Dort könnten neuartige Chips aus Graphen die Lösung sein. Das ist aber noch Grundlagenforschung. Aber ich habe vor kurzem gelesen, daß CPUs aus Graphen mit so wenig Strom auskommen (könnten, wenn sie denn erst mal existieren), daß wohl Taktraten von 200 GHz machbar sein werden.
Prinzipiell muß ja demnächst bei der CPU-Entwicklung etwas Revolutionäres passieren, denn die klassische Fertigungstechnik nähert sich dem physikalischen Ende. Die Strukturen sind ja jetzt schon bei 22 Nanometer und bald sollen 14 Nanometer bei Intel kommen. Und irgendwo im Bereich von 1-5 Nanometer (darüber gibt es unterschiedliche Meinungen) ist bei der bisherigen Bauweise Schluß, weil dann die Leiterbahnen so dicht beieinander liegen, daß die Elektronen bei Stromfluß einfach überspringen - also Kurzschluß.
Ergo muß sehr bald ein völlig neues Konstruktionsprinzip her. Sei es nun Graphen-CPUs oder 3D-Chips oder was immer. Denn die bisherige Entwicklung wird sehr bald an ihr Limit stossen.

Stefan
Parent - - By Benno Hartwig Date 2014-06-07 10:43

> Wie kommt man an ein "Faktor 285"


Ausgehend von einer Stellung mit 7 Steinen (unter denen schon die beiden Könige sind) haben wir 57 freie Felder, auf die wir jetzt Dame, Turm, Läufer, Springer oder Bauer setzen können um zu einer 8-Stein-Stellung zu kommen (OK, viele Stellungen davon sind illegal und fallen gleich wieder raus. Auf jede 7-Steiner-Stellung kommen also erst mal 5 mal 57 gleich 285 8-Steiner-Stellungen, von denen aber gleich ganz viele wieder rausfliegen.
Auch werden wir auf diese Weise Stellungen doppelt konstruieren. Es werden also wieder weniger.
Es könnten aber auch wieder einige hinzukommen, da die 7-Steiner-Stellung ggf. wegen Symmetrien mehrfach genutzt wird, während ein hinzugenommener Bauer diese Symmetrien nicht mehr zulässt. Aber das macht den Kohl vermutlich nicht fett.

Aber ich vermute, so kam die Zahl 285 in das Gespräch.

Benno
Parent - - By Michael Bechmann Date 2014-06-07 13:57 Edited 2014-06-07 14:00
Unter Berücksichtigung der Symmetrien müssten sich die verschiedenen Stellungen auf 1/2 oder auch 1/4 reduzieren, weil nach der Spiegelung auf eine senkrechte Achse ((zwischen d1/e1...d8/e8) oder waagerechte Achse (a4/a5...h4/h5) oder eventuell auch nach der Spiegelung einer der Diagonalen auf der "anderen Seite der Achse" die gleiche Stellung steht mit den gleichen Zugmöglichkeiten (abgesehen von den Schachbrett-Koordinaten) stehen. Die Bauern könnten die Symmetrie stören. 
Hier sind Mathematiker gefragt.
Parent - - By Benno Hartwig Date 2014-06-07 15:31
Stimmt.
Aber ich vermute, dass bei den 7-Steinern eh die meisten Stellungen irgendeinen Bauern haben. Dann ist es mit der Symmetrie eh vorbei.
Benno
Parent - - By Michael Bechmann Date 2014-06-07 22:02 Edited 2014-06-08 09:23
Zitat:
Dann ist es mit der Symmetrie eh vorbei.


nicht so voreilig.

Beispiele:





Ich hatte mich vorhin vorsichtig ausgedrückt. In diesem sehr simplen Beispiel gibt es hier Symmetrien an der senkrechten Achse mit 3 Bauern.
So gibt es daher viele vergleichbare Fälle.
Parent - By Olaf Jenkner Date 2014-06-07 22:18
Die Symmetrie an der senkrechten Achse war nicht gemeint, denn die ist selbstverständlich immer vorhanden.
Die einzige Ausnahme sind Stellungen mit noch vorhandenem Rochaderecht, aber diese werden sowieso von
den Tablebases stiefmütterlich behandelt.
Ohne Bauern gibt es Spiegelungen in alle Richtungen, sogar an den Diagonalen. Solche Stellungen werden
nur einmal gespeichert, womit die Platzersparnis sehr groß ist.
- By Philipp Date 2014-06-06 18:37
Ich bin zwar kein Experte von Quantenalgorythem, aber mit einem Quantencomputer sollte Schach lösbar sein, ich bau schon mal einen.
- By Philipp Date 2014-06-07 14:57
Naja von den 285 Möglichkeiten fallen 16 wieder raus und die Spiegelungen sind ja bereits bei den 7-Steinern berücksichtig, vergleicht mal die Datenbankgröße von 6 auf 7 Steine und schaut den Unterschied an, wobei man dann noch berücksichtigen muss, dass ein 6 Steiner theoretisch weniger bits braucht als ein 7 Steiner zur Speicherung.

Keine Ahnung, wie die Stellungen gespeichert werden, aber durch die Kompression wohl so stark es geht.
- - By Philipp Date 2014-06-08 08:57
Einen weiteren Beitrag könnte jemand leisten, der wüsste welche Stellungen für >3000 Elo überhaupt in Frage kommen.

Bestimmt keine mit Rochaderecht und 7 Steinen.

Welche Bauernkonstellationen kommen überhaupt vor usw usf

Bestimmt keine mit einem a einem h und einem f  Bauern, so eine Stellung entsteht wohl kaum, aber es gibt sicherlich noch unzählige Beispiele.

Eine Idee bis zu den 6 Steinern wäre mal zu wissen, welche davon von den engins überprüft werden und welche nicht.
Parent - - By Thomas Müller Date 2014-06-08 09:28
Hallo Philipp

dein Limit an Gastpostings wäre so langsam überschritten.
Stelle bitte einen Stammposterantrag damit wir entlastet werden
Danke!

gruß
thomas
Parent - By Frank Rahde (Mod.) Date 2014-06-08 12:16
Philipp ist schon längst Stammposter. Er hat es anscheinend nur vergessen  Ich hoffe, er hat eben meine Nachricht per Mailbenachrichtigung erhalten.
- By Philipp Date 2014-06-08 09:06
Da aber die N-Steiner von hinten aufgerollt werden, würde das keine Zeitersparniss für das Erstellungsprogramm bedeuten, oder zumindest nicht sehr viel und der Platzbedarf ist ja relativ gering im Vergleich zur benötigten Leistung um das auszurechnen.

Natürlich ist der Platz ein Problem für Desktop PC, aber schon ein kleiner Server sollte 135 TB speicher können (irgendwo habe ich die Zahl im Kopf für 7 Steiner), welche ja bekanntlich nicht freigegeben werden, sondern kommerziell genutzt werden.

Alles in allem ist jetzt natürlich Schach nur ein Spiel und es ist jetzt auch nicht so populär, dass davon viele reich werden können wie bsp im Fussball, sondern nur die Weltbesten.

Wo soll also das Interesse menschlicherseits nach extremer hardware kommen, ausser von ein paar Computerschach freaks, einer sagte mal, Computerschach ist eine Nische in einer Nussschale.

Seit die Computer die besten Menschen geschlagen werden, interessiert sich die KI Forschung nicht mehr dafür, kein Geld, keine Supercomputer bedeutet absbald keine 8 Steiner.

Aber ich gehe mal davon aus, dass man es in den nächsten 10 Jahren schafft zumindest im Serverbereich ganz andere Geschütze aufzufahren mit viel mehr Rechenleistung und bis dahin auch billig genug (Manycoresteme, GPU etc).
- By Philipp Date 2014-06-08 09:15
Und natürlich gibt es wichtigeres zu berechnen, wie bsp Atombombensimulationen.

Wäre es nun möglich, mit einem guten Schachzug Menschen zu töten, dann wäre das interessanter.

Das sehr wohl ein Haufen Strom und Hardware für absolut unnötige Berechnung gewinnbringend sein können, sieht man an den Bitcoins.

Kann mal jemand von euch den Chesscoin entwerfen ?
Up Topic Hauptforen / CSS-Forum / 7+n Steiner, wie verhält sich Berechnungszeit

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill