Gelöste Spiele

Ein gelöstes Spiel ist ein Spiel, dessen Ausgang (Sieg, Niederlage oder Unentschieden) von jeder Stellung aus korrekt vorhergesagt werden kann, vorausgesetzt, alle Parteien spielen optimal. Dieses Konzept wird meist auf Strategiespiele angewendet, insbesondere auf solche mit perfekter Information und ohne Zufallselemente. Die Lösung solcher Spiele beruht meist auf Kombinatorik und Spieltheorie oder Brute-Force Lösungen durch Computer.

Ein zufallsfreies Zwei-Personen-Spiel mit perfekter Information kann in unterschiedlicher Weise gelöst werden:^[1][2]

• Sehr schwach gelöst (engl. ultra weakly solved) ist ein Spiel, wenn man für die Startposition des Spieles dasjenige Spielergebnis bestimmen kann, das jeder der beiden Spieler unabhängig von der Spielweise seines Gegners mindestens erzwingen kann. Ein diesbezüglicher Nachweis muss über die dafür notwendigen Spielweisen keine Aussage machen.
• Schwach gelöst ist ein Spiel, wenn darüber hinaus ein praktisch realisierbarer Algorithmus angegeben werden kann, mit dem die beidseitig optimalen Spielweisen ausgehend von der Startposition des Spiels bestimmt werden können.
• Stark gelöst ist ein Spiel, wenn ein allgemeiner, praktisch realisierbarer Algorithmus existiert, mit dem für jede Position ein optimaler Zug berechnet werden kann. Im Unterschied zu schwach gelösten Spielen muss dieser Algorithmus auch für solche Positionen funktionieren, die ausgehend von der Ausgangsposition nur bei fehlerhafter Spielweise vorkommen.

Wichtig ist die Anforderung eines praktisch (auf einem Computer) realisierbaren Algorithmus, da mit dem Minimax-Algorithmus stets ein allgemeines Verfahren existiert, mit dem theoretisch für jede Position eines endlichen Zwei-Personen-Spiels mit vollständiger Information ein optimaler Zug berechnet werden kann.

• Checkers, die amerikanische Dame-Version, wurde von Jonathan Schaeffer 2007 schwach gelöst: Ein perfekter Spieler verliert demnach nie.
• Fanorona: Schwach gelöst. Unentschieden.
• Fünf in eine Reihe (Free-style Gomoku, ohne Eröffnungsregeln): Stark gelöst von Victor Allis (1993). Der anziehende Spieler besitzt eine Gewinnstrategie, d. h., er kann einen Gewinn erzwingen.
• Hex wurde durch John Nash 1947 sehr schwach gelöst: Ohne Tauschregel muss für den anziehenden Spieler eine Gewinnstrategie existieren, denn einerseits kann keine Partie remis enden und andererseits kann der nachziehende Spieler keine Gewinnstrategie besitzen, da sonst der anziehende Spieler diese übernehmen könnte (Argument des so genannten Strategieklaus). Mit der Tauschregel existiert für den nachziehenden Spieler eine Gewinnstrategie.
• L-Spiel: Stark gelöst. Ausgehend von der Anfangsposition können zwei perfekte Spieler endlos lange spielen, ohne zu verlieren.
• Nim-Spiel: Stark gelöst mit Methoden der Kombinatorischen Spieltheorie, auch für alle Varianten, bei denen der zuletzt ziehende Spieler gewinnt (Satz von Sprague-Grundy).
• Mühle wurde durch Ralph Gasser 1993 schwach gelöst. Stark gelöst wurde Mühle – unabhängig voneinander – durch die Informatiker Peter Stahlhacke (Mr. Data) und Alexander Szabari (2013 – Brillant Mill): Eine Partie endet bei perfektem Spiel beiderseits immer Remis.^[3]
• Pentago: Stark gelöst von Geoffrey Irving (2014). Der erste Spieler gewinnt.^[4]
• Pentominos: Schwach gelöst. Der anziehende Spieler besitzt eine Gewinnstrategie.^[5]
• Räuberschach: Schwach gelöst. Weiß gewinnt mit 1.e3.^[6]
• Sim: Der zweite Spieler gewinnt.
• Solitaire: Stark gelöst^[7].
• Tic-Tac-Toe: Aufgrund des kleinen Entscheidungsbaums bereits früh stark gelöst. Bereits 1972 wurden basierend auf 8 Regeln perfekte Tic-Tac-Toe Programme entwickelt, die jedes Spiel gewinnen oder zumindest ein Unentschieden erzwingen konnten.^[8]

  

• Vier gewinnt: Zunächst schwach gelöst, und zwar unabhängig voneinander von Victor Allis (veröffentlicht 1988) und James D. Allen (veröffentlicht 1990). Der anziehende Spieler besitzt eine Gewinnstrategie, falls er in der mittleren Spalte beginnt. Beginnt er in der Spalte links oder rechts daneben, endet das Spiel bei beiderseits perfektem Spiel remis; wirft er seinen ersten Stein in eine der vier restlichen Spalten, verliert er gegen einen perfekten Gegner. 2025 wurde eine starke Lösung des Spiels veröffentlicht.^[9]

• Damespiel (10×10 Brett)
  Endspiele mit 8 Steinen, dazu einige 9-Steiner sind stark gelöst.^[10][11]
• Go
  5×5 wurde 2002 gelöst.^[12] 7×7 wurde 2015 gelöst.^[13]
• Othello (Reversi)
  auf 4×4- und 6×6-Spielbrettern wurde stark gelöst, dabei besitzt der nachziehende Spieler eine Gewinnstrategie. Für das übliche 8×8-Spielbrett und größere Spielbretter mit einer graden Anzahl von Zeilen und Spalten wird vermutet, dass zwei perfekte Spieler ein Unentschieden herbeiführen können. Das übliche Spiel auf einem 8×8-Spielbrett ist fast komplett untersucht.
• Schach
  Zunehmend im Endspiel gelöst. Perfekte Lösungen aller Schachkombinationen mit bis zu 7 Figuren (einschließlich Könige) sind seit 2012 öffentlich in Tabellen zugänglich, an der Lösung von 8 Figuren wird seitdem gerechnet.^[14]
• Sprouts
  Für bis zu 6 Punkte lassen sich Gewinnstrategien manuell bestimmen, mit Computerhilfe wurden Strategien für bis zu 32 (und teilweise 47) Punkte untersucht.^[15]