Nein, 8×8 Reversi (Othello) wurde nicht gelöst. Während Computer eine übermenschliche Stärke erreicht haben — das Endspiel perfekt lösend und auf einem Niveau spielend, das kein Mensch konstant erreichen kann — wurde der vollständige Spielbaum (~10^28 mögliche Positionen) noch nie erschöpfend analysiert. Kleinere Varianten wurden gelöst: 6×6 Reversi ist ein bewiesener Sieg des ersten Spielers unter perfektem Spiel. Das 8×8-Spiel bleibt offen. Wie sich dies auf die Programme auswirkt, die Spieler heute verwenden, erfahren Sie unter Wie Reversi-KI funktioniert und Reversi-Software-Tools.
Was bedeutet es, ein Spiel zu „lösen"?
In der Spieltheorie gilt ein Spiel als gelöst, wenn das Ergebnis des perfekten Spiels von der Ausgangsposition bewiesen ist — Sieg, Niederlage oder Unentschieden — unabhängig davon, was beide Spieler tun. Es gibt zwei Lösungsebenen:
Schwach gelöst: Das Ergebnis von der Ausgangsposition unter perfektem Spiel ist bekannt. Sie wissen, dass der erste Spieler gewinnt (oder unentschieden spielt oder verliert), aber Sie haben nicht unbedingt eine vollständige Strategiekarte.
Stark gelöst: Perfektes Spiel wird von jeder möglichen Position im Spiel berechnet. Eine vollständige Strategie, die zum optimalen Ergebnis führt, ist unabhängig davon bekannt, wo im Spiel Sie sich befinden.
Die meisten „gelösten" Spiele sind nur schwach gelöst. Starke Lösungen erfordern enorme Rechenressourcen.
Bekannte gelöste Spiele
| Spiel | Status | Ergebnis | Jahr |
|---|---|---|---|
| Tic-Tac-Toe | Stark gelöst | Unentschieden | Seit der Antike bekannt |
| Vier gewinnt | Stark gelöst | Erster Spieler gewinnt | 1988 (Victor Allis) |
| Dame (8×8) | Schwach gelöst | Unentschieden | 2007 (Schaeffer et al., Science) |
| 6×6 Reversi | Schwach gelöst | Erster Spieler gewinnt | 1993 (Allis & Buro) |
| Schach (8×8) | Ungelöst | Unbekannt | — |
| Go (19×19) | Ungelöst | Unbekannt | — |
| 8×8 Reversi (Othello) | Ungelöst | Unbekannt | — |
Warum wurde 8×8 Reversi noch nicht gelöst?
Das Ausmaß des Problems
Der Spielbaum von Reversi ist groß, wenn auch nicht astronomisch gemessen an den Standards komplexer Brettspiele:
- Mögliche Positionen: Geschätzt auf ungefähr 10^28
- Durchschnittlicher Verzweigungsfaktor: Etwa 10 legale Züge pro Position
- Spiellänge: 60 Züge insgesamt (einer pro leerem Feld, ab den 4 Startsteinen)
Zum Vergleich:
- Schach hat ungefähr 10^44 mögliche Positionen und 10^123 Spielbaumknoten
- Go (19×19) hat ungefähr 10^170 mögliche Positionen
Reversi ist nach den Standards dieser Spiele handhabbar — aber 10^28 Positionen liegen immer noch weit jenseits erschöpfender Aufzählung mit aktueller Hardware. Das Lösen von Dame (10^21 Positionen) erforderte Jahrzehnte des verteilten Rechnens — Jonathan Schaeffer und Kollegen an der Universität Alberta benötigten fast zwei Jahrzehnte Arbeit, bevor sie ihren Beweis 2007 in Science veröffentlichten. Der Spielbaum von Reversi ist ungefähr 10 Millionen Mal größer.
Warum Endspiele gelöst sind, aber vollständige Spiele nicht
Die entscheidende Asymmetrie in der Reversi-Berechnung: Endspiele sind handhabbar, vollständige Spiele nicht.
Mit noch 20 leeren Feldern gibt es höchstens 10^20 Positionen von diesem Zustand aus zu berücksichtigen — und starke Programme können diese in Sekunden lösen. Mit 25 leeren Feldern ist es mit guter Hardware noch machbar. Aber das Lösen ab Zug 1 erfordert, perfektes Spiel rückwärts durch den gesamten Spielbaum zu propagieren, was rechentechnisch außer Reichweite bleibt.
Deshalb spielen Computer-Reversi-Programme das Endspiel perfekt, verwenden aber heuristische Bewertung (Bewertungsfunktionen) für das Früh- und Mittelspiel. Die Heuristiken sind sehr stark — stark genug, um jeden Menschen zu schlagen — aber sie sind nicht nachweislich perfekt.
Die 6×6-Lösung
1993 bestätigten die Forscher Victor Allis und Michael Buro, dass 6×6 Reversi unter perfektem Spiel ein Sieg des ersten Spielers ist. Die Analyse war machbar, da 6×6 nur 36 Felder und einen weit kleineren Spielbaum als die Standard-8×8-Version hat. Allis hatte zuvor ähnliche retrograde Analysetechniken angewendet, um Vier gewinnt zu lösen (1988).
Dieses Ergebnis ist wichtig für das Verständnis des 8×8-Spiels: Es legt nahe, dass das Ergebnis des perfekten 8×8-Reversi nicht aus grundlegenden Prinzipien offensichtlich ist. Das 6×6-Ergebnis bestätigte auch, dass der Erstspielervorteil (Schwarz zieht zuerst) bei kleineren Brettgrößen entscheidend sein kann. Weitere Informationen zu Reversi-Varianten und kleineren Brettgrößen finden Sie unter Reversi-Varianten.
Wie stark ist Computer-Reversi heute?
Obwohl das Spiel nicht gelöst ist, haben Computer ein Spielniveau erreicht, das weit über jedem Menschen liegt. Wichtige Meilensteine:
Logistello (1990er Jahre)
Entwickelt von Michael Buro an der Universität Alberta, war Logistello eines der ersten Programme, das menschliche Weltmeister dominierte. 1997 besiegte Logistello den Othello-Weltmeister Takeshi Murakami mit 6–0 in einem Match. Das Programm kombinierte tiefe Alpha-Beta-Suche mit einer ausgeklügelten erlernten Bewertungsfunktion, wie in Buros 1997er Artikel im ICCA Journal beschrieben.
Dies war ein historischer Moment — ähnlich wie als IBMs Deep Blue im selben Jahr Kasparov im Schach besiegte. Reversi-Computer hatten für praktische Zwecke die menschliche Fähigkeit übertroffen.
Moderne Programme
Zeitgenössische Reversi-Programme verwenden:
- Endspiel-Löser: Perfektes Spiel für die letzten 20–25 Züge
- Musterbasierte Bewertung: Heuristiken, trainiert auf Millionen von Spielen
- Bewertung mit neuronalen Netzen: Neuere Programme integrieren Deep-Learning-Ansätze ähnlich AlphaZero
- Eröffnungsbücher: Datenbanken analysierter Eröffnungspositionen
Diese Programme sind im ernsthaften Spiel praktisch unschlagbar für Menschen, obwohl sie kein nachweislich perfektes Spiel von Zug eins an ausführen.
Was wäre erforderlich, um 8×8 Reversi zu lösen?
Rein hypothetisch würde eine vollständige schwache Lösung Folgendes erfordern:
- Hardware: Entweder einen Quantencomputer mit ausreichend Qubits oder einen massiv verteilten klassischen Rechenaufwand, der viele Größenordnungen über dem liegt, was Dame gelöst hat
- Algorithmus: Retrograde Analyse (rückwärts von allen Endpositionen lösen) kombiniert mit aggressiver Symmetriereduzierung
- Zeit: Geschätzt möglicherweise Jahrhunderte mit aktueller klassischer Hardware; weit weniger mit zukünftigen Technologien
Die praktische Auswirkung einer solchen Lösung wäre für Spieler interessant, aber etwas antiklimatisch — da Computer bereits auf übermenschlichem Niveau spielen, würde das Kennen des theoretischen Ergebnisses unter perfektem Spiel die menschliche Erfahrung des Spiels nicht verändern.
Was der „nahezu gelöste" Status für Spieler bedeutet
Die Tatsache, dass Computer Reversi dominieren, hat reale praktische Auswirkungen:
Für das Lernen: Computeranalyse kann Ihnen den besten Zug in fast jeder Position zeigen. Gegen starke KI zu spielen und Spiele zu analysieren ist eine der effektivsten Methoden zur Verbesserung.
Für das Wettkampfspiel: Menschen treten weiterhin auf höchstem Niveau an, da menschliche Psychologie, Ausdauer, Zeitmanagement und Eröffnungsvorbereitung unter Turnierbedingungen eine Rolle spielen — auch gegen andere Menschen. Die WOC bleibt eine bedeutungsvolle Meisterschaft.
Für die Wertschätzung des Spiels: Anders als bei einigen Spielen, bei denen die Computer-Dominanz die Begeisterung gedämpft hat, hat die Reversi-Gemeinschaft die Computeranalyse als Lehrmittel angenommen. Eröffnungstheorie, Endspiel-Technik und positionelles Verständnis haben sich alle aufgrund der KI-Analyse vertieft.
Vergleich mit Schach und Go
| Schach | Go | Reversi (8×8) | |
|---|---|---|---|
| Spielbaumgröße | ~10^123 | ~10^360 | ~10^28 |
| Gelöst? | Nein | Nein | Nein |
| Computerstärke | Übermenschlich (ab 2005) | Übermenschlich (ab 2016) | Übermenschlich (ab 1997) |
| Endspiel perfekt? | Endspiel-Tablebases (7 Figuren) | Teilweise | Ja (letzte 20–25 Züge) |
| Lösungsaussicht | Sehr gering (Jahrhunderte) | Im Wesentlichen null | Gering, aber denkbar |
Reversi ist angesichts seines kleineren Zustandsraums das wahrscheinlichste der drei, irgendwann gelöst zu werden — bleibt aber auf absehbare Zeit ein offenes Problem.