Gewinnstrategie

aus Wikipedia, der freien Enzyklopädie

Für ein Spiel mit vollständiger Information können verschieden starke Gewinnstrategien aufgestellt werden:

• Sehr schwache Gewinnstrategie: Es kann bewiesen werden, dass ein bestimmter Spieler bei perfektem Spiel gewinnen oder zumindest ein Unentschieden herbeiführen kann. Der Beweis kann dabei unter Umständen keine Aussage dazu machen, wie zu spielen ist.

• Schwache Gewinnstrategie: Es kann ein Algorithmus angegeben werden, der den Spieler ausgehend vom aktuellen Spielstand zu einem Gewinn oder Unentschieden führt, unabhängig von den Zügen des Gegenspielers.

• Starke Gewinnstrategie: Ein allgemeiner Algorithmus existiert, der unabhängig vom aktuellen Spielstand perfektes Spiel vorgibt, auch, wenn in den bisherigen Zügen bereits Fehler gemacht wurden. Für ein Spiel mit einer endlichen Anzahl von Zügen bzw. Positionen ist dies grundsätzlich möglich, z.B. mit Hilfe eines genügend schnellen Computers. Das Problem könnte jedoch darin liegen, einen effizienten Algorithmus zu erstellen.

[Bearbeiten] Gelöste Spiele

• Fünf in eine Reihe (Gomoku)
  • Gelöst von Victor Allis (1993). Der Spieler mit dem ersten Zug gewinnt. Starke Gewinnstrategie.

• L-Spiel
  • Einfach zu lösen, zwei perfekte Spieler werden endlos lange spielen, ohne zu verlieren. Starke Gewinnstrategie.

• Nim-Spiel
  • Komplett gelöst für alle Variationen, starke Gewinnstrategie.

• Pentamino
  • Es existiert eine schwache Gewinnstrategie, nach der der Spieler mit dem ersten Zug gewinnen kann.

• Tic Tac Toe
  • Trivial, perfekte Spieler werden immer zu einem Unentschieden kommen.

• Vier gewinnt
  • Gelöst von Victor Allis (1988) und James D. Allen (1989) unabhängig voneinander. Der Spieler mit dem ersten Zug gewinnt.

[Bearbeiten] 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
  • Es existiert eine starke Gewinnstrategie für 4×4 Spielfelder (ein normales Spiel wird auf einem 19×19 Spielfeld gespielt)

• Othello (Reversi)
  • Für 4×4 und 6×6 Spielfelder existieren starke Gewinnstrategien, der zweite Spieler am Zug gewinnt. Für das Standard 8×8 Spielfeld und größeren Felder mit einer graden Anzahl von Zeilen und Spalten wird vermutet, das zwei perfekte Spieler ein Unentschieden herbeiführen können. Das 8×8 Spielfeld ist fast komplett untersucht.

• Schach
  • Endspiele für 2 bis 5 Steine sind gelöst (starke Gewinnstrategie).

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