Gibt es bei unendlicher Rechenleistung einen Algorithmus, der Schach perfekt spielen würde?

29

Gibt es einen solchen Algorithmus, bei dem ein Computer bei unendlicher Rechenleistung perfekt Schach spielen könnte, damit er niemals verliert?

Wenn ja, wo finde ich Pseudocode dafür?

Jona
quelle
8
Was meinst du mit perfektem Schach?
Herb Wolfe
5
@HerbWolfe Ich gehe davon aus, dass er bedeutet, dass er niemals einen Zug macht, der es seinem Gegner erlaubt, ihn zum Verlieren zu zwingen, und nur dann zurücktritt, wenn jeder mögliche Zug es seinem Gegner erlaubt, ihn zum Verlieren zu zwingen.
David Schwartz
5
@DavidSchwartz - "Perfektes Schach" kann natürlich nicht definiert werden. Weder kann "unendliche Rechenleistung". Bedeutet dies, dass "alle Befehlssequenzen in 0-Zeit ausgeführt werden"? Msgstr "Hat eine unendliche Anzahl von Prozessoren zur Verfügung"? FWIW - meine Definition von "perfektem Schach" ist "verliert nie ein Spiel".
Bob Jarvis - Reinstate Monica
24
Ja, das nennt man rohe Gewalt. Mit unendlicher Rechenleistung müssen Sie kein Alpha-Beta-Bereinigen durchführen, obwohl Sie möglicherweise auch viel Speicherplatz benötigen, um Ihren Suchbaum zu speichern.
Michael
4
Das Konzept eines "Algorithmus" und das Konzept der unendlichen Rechenleistung passen nicht zusammen. Die Theorie der Algorithmen und der Berechenbarkeit basiert auf der Annahme, dass ein Ergebnis in einer endlichen Anzahl von Schritten erzielt wird. Wenn Sie eine unendliche Anzahl von Schritten ausführen dürfen, verschwindet die Unterscheidung zwischen berechenbaren und nicht berechenbaren Schritten.
Michael Kay

Antworten:

62

Gibt es einen Algorithmus? Ja. Nach dem Satz von Zermelo gibt es drei Möglichkeiten für ein endliches deterministisches Zwei-Spieler-Spiel mit perfekten Informationen wie Schach: Entweder hat der erste Spieler eine Gewinnstrategie, oder der zweite Spieler hat eine Gewinnstrategie, oder jeder Spieler kann ein Unentschieden erzwingen. Wir wissen (noch) nicht, was es für ein Schach ist. (Checkers hingegen wurde gelöst : Jeder Spieler kann ein Unentschieden erzwingen.)

Konzeptionell ist der Algorithmus recht einfach: Erstellen Sie einen vollständigen Spielbaum , analysieren Sie die Blattknoten (die Positionen, an denen das Spiel endet) und machen Sie entweder den ersten Zug, geben Sie auf oder bieten Sie ein Unentschieden an.

Das Problem liegt im Detail: Es gibt ungefähr 10 43 mögliche Positionen und eine noch größere Anzahl von Zügen (die meisten Positionen können auf mehrere Arten erreicht werden). Sie brauchen wirklich Ihren unendlich leistungsfähigen Computer, um dies zu nutzen, da ein Computer, der diesen Algorithmus nutzen kann, entweder nicht in das bekannte Universum passt oder die Berechnung erst irgendwann nach dem Ende des Universums abschließt.

Kennzeichen
quelle
13
@Wildcard Nein, es wird nichts vorausgesetzt: Es enthält nur alle möglichen legalen Schachpartien und es werden alle ausgewählt, bei denen der Spieler nicht verliert.
Gented
11
@gented, ich bezog mich auf den Schritt "resign" des Algorithmus. Das ist überhaupt kein notwendiger Schritt.
Wildcard
38
Die Drei-Wiederholungs-Regel begrenzt den Suchraum, sodass der Computer nicht unendlich leistungsfähig sein muss, sondern nur astronomisch.
Hoa Long Tam
9
Vergleichen Sie als Referenz eine Untergrenze für die Anzahl der möglichen Spiele ( 10 ^ 120 ) mit der Anzahl der Atome im beobachtbaren Universum (in der Größenordnung von 10 ^ 80 ). Der einfachste Algorithmus müsste all diese Spiele finden und ihre Daten speichern. Das Speichern eines Spiels pro Atom würde 10 ^ 40-mal so viele Atome erfordern, wie wir im beobachtbaren Universum schätzen.
Ingenieur Toast
6
Diese Antwort ist bis zum Schluss großartig, wenn Sie sich auf einen "unendlich leistungsfähigen Computer" beziehen. Das meinen Sie nicht , und dieser Satz gehört weder in die Frage noch in die Diskussion.
Don Hatch
25

