Nicht zu schlagen

Dame-Computer “Chinook” ist unbesiegbar

(Bild: www.cs.ualberta.ca)

Kanadische Forscher haben ein unbesiegbares Computerprogramm für das Brettspiel Dame geschaffen. Kein Gegner könne mehr als ein Unentschieden gegen das Programm namens Chinook erreichen, berichteten Jonathan Schaeffer und Kollegen von der Universität von Alberta in Edmonton. 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.

Tag und Nacht waren dafür im Schnitt rund 50 Computer im Einsatz. Mit dem Ergebnis sei das Brettspiel gelöst, erläutern Schaeffer und Kollegen im US-Fachjournal "Science". Im Jahr 1994 hatte Chinook erstmals die Dame-Weltmeisterschaft gewonnen. Die Software ging damit als erstes Computerprogramm, das in irgendeinem Spiel eine menschliche Weltmeisterschaft gewinnt, ins Guinness-Buch der Rekorde ein.

Insgesamt sind auf einem Dame-Spielbrett rund 500 Millionen Billionen (exakt: 500 995 484 682 338 672 639) Stellungen möglich. Diese immense Menge konnten Schaeffers Computer nicht komplett durchspielen. "Das würde zu meinen Lebzeiten nicht fertig", erläuterte 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 (exakt: 39 271 258 813 439). 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 Informatiker eine allgemeine Dame-Strategie, mit der sich immer eine Konstellation erreichen lässt, die zu einem Patt führt. Dies sei ein Meilenstein für den Forschungszweig der Künstlichen Intelligenz.

Der jetzt vorgestellte Erfolg werfe die Frage auf, ob auch Schach lösbar sei. Angesichts der vermutlich Billiarden Billiarden Billiarden verschiedenen Spielstellungen beim Schach werde eine Lösung zumindest lange auf sich warten lassen, meinen die Forscher um Schaeffer.