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

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?

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 ⁴³ 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.

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.

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.

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.

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.

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.

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)

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.