Gelöste Spiele

Ein zufallsfreies Zwei-Personen-Spiel mit perfekter Information kann in unterschiedlicher Weise gelöst werden:

  • 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.

Gelöste Spiele

  • 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.[1]
  • Pentago: Stark gelöst von Geoffrey Irving (2014). Der erste Spieler gewinnt.[2]
  • Pentominos: Schwach gelöst. Der anziehende Spieler besitzt eine Gewinnstrategie.[3]
  • Räuberschach: Schwach gelöst. Weiß gewinnt mit 1.e3.[4]
  • Sim: Der zweite Spieler gewinnt.
  • Solitaire: Stark gelöst[5].
  • Tic-Tac-Toe: Stark gelöst. Offensichtlich muss kein Spieler verlieren.
  • Vier gewinnt: 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.

Teilweise gelöste Spiele

  • Damespiel (10×10 Brett)
    Endspiele mit 8 Steinen, dazu einige 9-Steiner sind stark gelöst.[6][7]
  • Go
    5×5 wurde 2002 gelöst.[8] 7×7 wurde 2015 gelöst.[9]
  • 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
    Endspiele mit 2 bis 8 Steinen (Könige mitgerechnet) sind gelöst.
  • 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.[10]

Quellen

  1. ↑ Ralph Gasser: Solving Nine Men's Morris, Games of No Chance, MSRI Publications, Volume 29, 1996, S. 101–113 (PDF; 236 kB)
  2. ↑ Geoffrey Irving: Pentago is a first player win. Abgerufen am 30. Januar 2014.
  3. ↑ H. K. Orman: Pentominoes: A First Player Win, Games of No Chance, MSRI Publications, Volume 29, 1996, S. 339–345 (PDF; 131 kB)
  4. ↑ John Beasley: Losing Chess : 1 e3 is a win for White (reporting work by Mark Watkins). Mit Verlinkung des Aufsatzes von Watkins. Englisch. Abgerufen am 15. November 2018
  5. ↑ Eichler, Jäger, Ludwig (c’t 07/1999) Spielverderber, Solitaire mit dem Computer lösen
  6. ↑ KingsRow: 8-Stein Datenbank vollständig erstellt (Memento vom 8. März 2010 im Internet Archive)
  7. ↑ KingsRow: Turnierbericht (Memento vom 2. März 2010 im Internet Archive)
  8. ↑ 5x5 Go is solved by Erik van der Werf
  9. ↑ 7×7 Go is solved (article in Chinese)
  10. ↑ Julien Lemoine, Simon Viennot: Computer analysis of Sprouts with nimbers. 13. August 2010 (msri.org [PDF; abgerufen am 7. Januar 2022]).