Unentschieden! – Mehr ist nicht drin, wenn Schwarz bei einer Partie Dame anzieht und genau wie Weiß absolut fehlerfrei spielt. Das klingt enttäuschend und fördert nicht gerade den Spaß am geistigen Kräftemessen auf dem karierten Brett. Aber wenigstens ein Trost bleibt den kleinen und großen menschlichen Dame-Freunden: Fast zwanzig Jahre haben Dutzende Computer gerechnet, bis sie endlich den entscheidenden Teil der rund 500 Trillionen (500 Milliarden Milliarden) mögliche Positionen analysiert hatten.

Der Anfang vom Ende des Unbekannten im Damespiel begann 1989, als Informatiker um Jonathan Schaeffer an der kanadischen Universität von Alberta mit der Programmierung von CHINOOK begannen. Erklärtes Ziel dieser Software war es, die Weltmeisterschaften in Dame zu gewinnen sowie immer und allzeit perfekte Partien zu spielen.

Es begann mit CHINOOK

Seine erste Chance erhielt CHINOOK bereits ein Jahr später, als es sich für das Turnier qualifizierte. Damals unterlag die Maschine noch der Intuition des Menschen. Auch 1992 behielt der Ausnahmespieler und Weltmeister Marion Tinsley knapp die Oberhand. Zwei Jahre später musste er aus gesundheitlichen Gründen aufgeben, und spätestens seit 1996 hatte kein menschlicher Spieler mehr eine Chance gegen das Programm.

Der Titel war gewonnen – die absolute Perfektion aber noch nicht erreicht. Denn dafür musste CHINOOK für jede beliebige Stellung sicher wissen, wie sie zu gewinnen oder zumindest nicht zu verlieren ist – bei 500 Trillionen Möglichkeiten selbst für Computer keine leichte Aufgabe. Nur die ständigen Fortschritte in der Hardware-Technik, verbesserte Suchalgorithmen und immer größere Speicherkapazitäten brachten schließlich den Durchbruch. Mit einer Lücke in den Jahren 1997 bis 2001 waren im Schnitt 50 Computer jeden Tag mit den Berechnungen beschäftigt, in Spitzenzeiten sogar über 200.

CHINOOK verfolgte dabei drei unterschiedliche Ansätze:
- Eine Endspiel-Datenbank enthielt alle Schlussphasen mit zehn oder weniger Steinen. Der Computer analysierte hier rückwärts von der Endstellung zur Ausgangsposition.
- Eine Manager-Komponente, die bereits gelöste Zugfolgen enthielt und weitere Stellungen zur Analyse auswählte.
- Einen Problem-Löser, der die jeweiligen Stellungen bewertet hat. Um bessere Resultate zu erhalten, waren gleich zwei unabhängige Teilprogramme mit dieser Aufgabe beschäftigt.

Welches Ergebnis durch welchen Zug?

In seinen ersten Durchläufen erhielt CHINOOK meist nur eine grobe Abschätzung für eine Stellung. Es betrachtete dann zunächst jenen Zug genauer, der den größten Erfolg versprach, und erkundete in späteren Runden die Seitenzweige. Mit jedem Zyklus wurde so der Wert für die Position immer genauer, bis letztlich feststand, zu welchem Spielergebnis jeder denkbare Zug führen würde. Wie bei einer Straßenkarte, die von groben Raster der Autobahnen bis zum feinen Netz von Nebenstraßen den Weg weist, gelangt CHINOOK mit seinen Ergebnissen schließlich per Spiel-Navigation zum Sieg oder wenigstens zu einem Unentschieden.

Obwohl das Spiel gegen CHINOOK für Menschen sicherlich frustrierend ist, fallen für Turnierspieler dennoch einige Erkenntnisse aus der Rechenarbeit ab. So sind aus dem Satz von etwa 300 Anfängen mit drei Zügen Tiefe nur 19 unterschiedliche Varianten sinnvoll. Und was danach kommt, haben menschliche Theoretiker meist sehr zutreffend analysiert.

Nicht alles ist gespeichert

Wenn CHINOOK ans Brett tritt, hat das Programm aber längst nicht alle Stellungen im Speicher parat, sondern "nur" zehn Millionen. Durchgerechnet hatte es insgesamt etwa 100 Billiarden Positionen. Der komplette Satz des Möglichen bleibt unmöglich zu speichern; selbst mit sehr guten Komprimierungsverfahren wären dafür um die eine Million Festplatten mit je einem Terabyte Speicherkapazität notwendig.

Das Unentschieden im Damespiel ist für die Forschung an künstlicher Intelligenz ein Sieg. Niemals zuvor konnte eine so komplexe Aufgabe bewältigt werden. Schon haben Unternehmen, die mit unübersichtlichen Informationsfüllen arbeiten, Interesse an den Verfahren und Algorithmen angemeldet. In der Bioinformatik gibt es beispielsweise Unmengen an Daten zu analysieren, wenn einmal wieder ein Erbgut komplett entschlüsselt ist.

Für Spielernaturen dürfte jedoch einstweilen Entwarnung gelten. Das Spiel der Könige etwa wird seine unergründlichen Tiefen noch eine ganze Weile für sich behalten. Denn die Zahl möglicher Stellungen wird beim Schach auf 10⁴⁰ bis 10⁵⁰ geschätzt – dagegen nehmen sich die 5x10²⁰ Positionen beim Dame recht bescheiden aus.