Ist Dame rechnerisch gelöst? Wie 18 Jahre Rechenzeit das Unentschieden bewiesen und was das für Spieler bedeutet

Jahrhundertelang grübelten Mathematiker, Großmeister und begeisterte Amateure über eine grundlegende Frage: Besitzt das Damespiel einen unerbittlichen theoretischen Ausgang? Wenn zwei Meister fehlerfrei spielen, erzwingt der anziehende Spieler dann einen Vorteil, oder führt das Ringen unausweichlich zu einer gerechten Punkteteilung? Am Brett erlebten Generationen packende Stellungsgefechte, doch das letzte mathematische Geheimnis blieb lange Zeit im Verborgenen.

Im Sommer 2007 brachte ein Meilenstein der Informatik endgültige Klarheit^[1]. Ein Forscherteam an der University of Alberta unter der Leitung von Jonathan Schaeffer veröffentlichte im renommierten Fachjournal Science den Beweis, dass das Damespiel rechnerisch gelöst ist. Nach einem gigantischen Rechenprojekt, das 18 Jahre in Anspruch nahm und 1989 begonnen hatte, bewies das Programm Chinook unumstößlich: Wenn beide Seiten von Beginn an optimal ziehen, endet das traditionelle Damespiel stets mit einem Unentschieden.

Dieser Triumph der Wissenschaft zerstörte das Spiel jedoch keineswegs. Um zu verstehen, warum die Freude am Taktieren und Vorausberechnen am Holzbrett oder online ungebrochen bleibt, lohnt sich ein genauer Blick darauf, was die Spieltheorie unter einer solchen Lösung versteht.

Die drei Stufen gelöster Spiele in der Informatik

Im Alltag sagen wir oft leichthin, ein Rätsel sei gelöst, sobald wir den passenden Dreh gefunden haben. In der diskreten Mathematik und der künstlichen Intelligenz besitzt der Begriff jedoch eine strenge Definition. Der niederländische Informatiker Victor Allis formulierte 1994 drei formale Kategorien, nach denen Spiele wissenschaftlich klassifiziert werden^[2]:

1. Ultra-schwach gelöst. Ein mathematischer Beweis legt das theoretische Ergebnis der Ausgangsstellung eindeutig fest, ohne jedoch eine konkrete Zugfolge oder einen spielbaren Algorithmus anzugeben. Ein klassisches Beispiel bietet das Spiel Hex, bei dem die Spieltheorie nachweist, dass der erste Spieler eine Gewinnstellung erzwingen kann, ohne die dafür nötigen Züge auf großen Brettern explizit vorzurechnen.
2. Schwach gelöst. Ein konkreter Algorithmus garantiert aus der offiziellen Anfangsstellung heraus mindestens ein Remis oder einen Gewinn gegen jede denkbare Antwort des Kontrahenten. Das Programm kennt vielleicht nicht jede absurde Stellung, die nach groben Fehlern entstehen könnte, aber von Beginn an kann es unter keinen Umständen bezwungen werden. Genau in diese Kategorie gehört das Damespiel^[1].
3. Stark gelöst. Ein Algorithmus berechnet für jede einzelne, regelkonform erreichbare Brettstellung den exakten Wert sowie den optimalen Zug. Das bekannte Spiel Vier gewinnt wurde 1988 unabhängig voneinander stark gelöst: Der anziehende Spieler besitzt eine zwingende Gewinnstrategie von jedem Zustand aus^[2].

Dass Dame schwach und nicht stark gelöst wurde, liegt an den enormen Dimensionen des Spiels. Auf einem regulären 8x8-Brett stehen sich 12 dunkle und 12 helle Steine auf 32 dunklen Spielfeldern gegenüber^[3]. Um das Schicksal dieser 24 Steine zu klären, mussten die Forscher einen mathematischen Raum bezwingen, der die Fassungskraft menschlicher Gehirne bei Weitem übersteigt.

18 Jahre Rechenarbeit: Wie Chinook das Damespiel knackte

Wer Dame nur als unbeschwerten Zeitvertreib im Café oder Park betrachtet, unterschätzt die rechnerische Tiefe der Züge. Auf dem Brett existieren rund 5 x 10^20 erlaubte Stellungen^[1]. Das entspricht etwa einer Fünf mit zwanzig Nullen oder einer halben Trillion Konfigurationen. Hätte ein einzelner Rechner jede dieser Stellungen nacheinander durchforstet, hätte die Berechnung viele Jahrtausende beansprucht.

