Ist Dame ein gelöstes Spiel? Ja – und das bedeutet es konkret

Was bedeutet es, wenn ein Spiel „gelöst“ ist?

In der Spieltheorie gilt ein Spiel als gelöst, wenn bei perfektem Spiel jede Position hinsichtlich des Ergebnisses deterministisch ist. Bei der Untersuchung der Geschichte des Dame-Spiels konnten Forscher schließlich nachweisen, dass das Spiel bei perfektem Spiel beider Seiten unentschieden endet.

Es gibt drei Stufen der Spiellösung:

• Ultra-schwach gelöst: Ein Computer kann nachweisen, dass der erste Spieler beim ersten Zug gewinnen, verlieren oder unentschieden spielen kann, kennt aber möglicherweise nicht alle nachfolgenden Züge.
• Schwach gelöst: Das Spiel ist ausgehend von der Startposition gelöst und liefert eine Strategie, mit der gegen jeden Gegner das vorhergesagte Ergebnis erzielt wird.
• Stark gelöst: Der Computer kennt den besten Zug in einer bestimmten Spielposition, unabhängig von der Anzahl der zuvor begangenen Fehler.

Dame gilt als schwach gelöst. Wissenschaftler haben festgestellt, dass das Spiel zwangsläufig unentschieden endet, wenn keiner der Spieler einen Fehler begeht.

Wer hat das Dame-Spiel gelöst? Die Geschichte von Jonathan Schaeffer und Chinook

Jonathan Schaeffer und seinem Team an der University of Alberta wird die Lösung des Dame Spiels zugeschrieben. Das Projekt begann 1989 mit der Entwicklung eines Computerprogramms namens Chinook.

Es war kein Erfolg über Nacht. Das Projekt dauerte 18 Jahre und erforderte enorme Rechenleistung sowie fortschrittliche Algorithmen. Der schlüssige Beweis wurde schließlich 2007 in der Fachzeitschrift Science veröffentlicht.

Wie hat Chinook das Dame-Spiel gemeistert? Die Methode einfach erklärt

Ein Spiel mit 500 Billiarden ($5 \times 10^{20}$) möglichen Stellungen zu lösen, ist nicht einfach, indem man alle Züge ausprobiert. Würde man versuchen, sie einzeln zu zählen, wäre das Universum am Ende, bevor man fertig wäre. Aufgrund dieser Komplexität fragen sich viele Menschen, ob Schach schwieriger ist als Dame, da beide Spiele eine immense Rechenleistung zur Analyse erfordern. Anstelle von reiner Berechnung wandte das Chinook-Team zwei Haupttechniken an:

1. Die Endspiel-Datenbank

Das Team begann nach Spielende und arbeitete sich dann rückwärts vor. Es berechnete alle möglichen Stellungen mit zwei Steinen auf dem Brett, dann mit drei, dann mit vier und so weiter bis zu zehn. Dadurch konnte der Computer den Ausgang der Partie erkennen, sobald nur noch 10 Figuren übrig waren.

2. Heuristische Suche

Für die Partie in der Mitte, wo es zu viele Figuren gibt, um jeden Zweig zu berechnen, nutzte Chinook fortschrittliche Suchalgorithmen. Es erkundete die wahrscheinlichsten Wege von der Startposition zu den „bekannten“ Ergebnissen in der Endspieldatenbank.

Bis 2007 hatte Chinook genügend dieser Wege untersucht, um nachzuweisen, dass der Eröffnungszug zu einem Unentschieden führt. Wenn man heute gegen Chinook spielt, kann man bestenfalls auf ein Unentschieden hoffen, und wenn man auch nur einen kleinen Fehler macht, verliert man.

Marion Tinsley: Der Mensch, der dem perfekten Dame-Spiel am nächsten kam

Man kann nicht darüber sprechen, wie man auf höchstem Niveau Dame gewinnt, ohne Dr. Marion Tinsley zu erwähnen. Tinsley, der oft als der größte Dame-Spieler aller Zeiten angesehen wird, war eine menschliche Ausnahmeerscheinung. In seiner 45-jährigen Karriere verlor er Berichten zufolge nur sieben Partien.

1992 spielte Chinook gegen Tinsley um die Weltmeisterschaft. Tinsley gewann. Es war ein Meilenstein für die menschliche Intuition gegenüber roher Rechenleistung. Bei ihrem Rückkampf 1994 musste Tinsley jedoch aus gesundheitlichen Gründen zurücktreten, und Chinook wurde schließlich das erste Programm, das einen menschlichen Weltmeistertitel gewann.

Tinsleys Fähigkeit, das Spielbrett zu überblicken, war so außergewöhnlich, dass Forscher seine Partien nutzten, um Chinooks Logik zu verfeinern. Er war in jeder Hinsicht das menschliche Äquivalent eines gelösten Algorithmus.

Was bedeutet „gelöst“ eigentlich für Dame-Spieler?

Bedeutet die Tatsache, dass Dame gelöst ist, dass das Spiel tot ist? Keineswegs. Für den durchschnittlichen Spieler hat die Lösung so gut wie keine Auswirkungen. Die Komplexität von 500 Billiarden Stellungen liegt immer noch weit außerhalb der Reichweite des menschlichen Gehirns. Man kann sich die Lösung nicht merken, daher bleibt jede Partie, bei der man sich auf eine bestimmte Anordnung auf dem Dame-Brett konzentriert, eine Prüfung von Geschicklichkeit, Psychologie und Strategie.

In der Welt des hochkarätigen Wettkampfspiels führte die Tatsache, dass das Spiel gelöst ist, jedoch zur Einführung von 3-Zug-Beschränkungen. In diesen Turnieren werden die ersten drei Züge zufällig aus einem Kartenspiel gezogen. Dies zwingt die Spieler in unkonventionelle Stellungen und verhindert, dass sie jedes Mal einfach das perfekte Unentschieden ausspielen können.

Vergleich gelöster Spiele: Dame vs. Schach vs. andere Spiele

Was „gelöst“ für moderne Spieler bedeutet

Obwohl Computer jeden Menschen im Schach schlagen können, haben sie das Schachspiel nicht „gelöst“, da die Anzahl der möglichen Züge so enorm ist, dass es unmöglich ist, sie vollständig abzudecken. Dame wurde „gelöst“, weil es eine überschaubare Anzahl von Stellungen gibt, die ein Computer irgendwann beherrschen würde, während es im Schach mehr Varianten gibt als Atome im Universum.

Auch wenn ein Programm wie Stockfish unglaublich intelligent sein mag, berechnet es also immer noch lediglich die bestmögliche Vermutung, anstatt einem bewährten Spielzug bis zum Ende zu folgen. Dies verdeutlicht den Hauptunterschied zwischen Schach und Dame, wenn es um rechnerische Grenzen geht. In einem gelösten Spiel wie Dame können wir sicher sein, dass das perfekte Spiel zu einem Unentschieden führt, aber im Schach haben wir keine Ahnung, ob das perfekte Spiel zu einem Unentschieden oder zu einem garantierten Sieg für eine Seite führt.