Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.

Künstliche Intelligenz: Dame-Brettspiel ist gelöst

Mit der Rechenpower Dutzender Computer haben kanadische Forscher dem Dame-Spiel seine letzten Geheimnisse beraubt. Das von ihnen entwickelte Computerprogramm ist unschlagbar - Gegenspieler müssen ein Remis schon als Sieg feiern.

Jonathan Schaeffer hat sich einen Traum erfüllt. Seit 20 Jahren versucht der Informatiker, einem Computer das Brettspiel Dame beizubringen. Natürlich nicht einfach nur so, der Rechner sollte unschlagbar sein. Das scheint ihm nun gelungen.

Denksport-Olympiade in London (August 1999): Dame-Computer ist jetzt unschlagbar
Getty Images

Denksport-Olympiade in London (August 1999): Dame-Computer ist jetzt unschlagbar

1989 stellte der Informatiker von der kanadischen University of Alberta seine Software "Chinook" vor, in den Folgejahren verbesserte er sie mit seinen Kollegen kontinuierlich. 1994 errang das Programm den Dame-Weltmeistertitel. Allerdings musste der beste Spieler der Welt, Marion Tinsley, das Duell mit "Chinook" aus gesundheitlichen Gründen abbrechen. Er starb Monate später wegen einer Krebserkrankung.

Schaeffers Programm schaffte es so ins Guiness-Buch der Rekorde, weil es erstmals eine bislang nur unter Menschen ausgetragene Weltmeisterschaft gewonnen hatte. Doch der Makel des nicht wirklich errungenen Titels blieb. "Bis heute kommen Leute zu mir und sagen, Tinsley wäre niemals zu schlagen gewesen", sagte Schaeffer dem Magazin "Science".

Mit den Zweifeln an den Fähigkeiten seiner Dame-Software dürfte nun endgültig Schluss sein. Das renommierte Wissenschaftsjournal veröffentlicht in der aktuellen Ausgabe einen Artikel von Schaeffers Team, in dem die Forscher berichten: Unsere Software ist unschlagbar.

Wie Tic Tac Toe

"Ich denke, wir haben die Latte ein ganzes Stück höher gelegt, wenn es darum geht, was man mit Computertechnik und künstlicher Intelligenz erreichen kann", sagte Schaeffer. Zwischenzeitlich hatte der Informatiker seine Forschungsarbeit an dem Brettspiel sogar ganz unterbrochen - um von 1997 bis 2001 auf den 64-Bit-Prozessor zu warten.

Schaeffers Team gelang es, das Damespiel vollständig zu analysieren und zu lösen. In mehr als 18 Jahren haben die Informatiker über 39 Billionen Spielstellungen durchgerechnet und bewiesen, dass Dame immer auf ein Remis hinausläuft, wenn beide Seiten fehlerfrei spielen. Genauso ist die Situation bei Tic Tac Toe, nur das hier die Zahl der Kombinationen überschaubar bleibt.

Tag und Nacht waren für Schaeffers Projekt durchschnittlich 50 Computer im Einsatz, in Spitzenzeiten sogar 200. Mit dem Ergebnis sei das Brettspiel gelöst, schreiben Schaeffer und seine Kollegen. Die zu lösende Aufgabe war immens: Insgesamt sind auf einem Dame-Spielbrett rund 500 Trillionen Stellungen möglich - das ist eine 5 mit 20 Nullen. Diese immense Menge konnten Schaeffers Computer nicht komplett durchspielen. "Das würde zu meinen Lebzeiten nicht fertig", sagte der Forscher. "Zudem würde allein der Festplattenplatz, um alle diese Resultate zu speichern, zig Millionen Dollar kosten."

Stattdessen wählten die Informatiker einen gemischten Ansatz: Sie ließen ihre Computer alle möglichen Spielstellungen mit zehn oder weniger Steinen auf dem Brett analysieren - immerhin mehr als 39 Billionen Optionen. Dann identifizierten sie 19 relevante Spieleröffnungen, die sie so weit durchspielen ließen, bis nur noch zehn oder weniger Steine auf dem Spielbrett waren. Daraus entwickelten die Forscher eine allgemeine Dame-Strategie, mit der sich immer eine Konstellation erreichen lässt, die zu einem Patt führt - und machten ihre Software "Chinook" unschlagbar.

Verliert Dame seinen Reiz für Spieler?

"Das ist eine herausragende Leistung", sagte Jaap van den Herik, Herausgeber des "International Computer Games Journal". Es handle sich um einen wichtigen Fortschritt in der künstlichen Intelligenz. David Levy, Experte für Schach-Computer und Präsident der International Computer Games Association, sagte: "Das ist mit Abstand das komplexeste je gelöste Spiel."

Computerwissenschaftler nutzen eine Vielzahl von Spielen, um auf dem Gebiet der künstlichen Intelligenz voranzukommen. Nach "Vier gewinnt" markiert Schaeffers Lösung für Dame einen neuen Meilenstein. Um auch Schach auf diese Weise zu lösen, würden die derzeit schnellsten Computer allerdings nach menschlichen Maßstäben Ewigkeiten benötigen.

Der nun unschlagbare Dame-Computer könnte auch negative Auswirkungen auf alle jene haben, die Dame als Wettkampfspiel betreiben. In einigen Ländern ist das Brettspiel sogar ein Profisport. Doch van den Herik befürchtet, dass das Spiel nun an Reiz verlieren könnte.

Schaeffer macht sich darum weniger Sorgen. Er hat sich längst der nächsten Herausforderung zugewandt: dem Pokerspiel. Am 24. und 25. Juli tritt das von seinem Team entwickelte Programm "Polaris" in Vancouver gegen zwei Pokerprofis aus Fleisch und Blut an. Poker kann zwar nicht gelöst werden wie Dame, aber dafür geht es hier um viel mehr Geld. Bei dem Duell Mensch-Maschine sind es 50.000 Dollar, auf großen Turnieren sogar Millionen.

hda/dpa/ddp

Diesen Artikel...

© SPIEGEL ONLINE 2007
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH




Der kompakte Nachrichtenüberblick am Morgen: aktuell und meinungsstark. Jeden Morgen (werktags) um 6 Uhr. Bestellen Sie direkt hier: