Kann es einen perfekten Schachalgorithmus geben?

Gegenwärtige Schachalgorithmen gehen je nach den Zügen des Spielers und des Gegners etwa 1 oder vielleicht 2 Stufen einen Baum von möglichen Pfaden hinunter. Nehmen wir an, wir haben die Rechenleistung, um einen Algorithmus zu entwickeln, der alle möglichen Bewegungen des Gegners in einem Schachspiel vorhersagt. Ein Algorithmus, der alle möglichen Pfade enthält, die der Gegner zu einem bestimmten Zeitpunkt einschlagen kann, abhängig von den Bewegungen des Spielers. Kann es jemals einen perfekten Schachalgorithmus geben, der niemals verliert? Oder vielleicht ein Algorithmus, der immer gewinnt? Ich meine in der Theorie, dass jemand, der alle möglichen Züge vorhersagen kann, einen Weg finden muss, um jeden einzelnen von ihnen zu besiegen, oder einfach einen anderen Weg wählen kann, wenn ein bestimmter ihn effektiv zur Niederlage führen wird.

edit-- Was ist meine Frage wirklich. Nehmen wir an, wir haben die Rechenleistung für einen perfekten Algorithmus, der sich optimal spielen lässt. Was passiert, wenn der Gegner mit dem gleichen optimalen Algorithmus spielt? Dies gilt auch für alle 2-Spieler-Spiele mit einer begrenzten Anzahl von Zügen (sehr groß oder nicht). Kann es jemals einen optimalen Algorithmus geben, der immer gewinnt?

Persönliche Definition: Ein optimaler Algorithmus ist ein perfekter Algorithmus, der immer gewinnt ... (nicht einer, der niemals verliert, sondern einer, der immer gewinnt)

Ihre Frage ähnelt der alten Kastanie: "Was passiert, wenn eine unwiderstehliche Kraft auf einen unbeweglichen Gegenstand trifft?" Das Problem liegt in der Frage selbst: Die beiden beschriebenen Entitäten können nicht in demselben logisch konsistenten Universum existieren. Ihr optimaler Algorithmus, ein Algorithmus, der immer gewinnt, kann nicht von beiden Seiten in einem Spiel gespielt werden, in dem eine Seite gewinnen und die andere per Definition verlieren muss. Somit kann Ihr optimaler Algorithmus, wie er definiert ist, nicht existieren.

Zuallererst glaube ich, dass Schachalgorithmen mehr als zwei Lagen nach unten aussehen, obwohl sie nicht alle verschiedenen Möglichkeiten berücksichtigen. Das Beschneiden des Suchbaums ist sehr wichtig, um die kombinatorische Explosion der Anzahl möglicher Züge zu vermeiden.

Für eine Partie wie Schach gibt es drei Möglichkeiten, den Sieger zu identifizieren: Entweder hat Spieler 1 eine Gewinnstrategie oder Spieler 2 eine Gewinnstrategie, oder beide Spieler ziehen unter optimalen Bedingungen. Es ist nicht bekannt, was beim Schachspiel der Fall ist. Da Schach jedoch ein endliches Spiel ist, gibt es einen Computeralgorithmus, der aus einem sehr großen Tisch besteht und Schach optimal spielt.

Natürlich wäre ein solcher Algorithmus nicht praktisch. Bei einigen einfacheren Spielen wurde jedoch der "Wert" des Spiels (welcher Spieler gewinnt, falls vorhanden) ermittelt und ein optimaler Algorithmus entwickelt. Ein solches Spiel ist als gelöstes Spiel bekannt .

Das mathematische Fach, das sich mit (sogenannten) kombinatorischen Spielen befasst, ist die kombinatorische Spieltheorie . Mathematiker haben eine rekursive Methode entwickelt, um den Wert eines Spiels anhand des Diagramms des Spiels zu bestimmen, das alle zulässigen Positionen und Bewegungen enthält. Sie sollten in der Lage sein, eine Beschreibung dieses Algorithmus im Wikipedia-Eintrag oder in Vorlesungsnotizen zu diesem Thema zu finden.

Zuallererst sehen gute Schachalgorithmen mehr als 1 oder 2 Ebenen aus. Anstatt naive Baumsuche zu verwenden, führen sie Alpha-Beta-Bereinigung durch , um die Anzahl der zu berücksichtigenden Optionen einzugrenzen. Beachten Sie, dass für Eröffnungs- und Endspiele eine große Datenbank von Zügen verwendet wird, da diese eine bessere Leistung bietet als die Baumsuche, die in der Spielmitte verwendet wird.

Auf die Frage: Was Sie fragen, glaube ich, ist "Ist Schach lösbar ?". Hypothetisch ist dies der Fall, obwohl die Meinungen darüber, ob dieses Ergebnis in Kürze erreicht werden kann, unterschiedlich sind. Checkers wurde zum Beispiel 2007 gelöst, hat aber viel weniger Positionen (um die Quadratwurzel der Zahl im Schach). Siehe den Wikipedia-ArtikelWeitere Informationen finden .