Schaeffers Team meisterte diese gewaltige Hürde durch die geschickte Kombination zweier Rechenmethoden: Sie arbeiteten sich vom Endspiel rückwärts voran und stießen von der Anfangsstellung aus vorwärts in die Tiefe.

Die retrograde Analyse: 39 Billionen Stellungen im Speicher

Das feste Fundament des Beweises bildete eine gigantische Endspieldatenbank. Anstatt im Trüben zu fischen, begannen die Forscher am unausweichlichen Ende der Partie. Eine Konfiguration mit nur einem Stein auf jeder Seite ist mathematisch trivial und sofort als Remis bewertet. Stehen zwei Damen einem einzelnen gegnerischen Stein gegenüber, ist der Sieg forciert.

Mithilfe der retrograden Analyse berechnete Chinook systematisch alle legalen Stellungen mit wenigen Steinen. Wenn ein Zug in eine bekannte Gewinnstellung führt, wird die Ausgangsstellung ebenfalls als Sieg markiert. Führen alle legalen Auswege in eine Niederlage, gilt die Position als verloren. Bleibt das Gleichgewicht bei bestem Spiel gewahrt, steht das Unentschieden fest.

Über Jahre hinweg erweiterte das Team diese Datenbank Schritt für Schritt. Am Ende umfasste die Datenbank alle Stellungen mit 10 oder weniger Steinen auf dem Brett^[1]. Diese gigantische Tabelle enthält 39 Billionen verschiedene Stellungen. Sobald eine Partie auf 10 Steine reduziert ist, rechnet Chinook nicht mehr im herkömmlichen Sinne: Das Programm liest das perfekte Schicksal der Partie unmittelbar aus dem Festplattenspeicher ab.

Die Vorwärtssuche: Der Brückenschlag zur Endspieldatenbank

Die verbliebene Aufgabe bestand darin, den Weg von der Ausgangsstellung mit 24 Steinen hinab zu der 10-Steine-Schwelle lückenlos zu berechnen^[1].

Hierfür kombinierten die Wissenschaftler die bewährte Alpha-Beta-Suche mit speziellen Algorithmen zur Beweisnummernsuche. Diese Suchbäume identifizierten kritische Zugfolgen, verfolgten forcierte Abtausche und kappten Verzweigungen, sobald sich ein Zug als fehlerhaft oder nachteilig erwies.

Auf Hunderten vernetzten Rechnern liefen die Berechnungen jahrelang parallel. Unzählige irrelevante Pfade wurden aussortiert, bis ein lückenloser Beweisbaum stand. Jeder einzelne Hauptzweig aus der Anfangsstellung führte entweder in eine uneinnehmbare Festung oder mündete direkt in eine Remis-Stellung der 39-Billionen-Datenbank. Im Jahr 2007 war das Werk vollbracht: Dame ist bewiesenermaßen ein Remis^[1].

Der Mensch gegen die Maschine: Das Duell mit Marion Tinsley

Lange bevor Algorithmen das Spiel mathematisch ergründeten, kam ein Mensch der Perfektion durch reine Geisteskraft unglaublich nahe. Dr. Marion Tinsley, ein Mathematikprofessor aus Florida, gilt unbestritten als der beste Damespieler der gesamten Menschheitsgeschichte.

Tinsleys Turnierbilanz grenzt an das Unfassbare. In seiner 45 Jahre währenden Turnierlaufbahn verlor Tinsley lediglich 9 Partien bei Tausenden gespielten Runden^[1]. Er hielt den Weltmeistertitel über Jahrzehnte hinweg und trat nur dann zurück, wenn ihm die sportliche Herausforderung fehlte. Um Chinook gegen das absolute Maximum menschlichen Könnens zu testen, arrangierte Jonathan Schaeffer 1992 ein offizielles Duell um die Weltmeisterschaft.

Der Wettkampf von 1992 entwickelte sich zu einem historischen Kräftemessen. In 39 strapaziösen Partien bewies Tinsley eine unvergleichliche Stellungsbeherrschung und schlug Chinook mit 4 Siegen bei 2 Niederlagen und 33 Unentschieden^[1]. Es war das erste Mal in der Geschichte des Denksports, dass ein Computerprogramm in einem klassischen Brettspiel gegen einen amtierenden menschlichen Weltmeister antrat.

