Computer löst Dame-Spiel

Edmonton (Kanada), 21.07.2007 – Professor Jonathan Schaeffer von der University of Alberta in Kanada stellte am Donnerstag das Ergebnis seiner jahrzehntelangen Bemühungen vor, das Brettspiel Dame mit Computerhilfe zu lösen. Demnach gibt es für keinen der beiden Spieler eine sichere Gewinnstrategie, ein Dame-Spiel endet bei fehlerfreiem Spiel unentschieden.

Dame ist das erste Brettspiel mittlerer Komplexität, das mit Computerhilfe gelöst wurde. Bisher war das nur bei einfacheren Spiele wie Mühle oder Vier Gewinnt gelungen. Beim Lösen derartiger Spiele wird versucht, einen Beweis dafür zu finden, ob es eine sichere Gewinnstrategie für den anziehenden Spieler, für seinen Gegner oder für keinen von beiden gibt. In Brettspielen hoher Komplexität, wie Schach, spielen Computer zwar zum Teil schon stärker als die besten menschlichen Spieler, sind aber weit davon entfernt, völlig fehlerfrei zu spielen und in jeder Stellung den optimalen Zug berechnen zu können.

Die Gruppe um Schaeffer arbeitete bereits seit 1989 an „Chinook“, einem Computerprogramm, das Dame auf einem 8×8-Brett nach der englischen Regelsystemvariante spielt. In den 1990er-Jahren trat das Programm in zwei Mensch-gegen-Maschine-Turnieren gegen Marion Tinsley an, einem mehrfachen Dame-Weltmeister, der als unbesiegbar galt. Tinsley verlor in seiner Karriere kein einziges Weltmeisterschaftsspiel und nur sehr wenige Spiele insgesamt. Chinook konnte zum damaligen Zeitpunkt zwei Spiele gegen Tinsley gewinnen, verlor das erste Turnier aber. Das zweite Turnier konnte Tinsley aus gesundheitlichen Gründen nicht beenden.

In den letzten Jahren verwendete Schaeffer seinen Ehrgeiz verstärkt darauf, nicht nur ein spielstarkes Dame-Programm zu entwickeln, sondern das Spiel zu lösen. Mit Hilfe speziell entwickelter und optimierter Suchverfahren und dem Einsatz von Computerclustern erreichte er schließlich sein Ziel und konnte verkünden, dass Dame bei fehlerfreiem Spiel zu einem Unentschieden führt. Eine Publikation seiner Forschergruppe zum Thema wird in der Fachzeitschrift Science erscheinen. +wikinews+