Dame durchgespielt
Das Brettspiel "Dame" ist gelöst: Das Computerprogramm Chinook hat alle möglichen Züge durchgerechnet und sich selbst bestätigt, unschlagbar zu sein
Wenn Ihnen Ihr PC in Zukunft eine lockere Partie Dame anbietet - schlagen Sie die Einladung besser aus, der Computer will ihnen nur seine Überlegenheit demonstrieren. Denn das irgendwann im frühen Mittelalter in Südfrankreich entstandene Brettspiel ist nun vollständig gelöst, wie kanadische Forscher der University of Alberta in Edmonton in der aktuellen Ausgabe des Wissenschaftsmagazins Science beschreiben. Die Wissenschaftler haben aber nicht selbst monatelang am karierten Damebrett gehangen - sie haben den Computer für sich arbeiten lassen. In der Mathematik sind vom Computer geführte, also berechnete, Beweise inzwischen nicht mehr ungewöhnlich - sie sind zwar nicht so elegant wie andere, aber durchaus solide.
Durchgespielt wurde Dame vom Computerprogramm Chinook, das bereits einen gewissen Ruf in der Damegemeinde besitzt und sich 1994 auch gegen menschliche Gegner schon zum Weltmeistertitel gespielt hatte. Das Problem (für das Chinook 1997 als aktiver Spieler in Rente geschickt wurde) war durchaus kein kleines: 500 Milliarden Milliarden Positionen waren durchzurechnen. Das Ergebnis: wenn beide Spieler stets die optimalen Züge auswählen, ist das Damespiel nicht zu gewinnen.
Diese Vermutung ist der Damegemeinde nicht neu, sie wurde nun allerdings bestätigt. Das erreichten die Wissenschaftler in drei Schritten. Zunächst konstruierten sie eine Endspiel-Datenbank, die für maximal zehn auf dem Brett verbliebene Steine alle möglichen Ergebnisse enthält. Die Datenbank war bereits 2005 fertig berechnet.
Anschließend ging es darum, die zu den Positionen in der Endspiel-Datenbank führenden Züge zu evaluieren. Ein Programmteil entwarf dazu eine Baumstruktur der in Frage kommenden Züge, ein zweites rechnete die Baumstruktur durch. Seit 2004 beschäftigten sich durchschnittlich 50 Computer rund um die Uhr mit dieser Aufgabe - in Echtzeit wird diese erst in ein paar Jahren zu lösen sein. Gespeichert wurde allerdings nicht der komplette Beweis, sondern nur der Suchbaum. Die Forscher schätzen, dass der komplette Beweis eine Speicherkapazität von einigen zehn Terabyte erfordert hätte. Es lässt sich aber jederzeit jeder Zweig des Baums erneut durchrechnen.
Chinook spielte die britisch-amerikanische Version des Spiels, Checkers oder auch Draughts genannt. Sie benutzt ein 8x8-Brett und unterscheidet sich von der hierzulande bekannten Dame-Variante dadurch, dass die Damen (englisch „kings“) sich nicht beliebig weit, sondern immer nur ein Feld diagonal bewegen können. Das wirkt sich etwa im Endspiel auf: während eine einzelne „deutsche“ Dame bis zu drei gegnerischen Damen stets entkommen und damit ein Remis erreichen kann, gewinnen perfekt ziehende US-Spieler meist auch im Endspiel zwei gegen eins.
Die Geschichte des Versuchs, Dame zu lösen, ist auch eine Geschichte der Computertechnik. Als Chinook 1989 begann, eine Endspiel-Datenbank für maximal acht Steine durchzurechnen, brauchte die Software auf den damals aktuellen Rechnern noch sieben Jahre dafür. Dieselbe Rechnung war 2001 im Laufe eines Monats abgeschlossen. Die Forscher beschreiben aber auch, vor welchen praktischen Problemen ihr Computer-Beweis der Dame-Lösung stand.
So garantieren Festplatten-Hersteller zum Beispiel nur eine Fehlerhäufigkeit von 1 zu (10 hoch 13). Wegen der enormen Größe der Endspiel-Datenbank (237 Gigabyte für eine Zehn-Positionen-Datenbank) musste deshalb das so genannte „Bit-Rot“ ausgeschlossen werden, das zufällige Umkippen von Bits. Es existieren deshalb stets mehrere Kopien der Datenbank, die ständig auf Korrektheit geprüft werden. Trotzdem können die Chinook-Programmierer zum Beispiel Übertragungsfehler nicht völlig ausschließen. Die Wahrscheinlichkeit, dass ein im 40. Zug abgespeicherter Fehler sich bis ins Endspiel durchschleppt, halten sie jedoch für äußerst gering.
Schwerer wird es da ein anderes Programm haben, das vom selben Team entwickelt wurde: Polaris, eine Poker-Software, will in der kommenden Woche gegen zwei menschliche Pokerprofis um 50.000 Dollar Preisgeld antreten.