Siehe https://en.wikipedia.org/wiki/Endgame_tablebase .

Mit unendlicher Rechnerleistung könnte man eine solche Tabelle für die Ausgangsposition aufbauen und Schach lösen .

In der Praxis wurden nur Positionen mit bis zu sieben "Männern" (Bauern und Figuren, die Könige zählen) mit aktuellen Supercomputern gelöst, sodass wir weit davon entfernt sind, Schach zu lösen. Die Komplexität des Problems nimmt exponentiell mit der Stückzahl zu.

itub
quelle
9
Als Randnotiz: Wenn Sie tatsächlich eine solche Tabelle erstellen würden, würde sie, unabhängig davon, worauf Sie die Informationen gespeichert haben, ungefähr das 10- bis 43-fache des beobachtbaren Universums wiegen. wenn man bedenkt, dass es ~ 10 ^ 123 mögliche Schachpositionen und nur ~ 10 ^ 80 Baryonen im beobachtbaren Universum gibt.
Shufflepants
6
@Shufflepants wer sagte, dass ich es unter Verwendung von Baryonen speichere?
Michael
3
@Christoph Und unter der Annahme, dass die Informationen erhalten bleiben und dass Sie einen Detektor und einen Supercomputer mit unendlicher Rechenleistung haben, könnten Sie im Laufe von etwa Googolplex-Jahren die Tischbasis langsam als Falkenstrahlung auslesen.
Shufflepants
3
@Shufflepants Beachten Sie, dass eine tatsächliche Gewinnstrategie möglicherweise viel weniger Speicherplatz benötigt als eine vollständige Tabellenbasis. Zum Beispiel hat Nim eine Gewinnstrategie, die einfach zu beschreiben ist. Es ist nicht notwendig, eine riesige Tabelle aller möglichen Zustände zu erstellen.
Federico Poloni
1
Diese Lösung ist wie angegeben nicht realisierbar. Die Masse einer solchen Tabelle würde ein Schwarzes Loch bilden und es wäre unmöglich, Daten daraus herauszufiltern.
Emory
19

Wenn Sie wirklich unendlich viel Rechenleistung hätten, wäre ein solcher Algorithmus eigentlich trivial zu schreiben. Da Schach eine endliche Anzahl möglicher Zustände hat, können Sie theoretisch alle durchlaufen, bis Sie einen Weg des perfekten Spiels gefunden haben. Es wäre schrecklich ineffizient, aber wenn Sie unendliche Rechenleistung haben, wäre es egal.

vsz
quelle
Das ist nicht wahr. Er sagte, Sie hätten unendliche Rechenleistung, sagte aber nichts über unendlichen Raum.
Ubadub
@ubadub: Wir brauchen keinen unendlichen Platz. Die Länge eines Spiels ist aufgrund der 50-Züge-Regel begrenzt, und eine Regel kann erstellt werden, um alle möglichen Züge von einer Position aus zu sortieren. Da sie sortiert werden können, können sie als Ganzzahl gespeichert werden. Dies ist der gesamte Speicher, der erforderlich ist, um den gesamten Baum zu durchlaufen. Und wenn Sie unendlich viel Zeit haben, können Sie den Baum so oft laufen lassen, wie Sie möchten, sodass Sie nicht jedes mögliche Schachspiel speichern müssen.
vsz
Die Länge des Spiels ist begrenzt, aber extrem groß. Wenn Sie eine Tabelle erstellen würden, in der all diese Spiele gespeichert sind, würde sie, wie jemand anderes betonte, "unabhängig davon, in welcher Tabelle Sie die Informationen gespeichert haben, ungefähr das 10- bis 43-fache des beobachtbaren Universums wiegen. Wenn man bedenkt, dass ~ 10 ^ 123 möglich sind
schachstellungen
2
@ubadub: Das stimmt, aber ich habe nicht über "einen Tisch zum Speichern all solcher Spiele" gesprochen. Es gibt viele baumbezogene Algorithmen, die nicht alle Knoten des gesamten Baums im Speicher halten müssen.
vsz
@ vsz guter Punkt
ubadub
13

