Forscher haben das erste unbesiegbare Computerprogramm für das Brettspiel Dame entwickelt. Nach fast 19 Jahren Arbeit ist es dem Kanadier Jonathan Schaeffer und seinem Team gelungen, das Brettspiel vollständig zu analysieren und zu lösen. Wer gegen das Programm mit dem Namen Chinook antritt, kann sich ein Unentschieden erkämpfen, gewinnen wird der Mensch aber nie, sagen die Entwickler. Chinook ist zwar bereits seit 1994 offizieller Dame-Weltmeister, unschlagbar war der Computer aber bislang noch nicht.
Dame ist ein strategisches Brettspiel, bei dem das Glück keine Rolle spielt. Bei dem gewöhnlich benutzten Schach-Spielbrett aus acht mal acht Feldern gibt es etwa 500 Trillionen mögliche Stellungen ? eine 5 mit zwanzig Nullen. Mehr als 39 Billionen dieser Spielzüge hat das Computerprogramm seit 1989 durchgerechnet. Teilweise arbeitete es Tag und Nacht auf fünfzig Rechnern gleichzeitig, während Schaeffer und sein Team die Software unentwegt verbesserten.
Ende April dieses Jahres gelang ihnen der Beweis, dass Chinook unbesiegbar ist. Das Computerprogramm muss dabei nicht länger aus Fehlern lernen. Es ist vielmehr eine Datenbank, die in jeder Spielsituation “weiß”, welches der beste Zug ist. Selbst wenn der Gegner ebenfalls keine Fehler macht, kann Chinook nicht verlieren: Die Forscher konnten zeigen, dass Dame immer unentschieden ausgeht, wenn beide Seiten perfekt spielen.
Computerwissenschaftler nutzen eine Reihe von komplexen Gesellschaftsspielen, um auf dem Gebiet der Künstlichen Intelligenz zu forschen. Nach “Vier gewinnt” ist Dame mit seiner enormen Anzahl an möglichen Stellungen das größte bislang gelöste. Um auch Schach auf diese Weise zu lösen, würden die derzeit schnellsten Computer allerdings nach menschlichen Maßstäben Ewigkeiten benötigen.
Schaeffers Chinook hatte bereits 1994 die Dame-Weltmeisterschaften gewonnen, nachdem der Gegner das Spiel aus Gesundheitsgründen abbrechen musste. Als erstes Computerprogramm, das eine menschliche Weltmeisterschaft gewann, ging es damit ins Guinness-Buch der Rekorde ein.
Jonathan Schaeffer ( Universität von Alberta) et al.: Science, Online-Vorabveröffentlichung, DOI: 10.1126/science.1144079 ddp/wissenschaft.de ? Larissa Kessner
