Ein gelöstes Spiel ist ein Spiel, dessen Ergebnis (Gewinn, verlieren Sie oder ziehen Sie), kann von jeder Position richtig vorausgesagt werden, wenn jede Seite optimal spielt. Wie man sagt, sind Spiele, die nicht gelöst worden sind, "ungelöst". Wie man sagt, werden Spiele, für die nur einige Positionen gelöst worden sind, "teilweise gelöst". Dieser Artikel konzentriert sich auf Zwei-Spieler-Spiele, die gelöst worden sind.

Ein Zwei-Spieler-Spiel kann auf mehreren Niveaus "gelöst" werden:

Ultraschwacher

: Im schwächsten Sinn, ein Spiel lösend, bedeutet sich zu erweisen, ob der erste Spieler gewinnen, verlieren, oder von der anfänglichen Position in Anbetracht des vollkommenen Spieles an beiden Seiten ziehen wird. Das kann ein nichtkonstruktiver Beweis sein (vielleicht eine Strategie einschließend, Argument stehlend), der keine Bewegungen des vollkommenen Spieles wirklich zu bestimmen braucht.

Schwacher

: Mehr normalerweise bedeutet das Lösen eines Spiels, einen Algorithmus zur Verfügung zu stellen, der einen Gewinn für einen Spieler oder eine Attraktion für auch gegen irgendwelche möglichen Bewegungen durch den Gegner vom Anfang des Spiels sichert. D. h. mindestens ein ganzes ideales Spiel erzeugend (fangen alle Bewegungen an zu enden), mit dem Beweis, dass jede Bewegung für den Spieler optimal ist, der es macht.

Starker

: Der stärkste Sinn der Lösung verlangt einen Algorithmus, der vollkommenes Spiel (Bewegungen) von jeder Position erzeugen kann, d. h. selbst wenn Fehler bereits auf einem oder beiden Seiten gemacht worden sind.

In Anbetracht der Regeln jedes Zwei-Personen-Spiels mit einer begrenzten Zahl von Positionen kann man immer einen minimax Algorithmus trivial bauen, der den Spielbaum erschöpfend überqueren würde. Jedoch seitdem für viele nichttriviale Spiele würde solch ein Algorithmus verlangen, dass eine unausführbare Zeitdauer eine Bewegung in einer gegebenen Position erzeugt, wie man betrachtet, wird ein Spiel schwach oder stark nicht gelöst, wenn der Algorithmus durch die vorhandene Hardware in einer angemessenen Frist nicht geführt werden kann. Viele Algorithmen verlassen sich auf eine riesige vorerzeugte Datenbank, und sind effektiv nichts anderes als das.

Als ein Beispiel ist das Spiel von tic-tac-toe als eine Attraktion für beide Spieler mit dem vollkommenen Spiel (ein Ergebnis lösbar, das sogar manuell durch Schulkinder bestimmbar ist). Spiele wie nim lassen auch eine strenge Analyse mit der kombinatorischen Spieltheorie zu.

Ob ein Spiel gelöst wird, ist nicht notwendigerweise dasselbe als, ob es interessant für Menschen bleibt zu spielen. Sogar ein stark gelöstes Spiel kann noch interessant sein, wenn die Lösung zu kompliziert ist, um eingeprägt zu werden; umgekehrt kann ein schwach gelöstes Spiel seine Anziehungskraft verlieren, wenn die Gewinnen-Strategie einfach genug ist, sich (z.B Maharadscha und Sepoys) zu erinnern. Eine ultraschwache Lösung (z.B. Kauen Sie Laut, oder Hexe auf einem genug großen Ausschuss) betrifft allgemein playability nicht.

Vollkommenes Spiel

In der Spieltheorie ist vollkommenes Spiel das Verhalten oder die Strategie eines Spielers, der zum bestmöglichen Ergebnis für diesen Spieler unabhängig von der Antwort durch den Gegner führt. Gestützt auf den Regeln eines Spiels kann jede mögliche Endposition (als ein Gewinn, Verlust bewertet werden oder ziehen). Durch das rückwärts gerichtete Denken kann man eine Nichtendposition als identisch zu dieser der Position rekursiv bewerten, die ist, rückt man ab und am besten geschätzt wegen des Spielers, dessen Bewegung es ist. So kann ein Übergang zwischen Positionen auf eine bessere Einschätzung für den bewegenden Spieler nie hinauslaufen, und eine vollkommene Bewegung in einer Position würde ein Übergang zwischen Positionen sein, die ebenso bewertet werden. Als ein Beispiel würde ein vollkommener Spieler in einer gezogenen Position immer eine Attraktion oder Gewinn, nie ein Verlust bekommen. Wenn es vielfache Optionen mit demselben Ergebnis gibt, wird vollkommenes Spiel manchmal als die schnellste Methode betrachtet, die zu einem guten Ergebnis oder der langsamsten Methode führt, die zu einem schlechten Ergebnis führt.

