ein-handwerker.de

Gelöste Spiele

18.04.2012 @ 19:04, Frakturfreund,

Ein zufallsfreies Zwei-Personen-Spiel mit perfekter 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

*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: 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 (Satz von Satz von Sprague-Grundy).

*Mühle: Schwach gelöst von Ralph Gasser (1993): Ein perfekter Spieler verliert nie.[http://www.msri.org/publications/books/Book29/files/gasser.pdf Ralph Gasser: Solving Nine Men's Morris, Games of No Chance, MSRI Publications, Volume 29, 1996, S. 101–113]

*Pentominos: Schwach gelöst. Der anziehende Spieler besitzt eine Gewinnstrategie.[http://www.msri.org/publications/books/Book29/files/orman.pdf H. K. Orman: Pentominoes: A First Player Win, Games of No Chance, MSRI Publications, Volume 29, 1996, S. 339–345]

*Sim: Der zweite Spieler gewinnt.

*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 (10x10 Brett)
Endspiele mit 8 Steinen, dazu einige 9-Steiner sind stark gelöst.[http://pages.prodigy.net/eyg/Checkers/8_piece_international_draughts_db.htm KingsRow: 8-Stein Datenbank vollständig erstellt][http://pages.prodigy.net/eyg/Checkers/Culemborg2007.htm KingsRow: Turnierbericht]

*Go
5x5 wurde gelöst.[http://erikvanderwerf.tengen.nl/5x5/5x5solved.html 5x5 Go is solved] by Erik van der Werf Menschliche Berechnungen von bis zu 6x7 von Ted Drangehttp://www.mathpuzzle.com/go.html und 7x7 von Kudo Norio and Nakayama Noriyukihttp://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.pdf, p. 54, beruft sich auf: J. Davies. 7x7 Go. American Go Journal, 29(3):11, 1995. sind vermutlich keine Lösungen im mathematischen Sinn.http://senseis.xmp.net/?SmallBoardGo

*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 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

!

weiter