Digitale Pioniere (18): Jonathan Schaeffer: Das perfekte Dame-Spiel

Aller Ehren wert

Brettspiele sind einer der Prüfsteine für Computerentwickler. Jonathan Schaeffer schuf ein Dame-Programm, das die vollständige Lösung des Spiels erreicht und von keinem Menschen zu schlagen ist.

Zur Person

Der Kanadier, geboren 1957, hatte es in seinen Zwanzigerjahren zum nationalen Schachmeister gebracht. Zeitgleich studierte er Mathematik – und widmete sich bald der Schachprogrammierung. Schaeffer war aber an der vollständigen Lösung interessiert, was aufgrund der möglichen Züge beim Schach schier unmöglich ist. So kam er zum Dame-Spiel. Mit seinem Programm „Chinook“ gelang es ihm, den langjährigen Dame-Weltmeister Marion Tinsley mehrfach zu schlagen.

Schaeffer setzte auf parallele Berechnungen und nutzte die überschüssige Rechenleistung der Workstations in den Studentenpools der Universität von Alberta, wo er Professor ist. Im Jahr 2007 hatte er alle Teile des Suchraums bis zum Ende zu berechnet, die für eine komplette Lösung des Dame-Spiels erforderlich sind. Dafür waren 100 Billionen (10 hoch 14) Rechenoperationen nötig, die insgesamt 18 Jahre dauerten.

Gut zu wissen

Mit der vollständigen Lösung ist klar, dass Dame bei beiderseitig optimalen Zügen stets zu einem Unentschieden führt.

Vor 75 Jahren stellte Konrad Zuse den ersten funktionsfähigen Computer Z3 in Berlin vor. Aus diesem Anlass blicken das Zuse-Institut Berlin und der Tagesspiegel am 11. Mai auf einer internationalen Konferenz in die digitale Zukunft: „The Digital Future – 75 Years Zuse Z3 and the Digital Revolution.“  75 Folgen über die wichtigsten Wegbereiter des digitalen Zeitalters zeigen, was bisher geschah. Mehr zur Veranstaltung: www.science-match.info