Gewinnstrategie

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

• Sehr schwach gelöst (engl. ultra weak 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

• Dame
  Checkers, die amerikanische Dame-Version, wurde von Jonathan Schaeffer 2007 schwach gelöst: Ein perfekter Spieler verliert demnach nie.

• 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: Für den anziehenden Spieler muss 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).

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

• Mühle
  Schwach gelöst von Ralph Gasser (1993): Ein perfekter Spieler verliert nie.^[1]

• Pentominoes
  Schwach gelöst. Der anziehende Spieler besitzt eine Gewinnstrategie.^[2]

• 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
  Endspiele mit 9 und (teilweise) 10 Steinen sind gelöst, einige Eröffnungen wurden untersucht. Für eine Eröffnung konnte nachgewiesen werden, dass sie zu einem Unentschieden führt. Für die vollständige Lösung werden schnellere Computer benötigt.

• Go
  auf einem 2×2 bis 7×6-Spielbrett ohne komi (statt des üblichen 19×19-Spielbretts) wurde stark gelöst.

• Othello (Reversi)
  auf 4×4- und 6×6-Spielbrettern wurde stark gelöst, dabei besitzt der nachziehnde Spieler eine Gewinnstrategie. Für das übliche 8×8-Spielbrett und größeren Spielbrettern 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 6 Steinen und einige mit 7 Steinen (Könige mitgerechnet) sind stark gelöst.

• Sprouts
  Für bis zu 6 Punkte lassen sich Gewinnstrategien manuell bestimmen, mit Computerhilfe wurden Strategien für bis zu 11 Punkte untersucht.

Quellen

1. ↑ Nine Men's Morris is a Draw by Ralph Gasser
2. ↑ Gewinnstrategie (engl. PDF-Datei)