Wolfgang Schoch

Dame ist gelöst

Der Spiegel oder N-TV berichteten darüber: nach 18 Jahren der Forschung ist es dem Kanadier Jonathan Schaeffer gelungen, das Dame Spiel zu lösen. Lösen heißt in diesem Fall: egal wie gut der Gegner spielt, er wird gegen Schaeffners Programm im besten Fall ein Remis schaffen.

Das Projekt Chinook ist momentan das größte komplett gelöste Spiel der Welt. In den 18 Jahren in denen das Projekt lief, wurden von rund 50 Rechnern die rund um die Uhr liefen, 39 Billionen Stellungen berechnet. Das ist zwar ganz schön viel, aber dennoch nur ein Bruchteil aller möglichen Stellungen. Insgesamt umfasst der Suchraum bei einem Damespiel 5 * 10^20 Stellungen. Das sind 500 Trillionen, und das ist einfach zu viel für ein Menschenleben.

Aus diesem Grund wählten Schaeffner und sein Team einen anderen Ansatz als das bloße Berechnen aller Stellungen: Sie identifizierten 19 relevante Eröffnungen und rechneten diese soweit durch, bis nur noch 10 Spielsteine oder weniger auf dem Feld lagen. Aus diesen Informationen gelang es, eine allgemeine Dame Strategie zu entwickeln. Dabei beweisen Sie, dass Dame bei einem perfekten Spiel immer auf ein Remis hinausläuft.

Wer nun Interesse an der Thematik hat, der kann sich ein Video mit Jonathan Schaeffer  ansehen, in dem über das Chinook Projekt gesprochen wird. Außerdem sind auf der Seite noch ein Podcast sowie Präsentationsfolien zu finden. Außerdem finden sich auf der Projekthomepage gigabyteweise Endspieldatenbanken, die frei heruntergeladen werden können.