Vollkommenes Spiel kann zu nichtvollkommenen Informationsspielen als die Strategie verallgemeinert werden, die das höchste minimale erwartete Ergebnis unabhängig von der Strategie des Gegners versichern würde. Als ein Beispiel, die vollkommene Strategie für den Felsen, Zeitung, würde Schere jede der Optionen mit der gleichen (1/3) Wahrscheinlichkeit zufällig wählen sollen. Der Nachteil in diesem Beispiel ist, dass diese Strategie nichtoptimale Strategien des Gegners nie ausnutzen wird, so wird das erwartete Ergebnis dieser Strategie gegen jede Strategie immer dem minimalen erwarteten Ergebnis gleich sein.

Obwohl die optimale Strategie eines Spiels nicht (noch) bekannt sein darf, könnte ein spielspielender Computer noch aus Lösungen des Spiels von bestimmten Schlussphase-Positionen einen Nutzen ziehen (in der Form der Schlussphase tablebases), der ihm erlauben wird, vollkommen nach einem Punkt im Spiel zu spielen. Computerschachprogramme sind dafür weithin bekannt, das zu tun.

Gelöste Spiele

Awari (ein Spiel der Familie von Mancala)

: Die Variante von Oware, der Spiel erlaubt, das "großartigen Knall" beendet, wurde von Henri Bal und John Romein an Vrije Universiteit in Amsterdam, die Niederlande (2002) stark gelöst. Jeder Spieler kann das Spiel in eine Attraktion zwingen.

Essstäbchen

: Der zweite Spieler kann immer einen Gewinn zwingen.

Verbinden Sie vier

: Gelöst zuerst von James D. Allen (am 1. Okt 1988), und unabhängig durch Victor Allis (am 16. Okt 1988). Der erste Spieler kann einen Gewinn zwingen. Stark gelöst durch die 8-Falten-Datenbank von John Tromp (am 4. Febr 1995). Schwach gelöst für den ganzen boardsizes, wo width+height höchstens 15 (am 18. Febr 2006) ist.

Ziehen, Englisch (d. h. Kontrolleure)

: Das 8x8 Variante von Ziehen wurde am 29. April 2007 von der Mannschaft von Jonathan Schaeffer schwach gelöst, der für den Chinook, der "Weltkontrolleur-Meister der Mann-Maschine" bekannt ist. Von der Standardstartposition können beide Spieler eine Attraktion mit dem vollkommenen Spiel versichern. Kontrolleure sind das größte Spiel, das bis heute, mit einem Suchraum 5x10 gelöst worden ist. Die Zahl von beteiligten Berechnungen war 10, und diejenigen wurden über eine Zeitdauer von 18 Jahren getan. Der Prozess, der von 200 Tischcomputern an seiner Spitze unten zu ungefähr 50 beteiligt ist.

Fanorona

: Schwach gelöst von Maarten Schadd. Das Spiel ist eine Attraktion.

Freier Gomoku

: Gelöst von Victor Allis (1993). Der erste Spieler kann einen Gewinn zwingen, ohne Regeln zu öffnen.

Geist

: Gelöst von Alan Frank, der den Beamten verwendet, Scharren Wörterbuch 1987.

Hexe

:* Ein Strategie stehlendes Argument (wie verwendet, durch John Nash) wird zeigen, dass alle Quadratvorstandsgrößen vom ersten Spieler nicht verloren werden können. Verbunden mit einem Beweis der Unmöglichkeit einer Attraktion zeigt das, dass das Spiel gelöst als ein erster Spieler-Gewinn ultraschwach ist.

:* Stark gelöst durch mehrere Computer für Vorstandsgrößen bis zu 6×6.

:* Jing Yang hat eine Gewinnen-Strategie (schwache Lösung) für Vorstandsgrößen 7×7, 8×8 und 9×9 demonstriert.

:* Eine Gewinnen-Strategie für die Hexe mit dem Tauschen ist für 7×7 Ausschuss bekannt.

:* Die stark lösende Hexe auf einem N×N Ausschuss ist unwahrscheinlich, weil, wie man gezeigt hat, das Problem PSPACE-abgeschlossen gewesen ist.

:* Wenn Hexe auf einem N × N+1 Ausschuss dann der Spieler gespielt wird, der die kürzere Entfernung hat, um in Verbindung zu stehen, kann immer durch eine einfache zusammenpassende Strategie sogar mit dem Nachteil gewinnen, zweit zu spielen.

:* Eine schwache Lösung ist für alle öffnenden Bewegungen 8x8 Ausschuss bekannt.

Hexapawn

Kalah

: Die meisten Varianten, die von Geoffrey Irving, Jeroen Donkers und Jos Uiterwijk (2000) außer Kalah (6/6) gelöst sind. Die (6/6) Variante wurde von Anders Carstensen (2011) gelöst. Starker Vorteil des ersten Spielers wurde in den meisten Fällen bewiesen.

L Spiel

: Leicht lösbar. Jeder Spieler kann das Spiel in eine Attraktion zwingen.

Maharadscha und Sepoys