Um die Frage direkt anzusprechen: Ja, es gibt einen solchen Algorithmus. Es heißt Minimax. (Die Endspiel-Tabellenbasen werden mit diesem Algorithmus generiert (rückwärts!), Aber der einfache alte Minimax-Algorithmus ist alles, was Sie brauchen.) Dieser Algorithmus kann ein beliebiges Zwei-Spieler-Nullsummenspiel perfekt spielen. Finden Sie den Pseudocode hier:

https://en.wikipedia.org/wiki/Minimax

Beachten Sie, dass Varianten dieses Algorithmus von modernen Computerschachprogrammen verwendet werden.

Schachprogrammierer
quelle
4

Es gibt nicht nur einen Algorithmus, um perfektes Schach zu spielen, sondern es ist auch möglich, ein kurzes Programm zu schreiben, das (bei unendlichen Ressourcen) jedes deterministische, perfektes Wissensspiel mit endlicher Spieldauer für zwei Spieler perfekt spielt.

Die Game Engine muss nicht einmal die Regeln des Spiels kennen, das sie spielt. Alles, was es braucht, ist eine undurchsichtige Darstellung eines "Spielzustands" und von Funktionen, die (a) einen beliebigen Spielzustand voraussetzen, eine Liste der zulässigen nächsten Spielzustände bereitstellen und (b) bei gegebenem Spielzustand entscheiden, ob es sich um einen Gewinn für Spieler 1 handelt , ein Gewinn für Spieler 2, ein Unentschieden, oder es ist kein Endzustand.

Mit diesen Funktionen löst ein einfacher rekursiver Algorithmus das Spiel.

Auf diese Tatsache wurde in früheren Antworten vom Schachprogrammierer (Minimax) und von Acccumulation (der eine Version des Programms in Python zur Verfügung stellt) hingewiesen.

Ich habe ein solches Programm vor über 20 Jahren geschrieben. Ich habe es getestet, indem ich Nullen und Kreuze gespielt habe (Tic-Tac-Toe, wenn Sie Amerikaner sind). Sicher genug, es hat ein perfektes Spiel gespielt.

Natürlich wird dies auf jedem erdenklichen Computer für jedes ernsthafte Spiel schnell umschlagen. Da es rekursiv ist, baut es effektiv den gesamten Spielbaum auf dem Stapel auf, sodass Sie einen "Stapelüberlauf" (Wortspiel sehr beabsichtigt) erhalten, bevor Sie die 10 ^ 123 Schachzustände, auf die in anderen Antworten verwiesen wird, näherungsweise analysieren. Aber es macht Spaß zu wissen, dass dieses kleine Programm im Prinzip den Job machen würde.

Für mich sagt dies auch etwas Interessantes über KI aus: Wie viel "Intelligenz" Deep Blue oder Go Zero oder ein Mensch, der Schach oder Go spielt, in gewisser Weise haben diese Spiele ein triviales, genau berechenbares Optimum lösungen. Die Herausforderung besteht darin, in angemessener Zeit eine gute, wenn auch nicht optimale Lösung zu finden.

gareth
quelle
Ihr Algorithmus funktioniert nur bei Zwei-Spieler-Spielen mit perfektem Wissen. Bei Spielen mit versteckten Informationen wie Stratego wird dies nicht zutreffen , da die Implementierung von Funktion (a) gegen die Spielregeln verstößt. Es scheitert auch bei Spielen von potenziell unendlicher Dauer: Wenn Sie beispielsweise die Regel mit 50 Zügen aus dem Schach streichen, können Sie nicht erkennen, dass zwei Könige, die sich gegenseitig um das Spielfeld jagen, kein gewinnbarer Zustand sind. Alles was es sagen kann ist, dass es kein Endzustand ist.
Mark
Gültige Punkte. Ich werde meine Antwort bearbeiten.
Gareth
3

Ich werde der Einfachheit halber die Möglichkeiten von Zügen oder unendlichen Abfolgen von Zügen ignorieren. Wenn der Algorithmus erst einmal verstanden ist, ist es nicht besonders schwierig, ihn auf diese Fälle auszudehnen.

