HOME

Unbesiegbarer Dame-Computer: Der ewige Sieger

Forscher haben nach jahrelanger Arbeit einen unbesiegbaren Dame-Computer entwickelt. Dabei haben die Informatiker über 39 Billionen Spielstellungen durchgerechnet.

Wer gegen Chinook spielt, kann nicht gewinnen: 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 am Donnerstag. 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.

500 Billionen Stellungen möglich

Insgesamt sind auf einem Dame-Spielbrett rund 500 Millionen Billionen 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. 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.

Lösungen für Schach dauern länger

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.

ts/dpa/ddp
Themen in diesem Artikel