: Dieses asymmetrische Spiel ist ein Gewinn für den sepoys Spieler mit dem richtigen Spiel.

Nim

: Stark gelöst.

Morris von neun Männern

: Gelöst von Ralph Gasser (1993). Jeder Spieler kann das Spiel in eine Attraktion zwingen

Ohvalhu

: Schwach gelöst von Menschen, aber bewiesen durch Computer. (Dakon ist jedoch zu Ohvalhu, das Spiel, nicht identisch, das wirklich von de Voogt beobachtet worden war)

Pentominoes

: Schwach gelöst von H. K. Orman. Es ist ein Gewinn für den ersten Spieler.

Quartband

: Gelöst von Luc Goossens (1998). Zwei vollkommene Spieler werden immer ziehen.

Qubic

: Schwach gelöst von Oren Patashnik (1980) und Victor Allis. Der erste Spieler gewinnt.

Freier Renju

: (Ohne Regeln zu öffnen) hat behauptet, von János Wagner und István Virág (2001) gelöst zu werden. Ein Gewinn des ersten Spielers.

Sim

: Schwach gelöst: Gewinn für den zweiten Spieler.

Teeko

: Gelöst von Guy Steele (1998). Abhängig von der Variante gewinnt entweder ein erster Spieler oder eine Attraktion.

Drei Musketiere

: Stark gelöst von Johannes Laire 2009. Es ist ein Gewinn für die blauen Stücke (Die Männer von Kardinal Richelieu, oder, der Feind).

Morris von drei Männern

: Trivial lösbar. Jeder Spieler kann das Spiel in eine Attraktion zwingen.

Tic-tac-toe

: Trivial lösbar. Jeder Spieler kann das Spiel in eine Attraktion zwingen.

Tiger und Ziegen

: Schwach gelöst von Yew Jin Lim (2007). Das Spiel ist eine Attraktion.

Teilweise gelöste Spiele

Schach

: Gelöst durch die rückläufige Computeranalyse für alle drei - zum sechsteiligen, und einige siebenteilige Schlussphasen, die zwei Könige als Stücke aufzählend. Es wird für alle 3-3 und 4-2 Schlussphasen mit und ohne Pfänder gelöst, wo, wie man annimmt, 5-1 Schlussphasen mit einigen trivialen Ausnahmen gewonnen werden (sieh Schlussphase tablebase für eine Erklärung). Das volle Spiel hat 32 Stücke. Schach auf 3x3 Ausschuss wird von Kirill Kryukov (2004) stark gelöst. Die Frage dessen, ob Schach in der Zukunft vollkommen gelöst werden kann, ist umstritten.

Internationale Ziehen

: Alle Positionen mit zwei bis sieben Stücken wurden gelöst. Positionen mit 4x4 und 5x3 Stücke, wo jede Seite einen König oder weniger hatte. Positionen mit fünf Männern gegen vier Männer, fünf Männer gegen drei Männer und einen König, und vier Männer und einen König gegen vier Männer. Gelöst 2007 von Ed Gilbert der Vereinigten Staaten, Computeranalyse-Show, die hoch wahrscheinlich es immer in einer Attraktion beendet, wenn beide Spieler vollkommen spielen.

Gehen Sie

: Vorstandsgrößen bis zu 4×4 werden stark gelöst. 5×5 wird Vorstands-für alle öffnenden Bewegungen schwach gelöst. Menschen spielen gewöhnlich auf 19×19 Ausschuss, der mehr als 145 Größenordnungen ist, die komplizierter sind als 7x7.

Reversi (Othello)

: Stark gelöst auf 4×4 und 6×6 Ausschuss als ein zweiter Spieler-Gewinn im Juli 1993 durch Joel Feinstein. Auf 8×8 Ausschuss (der normale) ist es mathematisch ungelöst, obwohl Computeranalyse eine wahrscheinliche Attraktion zeigt. Keine stark angenommenen Schätzungen außer vergrößerten Chancen für den Startspieler, der auf 10×10 und größere Ausschüsse (schwarz) ist, bestehen.

M, n, K-Spiel

: Es ist trivial, um zu zeigen, dass der zweite Spieler nie gewinnen kann; sieh Strategie stehlendes Argument. Fast alle Fälle sind schwach für k  4 gelöst worden. Einige Ergebnisse sind für k = 5 bekannt. Die Spiele werden für k  8 gezogen.

Siehe auch

• Computerschach
• Computer Othello
• Spielkompliziertheit
• Der Algorithmus des Gottes
• Der Lehrsatz von Zermelo (Spieltheorie)

Weiterführende Literatur

• Allis, den Weltmeister Prügelnd? Das modernste im Computerspiel-Spielen. in Neuen Annäherungen an die Brettspiel-Forschung.

Außenverbindungen

• Rechenbetonte Kompliziertheit von Spielen und Rätseln durch David Eppstein.
• GamesCrafters - beim Lösen von Zwei-Personen-Spielen mit der vollkommenen Information und keiner Chance