Im Jahr 1994 fand die mit Spannung erwartete Revanche statt. Nach 6 aufeinanderfolgenden Unentschieden musste Tinsley den Wettkampf aufgrund einer schweren Krebserkrankung abbrechen, an der er 1995 verstarb^[1]. Spätere Analysen seiner Partien gegen Chinook zeigten Erstaunliches: Tinsleys Züge stimmten selbst in tiefsten Verwicklungen fast fehlerfrei mit den perfekten Berechnungen der Endspieldatenbank überein. Seine Intuition hatte die verborgene Geometrie des Spiels verinnerlicht.

Dame im Vergleich: Von Vier gewinnt bis Schach

Um die Tragweite der Lösung von 2007 einzuordnen, hilft ein vergleichender Blick auf die Komplexität bekannter Brettspiele.

Bereits 1950 widmete sich der Mathematiker Claude Shannon in einer grundlegenden Abhandlung der Komplexität des Schachspiels^[4]. Shannon schätzte die Zahl der möglichen Stellungen im Schach auf etwa 10^44 und die Zahl denkbarer Partieverläufe auf rund 10^120 – eine Größenordnung, die heute als Shannon-Zahl bekannt ist^[4].

Betrachten wir die Stufenleiter der kombinatorischen Spiele:

• Vier gewinnt: Wurde 1988 stark gelöst^[2]. Mit Billionen Zuständen lässt sich das Spiel heute auf jedem handelsüblichen Laptop binnen Sekunden vollständig durchrechnen.
• 8x8 Englische Dame: Wurde 2007 schwach gelöst^[1]. Mit rund 5 x 10^20 Stellungen erforderte der Beweis 18 Jahre Rechenarbeit und eine Datenbank von 39 Billionen Endspielpositionen.
• Schach: Völlig ungelöst. Mit 10^44 Stellungen und 10^120 Spielbäumen^[4] liegt eine Gesamtlösung in weiter Ferne. Gegenwärtig reichen Schachendspieldatenbanken lediglich bis zu 7 Figuren. Für 8 Figuren wären bereits gigantische Speicherkapazitäten nötig, und das vollständige Spiel mit 32 Figuren bleibt für klassische Computer unerreichbar.
• 10x10 Internationale Dame: Ebenfalls ungelöst. Auf 100 Feldern mit 20 Steinen pro Seite steigt der Zustandsraum auf geschätzte 10^30 Positionen. Die weitreichende fliegende Dame und der Mehrschlagzwang schaffen eine Komplexität, die heutigen Rechnern trotzt.

Warum die mathematische Lösung das Damespiel lebendig hält

Als die Nachricht 2007 um die Welt ging, befürchteten einige Beobachter das Ende des Damespiels. Wenn die Maschine weiß, dass alles im Remis endet – warum sollte sich dann noch ein Mensch ans Brett setzen?

Diese Sorge beruht auf einem grundlegenden Missverständnis. Eine mathematische Lösung beschreibt, was geschieht, wenn zwei unfehlbare Instanzen über Dutzende Züge hinweg keinen einzigen Fehler begehen. Doch Menschen sind keine Rechenmaschinen. Kein Turnierspieler kann 39 Billionen Endspielstellungen im Kopf behalten oder riesige Beweisbäume im Gedächtnis abrufen.

Am Brett bleibt Dame ein hochdynamischer, psychologischer Zweikampf. Der bekannte Schlagzwang sorgt dafür, dass kleinste Ungenauigkeiten dramatische Konsequenzen haben. Regelmäßig opfern erfahrene Spieler eigenes Material, um gegnerische Steine auf verletzliche Felder zu lenken und spektakuläre Mehrfachsprünge anzusetzen.

In der Praxis entscheiden drei wesentliche Faktoren:

1. Scharfe Eröffnungsfallen. Zwar führt der beste Pfad zum Ausgleich, doch abseits der Hauptwege lauern verheerende Fallen. Wer in der Eröffnung unbedacht zieht, gerät innerhalb weniger Züge in eine hoffnungslose Lage.
2. Strategisches Stellungsspiel. Die Kontrolle des Zentrums, das Sichern der Grundreihe und die Beherrschung von Randfeldern verlangen tiefes Positionsverständnis. Spieler, die sich mit solider Dame-Strategie auseinandersetzen, setzen sich regelmäßig gegen reine Gelegenheitsspieler durch.
3. Präzision im Endspiel. Bei ausgeglichener Steinzahl entscheidet oft die sogenannte Opposition über Sieg oder Niederlage. Ein einziger Fehltritt verwandelt einen sicheren Gewinn in ein Remis, wie wir in unserem Leitfaden über Dame-Endspiele ausführlich erläutern.