Erstens einige Definitionen:

  1. Jeder Zug, der das Spiel für den Spieler gewinnt, der diesen Zug macht, ist ein Gewinnzug.

  2. Jeder Zug, der das Spiel für den Spieler verliert, der diesen Zug macht, ist ein Verlustzug.

  3. Jeder Zug, bei dem der andere Spieler mindestens einen Gewinnzug hat, ist ebenfalls ein Verlustzug. (Da der Gegner diesen Zug machen und einen Verlust erzwingen kann.)

  4. Jeder Zug, bei dem der andere Spieler nur verliert, ist auch ein Gewinnzug. (Egal welchen Zug dein Gegner macht, du wirst gewinnen.)

  5. Eine perfekte Strategie bedeutet, dass Sie immer gewinnen, wenn noch Züge übrig sind, und zurücktreten, wenn Sie nur noch verlorene Züge übrig haben.

Nun ist es trivial, eine perfekte Strategie zu schreiben. Löse einfach alle möglichen Zugsequenzen auf und identifiziere Gewinn- / Verlustzüge. Wenn Sie eine Pattsituation ignorieren, wird jeder Zug als Gewinn- oder Verlustzug gewertet.

Jetzt ist die Strategie trivial. Schau dir alle deine möglichen Züge an. Wenn noch Gewinnzüge übrig sind, nimm einen und gewinne. Wenn nur noch verlorene Züge übrig sind, tritt zurück, da dein Gegner dich zum Verlieren zwingen kann.

Es ist nicht schwierig, die Strategie so anzupassen, dass eine Pattsituation möglich ist.

Update : Nur für den Fall, dass nicht klar ist, wie jeder Zug als Gewinn- oder Verlustzug identifiziert wird, überlegen Sie:

  1. Jeder Zug, der zu einem Gewinn führt, ist ein Gewinnzug.
  2. Jeder Zug, der zu einem Verlust führt, ist ein Verlustzug.
  3. Jeder Zug, bei dem der Gegner nur gewinnt oder verliert, ist entweder ein Gewinn- oder ein Verlustzug.
  4. Nennen Sie ndie Anzahl der Züge im längsten möglichen Schachspiel. (Wir ignorieren derzeit unbegrenzte Sequenzen, obwohl es nicht schwierig ist, sie einzubeziehen.)
  5. Es gibt keine Züge mit nvorherigen Zügen, die wir berücksichtigen müssen.
  6. Jeder Zug mit n-1vorherigen Zügen ist entweder ein Gewinnzug oder ein Verlustzug, da der Zug ndas längste Spiel beendet.
  7. Auf jede Bewegung in der Tiefe n-2folgen also nur Gewinn- oder Verlustbewegungen und somit selbst Gewinn- oder Verlustbewegungen.
  8. Und so weiter zurück zum ersten Zug.
David Schwartz
quelle
1
Ihre Definitionen von Gewinn- und Verlustzügen sind nicht umfassend genug. Der erste Zug zum Beispiel gewinnt weder das Spiel (Nr. 1), noch verliert der Gegner nur Züge (Nr. 4), es handelt sich also nicht um einen "Gewinnzug". Weder verliert es das Spiel (# 2), noch lässt es den Gegner bei einem Gewinnzug (# 3), so dass es kein "Verlustzug" ist. Ihre Strategie erfordert, dass jeder Zug entweder als "Gewinnzug" oder als "Verlustzug" definiert wird, was einfach nicht der Fall ist, wie Sie es definiert haben.
Nuclear Wang
2
@NuclearWang Definiert jeden Zug als Gewinnzug oder Verlustzug. Was denkst du, ist die dritte Alternative? Visualisieren Sie den Baum aller möglichen Schachpartien (und denken Sie daran, wir schließen derzeit Krawatten oder unendliche Sequenzen aus). Jede Kette endet entweder mit einem Gewinn oder einer Niederlage. Dies sickert durch den Baum und identifiziert schließlich jeden Zug als einen Gewinnzug oder einen Verlustzug.
David Schwartz
13
@NuclearWang entweder der erste Schritt ist ein Siegeszug für einen Spieler oder auch Schach ist (wie Tic-Tac-Toe) ein gezogenes Spiel mit perfektem Spiel. Wir wissen nicht, welche, weil niemand jemals die Rechenleistung hatte, um diesen Algorithmus vollständig auszuführen, und niemand einen direkteren Beweis gefunden hat.
Hobbs
8
Es gibt keine Zufälligkeit und keine versteckten Informationen im Schach, was keinen Raum für "Vielleicht" lässt. Jede Position wird gewonnen, verloren oder gezogen (auch wenn wir es nicht geschafft haben , sie als solche zu identifizieren ). Und diese Erklärung lässt der Einfachheit halber die Option "gezogen" weg, aber sie beträgt meistens 1) eine Position wird gezogen, wenn sie nach den Regeln gezogen wird, und 2) eine Position wird gezogen, wenn sie keine Gewinnzüge hat, aber at hat Mindestens ein Zug, bei dem der Gegner keine Gewinnzüge mehr macht.
Hobbs
2
@DavidSchwartz: Es sei denn, jemand verliert, ist jede Bewegung, die nicht perfekt ist, schlecht. In einer Verlustposition würde es im Allgemeinen keinen einzigen "perfekten" Zug geben (außer in einer erzwungenen Zugsituation), da jeder legale Zug unter bestimmten denkbaren (möglicherweise hoch entwickelten) Umständen mit einer gewissen Wahrscheinlichkeit der einzige Gewinn- oder Ziehungszug sein könnte. Der Rücktritt scheint jedoch der eindeutig schlechteste "Schachzug" zu sein. Angenommen, das Spiel ist als Gewinn für Weiß mit d4 gelöst. Möchten Sie ein Schachprogramm zu spielen , die hat 1. d4mit ...resigns?
Supercat
2

