Dame (engl. Checkers oder Draughts) ist ein Spiel mit zwei Spieler:innen und wird auf einem kariertem 8×8 Brett (engl. checkerboard) gespielt. Es gehört zu den Strategiespielen mit perfekter Information. Ähnliche Spiele mit karierten Spielbrettern existieren schon seit Jahrtausenden. In seiner heutigen Form wurde Dame im 16. Jahrhundert in Spanien populär und erfreut sich seit dem 18. Jahrhundert insbesondere im englischsprachigen Raum großer Beliebtheit.
¶ Spielregeln
Es gibt etliche Varianten des Damespiels. Dieser Artikel behandelt das amerikanische Checkers, das sich insbesondere durch die geringere Mobilität der Damen von der deutschen Variante unterscheidet. Die Spieler:innen sitzen einander gegenüber am Spielbrett, wobei das Feld links unten dunkel ist. Sie starten mit je 12 Figuren, die auf den dunklen Spielfeldern platziert sind (siehe Abb. 1). Die Spielsteine können nur diagonal um ein Feld nach vorne bewegt werden, bleiben also das ganze Spiel über auf den dunklen Feldern. Schwarz fängt mit dem ersten Zug an, wonach sich beide Seiten abwechseln. Die Figuren können diagonal anliegende gegnerische Spielsteine schlagen, wenn hinter ihnen ein freies Feld liegt, indem sie über sie springen. In einem einzigen Zug können miteinander folgenden Sprüngen derselben Figur mehrere gegnerische Steine entfernt werden. Es herrscht Schlagzwang: Man muss also schlagen, wenn die Möglichkeit besteht.
Wenn eine Figur das andere Ende des Felds erreicht, wird sie zur Dame. Eine Dame kann sich zusätzlich rückwärts bewegen, jedoch auch nur um ein Feld je Zug. Sie kann auch vorwärts und rückwärts springen, und mehrere Steine mit einem verketteten Sprung schlagen. Das Spiel ist verloren, wenn man keinen Zug mehr ausführen kann. Also, wenn alle Figuren der eigenen Farbe vom Gegner geschlagen wurden oder blockiert sind. Es kommt zum Unentschieden, wenn sich beide Seiten darauf einigen oder sich ein Spielfeldzustand dreimal wiederholt hat.
Den Spielfeldern werden nach der in Abb. 2 illustrierten Konvention Zahlen zugewiesen, um die Kommunikation über Positionen und Spielzüge ("<von>-<zu>") zu erleichtern. Die Abbildung ist aus der Perspektive von Weiß zu lesen.
¶ Alpha-Beta-Suche
So wie viele Zwei-Spieler:innen-Spiele, lässt sich der Spielbaum von Dame mit dem Minimax-Algorithmus durchsuchen. Siehe Alpha-Beta-Suche für eine ausführlichere Erklärung des Algorithmus.
In Abb. 3 ist die Alpha-Beta-Suche für einen beispielhaften Ausgangszustand illustriert. Der Suchbaum ist aus der Sicht von Schwarz. Schwarz ist als erstes dran. Neben jedem Zug steht die Kodierung des Zuges in konventioneller Notation (siehe Abb. 2) und welche Seite ihn ausführt. Der Baum wird depth-first und left-to-right traversiert. Blatt-Knoten sind Endzustände mit einem festen Spielausgang. Knoten, an denen Schwarz dran ist, sind mit W annotiert, wenn von da aus ein Sieg erzwingbar ist, oder mit L, wenn Schwarz bei idealem Gegenspiel verliert. Da Schwarz zu Beginn mit dem Zug 18-22 zwingend zu einem Sieg kommen kann, zeigt die Suche, dass Schwarz das gesamte Spiel gewinnt. Zu beachten ist das Alpha-Beta-Pruning: Nachdem gezeigt ist, dass Weiß mit dem Zug 26-22 den eigenen Sieg erzwingen kann, werden keine anderen Züge mehr traversiert, die auf 13-17 von Schwarz folgen. Ebenso endet die gesamte Suche, nachdem der Sieg für Schwarz durch 18-22 gezeigt worden ist.
¶ "Checkers is solved" [1]
Spieler:innen haben schon lange vermutet, dass Dame bei perfekter Strategie in einem Unentschieden endet. Weil es bei Partien zwischen Menschen so häufig zum Unentschieden kommt, werden bei Turnieren seit den 1930ern die ersten drei Spielzüge zufällig ausgewählt. Somit gibt es ca. 300 verschiedene Openings von drei Zügen, dessen Ausgang überprüft werden muss. Im Jahr 2007 veröffentlichte Jonathan Schaeffer in Zusammenarbeit mit anderen von der University of Alberta den Beweis, dass Dame bei perfektem Spiel mit einem Unentschieden endet. Mit der Arbeit wurde das Spiel schwach gelöst.
¶ Gelöste Spiele [2]
Es wird häufig die Formulierung verwendet, dass ein Strategiespiel gelöst ist (engl. solved). Diese Bezeichnung kann selbst in unserem Fall uneindeutig sein, in dem es sich um ein Nullsummenspiel mit zwei Parteien und perfekter Information handelt. Deshalb sind für das Gelöstsein eines Spiels drei verschiedene Abstufungen definiert worden:
Ultra-weakly solved (ultra-schwach gelöst)
Für die Startposition ist das Ergebnis bei perfekter Spielweise bekannt.
Beispiel: Hex
Weakly solved (schwach gelöst)
Für die Startposition ist eine Strategie für beide Seiten bekannt, um das beste Ergebnis mit angemessenen Rechenressourcen zu erreichen.
Beispiel: Dame
Strongly solved (stark gelöst)
Für alle möglichen Spielposition ist eine Strategie für beide Seiten bekannt, um das beste Ergebnis mit angemessenen Rechenressourcen zu erreichen.
Beispiel: Tic-Tac-Toe
Es gilt eine Ordnung zwischen den Mengen von Spielen, auf die diese Definitionen zutreffen:
Die etwas unspezifische Formulierung "mit angemessenen Rechenressourcen" ist notwendig, da sonst eine naive Alpha-Beta-Suche über den gesamten Suchbaum als ausreichende Strategie angesehen werden müsste.
¶ Die Architektur des Beweises - Ein Überblick
Dame hat ca. 500 Milliarden Milliarden () verschiedene Spielpositionen. Mit dem Beweis war es das zu der Zeit komplexeste Spiel, das je gelöst worden ist. Ein verteiltes System war zur parallelen Berechnung des Beweises notwendig und es besteht aus drei Komponenten:
In Endgame Databases ist der Ausgang aller Spielfeldkonfiguration mit 10 Steinen oder weniger gespeichert.
Der Proof-Tree Manager leitet den Beweis an und hält den Beweisbaum. Er ruft die Proof Solvers auf und verwendet PN-Search.
Die Proof Solvers erhalten Positionen vom Proof-Tree Manager, und bewerten diese mittels Chinook und Df-pn.
¶ Chinook
Chinook ist ein Programm, das Dame spielt und ist von Jonathan Schaeffer et. al von 1989 bis 2007 entwickelt worden. Man kann gegen Chinook heute noch online spielen. Bereits 1990 spielte Chinook mit dem Spielniveau der besten Dame-Champions. Der einzige menschliche Spieler, der das Programm gelegentlich besiegt hat, war Marion Tinsley, der von vielen als bester Dame-Spieler aller Zeiten angesehen wird. 1994 gewann Chinook gegen Tinsley, da er das Spiel aufgrund einer schweren Erkrankung aufgeben musste. Tragischerweise ist er kurze Zeit später verstorben. Seitdem gilt Chinook als ungeschlagener Meister der sogenannten Man vs. Machine World Championship.[3]. Chinook verwendet vor allem eine optimierte Alpha-Beta-Suche mit beschränkter Suchtiefe und ermittelt meistens nur heuristische Spielergebnisse, beweist den Spielausgang also nicht sicher. Das reichte aus, um superhuman play zu demonstrieren, womit Chinook dem berühmten Schach-Programm Deep Blue vorausging.
¶ Endgame Databases (Retrograde Analysis)
Dame hat insgesamt 120 Positionen mit nur einer Figur auf dem Spielfeld. Für diese Positionen ist es trivial, ihren Spielausgang zu bestimmen, und zwar gewinnt immer die Seite, der die verbleibende Figur gehört. Als nächstes werden alle Positionen mit zwei Figuren ausgewertet. Züge von diesen Zuständen führen entweder zu bereits ausgewerteten Positionen mit nur einer Figur, oder sie führen zu einer Wiederholung desselben Zustands, was ein Unentschieden ergibt. Dieser Algorithmus kann für Positionen mit drei Figuren oder mehr fortgeführt werden und heißt Retrograde Analysis. Dabei werden die Resultate für jede betrachtete Position abgespeichert, und können daraufhin von Chinook oder anderen Suchalgorithmen verwendet werden. Häufig reduziert das die notwendige Suchbaumtiefe enorm. Für diesen Beweis wurden die Ausgänge aller Spielfeldzustände mit 10 oder weniger Figuren ermittelt. Dabei handelt es sich um ca. 39 Billionen Möglichkeiten (siehe Table 1). Das Team war in der Lage, diese Datenmenge auf 237 GB zu komprimieren, was ca. entspricht. So konnten die Datenbanken selbst in den frühen 2000er Jahren lokal auf den Rechnern gespeichert werden, die die Proof Solvers ausführten. I/O-Zugriffe auf die Endgame databases waren nämlich ein großer Bottleneck der Proof-Solver-Prozesse und so konnten teure Netzwerkzugriffe vermieden werden.[4] Alle Positionen mit deutlich mehr als 10 Figuren zu inkludieren, wäre zu rechen- und speicheraufwendig (siehe Table 1).
| Figuren | Anzahl an Positionen | Figuren | Anzahl an Positionen | |
|---|---|---|---|---|
| 1 | 120 | 11 | ≈ 260 ⋅ 10¹² | |
| 2 | 6972 | 12 | ≈ 1.6 ⋅ 10¹⁵ | |
| 3 | 261224 | 13 | ≈ 9.7 ⋅ 10¹⁵ | |
| 4 | ≈ 7.1 ⋅ 10⁶ | 14 | ≈ 49 ⋅ 10¹⁵ | |
| 5 | ≈ 150 ⋅ 10⁶ | 15 | ≈ 220 ⋅ 10¹⁵ | |
| 6 | ≈ 2.5 ⋅ 10⁹ | 16 | ≈ 850 ⋅ 10¹⁵ | |
| 7 | ≈ 35 ⋅ 10⁹ | 17 | ≈ 2.9 ⋅ 10¹⁸ | |
| 8 | ≈ 410 ⋅ 10⁹ | 18 | ≈ 8.6 ⋅ 10¹⁸ | |
| 9 | ≈ 4 ⋅ 10¹² | 19 | ≈ 22 ⋅ 10¹⁸ | |
| 10 | ≈ 34 ⋅ 10¹² | 20 | ≈ 46. ⋅ 10¹⁸ | |
| Gesamt 1–10 | ≈ 39 ⋅ 10¹² | 21 | ≈ 82 ⋅ 10¹⁸ | |
| 22 | ≈ 120 ⋅ 10¹⁸ | |||
| 23 | ≈ 130 ⋅ 10¹⁸ | |||
| 24 | ≈ 90 ⋅ 10¹⁸ | |||
| Gesamt 1–24 | ≈ 500 ⋅ 10¹⁸ |
¶ Proof-Tree Manager
Der Proof-Tree Manager verteilt Arbeit an die einzelnen Proof Solvers. PN-Search wird eingesetzt, um relevante Positionen zu ermitteln. Die Proof Solvers können verschiedene Arten von Ergebnissen zurückgeben:
- Bewiesen (Sieg/Niederlage/Unentschieden)
- Partiell bewiesen (mindestens Unentschieden/höchstens Unentschieden)
- Heuristische Scores (Schätzung wie gut eine Position ist)
Der Manager kann die heuristischen Ergebnisse nutzen, indem er Scores ab einem gewissen Threshold behandelt, als wären sie Siege bzw. Niederlagen und das als Grundlage für Priorisierung weiterer Positionen für die Proof Solvers verwendet. Der Manager speichert die Ergebnisse der Proof Solvers in einem B-Tree[4:1], die wiederum immer stärkere Ergebnisse zu den vom Manager neu ausgewählten Positionen zurückgeben. Iterativ wird der Threshold vom Manager erhöht, sodass er mit der Zeit die Schwelle erreicht, (partiell) bewiesene Ergebnisse zu benötigen. Als Grundlage für diese Iteration dient eine vorgegebene Abfolge von Zügen, das sogenannte Seeding. Dabei handelt es sich um bei Dame-Expert:innen länger bekannte Standard-Zugabfolgen für ein jeweiliges Opening. Von den ca. 300 verschiedenen Openings sind Hunderte trivial per Alpha-Beta-Suche lösbar oder Transpositionen anderer Openings. Es bleiben von ihnen nur 19 relevante übrig, für die das Beweis-System die Spielausgänge (partiell) beweisen konnte. Die Wurzel des Beweis-Baums ist in Abb. 4 dargestellt. Die Labels "<=D", ">=D", "=D", oder "=L" geben darüber Auskunft, ob es sich um mindestens bzw. höchstens Unentschieden, also partielle Lösungen, oder um ein sicheres Unentschieden bzw. eine sichere Niederlage handelt. Es sei zu beachten, dass partiell bewiesene Spielausgänge ausreichen, um das Gesamtergebnis eines Unentschiedens festzustellen.
¶ Proof Solvers
Die Proof Solvers bauen maßgeblich auf der heuristischen Alpha-Beta-Suche von Chinook auf. Ihre Aufgabe ist es, für eine Position einen heuristischen Score zu berechnen. Im Gegensatz zum Proof-Tree Manager, speichern sie nicht dauerhaft Informationen über vergangene Berechnungen. Das macht ihre Arbeit sehr parallelisierbar. Die Proof Solvers greifen jedoch auf die Endgame Databases zu, was eine zentrale Rolle für ihre Performance spielt. Zunächst ermitteln sie einen heuristischen Wert mittels Chinook. Auf Grundlage dessen, versuchen sie daraufhin das Ergebnis mit Df-pn (partiell) zu beweisen. Pro Position haben sie für die weniger anspruchsvolle heuristische Suche und die rechenintensivere PN-Suche verschiedene Zeitlimits, um möglichst früh weniger aussichtsvolle Berechnungen abzubrechen.
¶ Abbildungen und Tabellen
Abb 1: Selbst erstellt
Abb 2: Mit Änderungen übernommen[1:1]
Abb 3: Mit Änderungen übernommen[5]
Abb 4: Vollständig übernommen[1:2]
Table 1: Mit Änderungen übernommen[1:3]
¶ Literatur
J. Schaeffer et al., “Checkers Is Solved”, Science, vol. 317, no. 5844, pp. 1518–1522, 2007, Zugegriffen: 19. Januar 2026. doi: 10.1126/science.1144079. [Science]. Verfügbar unter: https://www.science.org/doi/full/10.1126/science.1144079 ↩︎ ↩︎ ↩︎ ↩︎
L. V. Allis, "Searching for solutions in games and artificial intelligence", pp. 7-9, 1994, Zugegriffen: 19. Januar 2026. doi: 10.26481/dis.19940923la. [Doctoral Thesis, Maastricht
University]. Rijksuniversiteit Limburg. https://doi.org/10.26481/dis.19940923la ↩︎S. Sreedhar, „Checkers, Solved! - IEEE Spectrum“, 2007. Zugegriffen: 9. Juli 2025. [Online, IEEE Spectrum]. Verfügbar unter: https://spectrum.ieee.org/checkers-solved ↩︎
J. Schaeffer et al., “Solving checkers,” in Proceedings of the 19th international joint conference on Artificial intelligence, in IJCAI’05. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., Jul. 2005, pp. 292–297, Zugegriffen: 19. Januar 2026. doi: 10.5555/1642293.1642340. [ACM] Verfügbar unter: https://webdocs.cs.ualberta.ca/~jonathan/PREVIOUS/Papers/Papers/ijcai05checkers.pdf ↩︎ ↩︎
J. Schaeffer et al., “Checkers Is Solved”, Science, vol. 317, no. 5844, pp. 1518–1522, 2007, Supporting Online Material, Zugegriffen: 19. Januar 2026. doi: 10.1126/science.1144079. [Science] Verfügbar unter: https://www.science.org/doi/suppl/10.1126/science.1144079/suppl_file/schaeffer.som.pdf ↩︎