Ist 2035 das Schach gelöst?

By Olaf Jenkner Date 2009-01-29 17:44

Die 10^46 Stellungen sind die insgesamt theoretisch
möglichen Stellungen, also auch Stellungen, die nur
durch dümmstes Spiel beider Seiten zustande kommen.
Wahrscheinlich sind in der Zahl auch noch illegale
Stellungen enthalten, z.B. Stelungen, wo Weiß und
Schwarz im Schach stehen oder Stellungen, wo sich
retroanalytisch die Unmöglichkeit beweisen läßt.
Beim Versuch, Schach vollständig auszurechnen, kann
man auf dumme Züge verzichten, man muß sie nur zweifels-
frei erkennen. Dumme Züge sind z.B. solche, die ein
Matt zulassen, sofern es noch Alternativen gibt.
In den 10^46 Stellungen steckt eine riesige Zahl von
Stellungen mit großem Materialungleichgewicht, z.B.
8 Bauern gegen 9 Damen.
Wenn man annimmt, daß bei beiderseitigem perfekten Spiel
niemals mehr als 4 Umwandlungsfiguren gleichzeitig auf
dem Brett stehen können (was wohl schwer zu beweisen ist,
aber für Schachspieler plausibel klingt), können wir
von den 10^46 getrost ein paar Nullen streichen.
Trotzdem glaube ich nicht, daß van der Herik Recht hat.
Was Vielen Computerfreaks noch nicht aufgefallen ist:
Seit Jahren verlangsamt sich die Hardwareentwicklung, sie
stagniert eigentlich schon fast. Welche Taktfrequenz
hatten denn die Rechner vor 4 Jahren und wo stehen sie
jetzt? Natürlich war der Pentium IV sehr uneffektiv, aber
sooo viel effektiver sind die Cores auch nicht, maximal
35% schneller bei gleichem Takt. Durch Verkleinerung der
Strukturen geht man jetzt in die Breite und packt mehr
Kerne auf einen Chip. Auch das ist in wenigen Jahren aus-
gereizt.
Mittlerweile sieht es so aus, daß Quantencomputer, sollte
es sie jemals geben, wahrscheinlich nicht für Schach einge-
setzt werden können.

OJe

By Benno Hartwig Date 2009-01-30 14:21

[quote="Olaf Jenkner"]Seit Jahren verlangsamt sich die Hardwareentwicklung, sie
stagniert eigentlich schon fast.[/quote]
Ich bin mal gespannt, ob eine Frage "knacken wir das Schachspiel endgültig" zu einem Aufbau wie bei Seti@home führen kann.
Wenn denn eine Software entwickelt würde, die beim Einsatz einiger hunderttausend Rechner über einige Jahre eine reelle Chance bietet, diese Frage zu beantworten.
Dann wären wir doch bei Rechenleistungen, die sich eben doch sehr erheblich von der eines heutigen Quads unterscheiden.

Aber OK, ich weiß natürlich auch, dass eine plietsche neue Algorithmus-Idee kommen muss.
Rechenpower allein wird es sicher nicht bringen.

Benno

By Olaf Jenkner Date 2009-01-30 14:47

Keine Chance, nach meiner Schätzung gibt es statt 10^46 vielleicht 10^36
wichtige Stellungen. Das sind 36 Nullen. Bei 10 Mio Fans, die weltweit
mitrechnen würden, hätten wir 7 Nullen weniger, also noch 10^29.
Das ist weit weg von allem Vorstellbaren.

OJe

By Timo Schneider Date 2009-01-30 17:50

es wurden schon komplexe TSPs (travelling salesman problem = kürzeste Route durch alle Zielorte) mit ca. 25 000 Orten gelöst.

Suchraum: 25 000! = ca. 10^100.000 (immens mehr als alle Atom-Elektronenhüllen des Universums in zig-Trilliarden Jahren an messbaren Zustandsänderungen hätten haben können bei 1 Delta pro Planck-Zeit = ca. 5*10^-44 s)

dazu werden OR-Algos mit sehr starken, meist geometrisch basierten Such-Reduktionen verwendet (Branch+Bound)

ergo könnte es durchaus bisher unbekannte Verfahren geben, womit 2-Parteien Nullsummenspiele wie Schach "elegant" und ohne großen Aufwand lösbar wären im spieltheoretischen Sinn

ich kenne keinen Gegenbeweis hierzu

der codierte Algo zum Durchrechnen von Schach könnte theoretisch sogar in Pi enthalten sein (sofern es wie manche vermuten, alle endlichen Ziffernfolgen mindestens einmal enthält - eine schwächere Version der Normalitätsbedingung: de.wikipedia.org/wiki/Normale_Zahl ) - und das in jeder nur denkbaren Algo-Sprache. die Lösung selbst wäre dann auch codiert in Pi enthalten, nur wäre sie wohl "etwas" länger.

während wir auf den 160-bit Quantenrechner warten ist die entscheidende Frage wohl, wie viele Stellungen man mit Turing-Algos minimal traversieren muss bis zum Erreichen der verfügbaren Endspieltabellen, um Schach zu lösen - nur einen Bruchteil der tatsächlichen, das ist klar - aber welchen Bruchteil?

timosh

By Benno Hartwig Date 2009-01-30 20:58

[quote="Olaf Jenkner"]Keine Chance, nach meiner Schätzung gibt es statt 10^46 vielleicht 10^36
wichtige Stellungen.[/quote]Mir ist nicht klar, wieviele Stellungen relevant wären für den Beweise eines konkreten weiss-Gewinnweges, so er denn existiert.
Es müssen halt die Widerlegungsversuche jeweils abgeklopft werden.
Deine 10^36 kann ich nicht nachvollziehen.