Übrigens, die derzeit besten Schach-AIs besiegen oder ziehen fast immer gegen Weltmeister; Die Algorithmen sind also, obwohl sie derzeit nicht perfekt sind, zumindest ziemlich gut!

Grundsätzlich ist Schach wie jedes andere Spiel lösbar. Wie die anderen Antworten gezeigt haben, ist dies jedoch nicht zu erwarten.

Bearbeiten: In den Kommentaren wurde darauf hingewiesen, dass [1] ein Schwindel ist. Überspringen Sie daher den Rest dieser Antwort.

Allerdings hat es in letzter Zeit einige Entwicklungen in diese Richtung gegeben. [1] behauptet, gezeigt zu haben, dass die Schachöffnung namens King's Gambit gelöst ist : Es gibt nur einen Zug, der für Weiß unentschieden ist, während alle anderen Eröffnungszüge zu einem Gewinn für Schwarz führen. Beachten Sie, dass [1] den Spielbaum nicht in voller Tiefe untersucht hat, sondern nur behauptet, dass diese Ergebnisse mit hoher Wahrscheinlichkeit erhalten bleiben.

[1] http://chessbase.com/newsdetail.asp?newsid=8047

Ob es möglich ist, immer eine Partie Schach zu gewinnen oder nicht, hängt von den Spielregeln ab. Es gibt jedoch eine Technik / einen Algorithmus namens Minimax (Einzelheiten finden Sie unter https://en.wikipedia.org/wiki/Minimax ). Der Algorithmus besteht darin, vorherzusagen, welcher Spieler in verschiedenen Szenarien mit einer rekursiven Funktion die Oberhand hat. Hier ist eine klare Erklärung, wie dies mit einem einfacheren Spiel funktioniert: Tic-Tac-Toe https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13 .

wird eine weitere Antwort hinzufügen, die den massiven Zustandsraum betont, der in der Frage nicht wirklich begriffen oder in anderen Antworten hervorgehoben ist. muss mit Ihrer Prämisse nicht einverstanden sein:

Nehmen wir an, wir haben die Rechenleistung, um einen Algorithmus zu entwickeln, der alle möglichen Bewegungen des Gegners in einem Schachspiel vorhersagt.

Siehe Info zu Shannon 1950, "Programming a Computer for Playing Chess" (Programmieren eines Computers zum Spielen von Schach), das das Gebiet des computergestützten Schachspielens / -algorithmus einführte und dessen Analyse im Grunde unverändert und immer noch solide ist (auch durch die nachfolgende Computerrevolution und das Moores-Gesetz ). es schätzt die Anzahl der Züge. Es ist absolut astronomisch. im Bereich "nie innerhalb denkbarer Hardware auch bei revolutionären unvorhergesehenen Fortschritten".

Es ist eine dokumentierte psychologische Tatsache [3], wahrscheinlich eine der vielen psychologischen Vorurteile [2], dass Menschen Schwierigkeiten haben, Zahlen dieser Größenordnung zu verstehen. siehe auch counterfactual Denken . [4] , während Supercomputer berechnen massive Probleme, sein unumstritten nicht im Bereich eines Supercomputers , die derzeit gebaut wird oder überhaupt könnte werden gebaut. (und viele Schachfans würden argumentieren, dass diese "kombinatorische Explosion" der Bewegungs- / Positionsmöglichkeiten ein wesentlicher Aspekt des "Flavours" der Spiele ist, der absichtlich in das jahrtausendealte Spiel integriert zu sein scheint ).

Daher unterscheidet sich Schach grundlegend von einigen Spielen, die kleinere "lösbare" Zustandsräume haben (von denen es einige Studien in Informatik und Spieltheorie usw. gibt) und in einigen Schlüsselbereichen nicht in diesem Rahmen bewertet werden können.

Allis schätzte auch die Komplexität des Spielbaums als mindestens $10^{123}$, "basierend auf einem durchschnittlichen Verzweigungsfaktor von 35 und einer durchschnittlichen Spieldauer von 80". Zum Vergleich wird die Anzahl der Atome im beobachtbaren Universum, mit denen es oft verglichen wird, auf einen Wert zwischen geschätzt$4×10^{79}$ und $10^{81}$.

Allerdings ist es denkbar (aber unwahrscheinlich), dass es theoretische Einblicke in das Spiel gibt, mit denen der Suchraum erheblich eingeschränkt werden kann. das ist seit 1950 passiert, aber nicht wirklich auf grundlegend bahnbrechende Weise.

siehe auch

[1] Wie hoch ist der Rechenaufwand beim Lösen von Schach, tcs.se

[2] menschliche Vorurteile bei der Beurteilung und Entscheidungsfindung

[3] Psychologiestudenten veröffentlichen Forschungsergebnisse zur Konzeptualisierung von Zahlen

[4] kontrafaktisches Denken