Im Turniersport sorgt das Auslosen der ersten Züge dafür, dass ausgetretene Eröffnungspfade verlassen werden und sofort lebendiges Neuland betreten wird. Das Damespiel ist nicht gestorben; der mathematische Beweis hat vielmehr gezeigt, wie ausgewogen und kunstvoll dieser Klassiker aufgebaut ist.

Gerade im Verein und im Wettkampf zeigt sich, wie lebendig das Spiel geblieben ist. Selbst erfahrene Meister geraten unter Zeitdruck ins Grübeln, wenn ungewohnte Zugfolgen das gewohnte Gleichgewicht herausfordern. Wer die geometrischen Muster des Brettes versteht und Tempovorteile gezielt ausnutzt, findet auch abseits starrender Rechenbäume stets Raum für originelle Manöver. Die Faszination speist sich nicht aus der Ungewissheit des mathematischen Endurteils, sondern aus dem unmittelbaren Duell zweier wacher Geister am Brett.

Egal, ob du gerade erst die offiziellen Dame-Regeln verinnerlichst, internationale Dame-Varianten mit fliegenden Damen erkundest oder online eine Partie Dame online spielen möchtest: Das Brett bleibt ein faszinierendes Experimentierfeld für Taktik, Fantasie und Konzentration. Die Wissenschaft mag das theoretische Ziel vermessen haben, doch der Weg dorthin bleibt ein packendes Abenteuer für jeden Spieler.

Häufige Fragen zur Lösung des Damespiels

Ist Dame für absolut jeden erdenklichen Zug gelöst?

Nein, Dame ist schwach gelöst, nicht stark gelöst. Der Beweis garantiert eine lückenlose Strategie aus der offiziellen Anfangsstellung von 24 Steinen auf 32 dunklen Feldern und sichert das Remis^[1]. Zudem sind alle Stellungen mit 10 oder weniger Steinen durch die 39-Billionen-Datenbank vollkommen gelöst. Grobe Fehlerketten mit zahlreichen verbliebenen Steinen sind jedoch nicht vollständig kartiert.

Kann ein Mensch heute noch gegen Chinook gewinnen?

Gegen Chinook mit Zugriff auf die vollständige Eröffnungsbibliothek und die 10-Steine-Datenbank kann kein Mensch mehr gewinnen. Da das Spiel ein theoretisches Remis ist, verliert das optimal programmierte System unter keinen Umständen. Spielt der Mensch perfekt, endet die Partie unentschieden; unterläuft dem Menschen der kleinste Positionsfehler, nutzt das Programm diesen Vorteil aus und gewinnt forciert.

Hat Weiß oder Schwarz im Damespiel einen Vorteil?

In der Englischen Dame hat Schwarz den ersten Zug. Dieser Anzugsvorteil ermöglicht es Schwarz zwar, frühzeitig um wichtige zentrale Felder zu kämpfen, reicht nach Schaeffers Beweis jedoch nicht aus, um gegen korrekte Verteidigung einen Sieg zu erzwingen^[1]. Bei optimaler Gegenwehr verflüchtigt sich die Initiative zum Remis.

Wo kann ich Dame gegen faire Gegner trainieren?

Du kannst dein taktisches Gespür und deine Endspieltechnik verfeinern, indem du bei Checkers Crown direkt im Browser oder in der App antrittst. Dort kannst du jederzeit kostenlos Dame online spielen und dich mit Spielern aller Leistungsstufen messen.

Quellen

1. Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., & Sutphen, S. (2007). Checkers Is Solved. Science, 317(5844), 1518–1522.
2. Allis, L. V. (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, Maastricht.
3. Boardgammon. “Checkers Rules: How to Play, Movement, and Captures.”
4. Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, Ser. 7, 41(314), 256–275.
5. Boardgammon. “Checkers Crown: Play Online Checkers and Regional Draughts Variants.”
6. Boardgammon. “Play Checkers Online: Free Browser and Mobile Draughts.”
7. Boardgammon. “Checkers Variants: The Kinds of Draughts Played Around the World.”

Fehler entdeckt oder über eine Formulierung gestolpert? Schreib uns