Benno

By Thomas P. Date 2013-05-10 18:35

[quote="Olaf Jenkner"]
Mittlerweile sieht es so aus, daß Quantencomputer, sollte
es sie jemals geben, wahrscheinlich nicht für Schach einge-
setzt werden können.
[/quote]

Warum, wenn ich fragen darf??

By Karl-Heinz Milaster Date 2009-01-30 10:59

[quote="Walter Eigenmann"]Der holländische Uni-Professor Herik gibt dem Schach keine 30 Jahre mehr, bis es von den Computern gelöst sein wird.[/quote]
Mit den heutigen Schachprogrammen ist es nicht möglich, diese These zu belegen oder zu widerlegen, da sie aufgrund von Heuristiken ("all heuristics are fallible") den Suchbaum begrenzen.

Man kann sicher eine Schachprogramm ("brute force") schreiben, mit dem die Aussage belegbar ist, allerdings scheinen mir für diesen Versuch 30 Jahre etwas knapp bemessen zu sein. Eher müssen wir den lieben Gott bitten, beim nächsten Urknall unseren Schach-Rechner zu verschonen, damit er "irgendwann" zu einem Ergebnis kommt.

Alternativ müsste man ein auf Schach spezialisertes, künstliches Gehirn entwickeln, das hochgradig parallel arbeitet. Mit einem simplen Zusammenschalten von mehreren (tausend) CPU-Kernen ist es da leider nicht getan.

Bleibt die Frage, warum der Herr Professor bisher kein auf KI basierendes, spielstarkes Schachprogramm veröffentlicht hat.
Bisher sind alle mir bekannten derartige Versuche kläglich gescheitert.

Gruss,
khm

By Benjamin Bahnsen Date 2013-05-08 23:11

Eigentlich habe ich mir geschworen mich zu diesem Thema nicht mehr zu äußern, aber bei den vielen falschen Meinungen hier, juckt es mir unter den Fingern. Ich werfe hier mal einen sehr schweren Stein in die Waagschale, denn ich habe meine Diplomarbeit über dieses Thema geschrieben (Informatik).

Beim Lösen von Spielen wird nach dem spieltheoretischen Wert gesucht. Das spieltheoretische Wert ist das Endergebnis eines Spiels bei optimalem Spiel von beiden Seiten. Wenn man von "gelöst" spricht, unterscheidet man normalerweise zwischen schwach gelöst und stark gelöst. Schwach gelöst ist ein Spiel, wenn es einen Algorithmus gibt, der den spieltheoretischen Wert der Ausgangsstellung bestimmt. Stark gelöst ist ein Spiel, wenn der spieltheoretische Wert jeder Spielstellung bestimmt werden kann. Eine weitere Voraussetzung ist natürlich, dass der Algorithmus in begrenzter Zeit zu einem Ergebnis kommt; er muss also praktisch realisierbar sein.

Es gibt nun verschiedene Techniken, wie man den spieltheoretischen Wert bestimmen kann, z.B.

1. ... die rückwärtsgerichtete Suche (Retrograde Analysis), wie wir sie von Tablebases kennen.
2. ... eine vorwärtsgerichtete Suche, die in jeder Variante bis zum Spielende reicht.
3. ... die Definition einer Strategie, die das optimale Spiel beider Seiten beschreibt.

Technik 1 hat z.B. Mühle stark gelöst. Der spieltheoretische Wert der Ausgangsstellung ist Unentschieden, was vorher nicht unbedingt klar war. Der Nachziehende hat ein deutlich einfacheres Spiel. Beim Damespiel hat eine Kombination der Techniken 1 und 2 zum Ziel geführt. Dame ist übrigens nur schwach gelöst - man weiß lediglich, dass die Ausgangsstellung bei optimalen Spiel zum Unentschieden führt. Über andere Stellungen, die im praktischen Spiel entstehen können, lässt sich dieser Wert (noch) nicht bestimmen.

Mit Technik 3 wurde Vier-Gewinnt gelöst. Und trotz ca. 10^14 möglicher Stellungen (100 Billionen!) hat man dafür nicht einmal einen Computer gebraucht. Ein kluger Mensch hat sich einfach hingesetzt und eine Gewinnstrategie beschrieben.... und damit auch den Beweis erbracht, dass die Komplexität eines Spiels überhaupt nichts darüber aussagt, wie schwer es ist dieses Spiel zu lösen. So ist die Komplexität von Mühle viel geringer (ungefähr Faktor 1000) als die von 4-Gewinnt - und trotzdem war es sehr viel schwerer dieses Spiel zu lösen!

Schach ist noch einmal eine ganze Ecke komplexer - aber das heißt nicht, dass es nicht gelöst werden kann. Keiner behauptet, dass wir Schach allein mit Technik 1 oder 2 lösen können. Auch eine Kombination aus 1 und 2 wird vermutlich nicht ausreichen. Aber wenn noch zusätzliches Schachwissen Einzug erhält, kann und wird man dieses Spiel lösen. Ich bin davon überzeugt, dass die meisten von uns den spieltheoretischen Wert der Ausgangsstellung noch erfahren werden. Wann das der Fall sein wird, hängt meiner Meinung nach von dem Wert selbst ab. Ein Gewinn ist sehr viel einfacher zu beweisen als ein Unentschieden. 2035 halte ich für realistisch falls der Anziehende zwingend gewinnen kann. Bei einem Unentschieden werden wir noch ein paar Jahre länger warten müssen. Die Tendenz dafür wird sich aber schon viel eher abzeichnen. Erahnen lässt sich das Ergebnis vielleicht schon 2025... der endgültige Beweis wird dann noch etwas dauern.