Angenommen , Sie drei Funktionen haben: win_state, get_player, und next_states. Die Eingabe für win_stateist ein Spielstatus, und die Ausgabe ist -1, wenn sich Weiß im Schachmatt befindet, 0, wenn es sich um ein Unentschieden handelt, 1, wenn sich Schwarz im Schachmatt befindet, und Noneansonsten. Die Eingabe für get_playerist ein Spielstatus und die Ausgabe ist -1, wenn Schwarz an der Reihe ist, und 1, wenn Weiß an der Reihe ist. Die Eingabe für next_statesist eine Liste möglicher nächster Spielzustände, die sich aus einem legalen Zug ergeben können. Wenn ein Spielstatus und ein Spieler angegeben sind, sollte die folgende Funktion Ihnen mitteilen, in welchen Spielstatus sich dieser Spieler bewegen soll, um zu gewinnen.

def best_state(game_state,player)
  def best_result(game_state):
     if win_state(game_state):
        return(win_state)
     else:
         player = get_player(game_state)
         return max([best_result(move)*player for move in next_states(game_state)])*player
  cur_best_move = next_states(games_state)[0]
  cur_best_outcome = -1
  for state in next_states(game_state):
     if best_result(state)*player > cur_best_outcome:
           cur_best_outcome = best_result(state)*player
           cur_best_move = state
return(best_move)
Akkumulation
quelle
0

Verwenden Sie eine Nachschlagetabelle

Ja. Es ist einfach. Sie benötigen nicht einmal unendliche Rechenleistung. Alles, was Sie brauchen, ist eine Nachschlagetabelle, die für jede mögliche Brettposition den besten Zug enthält, um in dieser Position zu spielen. Hier ist der Pseudocode:

def play-move(my-color, board-position):
    return table-of-best-moves[my-color, board-position]

Der Fang

Der einzige Haken ist, dass diese Nachschlagetabelle sehr, sehr groß sein müsste - vielleicht größer als die Milchstraße - und dass es lange dauern würde, sie aufzubauen - vielleicht länger als das aktuelle Zeitalter des Universums, wenn es keine gibt eine unentdeckte Regelmäßigkeit im Schach, die es viel einfacher macht, als wir jetzt sehen können. Wenn Sie jedoch diese Nachschlagetabelle hätten, könnte die Unterroutine, mit der jedes Mal eine perfekte Bewegung ausgewählt wird, in nur einer CPU-Anweisung implementiert werden.

Angesichts unserer derzeitigen Schachkenntnisse gibt es keine Möglichkeit, sicherzugehen, dass ein perfektes Spiel garantiert, dass Sie nicht verlieren. Wenn beispielsweise ein perfektes Spiel einen Gewinn für Weiß garantiert, würde Schwarz verlieren, auch wenn Schwarz perfekt spielt.

Ben Kovitz
quelle